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".