math.wiki
Number theory › Congruences › RSA and primality tests
Sign in

RSA and primality tests

RSA needs primes hundreds of digits long and stays safe only while no one can factor their product. How can we tell quickly that a huge number is prime without factoring it, and which careless uses of a key give the factors or the message away?

Where you are 2 in Congruences

Why this exists

An RSA key uses two primes p \ne q, the modulus n = pq, a public e coprime to \varphi(n) = (p-1)(q-1) and a private d with ed \equiv 1 \pmod{\varphi(n)}; unlocking works by Theorem 2 there. A key needs primes of about 300 digits, far beyond trial division, and by the prime number theorem (stated in How the primes are spread out) roughly one integer in \ln x near x is prime, so a key generator tries hundreds of random candidates and needs a fast test. And factoring being hard protects only a key used with care.

The Fermat test (Corollary 6 of Fermat's little theorem) proves n composite when a^{n-1} \not\equiv 1 \pmod{n} for some a with n \nmid a, but a Carmichael number such as 561 (Example 6 there) passes for every base coprime to it. This lesson finds exactly which numbers those are, strengthens the test so that no composite fools it for more than a quarter of the bases, and proves that a leaked d, or one message sent carelessly, gives the secret away.

Definition

A Carmichael number is a composite positive integer n with a^{n-1} \equiv 1 \pmod{n} for every a with \gcd(a, n) = 1. A positive integer is squarefree if the square of no prime divides it. For a composite n and 1 \le a \le n - 1, the base a is a Fermat liar if a^{n-1} \equiv 1 \pmod{n} and a Fermat witness otherwise.

Now let n \ge 3 be odd and write n - 1 = 2^s t with s \ge 1 and t odd. For a base a with 1 \le a \le n - 1, the Miller-Rabin sequence is

x_r = a^{2^r t} \bmod n, \qquad r = 0, 1, \dots, s,

so each term is the square of the one before modulo n, and x_s = a^{n-1} \bmod n. The number n passes to base a if x_0 = 1, or x_r = n - 1 for some r with 0 \le r < s. For a composite n, a base it passes to is a strong liar, and any other base is a strong witness. The Miller-Rabin test picks k bases independently and uniformly from 1, \dots, n - 1; it declares n composite at the first strong witness and “probably prime” if all k pass.

A liar of either kind is coprime to n: a prime dividing a and n would divide a^j \mp 1 and a^j, hence 1. A strong liar is a Fermat liar, because squaring 1 or n - 1 onward reaches x_s = 1; so the strong test is never weaker than Fermat’s.

Intuition

Modulo a prime, 1 has only the square roots \pm 1 (Lemma 4). In a Miller-Rabin sequence each term squares to the next, so for a prime n the sequence is either all 1s or reaches its first 1 straight from n - 1. Modulo a product of two odd primes, 1 has four square roots, one for each choice of \pm 1 modulo each prime (The Chinese remainder theorem), and the sequence may step into 1 from one of the two extra ones. Seeing such a step proves n composite, and does more: the extra root x has x \equiv 1 modulo one prime and x \equiv -1 modulo the other, so \gcd(x - 1, n) is a factor.

28 8 64 22 96 1
n = 97,\ a = 5
prime: passes 8 64 1 1 1 1 1
n = 65,\ a = 8
composite: passes 257 259 1
n = 645,\ a = 2
composite: fails
Figure 1Miller-Rabin sequences. Shaded boxes hold n - 1. For 645 the term before the first 1 is 259, a square root of 1 that is not \pm 1, so 645 is composite.

In the bottom row, 259 \equiv 1 \pmod{3}, 259 \equiv -1 \pmod{5} and 259 \equiv 1 \pmod{43}. In the middle row, 64 \equiv -1 \pmod{65} and the composite looks like a prime; Theorem 6 limits such bases to a quarter.

Results

Theorem 1 (Korselt’s criterion). A composite positive integer n is a Carmichael number if and only if n is squarefree and p - 1 \mid n - 1 for every prime p dividing n.

Corollary 2. Every Carmichael number is odd and has at least three different prime factors.

Theorem 3 (Fermat liars). If n is composite and not a Carmichael number, at most \varphi(n)/2 of the bases 1, \dots, n - 1 are Fermat liars.

Lemma 4 (square roots of 1). (a) If p is prime and x^2 \equiv 1 \pmod{p}, then x \equiv \pm 1 \pmod{p}. (b) If n \ge 2, x^2 \equiv 1 \pmod{n} and x \not\equiv \pm 1 \pmod{n}, then 1 < \gcd(x - 1, n) < n.

Theorem 5 (primes pass). If n is an odd prime, n passes the Miller-Rabin test to every base a with 1 \le a \le n - 1.

Theorem 6 (Monier and Rabin, stated without proof). If n is an odd composite number other than 9, at most \varphi(n)/4 of the bases 1, \dots, n - 1 are strong liars. So a composite n passes k independent random bases with probability below 4^{-k}.

Theorem 7 (a private exponent factors n). Let n = pq with p \ne q odd primes, and let m be a positive integer divisible by p - 1 and by q - 1; for an RSA key, m = ed - 1 is one. Write m = 2^s t with t odd. For at least half of the a \in \mathbb{Z}_n^{\times}, some term x of the list a^t, a^{2t}, \dots, a^{2^s t}, reduced modulo n, has x^2 \equiv 1 and x \not\equiv \pm 1 \pmod{n}, and then \gcd(x - 1, n) is p or q.

Theorem 8 (one message, e moduli). Let n_1, \dots, n_e be pairwise coprime, N = n_1 \cdots n_e, 0 \le m < \min_i n_i and c_i = m^e \bmod n_i. If C is the integer with 0 \le C < N and C \equiv c_i \pmod{n_i} for every i, then C = m^e, so m is the ordinary eth root of C.

Monier and Rabin proved Theorem 6 independently in 1980; see Crandall and Pomerance, Prime Numbers: A Computational Perspective, Section 3.5.

Why it is true

From Bezout's identity and the extended Euclidean algorithm we use Euclid’s lemma and the coprime factor lemma (a \mid bc and \gcd(a, b) = 1 give a \mid c), with its consequence that coprime divisors of an integer have product dividing it.

Proof of Theorem 1. Suppose n is squarefree, n = p_1 \cdots p_k with different primes, and p_i - 1 \mid n - 1 for each i. If \gcd(a, n) = 1, Fermat’s little theorem gives a^{p_i - 1} \equiv 1, so a^{n-1} \equiv 1 \pmod{p_i} for each i, and the p_i are coprime, so n \mid a^{n-1} - 1.

Conversely let n be a Carmichael number and p a prime factor. If p^2 \mid n, put a = 1 + n/p. Every prime factor of n divides n/p (for p because p^2 \mid n, for the others by Euclid’s lemma), so a \equiv 1 modulo each of them and \gcd(a, n) = 1. Since (n/p)^2 = n \cdot n/p^2 \equiv 0 \pmod{n}, the binomial theorem gives a^{n-1} \equiv 1 + (n - 1)\,n/p \pmod{n}. If this were 1, then n \mid (n-1)\,n/p, so p \mid n - 1; with p \mid n that gives p \mid 1. So a^{n-1} \not\equiv 1, a contradiction, and n is squarefree. Now p and n/p are coprime. Let g be a primitive root modulo p (Primitive roots, Theorem 7) and, by The Chinese remainder theorem, choose a with a \equiv g \pmod{p} and a \equiv 1 \pmod{n/p}. Then \gcd(a, n) = 1, so a^{n-1} \equiv 1 \pmod{n}, hence g^{n-1} \equiv 1 \pmod{p}, and p - 1 = \operatorname{ord}_p(g) divides n - 1 (Theorem 1(a) there). \square

Proof of Corollary 2. A composite squarefree n has two different prime factors, so an odd one p, and p - 1 is even and divides n - 1: n is odd. If n = pq with 3 \le p < q, then q - 1 divides n - 1 = p(q - 1) + (p - 1), so q - 1 \mid p - 1, impossible as 0 < p - 1 < q - 1. \square

Proof of Theorem 3. Some b coprime to n has b^{n-1} \not\equiv 1. For each Fermat liar a, the remainder of ab is coprime to n and (ab)^{n-1} \equiv b^{n-1} \not\equiv 1, so it is a Fermat witness coprime to n. Different liars give different products, since b cancels (Modular inverses and linear congruences). So among the \varphi(n) bases coprime to n there are at least as many witnesses as liars, and every liar is coprime to n. \square

Proof of Lemma 4. (a) p \mid (x - 1)(x + 1), so Euclid’s lemma gives p \mid x - 1 or p \mid x + 1. (b) n \mid (x - 1)(x + 1). If \gcd(x - 1, n) = 1, the coprime factor lemma gives n \mid x + 1; if \gcd(x - 1, n) = n, then n \mid x - 1. Both are excluded. \square

Proof of Theorem 5. By Fermat’s little theorem x_s = 1. If x_0 \ne 1, let j \ge 1 be the least index with x_j = 1. Then x_{j-1}^2 \equiv 1 and x_{j-1} \ne 1, so x_{j-1} = n - 1 by Lemma 4(a), with j - 1 < s. \square

Proof of Theorem 7. As p - 1 is even and divides m, s \ge 1. For a unit a, a^m \equiv 1 modulo p and modulo q by Fermat’s little theorem, hence modulo n, so the list ends in 1. Let g, h be primitive roots modulo p and q. By the bijection of The Chinese remainder theorem (Theorem 4) and Corollary 3 of Primitive roots, the units a modulo n match the pairs (i, j), 0 \le i < p - 1, 0 \le j < q - 1, with a \equiv g^i \pmod{p} and a \equiv h^j \pmod{q}.

Write p - 1 = 2^u p' with p' odd. Since p' \mid 2^s t and \gcd(p', 2^s) = 1, p' \mid t, and as t/p' is odd, \gcd(p - 1, it) = p' \gcd(2^u, i). By Theorem 2 of Primitive roots, \operatorname{ord}_p(a^t) = (p-1)/\gcd(p-1, it) = 2^{\alpha} with 2^{\alpha} = 2^u/\gcd(2^u, i): so \alpha = u if i is odd and \alpha < u if i is even. Likewise q - 1 = 2^v q' and \operatorname{ord}_q(a^t) = 2^{\beta}, with \beta = v exactly when j is odd. Also u, v \le s, as p - 1 and q - 1 divide m.

Suppose \alpha < \beta and let x = a^{2^{\beta-1} t}, in the list as \beta \le v \le s. Modulo p, x \equiv 1, since 2^{\alpha} \mid 2^{\beta - 1}. Modulo q, x has order 2^{\beta}/2^{\beta-1} = 2 by Theorem 2 again, so x \not\equiv 1, x^2 \equiv 1, and x \equiv -1 by Lemma 4(a). So x^2 \equiv 1 \pmod{n}, x \not\equiv 1 (modulo q), x \not\equiv -1 (modulo p, as p \ne 2), and p \mid x - 1 while q \nmid x - 1: \gcd(x - 1, n) = p. If \beta < \alpha, exchanging the roles gives q.

It remains to count the pairs with \alpha \ne \beta. Name the primes so that u \le v. If u < v, every pair with j odd has \alpha \le u < v = \beta, and these are half of all pairs, as q - 1 is even. If u = v, the pairs with i odd and j even, and those with i even and j odd, are each a quarter of all pairs and have \alpha \ne \beta. \square

Proof of Theorem 8. Each m < n_i, so m^e < N. And m^e \equiv c_i \equiv C \pmod{n_i} for every i, so N \mid m^e - C by the coprime factor lemma, one modulus at a time. Two integers in [0, N) that differ by a multiple of N are equal. \square

Worked examples

Example 1

Korselt’s criterion on three candidates

Given 2821 = 7 \cdot 13 \cdot 31, 3367 = 7 \cdot 13 \cdot 37 and 6601 = 7 \cdot 23 \cdot 41, decide which are Carmichael numbers. For any that is not, find a Fermat witness.

Solution

All three are squarefree, so Theorem 1 asks whether each p - 1 divides n - 1. For 2821: 2820 = 6 \cdot 470 = 12 \cdot 235 = 30 \cdot 94, so yes. For 6601: 6600 = 6 \cdot 1100 = 22 \cdot 300 = 40 \cdot 165, so yes. For 3367: 3366 = 2 \cdot 1683 with 1683 odd, so 4 \nmid 3366 and 12 \nmid 3366. So 2821 and 6601 are Carmichael numbers and 3367 is not.

The proof of Theorem 1 says where to look for a witness: a primitive root modulo 13. Since 2^6 = 64 \equiv -1 \pmod{13} and 2^4 \equiv 3, 2 is a primitive root modulo 13, and 3366 = 12 \cdot 280 + 6 gives 2^{3366} \equiv 2^6 \equiv -1 \pmod{13}. So 2^{3366} \not\equiv 1 \pmod{3367}, and 2 is a Fermat witness for 3367.

Example 2

The strong test catches a Fermat liar

Show that 2 is a Fermat liar for the composite 645 but a strong witness, and use the computation to factor 645.

Solution

Here 644 = 4 \cdot 161, so s = 2 and t = 161. The squares 2^{2^k} \bmod 645 for k = 0, \dots, 7 are 2, 4, 16, 256, 391, 16, 256, 391. As 161 = 128 + 32 + 1,

\begin{aligned} x_0 &\equiv 391 \cdot 16 \cdot 2 = 12{,}512 \\ &= 19 \cdot 645 + 257. \end{aligned}

Then x_1 \equiv 257^2 = 66{,}049 = 102 \cdot 645 + 259 and x_2 \equiv 259^2 = 67{,}081 = 104 \cdot 645 + 1. So 2^{644} \equiv 1 and 2 is a Fermat liar. But x_0 = 257 \ne 1 and x_0, x_1 \ne 644, so 2 is a strong witness. The term 259 is a square root of 1 other than \pm 1, and by Lemma 4(b), \gcd(258, 645) = 129 is a proper factor: 645 = 5 \cdot 129 = 3 \cdot 5 \cdot 43.

Example 3

Counting the liars of 65

Find every strong liar for n = 65, and count its Fermat liars.

Solution

64 = 2^6, so t = 1, s = 6, and a is a strong liar when a \equiv 1 or a^{2^r} \equiv -1 \pmod{65} for some r \le 5. For a coprime to 65, a^4 \equiv 1 \pmod{5}, so a^{2^r} \equiv 1 \pmod{5} for r \ge 2, and r = 0, 1 remain. r = 0 gives a = 64. Now a^2 \equiv -1 \pmod{65} means a^2 \equiv -1 modulo 5 and modulo 13, that is a \equiv 2, 3 \pmod{5} and a \equiv 5, 8 \pmod{13}; the The Chinese remainder theorem turns the four pairs into 8, 18, 47, 57. The strong liars are 1, 8, 18, 47, 57, 64: six of the \varphi(65) = 48 units, an eighth.

For Fermat liars, a^{64} \equiv 1 \pmod{5} always, and modulo 13, a^{64} \equiv a^4 since 64 = 5 \cdot 12 + 4. The congruence x^4 \equiv 1 \pmod{13} has 4 solutions, as 4 \mid 12 (Exercise 17 of Primitive roots), so there are 4 \cdot 4 = 16 Fermat liars, a third of the units.

Example 4

A family of Carmichael numbers

Let k \ge 1 be such that 6k + 1, 12k + 1 and 18k + 1 are all prime. Prove that their product n is a Carmichael number.

Solution

Proof. Multiplying out,

\begin{aligned} n &= 1296k^3 + 396k^2 + 36k + 1, \\ n - 1 &= 36k\,(36k^2 + 11k + 1). \end{aligned}

So n - 1 is a multiple of 36k, and hence of each of 6k, 12k and 18k, which are p - 1 for the three primes. The primes are different, so n is squarefree and composite, and Theorem 1 says n is a Carmichael number. \square

For k = 1 this gives 7 \cdot 13 \cdot 19 = 1729, with 1728 = 36 \cdot 48.

Example 5

A leaked private exponent

Samir publishes the key (n, e) = (3071, 5). His private exponent d = 1181 leaks. Factor n.

Solution

By Theorem 7 with m = ed - 1 = 5904 = 2^4 \cdot 369, take t = 369 and try a = 2. As 369 = 256 + 64 + 32 + 16 + 1, repeated squaring (the squares 2^{2^k} for k = 4, \dots, 8 are 1045, 1820, 1862, 2956, 941 modulo 3071) gives 2^{369} \equiv 1659. Then

\begin{aligned} 1659^2 &\equiv 665, \\ 665^2 = 442{,}225 &= 144 \cdot 3071 + 1. \end{aligned}

So x = 665 has x^2 \equiv 1 and x \not\equiv \pm 1 \pmod{3071}. The Euclidean algorithm on 664 and 3071: 3071 = 4 \cdot 664 + 415, 664 = 415 + 249, 415 = 249 + 166, 249 = 166 + 83, 166 = 2 \cdot 83. So \gcd(664, 3071) = 83, and 3071 = 37 \cdot 83.

Example 6

Three keys, one message

Amara sends the same lot number m to three offices whose keys (55, 3), (391, 3) and (1189, 3) all use e = 3. An eavesdropper sees c_1 = 3, c_2 = 189 and c_3 = 370. Find m.

Solution

The three moduli are pairwise coprime (each gcd is 1), and m is below each, so by Theorem 8 it is enough to solve the three congruences. First x = 3 + 55k with 55k \equiv 186 \pmod{391}. From 391 = 7 \cdot 55 + 6 and 55 = 9 \cdot 6 + 1, 1 = 64 \cdot 55 - 9 \cdot 391, so k \equiv 186 \cdot 64 \equiv 174 and

x \equiv 3 + 55 \cdot 174 = 9573 \pmod{21{,}505}.

Next x = 9573 + 21{,}505j \equiv 370 \pmod{1189}. Reducing, 61 + 103j \equiv 370, so 103j \equiv 309 = 3 \cdot 103, and j \equiv 3, as 103 is prime and does not divide 1189. So C = 9573 + 3 \cdot 21{,}505 = 74{,}088 = 42^3, and the lot number is m = 42, found without factoring any modulus.

Boundaries

  • A pass is not a proof. The composite 2047 passes to base 2 (Exercise 5). Theorem 6 bounds the chance that a fixed composite passes k random bases; the chance that a number which passed is composite also depends on how the candidates were chosen.
  • Determinism costs more. The bases 2, 3, 5, 7 together expose every odd composite below 3{,}215{,}031{,}751, which itself passes all four. In 2002 Agrawal, Kayal and Saxena gave a test that decides primality in time polynomial in the number of digits, with no random choices; both facts are stated here without proof.
  • A witness need not name a factor. Example 2 found one because the sequence reached 1 through a square root of 1 other than \pm 1. A Fermat witness, whose sequence never reaches 1, gives no factor this way.
  • The attacks need carelessness. Theorem 8 needs the same unpadded m under e moduli, and random padding defeats it; Theorem 7 needs d. No fast way to factor n from (n, e) alone is known.

Where this goes next

Euler’s criterion in Quadratic residues and the Legendre symbol sharpens a^{(p-1)/2} \equiv \pm 1 to the Legendre symbol, and comparing the two for a composite n, with the Jacobi symbol of Quadratic reciprocity, gives the Solovay-Strassen test. On the factoring side, Pollard’s p - 1 method factors n quickly when p - 1 has only small prime factors, so such a prime makes a weak key.

Exercises

Carmichael numbers and the Fermat test

  1. Given 4371 = 3 \cdot 31 \cdot 47, 8911 = 7 \cdot 19 \cdot 67 and 10{,}585 = 5 \cdot 29 \cdot 73, decide which are Carmichael numbers.
  2. Show that 5 is a Fermat witness for 4371 by working modulo 31.
  3. Find the least k \ge 2 for which the construction of Example 4 gives a Carmichael number, and find that number.

The Miller-Rabin test

  1. Run the Miller-Rabin sequence for the prime 113 with bases 2 and 3.
  2. Show that the composite 2047 = 23 \cdot 89 passes the Miller-Rabin test to base 2.
  3. Run the Miller-Rabin test on the Carmichael number 1729 with base 2, and use the result to find a factor of 1729.
  4. Count the Fermat liars and the strong liars for 91 = 7 \cdot 13, and compare with Theorems 3 and 6.
  5. How many random bases make the bound 4^{-k} of Theorem 6 smaller than 10^{-30}?

Attacks on RSA keys

  1. A key (2419, 3) has private exponent d = 1547. Given 2^{145} \equiv 2123 \pmod{2419}, factor 2419.
  2. Two branch offices share the modulus n = 667 with exponents 3 and 5, and the same m is sent to both as c_1 = 167 and c_2 = 499. Find m without factoring n.

Proofs

  1. Let n be odd. Prove that if a is a strong liar for n, so is n - a.
  2. Let n be a Carmichael number and p a prime factor of n. Prove that n \equiv p \pmod{p(p-1)}.
  3. With n and p as in Exercise 12, prove that \displaystyle p < \sqrt{n}.
  4. Let p \ne q be odd primes. Prove that x^2 \equiv 1 \pmod{pq} has exactly four solutions modulo pq, and that for each solution x \not\equiv \pm 1, \gcd(x - 1, pq) is p or q.
  5. Let \gcd(e_1, e_2) = 1, c_i = m^{e_i} \bmod n and \gcd(c_2, n) = 1. Prove that m can be computed from n, e_1, e_2, c_1, c_2 alone.
  6. A key holder learns that d has leaked and proposes to keep n and choose a new e. Explain why this is not safe.
Answers
  1. 8911 and 10{,}585 are; 4371 is not. 8910 = 6 \cdot 1485 = 18 \cdot 495 = 66 \cdot 135; 10{,}584 = 4 \cdot 2646 = 28 \cdot 378 = 72 \cdot 147; but 30 \nmid 4370, as 4370 is not a multiple of 3.
  2. \gcd(5, 4371) = 1 and 5^3 = 125 \equiv 1 \pmod{31}. As 4370 = 3 \cdot 1456 + 2, 5^{4370} \equiv 25 \pmod{31}, so 5^{4370} \not\equiv 1 \pmod{4371}.
  3. k = 6, giving 37 \cdot 73 \cdot 109 = 294{,}409. For k = 2, 3, 4, 5 one of the three is composite: 25, 55, 25, 91 = 7 \cdot 13.
  4. 112 = 2^4 \cdot 7. Base 2: 2^7 = 128 \equiv 15, then 15^2 = 225 \equiv 112: passes at r = 1. Base 3: 3^7 = 2187 \equiv 40, then 40^2 \equiv 18, 18^2 \equiv 98, 98^2 \equiv 112: passes at r = 3. In both, the first 1 comes straight after 112, as Theorem 5 requires.
  5. 2046 = 2 \cdot 1023 and 2^{11} = 2048 \equiv 1 \pmod{2047}. As 1023 = 11 \cdot 93, x_0 = 2^{1023} \equiv 1, so 2047 passes.
  6. 1728 = 2^6 \cdot 27. 2^{11} = 2048 \equiv 319, 319^2 \equiv 1479, and 2^{27} \equiv 1479 \cdot 32 \equiv 645. Then 645^2 \equiv 1065 and 1065^2 \equiv 1. As 645 \ne 1 and 645, 1065 \ne 1728, base 2 is a strong witness; \gcd(1064, 1729) = 133 and 1729 = 13 \cdot 133.
  7. 36 Fermat liars and 18 strong liars, out of \varphi(91) = 72: exactly a half and exactly a quarter: both bounds are attained. Fermat: a^{90} \equiv 1 \pmod{7} always, and a^{90} \equiv a^6 \pmod{13} has 6 solutions. Strong: 90 = 2 \cdot 45, so liars have a^{45} \equiv \pm 1. With a \equiv g^i for a primitive root g (modulo 7, then modulo 13), a^{45} \equiv a^3 \pmod{7} is 1 for even i and -1 for odd i, 3 each; a^{45} \equiv a^9 \pmod{13} is 1 when 4 \mid i and -1 when i \equiv 2 \pmod{4}, 3 each. So 9 + 9 = 18.
  8. 50. 4^{-k} < 10^{-30} means k > 30/\log_{10} 4 \approx 49.8; 4^{-50} = 2^{-100} \approx 7.9 \cdot 10^{-31}.
  9. 2419 = 41 \cdot 59. ed - 1 = 4640 = 2^5 \cdot 145. 2123^2 \equiv 532 and 532^2 \equiv 1, with 532 \ne \pm 1, so \gcd(531, 2419) = 59.
  10. m = 100. 2 \cdot 3 - 1 \cdot 5 = 1, so m \equiv c_1^2 \cdot c_2^{-1}. 167^2 \equiv 542, the Euclidean algorithm gives 499^{-1} \equiv 266 \pmod{667}, and 542 \cdot 266 \equiv 100. Check: 100^3 \bmod 667 = 167.
  11. Proof. n - a \equiv -a, and t is odd, so (n - a)^t \equiv -a^t. If a^t \equiv 1, then (n - a)^t \equiv -1; if a^t \equiv -1, then (n - a)^t \equiv 1. If a^{2^r t} \equiv -1 with 1 \le r < s, the exponent is even and (n - a)^{2^r t} \equiv a^{2^r t} \equiv -1. \square
  12. Proof. By Theorem 1, p - 1 \mid n - 1, so n \equiv 1 \equiv p \pmod{p - 1}; and n \equiv 0 \equiv p \pmod{p}. As \gcd(p, p - 1) = 1, p(p - 1) \mid n - p. \square
  13. Proof. By Exercise 12, p - 1 \mid n - p = p(n/p - 1), and \gcd(p - 1, p) = 1, so p - 1 \mid n/p - 1 by the coprime factor lemma. By Corollary 2, n/p > 1, so n/p - 1 \ge p - 1 and n/p \ge p. Equality would give n = p^2, not squarefree. So p^2 < n. \square
  14. Proof. x^2 \equiv 1 \pmod{pq} if and only if it holds modulo p and modulo q, that is, by Lemma 4(a), x \equiv \pm 1 \pmod{p} and x \equiv \pm 1 \pmod{q}. By the The Chinese remainder theorem each of the four sign pairs is one class modulo pq, and the pairs differ since 1 \not\equiv -1 modulo an odd prime. The two classes other than \pm 1 are (1, -1) and (-1, 1). For (1, -1), p \mid x - 1 and q \nmid x - 1 (else q \mid 2), so \gcd(x - 1, pq) = p; likewise (-1, 1) gives q. \square
  15. Proof. A prime dividing m and n would divide c_2, so \gcd(m, n) = 1 and inverses modulo n of m and c_2 exist (Modular inverses and linear congruences). The extended Euclidean algorithm gives integers x, y with e_1 x + e_2 y = 1; they are not both negative. If x, y \ge 0, then c_1^x c_2^y \equiv m^{e_1 x + e_2 y} = m directly. If y < 0, then c_1^x \cdot (c_2^{-1})^{-y} \equiv m^{e_1 x} \cdot m^{e_2 y} = m^{e_1 x + e_2 y} = m, the negative power meaning a power of the inverse. If x < 0 instead, the same works with \gcd(c_1, n) = 1, which follows from \gcd(m, n) = 1. \square
  16. By Theorem 7, anyone holding n, e and d factors n, each random base succeeding with probability at least \displaystyle \frac{1}{2}. Then \varphi(n), and the private exponent for any new e, follow at once (RSA public-key encryption, Example 1). New primes are needed.
math.wiki · updated 2026-11-18 · CC-BY-SA-4.0