invertable matrices - hill cipher
TejloR
Cipher.
I know that number of all invertible matrices (size 2x2) whose
elements are members of Z_26 is 157248 (this result I got from some
book). There are 26^4 = 456976 of them. I also know that I must
compute for each matrix determinat and if the determinant has an
inverse over Z_26, then matrix is invertable. Is there any formula or
algorithm which could proof this results?
If I use prime numbers (p) and 2x2 matrices over Z_p then number of
invertible matrices is equal to the equation: (p^2-1)*(p^2-p).
So for:
p=2 > (4-1)*(4-2)=6
p=3 > (9-1)*(9-3)=48
p=5 > (25-1)*(25-5)=480
.. .. .. ..
.. .. .. ..
.. .. .. ..
p=13 > (169-1)*(169-13)=26208
btw: I noticed that 26208*6=157248 !! this is result for number of all
invertible 2x2 matrices over Z_26. How is that possible? What is the
formula for calculating this out (somebody mentioned Chinese Reminder
Theorem). I'm familiar a little bit with Chinese Reminder, but I don't
know how to use it on this problem.
Any help would be appreciated,
Tejlor
Michael Nüsken
An integer matrix is invertible modulo 26 iff it is
invertible modulo 13 and invertible modulo 2. And by the
CRT (Chinese Remainder Theorem) the set of matrices modulo
26 is in bijective correspondance to the set of pairs of a
matrix modulo 13 and a matrix modulo 2. Now, as you write,
there are (p^2-1)*(p^2-p) invertible 2x2-matrices modulo p
provided p is prime. Thus you have (13^2-1)*(13^2-13)
invertible 2x2-matrices modulo 13, ie. 26208, and
(2^2-1)*(2^2-2) invertible 2x2-matrices modulo 2, ie. 6.
Concluding you have 26208*6 invertible 2x2-matrices modulo
26.
It is easy to generalize this to other moduls that are a
product of different primes. If your number contains
multiple prime factors, say p^k, you must have a formula for
the number of invertible matrices modulo p^k. But a matrix
is invertible modulo p^k iff its determinant is invertible
modulo p^k, and this in turn is equivalent to saying that
the determinant is non-zero modulo p. Thus in total a
matrix is invertible modulo p^k iff it is invertible modulo
p. Now, simply multiply the number of invertible matrices
modulo p by p^((k-1)*n^2) to obtain the number of invertible
nxn-matrices modulo p^k. By CRT you are done now for all
moduls.
Best regards,
|\/| Michael Nüsken
| \| ++49 5251 60-2653 (privat: ++49 5252 940200)
WWW: http://www-math.uni-paderborn.de/~nuesken/ .
TejloR
thanks,
> It is easy to generalize this to other moduls that are a
> product of different primes. If your number contains
> multiple prime factors, say p^k, you must have a formula for
> the number of invertible matrices modulo p^k. But a matrix
> is invertible modulo p^k iff its determinant is invertible
> modulo p^k, and this in turn is equivalent to saying that
> the determinant is non-zero modulo p. Thus in total a
> matrix is invertible modulo p^k iff it is invertible modulo
> p. Now, simply multiply the number of invertible matrices
> modulo p by p^((k-1)*n^2) to obtain the number of invertible
> nxn-matrices modulo p^k. By CRT you are done now for all
> moduls.
>
OK, I agree, - but still if I would have ring Z24. I would break
number 24 to primes 2 and 3 (2*2*2*3=24), that means that number of
invertable matrices over ring Z24 would be product of
3 * p=2 > (4-1)*(4-2)=6 and p=3 > (9-1)*(9-3)=48
K= 6*6*6*48 = 10368
Am I right or not ?
Best regards,
Tejlor
Michael Nüsken
No, you are wrong, your value of K is too small by a factor
256/36:
The CRT only holds when you split the modulus into *coprime*
factors.
Thus you can only split 24 = 8 * 3 and you have to count
invertible matrices modulo 8 (there are
(2^2-1)*(2^2-2)*2^((3-1)*2^2) = 6*2^8 invertible
2x2-matrices modulo 8) and invertible matrices modulo 3
(there are (3^2-1)*(3^2-3) = 48 invertible 2x2-matrices
modulo 3. In the example you find that there are
6*2^8 * 48 invertible 2x2-matrices modulo 24.
Mok-Kong Shen
Michael Nüsken wrote:
>
[snip]
> It is easy to generalize this to other moduls that are a
> product of different primes. If your number contains
> multiple prime factors, say p^k, you must have a formula for
> the number of invertible matrices modulo p^k. But a matrix
> is invertible modulo p^k iff its determinant is invertible
> modulo p^k, and this in turn is equivalent to saying that
> the determinant is non-zero modulo p. Thus in total a
> matrix is invertible modulo p^k iff it is invertible modulo
> p. Now, simply multiply the number of invertible matrices
> modulo p by p^((k-1)*n^2) to obtain the number of invertible
> nxn-matrices modulo p^k. By CRT you are done now for all
> moduls.
How does one get the multiplier p^((k-1)*n^2)? Could you
explain a little bit more? Thanks.
M. K. Shen
ikram.ut...@gmail.com
What will be the number of invertible matrices mod 27?
Kind regards
nob...@nowhere.invalid
ikram.ut...@gmail.com schrieb:
>
> On Wednesday, 27 March 2002 11:19:22 UTC+1, Michael NĂĽsken wrote:
> > Hi Tejlor!
> >
> > [...]
> >
> > Best regards,
> > |\/| Michael NĂĽsken
> > WWW: http://www-math.uni-paderborn.de/~nuesken/ .
>
> Hi Michael:
> What will be the number of invertible matrices mod 27?
>
> Kind regards
Looks like Michael Nüsken can now be found at Bonn University:
<https://cosec.bit.uni-bonn.de/~nuesken/>
I suspect that he no longer follows the sci.math.symbolic newsgroup.
Martin.