       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