We will look at the setting where Alice has some message that she wants to send to Bob. She encodes this message using the public key that Bob publishes, which will be a pair of numbers . Bob uses a secret, private key to decrypt incoming messages. This way, even if an eavesdropper gets the encrypted message, she can’t decipher the message provided that the encryption is secure.
1) Choose two random -bit primes and for .
Choose a random -bit . Check if it’s prime (we’ll see how to do this in a moment). The probability that it will be prime is .
2) Find which is relatively prime to
(i.e., find where gcd() = 1).
4) Publish public key
5) Bob’s private key is , which we find using the extended Euclid algorithm.
Alice (wants to send a message to Bob):
1) Looks up Bob’s public key:
2) Computes using the fast modular exponentiation algorithm.
3) Sends to Bob.
1) Gets .
2) Computes .
Note: . Therefore, we know that for some integer .
Then by Euler’s theorem when .
If gcd(, then the statement is still true () but to prove it we need to use the Chinese remainder theorem so we’ll skip that here.
Assumption: Given , where , it is computationally difficult to determine . The natural way would be to factor , but there is no known polynomial time algorithm for factoring.
If the message corresponds to a small number where , then doesn’t do anything so to decrypt the message one just computes which is easy if is small. To avoid this issue, Alice can choose a random string and pad the message. Alice sends two messages: and , and Bob can decrypt both and use to get .
We also need that , but we can break a large message into smaller messages and encode each smaller message separately.
How do we test whether or not some number is prime?
If is prime, then .
If is composite, then where . Such an will be a witness (or certificate) that is not prime. Our goal will be to find such an , if it exists. We call a Fermat witness (FW).
To see why a composite always has such an , consider some composite and some such that . (Note, is composite so has at least one factor and this factor has .) Then and are multiples of , say for integers . Hence, for some integer . Therefore, is also a multiple of , so .
This was a trivial Fermat witness because from the gcd statement, we see that divides already.
We are looking for nontrivial format witnesses (NFWs). We are looking for an where and .
Not every composite will have a NFW. The Carmichael numbers are composite ‘s with no NFWs. Carmichael numbers are rare, the smallest one is 561. We will ignore these “pseudo-primes” for the moment and deal with them later. It turns out for non-Carmichael composite numbers there are a lot of Fermat witnesses. By definition, non-Carmichael composite numbers have at least one NFW, and from that we can prove the following lemma saying that there are a lot of Fermat witnesses.
Lemma: If there exists NFW for , then of the are Fermat witnesses.
Let be a NFW such that and . We will prove the lemma by breaking up into and , where all satisfy and all satisfy . (So are Fermat witnesses and is the “bad” set of non-witnesses.) Then the lemma is equivalent to saying that . To prove this, we will map elements in to elements in such that every element of is mapped to a unique element of , and hence has at least as many elements as , which proves the lemma.
The mapping that we use for any is . Then , so .
Suppose two ‘s map to the same . Then . Since is a NFW so which means exists, so we get .
That proves the theorem. Now (ignoring Carmichael numbers) we have an algorithm to test primality. Choose a random from , and compute to see if this is a Fermat witness or not. This will work with probability because of the lemma. To boost the probability we instead choose numbers from and test to see if any of these numbers are Fermat witnesses. Here is the algorithm in detail:
Primality testing algorithm:
Choose randomly from .
If , , output “ is a prime number”
If such that , then output “ is composite ”.
If is prime, then Pr[algorithm says is prime] = 1. If is composite and not Carmichael, then Pr[algorithm is wrong] .
Dealing with Carmichael numbers
Recall that we put off Carmichael numbers from earlier. Carmichael numbers are composite but have no NFW. For example, 561 is a Carmichael number.
For if , then is a square root of . and are always square roots of . Any other square root is a nontrivial square root of .
If is prime, then there are no nontrivial square roots of .
Take where . Then . Then . Note that . Then or . Then or . Thus, is a trivial square root of .
Thus, to prove some number is not prime, it suffices to find a nontrivial square root of .
Suppose is composite and odd (if is even, then things are easy). Then is even, so , where is odd (we take out as many factors of 2 as possible). We will use Fermat’s test, which checks if for a random . First, we compute by repeated squares:
If , then we know that is composite by Fermat’s little theorem. Suppose . Then go back to the first point where . We know that is a square root of . If this is non-trivial, then we have proved that is composite.
Fact: At least of the choices for in lead to a nontrivial square root in this manner.
This algorithm works for all composite numbers (including Carmichael numbers).
This leads us to a new algorithm that works for any composite number. We run our algorithm as before and find the first where , but which is a square root of . If it is , output “prime”. Else, output “not prime”.