please help me what is number of invertible matrix $m*m$ on Group $\mathbb{z}_n$ ?, assuming we know this number in $\mathbb{Z}_p \quad$ (p is prime) is $(p^{n}-1)(p^{n}-p) \cdots (p^n-p^{n-1})$
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ How is this related to cryptography? $\;$ $\endgroup$– user991Apr 23, 2015 at 11:00
-
1$\begingroup$ You are talking about the General Linear Group of matrices of degree m over $\mathbb Z_p$. $\endgroup$– cygnusvApr 24, 2015 at 7:11
-
$\begingroup$ @Ricky Demer: the OP gives a hint with the tag hill-cipher, which indeed uses as key an invertible $m\times m$ matrix with elements in $\mathbb Z_n$. $\endgroup$– fgrieu ♦Apr 24, 2015 at 8:32
-
$\begingroup$ The question is in fact a duplicate of this one, which has a satisfactory solution (if not answer in the sense of the CSE website logic) in comment, and as an edit of the question. $\endgroup$– fgrieu ♦Apr 24, 2015 at 8:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Assume you know the number of invertible $m \times m$ matrices over $\mathbb{Z}_{p^k}$ for $p$ prime. Call this number $N(p^k)$.
By the Chinese Remainder Theorem, $N(\prod_{i=1}^l p_i^{k_i}) = \prod_{i=1}^l N(p_i^{k_i})$ because a matrix is invertible iff every component in its CRT decomposition is invertible. For $m = 1$, $N$ is just the $\phi$ function.
Finding $N(p^k)$ is another matter.
