Three applications of Euler’s theorem
Fermat's little theorem says that if p is a prime and a is not a multiple of p, then
ap-1 = 1 (mod p).
Euler's generalization of Fermat's little theorem says that if a is relatively prime to m, then
aI(m) = 1 (mod m)
where I(m) is Euler's so-called totient function. This function counts the number of positive integers less than m and relatively prime to m. For a prime number p, I(p) = p-1, and to Euler's theorem generalizes Fermat's theorem.
Euler's totient function is multiplicative, that is, if a and b are relatively prime, then I(ab) = I(a) I(b). We will need this fact below.
This post looks at three applications of Fermat's little theorem and Euler's generalization:
- Primality testing
- Party tricks
- RSA public key encryption
The contrapositive of Fermat's little theorem is useful in primality testing: if the congruence
ap-1 = 1 (mod p)
does not hold, then either p is not prime or a is a multiple of p. In practice, a is much smaller than p, and so one can conclude that p is not prime.
Technically this is a test for non-primality: it can only prove that a number is not prime. For example, if 2p-1 is not congruent to 1 (mod p) then we know p is not a prime. But if 2p-1is congruent to 1 (mod p) then all we know is that we haven't failed the test; it's still conceivable that p is prime. So we try another value of a, say 3, and see whether 3p-1 is congruent to 1 (mod p).
If we haven't disproved that p is prime after several attempts, we have reason to believe p is probably prime.[1]. There are pseudoprimes, a.k.a. Carmichael numbers that are not prime but pass the primality test above for all values of a. But these numbers are much less common than primes.
By the way, if p is a huge number, say with hundreds or thousands of digits, doesn't it seem odd that we would want to compute numbers to the power p? Actually computing ap would be impossible. But because we're computing mod p, this is actually easy. We can apply the fast exponentiation algorithm and take remainders by p at every step, so we're never working with numbers more than twice as long as p.
Fifth root party trickA few days ago I wrote about the fifth root party trick. If someone raises a two-digit number to the fifth power, you can quickly tell what the number was. Part of what makes the trick work is that in base 10, any number n and its fifth power end in the same digit. You can prove this by trying all 10 possible last digits, but if you want to generalize the trick to other bases, it helps to use Euler's theorem. For example, you could use 9th powers in base 15.
Euler's theorem shows why raising a to the power I(m) + 1 in base m keeps the last digit the same, but only if a is relatively prime to m. To extend the fifth root trick to other bases you'll have a little more work to do.
RSA encryptionThe original [2] RSA public key cryptography algorithm was a clever use of Euler's theorem.
Search for two enormous prime numbers p and q [3]. Keep p and q private, but make n = pq public. Pick a private key d and solve for a public key e such that de = 1 (mod I(n)).
Since you know p and q, you can compute I(n) = (p - 1)(q - 1), and so you can compute the public key e. But someone who doesn't know p and q, but only their product n, will have a hard time solving for d from knowing e. Or at least that's the hope! Being able to factor n is sufficient to break the encryption scheme, but it's not logically necessary. Maybe recovering private keys is much easier than factoring, though that doesn't seem to be the case.
So where does Euler come in? Someone who has your public key e and wants to send you a message m computes
me (mod n)
and sends you the result [4]. Now, because you know d, you can take the encrypted message me and compute
(me)d = mI(n) = 1 (mod n)
by Euler's theorem.
This is the basic idea of RSA encryption, but there are many practical details to implement the RSA algorithm well. For example, you don't want p and q to be primes that make pq easier than usual to factor, so you want to use safe primes.
Related posts[1] Saying that a number is "probably prime" makes sense the first time you see it. But then after a while it might bother you. This post examines and resolves the difficulties in saying that a number is "probably prime."
[2] The original RSA paper used Euler's totient function I(n) = (p - 1)(q - 1), but current implementations use Carmichael's totient function I(n) = lcm(p - 1, q - 1). Yes, same Carmichael as Carmichael numbers mentioned above, Robert Daniel Carmichael (1879-1967).
[3] How long does it take to find big primes? See here. One of the steps in the process it to weed out composite numbers that fail the primality test above based on Fermat's little theorem.
[4] This assumes the message has been broken down into segments shorter than n. In practice, RSA encryption is used to send keys for non-public key (symmetric) encryption methods because these methods are more computationally efficient.