in this discussion is as in Flannery's original paper. Key generation Like RSA, Cayley-Purser begins by generating two large primes p and q and their product n, a semiprime. Next, consider 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: This group is chosen because it has large order (for large semiprime n), equal to (p2−1)(p2−p)(q2−1)(q2−q). Let and be two such matrices from GL(2,n) chosen such that . Choose some natural number r and compute: The public key is , , , and . The private key is . Encryption The sender begins by generating a random natural number s and computing: Then, to encrypt a message, each message block is encoded as a number (as in RSA) and they are placed four at a time as elements of a plaintext matrix . Each is encrypted using: Then and are sent to the receiver. Decryption The receiver recovers the original plaintext matrix via: Security Recovering the private key from is computationally infeasible, at least as hard as finding square roots mod n (see quadratic residue). It could be recovered from and if the system could be solved, but the number of solutions to this system is large as long as elements in the group have a large order, which can be guaranteed for almost every element. However, the system can be broken by finding a multiple of by solving for in the following congruence: Observe that a solution exists if for some and If is known, — a multiple of . Any multiple of yields . This presents a fatal weakness for the system, which has not yet been reconciled. This flaw does not preclude the algorithm's use as a mixed private-key/public-key algorithm, if the sender transmits secretly, but this approach presents no advantage over the common approach of transmitting a symmetric encryption key using a public-key encryption scheme and then switching to symmetric encryption, which is faster than Cayley-Purser. See also Non-commutative cryptography References Sarah Flannery and David Flannery. In Code: A Mathematical Journey. Public-key encryption schemes Broken cryptography algorithms