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