Editing Cayley–Purser algorithm (section)

=== Key generation ===

Like RSA, Cayley-Purser begins by generating two large primes ''p'' and ''q'' and their product ''n'', a [[semiprime]]. Next, consider [[general linear group|GL]](2,''n''), the [[general linear group]] of 2×2 matrices with integer elements and [[modular arithmetic]] mod ''n''. For example, if ''n''=5, we could write:

:<math>\begin{bmatrix}0 & 1 \\ 2 & 3\end{bmatrix} +
\begin{bmatrix}1 & 2 \\ 3 & 4\end{bmatrix} =
\begin{bmatrix}1 & 3 \\ 5 & 7\end{bmatrix} \equiv
\begin{bmatrix}1 & 3 \\ 0 & 2\end{bmatrix}</math>
:<math>\begin{bmatrix}0 & 1 \\  2 & 3 \end{bmatrix} \begin{bmatrix}1 & 2 \\ 3 & 4\end{bmatrix} =
\begin{bmatrix}3 & 4 \\ 11 & 16\end{bmatrix} \equiv
\begin{bmatrix}3 & 4 \\  1 &  1\end{bmatrix}</math>

This group is chosen because it has large order (for large semiprime ''n''), equal to (''p''<sup>2</sup>−1)(''p''<sup>2</sup>−''p'')(''q''<sup>2</sup>−1)(''q''<sup>2</sup>−''q'').

Let <math>\chi</math> and <math>\alpha</math> be two such matrices from GL(2,''n'') chosen such that <math>\chi\alpha \not= \alpha\chi</math>. Choose some natural number ''r'' and compute:

:<math>\beta = \chi^{-1}\alpha^{-1}\chi,</math>
:<math>\gamma = \chi^r.</math>

The public key is <math>n</math>, <math>\alpha</math>, <math>\beta</math>, and <math>\gamma</math>. The private key is <math>\chi</math>.