Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 40 ยท Math Foundations

Euler's Theorem and the Chinese Remainder Theorem

Learn Euler's totient, Fermat's little theorem, the Chinese Remainder Theorem and why the discrete logarithm is hard, with live Python you can run and edit.

Two results from number theory sit underneath most public-key cryptography. Euler's theorem tells you what happens when you raise a number to a power modulo n: the powers eventually cycle back to 1, and the length of the cycle is controlled by a function called the totient. The Chinese Remainder Theorem (CRT) tells you that working modulo a product of numbers is the same as working modulo each factor separately. RSA decryption uses the first to work at all and the second to run about four times faster.

The lesson ends with the flip side: while computing g^x mod p is fast, finding x from the result, the discrete logarithm problem, is believed to be hard. That one-way behavior is what Diffie-Hellman and DSA rely on. You should already be comfortable with modular arithmetic, pow(a, b, m) and the extended Euclidean algorithm.

The totient function

Euler's totient phi(n) counts how many integers from 1 to n are coprime to n (share no factor with it other than 1). For a prime p, every number below it is coprime, so phi(p) = p - 1. For a product of two distinct primes, phi(p*q) = (p-1)(q-1). More generally, if you know the prime factorization, you can compute the totient quickly; if you do not, you have essentially no shortcut. That asymmetry is the heart of RSA.

Python Counting the totient

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The formula version takes a prime factor p of n at a time and multiplies by (1 - 1/p). It needs the factors, which is why it only helps when you already know them.

Euler's theorem and Fermat's little theorem

Euler's theorem states: if a and n are coprime, then

aphi(n) โ‰ก 1 (mod n)

When n is a prime p, phi(p) = p - 1, and the statement becomes Fermat's little theorem: a^(p-1) = 1 (mod p) for every a not divisible by p. You met it as a primality test in primes and primality testing.

A useful consequence is that exponents live modulo phi(n). Since a^phi(n) is 1, you can reduce the exponent by phi(n) without changing the answer. That also gives a second way to compute a modular inverse: a^(-1) = a^(phi(n)-1) mod n.

flowchart LR
    A["a = 3"] --> B["3^1 = 3"]
    B --> C["3^2 = 9"]
    C --> D["3^3 = 27 = 5"]
    D --> E["3^4 = 15 = 1"]
    E -->|"cycle repeats"| B

Powers of 3 modulo 11 return to 1 after a fixed number of steps, and that cycle length always divides phi(11) = 10.

Python Euler's theorem in action

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the last line. Every order divides phi(11) = 10, and the numbers of order 10 are called primitive roots or generators: their powers visit every nonzero residue. Diffie-Hellman needs such a base.

This is exactly why RSA works. Choose e and d with e*d = 1 (mod phi(n)). Then (m^e)^d = m^(e*d) = m^(1 + k*phi(n)), which is m * (m^phi(n))^k = m modulo n. Decryption undoes encryption because of Euler's theorem. The full construction is in RSA from scratch.

The Chinese Remainder Theorem

Suppose you know a number x only through its remainders: it leaves 2 when divided by 3, 3 when divided by 5 and 2 when divided by 7. The CRT says that when the moduli are pairwise coprime, there is exactly one solution modulo the product (here 105), and you can compute it.

Say n = m1 * m2 * .... For each i, let Mi = n / mi. Then Mi is coprime to mi, so it has an inverse yi modulo mi. The answer is the sum of ri * Mi * yi over all i, reduced mod n. Each term is 1 modulo its own modulus and 0 modulo all the others.

Python Solving simultaneous congruences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why RSA uses the CRT

An RSA private key holder knows the primes p and q. Instead of computing c^d mod n with a 2048-bit modulus, they compute c^d modulo p and modulo q separately (each about half the size), then combine the two answers with the CRT. Exponentiation cost grows roughly with the cube of the bit length, so two half-size operations are about four times cheaper than one full-size one.

Python CRT speedup for modular exponentiation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the exponent is reduced modulo p - 1 and q - 1: that is Fermat's little theorem at work. The combining step, called Garner's formula, is the CRT written with a single inverse.

The discrete logarithm problem

In a group of integers modulo a prime p, take a generator g. Computing y = g^x mod p is fast, thanks to square-and-multiply. The reverse, finding x given g, y and p, is the discrete logarithm. For small p you can just try every exponent. For a 2048-bit prime, the best known classical algorithms are far out of reach, and no efficient method is known.

Python Easy forward, hard backward

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Baby-step giant-step trades memory for time and finds the exponent in about sqrt(p) steps. That sounds fast until you remember that sqrt(p) for a 2048-bit prime is itself a 1024-bit number. More sophisticated attacks (index calculus) are faster, which is why discrete-log keys over plain integers are 2048 bits or more. Elliptic curve groups resist those faster attacks, so they get the same security with 256-bit keys. See Diffie-Hellman and elliptic curves.

Do not mix these problems up. RSA relies on the difficulty of factoring n (which would reveal phi(n)); Diffie-Hellman relies on the discrete logarithm. They are different problems, though a large quantum computer would break both (see post-quantum cryptography).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is phi(35)?

    35 = 5 * 7, so phi(35) = (5 - 1) * (7 - 1) = 4 * 6 = 24.
  2. 2. Euler's theorem says a^phi(n) = 1 (mod n). When does it apply?

    The condition is gcd(a, n) = 1. If a shares a factor with n, powers of a never reach 1 modulo n.
  3. 3. Why is RSA decryption faster when the CRT is used?

    The private-key holder knows p and q, so the exponentiation can be split into two much cheaper ones whose results are combined with the CRT.
  4. 4. Which statement about the discrete logarithm problem is correct?

    Modular exponentiation is fast, but inverting it has no known efficient algorithm on classical computers, which makes it a one-way function for Diffie-Hellman.

Summary

  • The totient phi(n) counts numbers coprime to n; phi(p) = p - 1 and phi(p*q) = (p-1)(q-1).
  • Euler's theorem: a^phi(n) = 1 (mod n) for coprime a and n; Fermat's little theorem is the prime case. Exponents can be reduced modulo phi(n).
  • The CRT reconstructs a number from its remainders modulo pairwise coprime moduli, and speeds up RSA private-key operations about fourfold.
  • The discrete logarithm is easy to compute forward and believed hard to reverse, which underpins Diffie-Hellman and DSA.

Next: Randomness, Entropy and Secure Randomness.