[Date Index]
[Thread Index]
[Author Index]
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**
| |