1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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}$). $\endgroup$
    – Mehdi Tibouchi
    Apr 10, 2014 at 8:17
  • $\begingroup$ @Mehdi Tibouchi ya...i just not see each part got a p^k...so totally it p^(k^2) $\endgroup$
    – atom2ueki
    Apr 10, 2014 at 12:18

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.