Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


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


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:


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

the result should be:


but still different from the answer.

share|improve this question
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^ totally it p^(k^2) – atom2ueki Apr 10 '14 at 12:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.