Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2003
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

Can matrix inversion mod N be automated?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg39251] Can matrix inversion mod N be automated?
  • From: "flip" <flip_alpha at safebunch.com>
  • Date: Thu, 6 Feb 2003 03:07:05 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

Hello,

while doing some crypto stuff with affine ciphers, we need to find matrix
inverse mod some N.

Sometimes, the plaintext-ciphertext pairs do not allow for inversion when N
is composite.

We can write the matrix as a linear combination of the factor of N and
proceed to find an invertible matrix.

Here are the steps to such a task.

***

(* Problem III.2, #23 a., b. and c.    Wilson Figueroa *)
matlist[n_, p_] :=
  Map[Partition[#, n] &,
    Flatten[ Outer[List, Apply[Sequence, Table[Range[0, p - 1], {n^2}]]],
      n^2 - 1]]
p = {{3, 3}, {2, 5}};
c = {{17, 8}, {8, 29}};
Inverse[c, Modulus -> 30]
aa = matlist[2, 3];
a0 = {{7, 9}, {6, 9}};
a = Table[(3*a0 + 10*aa[[i]]), {i, 1, Length[aa]}];
b = Table[Mod[a[[i]], 3], {i, 1, Length[a]}];
d = Table[GCD[Det[b[[i]]], 3], {i, 1, Length[b]}];
dd = Flatten[Position[d, 1]]
e = Table[a[[dd[[i]]]], {i, 1, Length[dd]}];
g = Table[Mod[e[[i]], 30], {i, 1, Length[e]}];
h = g.p;
w = Table[Mod[h[[i]], 30], {i, 1, Length[h]}];
x = Flatten[Position[w, {{17, 8}, {8, 29}}]]
y = Table[g[[x[[i]]]], {i, 1, Length[x]}]
Table[MatrixForm[y[[i]]], {i, 1, Length[y]}]
(* Verify Result *)
z = Table[Mod[y[[i]].p, 30], {i, 1, Length[y]}]
Table[MatrixForm[z[[i]]], {i, 1, Length[z]}]

***

My question is, can this process be automated for various N?

When N = 26, we would have A = 2 a0 + 13 a1
When N = 30, we have A = 3 a0 + 10 a1, (as shown above), etc.

Hope that is clear and thanks for any inputs, Flip

To email me remove "_alpha1".





  • Prev by Date: Algebra of differential operators
  • Next by Date: Re: Formatted output
  • Previous by thread: Re: Algebra of differential operators
  • Next by thread: Random Numbers