Suppose the numbers $n = 3053$ and $e = 13$ are published, with an invitation to send messages to their owner. To send the message $M = 2026$, anyone can compute the remainder of $2026^{13}$ on division by 3053, which is $C = 1280$, and transmit that. Recovering 2026 from 1280 looks hard: it means finding a number whose thirteenth power is 1280 in $\mathbb{Z}_{3053}$. Yet the owner recovers it with a single computation, raising 1280 to the power 1357, because the owner knows something not published: $3053 = 43 \cdot 71$. Why does the power 1357 undo the power 13, and how can the rule for encrypting be public while the rule for decrypting stays secret?
This is the RSA cryptosystem, published by Rivest, Shamir and Adleman (1978) and named from their initials. The encryption rule is public, the decryption rule is private, and knowing the first does not, as far as anyone knows, reveal the second. Every step uses the arithmetic of $\mathbb{Z}_n$ developed earlier in the course.
- Repeated squaring makes the powers cheap.
- The inverse of a unit, found by the extended Euclidean algorithm, is the private key.
- Fermat's little theorem proves that decryption undoes encryption.
First we see the problem RSA solves and the proposal of Diffie and Hellman that framed it. Then we build the key above, encrypt 2026, and decrypt it twice, once directly and once prime by prime. Next we prove that decryption recovers every message, including the awkward ones, and see what each hypothesis does. Finally we turn to signatures, practical key sizes, and what is and is not known about why RSA is secure.
This is the second article of Public-Key Cryptography, and it assumes the first, Fermat's Little Theorem. It covers Chapter 13 of the course text (Hungerford, 2014), with Judson (2026, §7.2) as a free companion. The small numbers here are chosen for hand computation; real keys use primes of hundreds of digits.
The problem RSA solves
In a classical cipher the same secret governs both directions. A shift cipher on the alphabet, read as $\mathbb{Z}_{26}$, encrypts a letter $x$ as $x + 3$ and decrypts by subtracting 3. Anyone who knows how to encrypt knows how to decrypt. Modern symmetric ciphers are vastly stronger, but they share the structure: sender and receiver must hold the same key. So before two parties can communicate privately, they must already have exchanged a secret through some other secure channel. For a network in which strangers need to communicate, this key-distribution problem is a serious barrier.
Diffie and Hellman (1976) proposed a way around it. In a public-key cryptosystem, encryption and decryption are governed by different keys, and computing the decryption key from the encryption key is computationally infeasible. Each user can then publish an encryption key in a directory, and anyone can send that user a message that only the user can read. They also observed that such a system would give digital signatures. And they described the needed object, a trap-door one-way function: a function easy to compute and hard to invert, but easy to invert for whoever holds some secret information. They did not have one. Rivest, Shamir and Adleman (1978, §I) say that Diffie and Hellman's article "motivated our research, since they presented the concept but not any practical implementation", and RSA supplied one.
An aside: agreeing on a key in public
Diffie and Hellman did solve a related problem, letting two parties agree on a shared secret key over an open channel. Fix a prime $q$ and a primitive root $\alpha$ modulo $q$. Each party picks a secret exponent, $X_A$ and $X_B$, and publishes $Y_A = \alpha^{X_A}$ and $Y_B = \alpha^{X_B}$ in $\mathbb{Z}_q$. Then each can compute
$$K = Y_B^{X_A} = \alpha^{X_A X_B} = Y_A^{X_B},$$
and an eavesdropper who sees only $Y_A$ and $Y_B$ apparently cannot. With $q = 101$ and $\alpha = 2$ (the script checks that 2 has order 100 modulo 101), secret exponents 13 and 21 give $Y_A = 2^{13} = 11$ and $Y_B = 2^{21} = 89$. Both parties arrive at $K = 48$. An eavesdropper who could solve $2^X = 11$ in $\mathbb{Z}_{101}$ for $X$, a discrete logarithm, would break the scheme. For this toy prime a search over 100 exponents finds $X = 13$ at once. Diffie and Hellman (1976, §III) note that the security rests on the apparent difficulty of discrete logarithms for large $q$, and that they had no proof that breaking the scheme requires computing them. The scheme is a key exchange, not an encryption system with a published key, and Rivest, Shamir and Adleman (1978, §V) distinguish their method from it.
So the missing piece was still a trap-door function that anyone can apply and only the owner can undo. Here is the one RSA found.
The construction
Key generation. The owner of a key does the following.
- Choose two distinct primes $p$ and $q$ and compute $n = pq$.
- Compute $\varphi(n) = (p - 1)(q - 1)$, which is Euler's function of $n$, the number of units of $\mathbb{Z}_n$.
- Choose an integer $e$ with $1 < e < \varphi(n)$ and $\gcd(e, \varphi(n)) = 1$.
- Compute $d$ with $ed \equiv 1 \pmod{\varphi(n)}$ and $0 < d < \varphi(n)$. It exists and is unique because $e$ is a unit of $\mathbb{Z}_{\varphi(n)}$, and the extended Euclidean algorithm finds it.
The public key is the pair $(n, e)$. The private key is $d$, and $p$, $q$ and $\varphi(n)$ are also kept secret (or destroyed).
Encryption and decryption. A message is an integer $M$ with $0 \le M < n$; text is first converted to numbers by any agreed scheme and cut into blocks smaller than $n$. The ciphertext is
$$C = M^e \bmod n,$$
the remainder of $M^e$ on division by $n$, and the owner decrypts by computing $C^d \bmod n$. In the language of $\mathbb{Z}_n$, encryption is the function $x \mapsto x^e$ and decryption is $x \mapsto x^d$.
The original paper fixed $d$ first and computed $e$ as its inverse (Rivest, Shamir and Adleman, 1978, §V), as the course text does; the roles are symmetric. Current practice chooses $e$ first: the U.S. federal digital signature standard requires an odd $e$ with $2^{16} < e < 2^{256}$, chosen before the primes, and computes $d$ modulo $\operatorname{lcm}(p - 1, q - 1)$, which the proof below shows is enough (NIST, 2023, Appendix A.1.1).
A small key
Take $p = 43$ and $q = 71$, both prime by trial division. Then
$$n = 43 \cdot 71 = 3053, \qquad \varphi(n) = 42 \cdot 70 = 2940 = 2^2 \cdot 3 \cdot 5 \cdot 7^2.$$
Any $e$ without the prime factors 2, 3, 5 and 7 is allowed; take $e = 13$. To invert 13 modulo 2940, run the extended Euclidean algorithm, keeping each remainder as a combination $r_i = 2940\, s_i + 13\, t_i$:
| $i$ | $r_i$ | $s_i$ | $t_i$ | $q_i$ |
|---|---|---|---|---|
| 0 | 2940 | 1 | 0 | |
| 1 | 13 | 0 | 1 | 226 |
| 2 | 2 | 1 | $-226$ | 6 |
| 3 | 1 | $-6$ | 1357 | 2 |
| 4 | 0 | 13 | $-2940$ |
Row 3 reads $1 = 2940 \cdot (-6) + 13 \cdot 1357$, so $13 \cdot 1357 \equiv 1 \pmod{2940}$ and $d = 1357$. As a check, $13 \cdot 1357 = 17{,}641 = 6 \cdot 2940 + 1$. The public key is $(3053, 13)$ and the private key is 1357.
Check your understanding. With the same primes, could the owner have chosen $e = 11$? $e = 14$? $e = 15$?
Only 11. The script finds $\gcd(11, 2940) = 1$, while $\gcd(14, 2940) = 14$ and $\gcd(15, 2940) = 15$, so 14 and 15 have no inverse modulo 2940 and no private exponent exists for them. In fact no even $e$ ever works, since $\varphi(n) = (p - 1)(q - 1)$ is even for odd primes. That parity fact returns below.
Encrypting
To encrypt $M = 2026$, write $13 = 8 + 4 + 1$ and square repeatedly, reducing modulo 3053 at each step:
| Power | Computation | Value in $\mathbb{Z}_{3053}$ |
|---|---|---|
| $M$ | 2026 | |
| $M^2$ | $2026^2 = 4{,}104{,}676$ | 1444 |
| $M^4$ | $1444^2 = 2{,}085{,}136$ | 2990 |
| $M^8$ | $2990^2 = 8{,}940{,}100$ | 916 |
Then $M^{13} = M^8 \cdot M^4 \cdot M$: first $916 \cdot 2990 = 2{,}738{,}840 \equiv 299$, then $299 \cdot 2026 = 605{,}774 \equiv 1280$. The ciphertext is $C = 1280$, from three squarings and two multiplications.
Decrypting
The owner computes $1280^{1357}$ in $\mathbb{Z}_{3053}$. In binary, $1357 = 1024 + 256 + 64 + 8 + 4 + 1$, so ten squarings produce
$$C^{1}, C^{2}, \ldots, C^{1024} = 1280, \; 1992, \; 2217, \; 2812, \; 74, \; 2423, \; 10, \; 100, \; 841, \; 2038, \; 1364,$$
and five more multiplications combine $C^{1024} \cdot C^{256} \cdot C^{64} \cdot C^{8} \cdot C^{4} \cdot C = 1364 \cdot 841 \cdot 10 \cdot 2812 \cdot 2217 \cdot 1280$, which the script reduces to 2026. The message is back.
The owner can do less work by decrypting modulo each prime separately. Modulo 43, the ciphertext is $1280 \equiv 33$. Since exponents modulo a prime may be reduced modulo $p - 1$, the exponent 1357 may be replaced by $1357 \bmod 42 = 13$, and the script finds $33^{13} \equiv 5 \pmod{43}$. Modulo 71, $1280 \equiv 2$ and $1357 \bmod 70 = 27$, and $2^{27} \equiv 38 \pmod{71}$. So the message is congruent to 5 modulo 43 and to 38 modulo 71.
Only one number from 0 to 3052 has both remainders, and it is 2026. Two such numbers would differ by a multiple of both 43 and 71, hence, by the lemma on relatively prime moduli, by a multiple of 3053. Finding that number from its two remainders in general is the job of the Chinese remainder theorem. The standard specification of RSA allows the private key to be stored in this form: $p$ and $q$, the reduced exponents (here 13 and 27), and a coefficient for the recombination step (Moriarty et al., 2016, §3.2).
One message came back. Will every message come back, including those that are multiples of 43 or 71?
Why decryption works
Decryption raises $C \equiv M^e$ to the power $d$, giving $M^{ed}$, so what has to be shown is that $M^{ed} \equiv M \pmod n$.
Here is the plan of the proof. Modulo the prime $p$, the exponent $ed$ is 1 more than a multiple of $p - 1$, so Fermat's theorem strips away everything but one factor of $M$; if $p$ divides $M$, both sides are 0 anyway. The same holds modulo $q$, and the lemma on relatively prime moduli combines the two congruences into one modulo $n$.
Theorem. Let $p$ and $q$ be distinct primes and $n = pq$, and let $e$ and $d$ be positive integers such that $ed \equiv 1 \pmod{p - 1}$ and $ed \equiv 1 \pmod{q - 1}$. Then
$$M^{ed} \equiv M \pmod n \quad \text{for every integer } M.$$
In particular this holds when $ed \equiv 1 \pmod{(p - 1)(q - 1)}$, since $p - 1$ and $q - 1$ both divide $(p - 1)(q - 1)$. Consequently, if $0 \le M < n$ and $C = M^e \bmod n$, then $C^d \bmod n = M$.
Proof. Modulo $p$. Since $ed \equiv 1 \pmod{p - 1}$ and $ed \ge 1$, we can write $ed = 1 + (p - 1)s$ for an integer $s \ge 0$. If $p \nmid M$, then by Fermat's little theorem
$$M^{ed} = M \cdot \bigl(M^{p-1}\bigr)^{s} \equiv M \cdot 1^{s} = M \pmod p.$$
If $p \mid M$, then $M \equiv 0 \pmod p$, so $M^{ed} \equiv 0 \equiv M \pmod p$, since $ed \ge 1$. In both cases $M^{ed} \equiv M \pmod p$.
Modulo $q$. The same argument, with $ed = 1 + (q - 1)s'$, gives $M^{ed} \equiv M \pmod q$.
Modulo $n$. So $p$ and $q$ both divide $M^{ed} - M$. Distinct primes are relatively prime, so by the lemma on relatively prime moduli (if $m \mid c$, $k \mid c$ and $\gcd(m, k) = 1$, then $mk \mid c$), $pq = n$ divides $M^{ed} - M$, which is the congruence claimed.
Decryption. $C \equiv M^e \pmod n$ by the definition of a remainder, so by the rule for powers of congruences, $C^d \equiv M^{ed} \equiv M \pmod n$. The integers $C^d \bmod n$ and $M$ both lie between 0 and $n - 1$ and are congruent modulo $n$. Two such integers are equal, since every integer is congruent to exactly one of $0, \ldots, n - 1$. $\blacksquare$
The script confirms the theorem for every message modulo 3053, and for every pair of distinct primes below 60 with several exponents $e$ and every message.
Messages that share a factor with $n$
A shorter argument is often given, using Euler's theorem in place of Fermat's: if $\gcd(M, n) = 1$, then $M^{\varphi(n)} \equiv 1 \pmod n$, so $M^{ed} = M \cdot (M^{\varphi(n)})^t \equiv M$. That argument covers only messages relatively prime to $n$. For the others it fails at its first step.
Check your understanding. The message $M = 2130 = 30 \cdot 71$ is a multiple of 71, and the script finds $2130^{2940} \equiv 1420 \pmod{3053}$, not 1. Does RSA with the article's key still decrypt it correctly?
It does. $2130^{13} \equiv 497$ and $497^{1357} \equiv 2130 \pmod{3053}$. The Euler argument failed, not the system. The proof above covers such messages through the case $p \mid M$, where both sides vanish modulo that prime. The original paper gave this prime-by-prime proof, crediting Richard Schroeppel with the improved argument, and observed that it shows the identity holds for all $M$ (Rivest, Shamir and Adleman, 1978, §VI). Judson (2026, §7.2) treats the second case separately with Euler's theorem modulo the other prime.
The messages in question are rare. By the count behind $\varphi(pq)$, exactly $p + q - 1$ of the numbers $0, \ldots, n - 1$ share a factor with $n$. Here that is 113 of 3053, a fraction $\frac{1}{p} + \frac{1}{q} - \frac{1}{n} \approx 3.7\%$. With primes of hundreds of digits the fraction is so small that a message chosen without knowledge of $p$ or $q$ essentially never lands on one. The theorem guarantees that decryption works regardless.
What the hypotheses do
Which hypotheses did the proof actually use? Two can be tested directly.
The two primes must be distinct. Take $n = 25 = 5^2$ and exponents satisfying $ed \equiv 1 \pmod{\varphi(25)}$, for instance $e = 3$ and $d = 7$. The message 5 encrypts to $5^3 = 125 \equiv 0$, and then $0^7 = 0 \neq 5$. The script finds that this choice fails exactly for the four nonzero multiples of 5. The proof needed $n$ to be a product of distinct primes at the step where Fermat's theorem modulo $p$ was turned into a congruence modulo $n$. Modulo $p^2$, the case $p \mid M$ no longer makes both sides agree.
The exponent condition can be weakened, as the theorem's statement allows. For the key above, $\operatorname{lcm}(42, 70) = 210$, and $d' = 1357 \bmod 210 = 97$ satisfies $13 \cdot 97 = 1261 = 6 \cdot 210 + 1$. The script confirms that $C^{97}$ decrypts every message as well as $C^{1357}$ does. The original paper remarks that $\varphi(n)$ may be replaced by $\operatorname{lcm}(p - 1, q - 1)$ (Rivest, Shamir and Adleman, 1978, §IX-C), and the federal standard defines $d$ that way (NIST, 2023, Appendix A.1.1).
The theorem also shows that encryption is a permutation of $\{0, 1, \ldots, n - 1\}$. Decryption undoes it, so no two messages share a ciphertext and every number is the ciphertext of some message. The figure shows the permutation for the article's key.
Check your understanding. Without computing a power, predict the ciphertexts of the messages 0, 1 and 3052 under the article's key.
Each encrypts to itself. $0^{13} = 0$ and $1^{13} = 1$. And $3052 = -1$ in $\mathbb{Z}_{3053}$, while $e = 13$ is odd, so $(-1)^{13} = -1 = 3052$. Every RSA key leaves these three alone, since $e$ is always odd: it is relatively prime to the even number $\varphi(n)$. For this key the script finds 21 messages left unchanged in all.
Signatures
Decryption undoes encryption. Does encryption also undo decryption? Because $M^{de} = M^{ed}$, the two exponents can be applied in either order: encrypting a decrypted number also returns it. This gives signatures. To sign a message $M$, the owner of the key computes
$$S = M^d \bmod n$$
with the private exponent and sends $S$ with $M$. Anyone can check the signature with the public key, by verifying that $S^e \bmod n = M$. Only the holder of $d$ could have produced an $S$ that passes. With the article's key, the signature on the message 1729 is $S = 1729^{1357} \bmod 3053 = 1477$, and anyone holding the public key computes $1477^{13} \bmod 3053 = 1729$. The signature depends on the message: the signature on 1730 is 1887. The two uses of a public key, privacy for messages sent to its owner and signatures by its owner, are both due to Diffie and Hellman (1976). Rivest, Shamir and Adleman (1978, §§III–IV) show how their permutation provides both, and that a function usable for signatures must be a permutation, which RSA encryption is. In practice the number signed is not the message itself but a fixed-length hash of it, formatted by a padding scheme (Moriarty et al., 2016).
Making it practical
The mathematics works for any two distinct primes. What does it cost with primes of hundreds of digits? A system with public encryption is only useful if the honest parties' work is small while the attacker's is enormous. Each of the owner's steps is efficient.
- Powers. Repeated squaring computes $M^e \bmod n$ with at most about $2 \log_2 e$ multiplications and reductions (Rivest, Shamir and Adleman, 1978, §VII-A); for an exponent of 2048 bits this is a few thousand operations on numbers of a few hundred digits.
- The private exponent. The extended Euclidean algorithm finds $d$ in a number of steps proportional to the number of digits, by Lamé's bound.
- Primes. The owner generates random odd numbers of the desired size and tests them. Trial division is hopeless at this size, so the test is the strong probabilistic test built on Fermat's theorem. By the prime number theorem, about one number in $\ln x$ near $x$ is prime, so about one odd number in $\frac{1}{2}\ln x$. For 1024-bit primes, $\ln 2^{1024} \approx 709.8$, so on average about 355 odd candidates are tested before a prime is found. The original paper made the same estimate for its recommended 100-digit primes, about 115 candidates (§VII-B).
The current U.S. federal digital signature standard requires a modulus of at least 2048 bits, with $p$ and $q$ of equal length, and prescribes the Miller–Rabin test for generating them (NIST, 2023, §5.1 and Appendix B.3). The paper of 1978 recommended a modulus of about 200 decimal digits, roughly 664 bits.
Why it is believed secure
An eavesdropper sees $n$, $e$ and the ciphertext $C$. Breaking RSA has not been proved as hard as factoring $n$, and nothing in the mathematics proves that recovering $M$ is hard at all. What can be said is which attacks are known to work, which are known to be equivalent to each other, and which questions remain open.
Factoring breaks RSA. Whoever factors $n$ can compute $\varphi(n) = (p - 1)(q - 1)$ and then $d$ by the extended Euclidean algorithm, exactly as the owner did. For $n = 3053$, trial division finds the factor 43 after a handful of divisions; for a modulus of 600 digits, no known method finishes.
Knowing $\varphi(n)$ is as good as factoring. Since $\varphi(n) = pq - p - q + 1 = n - (p + q) + 1$, the sum $p + q = n - \varphi(n) + 1$ follows from $n$ and $\varphi(n)$. Then $p$ and $q$ are the two roots of $x^2 - (p + q)x + n = 0$. For the article's key, $p + q = 3053 - 2940 + 1 = 114$, the discriminant is $114^2 - 4 \cdot 3053 = 12{,}996 - 12{,}212 = 784 = 28^2$, and the roots are $(114 \pm 28)/2 = 71$ and $43$. So computing $\varphi(n)$ is no easier than factoring (Rivest, Shamir and Adleman, 1978, §IX-B).
Knowing $d$ is as good as factoring. The number $ed - 1$ is a multiple of $\varphi(n)$. Rivest, Shamir and Adleman (1978, §IX-C) cite Miller for a method that factors $n$ given any such multiple. Its core is the same square-root idea as the strong primality test, which split 1729 in the previous article. For the article's key, $ed - 1 = 17{,}640 = 2^3 \cdot 2205$, and the script finds $2^{2205} \equiv 214$ and $214^2 \equiv 1 \pmod{3053}$. So 214 is a square root of 1 other than $\pm 1$, and $\gcd(213, 3053) = 71$ is a factor.
Decrypting without $d$ is not known to require factoring. An attacker need not find $d$; it is enough to compute $e$-th roots modulo $n$ by some other route. Rivest, Shamir and Adleman (1978, §IX-D) conjectured that any general method of breaking their scheme would yield an efficient factoring algorithm, and said they could not prove it. The question is still open: in the words of Boudot et al. (2022), factoring and breaking RSA "are not known to be equivalent". Nor is factoring itself known to be hard; the evidence is that a great deal of effort has not produced a fast method.
How hard factoring is in practice. The original paper estimated that a 200-digit modulus would take billions of years with the best algorithm then known (§IX-A); algorithms and hardware have improved enormously since. At the time of the survey by Boudot et al. (2022), the record factorization of a modulus of RSA type was RSA-250, of 250 decimal digits (829 bits), in February 2020, using about 2,700 core-years of computation, and Boudot et al. (2022) estimate a 1024-bit modulus at roughly 200 times that effort. NIST rates a 2048-bit modulus at 112 bits of security strength and a 3072-bit modulus at 128 bits, a measure of the work needed to break it on the same scale as the key length of a symmetric cipher (Barker, 2020, §5.6.1.1, Table 2).
Quantum computers. Shor (1997) gave an algorithm that factors integers, and computes discrete logarithms, in polynomial time on a quantum computer. No quantum computer of the necessary size exists, and whether one can be built is an open question (Boudot et al., 2022). Because of the possibility, standards bodies are preparing replacements based on different mathematics, and NIST notes that schemes such as RSA may need to be replaced by quantum-resistant counterparts (Barker, 2020, §5.6.1).
The textbook scheme is not used as it stands. The construction above, often called textbook RSA, is deterministic: the same message always produces the same ciphertext.
Check your understanding. An eavesdropper intercepts $C = 1280$ and suspects that the message is 2025, 2026 or 2027. Can the eavesdropper decide which, without the private key and without factoring?
Yes. The public key is public, so the eavesdropper encrypts all three guesses and compares. The results are 2462, 1280 and 264, and only 2026 matches. No inverse was computed; a short list of plausible messages was enough.
Very small messages are also a problem, since if $M^e < n$ no reduction happens and an ordinary $e$-th root recovers $M$. The original paper already asked for exponents large enough that every message other than 0 and 1 is reduced modulo $n$ at least once (§VII-D). Practical RSA encryption therefore pads each message with random bits in a prescribed format before exponentiating. The standard scheme, RSAES-OAEP, is proved secure against strong attacks provided that computing $e$-th roots modulo $n$ is infeasible and under an idealized model of its hash functions (Moriarty et al., 2016, §7.1).
Where it leads
- Decryption prime by prime, then recombination, is an instance of the Chinese remainder theorem, which identifies $\mathbb{Z}_{pq}$ with $\mathbb{Z}_p \times \mathbb{Z}_q$ and makes the recombination step explicit.
- The primality tests that find RSA primes are the computational side of Fermat's theorem; Carmichael numbers such as 1729 show why the plain Fermat test is not enough.
- Euler's theorem is a statement about the group of units $U(n)$, and Lagrange's theorem explains it in the language of groups.
- Diffie–Hellman key exchange computes in the multiplicative group of the field $\mathbb{Z}_q$; other finite fields, constructed in Finite Fields and Field Extensions, and other groups can replace it.
What we have learned
An RSA key is two distinct primes $p$ and $q$, the public pair $n = pq$ and $e$, and the private inverse $d$ of $e$ modulo $(p - 1)(q - 1)$, found by the extended Euclidean algorithm. Encryption and decryption are powers in $\mathbb{Z}_n$, cheap by repeated squaring. Fermat's theorem modulo each prime, combined by the lemma on relatively prime moduli, proves $M^{ed} \equiv M$ for every message, including the multiples of $p$ or $q$ that Euler's theorem alone misses. So 1357 undoes 13 for all 3053 messages, and the same exponents in the other order give signatures. Factoring $n$ breaks the system, and so does knowing $\varphi(n)$ or $d$. Whether breaking it requires factoring is still open.
That completes the unit. Its arithmetic, like that of the first unit, was arithmetic of integers: division, gcds, Bezout's identity and primes. Does the same theory work for polynomials, with coefficients in $\mathbb{Z}$, in a field, or in a ring such as $\mathbb{Z}_{12}$? The next unit, Polynomial Arithmetic, finds that polynomials form rings of their own, and its first article, Polynomial Rings, shows that over $\mathbb{Z}_{12}$ two nonzero polynomials can multiply to zero.
References
- Barker, E. (2020). Recommendation for Key Management: Part 1, General, NIST Special Publication 800-57 Part 1, Revision 5. National Institute of Standards and Technology. §5.6.1.1, Table 2: a 2048-bit RSA modulus provides 112 bits of security strength and a 3072-bit modulus 128 bits; §5.6.1: RSA-based schemes may need quantum-resistant replacements. record
- Boudot, F., Gaudry, P., Guillevic, A., Heninger, N., Thomé, E., and Zimmermann, P. (2022). The state of the art in integer factoring and breaking public-key cryptography. IEEE Security & Privacy, 20(2), 80–86. Factoring and breaking RSA are not known to be equivalent; RSA-250 (829 bits) was factored in February 2020 for about 2,700 core-years; a 1024-bit modulus would take about 200 times as much; whether quantum computers able to run Shor's algorithm can be built is open. record
- Diffie, W., and Hellman, M. E. (1976). New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6), 644–654. Public-key cryptosystems and public key distribution, signatures, trap-door one-way functions; §III, key exchange by exponentiation modulo a prime, whose security rests on the apparent difficulty of logarithms modulo $q$, with no proof of the converse. record · 2 pages
- Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), Chapter 13. Brooks/Cole, Cengage Learning. The course text: the RSA construction and the proof that decryption works (Theorem 13.3). record · 44 pages
- Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026), §7.2. Free online at judsonbooks.org. Public-key cryptography and RSA, with a proof of correctness that treats messages sharing a factor with $n$ separately. record · 44 pages
- Moriarty, K. (Ed.), Kaliski, B., Jonsson, J., and Rusch, A. (2016). PKCS #1: RSA Cryptography Specifications Version 2.2, RFC 8017. Internet Engineering Task Force. §3.2: the second form of the private key, $p$, $q$, the exponents reduced modulo $p - 1$ and $q - 1$, and the coefficient $q^{-1} \bmod p$; §7.1: RSAES-OAEP and the conditions of its security proof; signature schemes that sign an encoded hash. record · 2 pages
- National Institute of Standards and Technology (2023). Digital Signature Standard (DSS), FIPS 186-5. §5.1: moduli of at least 2048 bits with primes of equal length; Appendix A.1.1: $e$ odd with $2^{16} < e < 2^{256}$, chosen before the primes, and $d = e^{-1} \bmod \operatorname{lcm}(p - 1, q - 1)$; Appendix B.3: the Miller–Rabin test. record · 2 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. §§II–IV: the properties of a public-key cryptosystem, privacy and signatures, credited to Diffie and Hellman; §V: the method, with $d$ chosen first; §VI: the proof of correctness for all $M$, credited to Schroeppel; §VII: repeated squaring, finding primes, computing $e$ from $d$, and the wrap-around condition; §IX: factoring $n$ breaks the system, $\varphi(n)$ or $d$ yields the factors, $\varphi(n)$ may be replaced by $\operatorname{lcm}(p - 1, q - 1)$, and the open conjecture that breaking the system requires factoring. record · 3 pages
- Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484–1509. Preliminary version in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science (1994). Read in the arXiv version, quant-ph/9508027. record