Editing Hill cipher (section)

===Key space size===
The [[key_space_(cryptography)|key space]] is the set of all possible keys. The key space size is the number of possible keys. The effective [[key size]], in number of bits, is the [[binary logarithm]] of the key space size.

There are <math>26^{n^2}</math> matrices of dimension ''n'' × ''n''. Thus <math>\log_2(26^{n^2})</math> or about <math>4.7n^2</math> is an upper bound on the key size of the Hill cipher using ''n'' × ''n'' matrices. This is only an upper bound because not every matrix is invertible and thus usable as a key. The number of invertible matrices can be computed via the [[Chinese Remainder Theorem]]. I.e., a matrix is invertible modulo 26 if and only if it is invertible both modulo 2 and modulo 13.
The number of invertible ''n'' × ''n'' matrices modulo 2 is equal to the order of the [[general linear group]] GL(n,'''Z'''<sub>2</sub>). It is 
:<math>2^{n^2}(1-1/2)(1-1/2^2)\cdots(1-1/2^n).</math>
Equally, the number of invertible matrices modulo 13 (i.e. the order of GL(n,'''Z'''<sub>13</sub>)) is
:<math>13^{n^2}(1-1/13)(1-1/13^2)\cdots(1-1/13^n).</math>
The number of invertible matrices modulo 26 is the product of those two numbers. Hence it is
:<math>26^{n^2}(1-1/2)(1-1/2^2)\cdots(1-1/2^n)(1-1/13)(1-1/13^2)\cdots(1-1/13^n).</math>
Additionally it seems to be prudent to avoid too many zeroes in the key matrix, since they reduce diffusion. The net effect is that the effective keyspace of a basic Hill cipher is about <math>4.64n^2 - 1.7</math><!-- I'm not sure how a previous editor found this formula. -->. For a 5 &times; 5 Hill cipher, that is about 114 bits. Of course, key search is not the most efficient known attack.