Until the 1970s, two parties who wanted to communicate in secret had to share a secret key first. The key was delivered by courier or agreed in person. Could strangers on an open network write to each other privately, without ever meeting?
Diffie and Hellman (1976) proposed an arrangement that would allow it. In a public-key cryptosystem, each person publishes a key for encrypting messages to them and keeps private a different key for decrypting. The proposal needed a function that is easy to compute but hard to invert without some secret information. Rivest, Shamir and Adleman (1978) found one in the arithmetic of the integers modulo $n$. Their construction uses nothing beyond what the first three units of this course prove.
The unit has two steps.
- First, a theorem about powers. In $\mathbb{Z}_{13}$ the twelfth power of every nonzero element is 1, and Fermat's little theorem says the same happens modulo every prime. Euler's theorem extends it to every modulus.
- Then, the cryptosystem built on it. The RSA cryptosystem encrypts by raising to one power modulo $n = pq$ and decrypts by raising to another, and Fermat's theorem proves that the second power undoes the first.
The unit's running numbers carry over from the first unit. The modulus 1729 turns out to be a Carmichael number, a composite that passes the Fermat test for every base relatively prime to it, while 1001 fails that test at the first try. A small RSA key of our own, $n = 3053 = 43 \cdot 71$, runs through the second article.
The unit covers Chapter 13 of the course text (Hungerford, 2014), which the course took up after the rings of Chapter 3. Judson (2026, §§6.3 and 7.2) is a free companion, and the original papers are those of Diffie and Hellman (1976) and of Rivest, Shamir and Adleman (1978).
Articles
- Fermat's Little Theorem: why does every nonzero element of $\mathbb{Z}_p$ reach 1 at the power $p - 1$? Multiplying by a unit rearranges the units, and that one observation proves Fermat's theorem and Euler's. A second proof, by the binomial theorem, gives the form $a^p \equiv a$ for every integer. The article then uses the theorem to reduce exponents, write inverses as powers, bound the order of an element, meet primitive roots, and show why an odd prime modulo which $-1$ has a square root must be $1$ more than a multiple of 4. It proves $\varphi(pq) = (p - 1)(q - 1)$ and shows how to combine congruences for relatively prime moduli. Finally it turns the theorem into a primality test, meets the pseudoprimes and Carmichael numbers that fool it, proves Korselt's criterion, and repairs the test with the strong test.
- The RSA Cryptosystem: how can an encryption rule be public while its inverse stays secret? The article starts from the key-distribution problem and Diffie–Hellman key exchange. It builds a key ($n = 3053$, $e = 13$, $d = 1357$) and encrypts and decrypts by repeated squaring and prime by prime. It proves that decryption works for every message, including those sharing a factor with $n$. It then shows why the primes must be distinct, how signatures work and how keys are made in practice. It ends with what is known, and what is not, about why RSA is secure.
Related topics
The unit applies Congruence and Modular Arithmetic: the units of $\mathbb{Z}_n$, their inverses and Euler's $\varphi$ function, and repeated squaring. It uses the field $\mathbb{Z}_p$ from Rings and Bezout's identity from Arithmetic in the Integers.
Later units return to its themes. The Chinese remainder theorem explains decryption prime by prime. Lagrange's theorem gives Euler's theorem a second proof through group theory. Finite Fields and Field Extensions constructs the other finite fields in which the same theorems hold. The next unit, Polynomial Arithmetic, turns from numbers to polynomials and repeats the theory of the first unit for them.
References
- Diffie, W., and Hellman, M. E. (1976). New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6), 644–654. record · 2 pages
- Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), Chapter 13. Brooks/Cole, Cengage Learning. The course text. record · 44 pages
- Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026), §6.3 and Chapter 7. Free online at judsonbooks.org. record · 44 pages
- Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120–126. record · 3 pages