Fermat, Euler and the Totient Function

The run

# Fermat, Euler, and the totient function.

def totient(n):
    """Euler's totient by trial division: how many of 1 to n are coprime to n."""
    result, m, p = n, n, 2
    while p * p <= m:
        if m % p == 0:
            while m % p == 0:
                m //= p
            result -= result // p
        p += 1
    if m > 1:
        result -= result // m
    return result

def coprime_to(n):
    from math import gcd
    return [a for a in range(1, n) if gcd(a, n) == 1]

print("the totient function counted directly, and by the formula:")
for n in (7, 10, 11, 12, 21, 26, 35, 187):
    direct = len(coprime_to(n)) if n < 200 else None
    print("   phi(%3d) = %3d   by formula %3d   agree: %s"
          % (n, direct, totient(n), direct == totient(n)))
print()

print("for a prime p, phi(p) = p - 1; the numbers coprime to 11 are")
print("  ", coprime_to(11))
print("for a product of two distinct primes, phi(pq) = (p-1)(q-1):")
for p, q in ((3, 7), (11, 17), (7, 11)):
    print("   phi(%d * %d) = phi(%d) = %d, and (%d-1)(%d-1) = %d"
          % (p, q, p * q, totient(p * q), p, q, (p - 1) * (q - 1)))
print()

print("Fermat's little theorem: for p prime and a not divisible by p,")
print("a to the power (p - 1) is congruent to 1 modulo p.")
for a, p in ((2, 7), (3, 11), (5, 13), (10, 17)):
    print("   %2d to the power %2d mod %2d = %d" % (a, p - 1, p, pow(a, p - 1, p)))
print()

print("Euler's theorem generalises it to any modulus:")
print("a to the power phi(n) is congruent to 1 modulo n, whenever gcd(a, n) = 1.")
for a, n in ((3, 10), (2, 11), (7, 187), (5, 26)):
    print("   %d to the power phi(%3d) = %d to the power %3d mod %3d = %d"
          % (a, n, a, totient(n), n, pow(a, totient(n), n)))
print()

print("and what the theorems do NOT say. 561 passes Fermat's test for base 2:")
print("   2 to the power 560 mod 561 =", pow(2, 560, 561))
print("   but 561 =", " * ".join(str(f) for f in (3, 11, 17)), "and so is composite.")
print("   A number that passes for every base coprime to it is a CARMICHAEL")
print("   number. The first four are 561, 1105, 1729 and 2465.")
from math import gcd
for n in (561, 1105, 1729, 2465):
    bad = [a for a in range(2, n) if gcd(a, n) == 1 and pow(a, n - 1, n) != 1]
    print("   %4d: bases coprime to it that FAIL Fermat's test: %d" % (n, len(bad)))
print()
print("so Fermat's test can prove a number COMPOSITE and can never prove one PRIME.")

the totient function counted directly, and by the formula:
   phi(  7) =   6   by formula   6   agree: True
   phi( 10) =   4   by formula   4   agree: True
   phi( 11) =  10   by formula  10   agree: True
   phi( 12) =   4   by formula   4   agree: True
   phi( 21) =  12   by formula  12   agree: True
   phi( 26) =  12   by formula  12   agree: True
   phi( 35) =  24   by formula  24   agree: True
   phi(187) = 160   by formula 160   agree: True

for a prime p, phi(p) = p - 1; the numbers coprime to 11 are
   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for a product of two distinct primes, phi(pq) = (p-1)(q-1):
   phi(3 * 7) = phi(21) = 12, and (3-1)(7-1) = 12
   phi(11 * 17) = phi(187) = 160, and (11-1)(17-1) = 160
   phi(7 * 11) = phi(77) = 60, and (7-1)(11-1) = 60

Fermat's little theorem: for p prime and a not divisible by p,
a to the power (p - 1) is congruent to 1 modulo p.
    2 to the power  6 mod  7 = 1
    3 to the power 10 mod 11 = 1
    5 to the power 12 mod 13 = 1
   10 to the power 16 mod 17 = 1

Euler's theorem generalises it to any modulus:
a to the power phi(n) is congruent to 1 modulo n, whenever gcd(a, n) = 1.
   3 to the power phi( 10) = 3 to the power   4 mod  10 = 1
   2 to the power phi( 11) = 2 to the power  10 mod  11 = 1
   7 to the power phi(187) = 7 to the power 160 mod 187 = 1
   5 to the power phi( 26) = 5 to the power  12 mod  26 = 1

and what the theorems do NOT say. 561 passes Fermat's test for base 2:
   2 to the power 560 mod 561 = 1
   but 561 = 3 * 11 * 17 and so is composite.
   A number that passes for every base coprime to it is a CARMICHAEL
   number. The first four are 561, 1105, 1729 and 2465.
    561: bases coprime to it that FAIL Fermat's test: 0
   1105: bases coprime to it that FAIL Fermat's test: 0
   1729: bases coprime to it that FAIL Fermat's test: 0
   2465: bases coprime to it that FAIL Fermat's test: 0

so Fermat's test can prove a number COMPOSITE and can never prove one PRIME.

Read five things out of that run.

The formula and the count agree for every value tested. phi(187) is 160 both ways, phi(35) is 24, phi(26) is 12. The formula is not being taken on trust.

phi(11 17) is 160, which is 10 16. That is the number the RSA chapter will use, and e of 7 with d of 23 came out of the previous chapter's extended Euclid on exactly 160.

Fermat's theorem holds on every instance shown, and Euler's holds on every instance including 7 to the power 160 modulo 187, which is 1.

561 passes Fermat's test for base 2 and is 3 times 11 times 17. So a number can satisfy a to the power n - 1 congruent to 1 modulo n without being prime. Such a number is a pseudoprime to that base.

And the exhaustive check is the important line. For each of 561, 1105, 1729 and 2465, the program counted the bases coprime to n that fail Fermat's test, and the count was 0 in every case. These are Carmichael numbers: composite numbers that pass Fermat's test for every base coprime to them. So no amount of trying more bases will detect them, and Fermat's test can prove a number composite but can never prove one prime. That is why the next chapter is about Miller and Rabin.

The proof of RSA, written out

Because it is set, and because it is short.

Given. n is pq with p and q distinct primes. e and d satisfy e d congruent to 1 modulo phi(n). The message M satisfies 0 <= M < n.

Step 1. Since e d is congruent to 1 modulo phi(n), there is a whole number k with e d = 1 + k phi(n).

Step 2. Decrypting the encryption computes (M to the power e) to the power d, which is M to the power e d, which is M to the power 1 + k phi(n).

Step 3. That equals M times (M to the power phi(n)) to the power k.

Step 4. If gcd(M, n) is 1, Euler's theorem says M to the power phi(n) is congruent to 1 modulo n, so the whole expression is congruent to M times 1 to the power k, which is M. Since M is less than n, the congruence pins it exactly.

Step 5, the case the textbooks skip. What if gcd(M, n) is not 1, so that M is a multiple of p or of q? The theorem as stated does not apply. It still works, and the reason is the Chinese Remainder Theorem: the congruence holds separately modulo p and modulo q (by Fermat's little theorem in each), and a number determined modulo p and modulo q is determined modulo pq. So RSA decrypts correctly for every message, not only for those coprime to n. A complete answer mentions this; most do not.

Distinctions that carry marks

What beginners get wrong here

Saying phi(n) is n - 1 for composite n. It is n - 1 only for a prime. For n equal to pq it is (p - 1)(q - 1), which is much smaller.

Computing phi of a prime power wrongly. phi(p to the power k) is p to the power k minus p to the power k - 1, not p - 1. So phi(9) is 6, not 2.

Thinking Fermat's test proves primality. It cannot, and the Carmichael numbers are why: 561, 1105, 1729 and 2465 pass for every base coprime to them, and the program checked every one.

Stopping the RSA proof at the coprime case. It holds for all messages, by the Chinese Remainder Theorem, and saying so is worth a mark.

Confusing which of n and phi(n) is public. n is published; phi(n) is as secret as the primes, because it is equivalent to them.

Quick revision

• phi(n) counts the integers below n coprime to it. phi(p) = p - 1; phi(pq) = (p - 1)(q - 1); phi(p to the power k) = p to the power k minus p to the power k - 1.
• Verified: phi(187) = 160, phi(35) = 24, phi(26) = 12, both by counting and by formula.
• Fermat: p prime, a not divisible by p, then a to the power p - 1 is 1 mod p.
• Euler: gcd(a, n) = 1, then a to the power phi(n) is 1 mod n. Fermat is the case n = p.
• RSA's proof: e d = 1 + k phi(n), so M to the power e d is M times (M to the power phi(n)) to the power k, which is M. It also holds when gcd(M, n) is not 1, by the Chinese Remainder Theorem.
• Fermat's test cannot prove primality. The Carmichael numbers 561, 1105, 1729 and 2465 pass for every base coprime to them, and the program counted the failures at 0.
• The trapdoor: n is computable by anybody, phi(n) only by somebody who knows p and q.

Test yourself

1. Define Euler's totient function and give its value for a prime and for a product of two primes. phi(n) is the number of positive integers less than n that are relatively prime to n. For a prime p it is p - 1, because every smaller positive integer is coprime to p. For a product of two distinct primes it is (p - 1)(q - 1).

2. State Fermat's little theorem and Euler's theorem, and give the relationship between them. Fermat: if p is prime and a is not divisible by p, then a to the power p - 1 is congruent to 1 modulo p. Euler: if gcd(a, n) is 1 then a to the power phi(n) is congruent to 1 modulo n. Fermat's theorem is the special case of Euler's with n prime, since phi(p) is p - 1.

3. Compute phi(35), phi(9) and phi(187). phi(35) is phi(5 7), which is 4 times 6, that is 24. phi(9) is phi(3 to the power 2), which is 9 minus 3, that is 6. phi(187) is phi(11 17), which is 10 times 16, that is 160.

4. Prove that RSA decryption recovers the plaintext. Since e d is congruent to 1 modulo phi(n) there is a whole number k with e d = 1 + k phi(n). Then (M to the power e) to the power d is M to the power 1 + k phi(n), which is M times (M to the power phi(n)) to the power k. By Euler's theorem the bracket is congruent to 1 modulo n when gcd(M, n) is 1, so the result is congruent to M, and since M is less than n it equals M. When gcd(M, n) is not 1 the result still holds, because the congruence is valid separately modulo p and modulo q by Fermat's little theorem, and the Chinese Remainder Theorem then fixes it modulo pq.

5. What is a Carmichael number, and what does its existence prove? A composite number that passes Fermat's test for every base coprime to it; the smallest are 561, 1105, 1729 and 2465. Its existence proves that Fermat's test can never establish primality, however many bases are tried, because for these numbers no coprime base fails. The chapter verifies this exhaustively: the count of failing coprime bases is zero for all four.

6. Why is phi(n) secret in RSA when n is public? Because computing phi(n) from n requires the factorisation of n. Anybody can publish n; only the holder of p and q can compute (p - 1)(q - 1) and hence obtain d as the inverse of e. Knowing phi(n) is equivalent to knowing the factors, so it is as secret as they are, and that asymmetry is the trapdoor the whole scheme rests on.

7. 341 passes Fermat's test for base 2. What does that tell you, and what would you do next? That 341 is a pseudoprime to base 2, so the test gives no information about its primality. The next step is to try another base: 341 is 11 times 31, and testing base 3 gives a value other than 1, which proves it composite. That works because 341 is not a Carmichael number; for a Carmichael number no base would help, which is the argument for Miller and Rabin.