# Hill cipher key space

Key space is the set of all possible keys that can be used to generate a key. We using the number of valid key to describe it.

I've given a hill cipher of block size $k$ over alphabet of size $p$, where $p$ is prime, how many keys there (valid key)?

Since the hill cipher key is a $k$ x $k$ matrix, all the elements getting from size $p$ alphabets, and from my understanding the number of possible keys should be $p^{k^2}$? but the answer is:

$(p^k-p^0)\times(p^k-p^1)\times(p^k-p^2)\times\cdots\times(p^k-p^{k-1})$

I believe it related to a matrix have a inverse or not, but don't know how to determine.

EDIT

By reading from the Key size of hill cipher from Wiki, got to known something, the example there shown the case cannot inverses is the co-factor of $26$, which is $13$ and $2$.the number of invertible for $n$ blocks over $26$ alphabets are:

$26^{n^{1}}(1-1/2)(1-1/2^{2})\cdots(1-1/2^{n})(1-1/13)(1-1/13^{2})\cdots(1-1/13^{n})$

so apply it to here, because $p$ is prime, so only $1$ or $p$ itself can divide $p^{k^2}$

the result should be:

$p^{k^2}(1-p^{-1})(1-p^{-2})\cdots(1-p^{-k})$

but still different from the answer.

• Actually, they're the same: $p^{k^2}(1-p^{-1})\cdots(1-p^{-k}) = p^{k^2}\prod_{i=1}^k(1-p^{-i}) = \prod_{i=1}^k p^k(1-p^{-i}) = \prod_{i=1}^k (p^k - p^{k-i})$ (this common value is indeed the number of invertible $k\times k$ matrices over $\mathbb{Z}/p\mathbb{Z}$). – Mehdi Tibouchi Apr 10 '14 at 8:17
• @Mehdi Tibouchi ya...i just not see each part got a p^k...so totally it p^(k^2) – atom2ueki Apr 10 '14 at 12:18