Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

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 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 at 12:18

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.