RA: Primality Testing

PDF of Eric’s handwritten notes is here.

RSA Protocol

We will look at the setting where Alice has some message m 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 (N,e). 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 n-bit primes p and q for n \approx 2000.
Choose a random n-bit r. Check if it’s prime (we’ll see how to do this in a moment). The probability that it will be prime is \approx 1/n.
2) Find e which is relatively prime to (p-1)(q-1)
(i.e., find e where gcd(e, (p-1)(q-1)) = 1).
3) Let N = pq
4) Publish public key (N,e)
5) Bob’s private key is d = e^{-1} \mod (p-1)(q-1), which we find using the extended Euclid algorithm.
Alice (wants to send a message m to Bob):
1) Looks up Bob’s public key: (N,e)
2) Computes y \equiv m^e \mod N using the fast modular exponentiation algorithm.
3) Sends y to Bob.
1) Gets y.
2) Computes y^d \mod N.

Note:  de \equiv 1 \mod (p-1)(q-1).  Therefore, we know that de = 1+k(p-1)(q-1) for some integer k.
Then y^d \equiv (m^e)^d \equiv m^{de} \equiv m\times (m^{(p-1)(q-1)})^{k} \equiv m \mod N by Euler’s theorem when gcd(m,N)=1.
If gcd(m,N) >1 , then the statement is still true (y^d \equiv m \mod N) but to prove it we need to use the Chinese remainder theorem so we’ll skip that here.
Assumption: Given N,e,y, where y\equiv m^e, it is computationally difficult to determine m. The natural way would be to factor N, but there is no known polynomial time algorithm for factoring.

Other issues

If the message corresponds to a small number where m^e < N, then mod N doesn’t do anything so to decrypt the message one just computes m^{1/e} which is easy if e is small.  To avoid this issue, Alice can choose a random string r and pad the message. Alice sends two messages: (m+r)^e and r^e, and Bob can decrypt both and use r to get m.

We also need that m < N, but we can break a large message into smaller messages and encode each smaller message separately.

Primality testing

How do we test whether or not some number x is prime?
If x is prime, then \forall a\in \{1,...,x-1\}, a^{x-1} \equiv 1 \mod x.
If x is composite, then \exists a where a^{x-1}\not \equiv 1\mod x. Such an a will be a witness (or certificate) that x is not prime. Our goal will be to find such an a, if it exists. We call a a Fermat witness (FW).

To see why a composite x always has such an a, consider some composite x and some a such that gcd(a,x) = d>1. (Note, x is composite so x has at least one factor a and this factor a has gcd(a,x)>1.)  Then a^{x-1} and x are multiples of d, say a^{x-1}=di, x=dj for integers i,j.  Hence, a^{x-1} \mod x = a^{x-1} - kx = d(i-kj) for some integer k.  Therefore,   a^{x-1} \mod x is also a multiple of d>1, so a^{x-1} \mod x \neq 1.

This was a trivial Fermat witness because from the gcd statement, we see that d divides x already.

We are looking for nontrivial format witnesses (NFWs). We are looking for an a where gcd(a,x) = 1 and a^{x-1} \not \equiv 1 \mod x.

Not every composite x will have a NFW. The Carmichael numbers are composite x‘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 \ge 1 NFW for x, then \ge 1/2 of the a\in \{1,2,...,x-1\} are Fermat witnesses.


Let a be a NFW such that gcd(a,x) = 1 and a^{x-1} \not \equiv \mod x. We will prove the lemma by breaking up \{1,...,x-1\} into W and B, where all w\in W satisfy a^{x-1} \not\equiv 1 \mod x and all b\in B satisfy b^{x-1} \equiv 1 \mod x. (So W are Fermat witnesses and B is the “bad” set of non-witnesses.)  Then the lemma is equivalent to saying that |W| \ge |B|. To prove this, we will map elements in B to elements in W such that every element of B is mapped to a unique element of W, and hence W has at least as many elements as B, which proves the lemma.

The mapping that we use for any b\in B is f(b) = ab \mod x. Then (ab)^{x-1} \equiv a^{x-1}b^{x-1} \equiv a^{x-1} \not \equiv 1 \mod x, so f(b)\in W.

Suppose two b‘s map to the same w \in W. Then b'a \equiv ba \mod x. Since a is a NFW so gcd(a,N)=1 which means a^{-1} \mod x exists, so we get b' \equiv b\mod x.  \square

That proves the theorem.  Now (ignoring Carmichael numbers) we have an algorithm to test primality.  Choose a random a from  \left\{1,2,\dots,x-1\right\}, and compute a^{x-1} \mod x to see if this a is a Fermat witness or not.  This will work with probability \geq 1/2 because of the lemma.  To boost the probability we instead choose k numbers from   \{1,2,\dots,x-1\} and test to see if any of these k numbers are Fermat witnesses.  Here is the algorithm in detail:

Primality testing algorithm:

Input: x
Choose a_1,...,a_k randomly from \{1,...,x-1\}.

For i=1 \rightarrow k:

Compute a_i^{x-1} \mod x

If \forall i, a_i^{k-1} \equiv 1 \mod x, output “x is a prime number”
If \exists i such that a_i^{x-1} \not\equiv 1 \mod x, then output “x is composite ”.

If x is prime, then Pr[algorithm says x is prime] = 1. If x is composite and not Carmichael, then Pr[algorithm is wrong] \le (\frac{1}{2})^k.

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 x,N if x^2 \equiv 1 \mod N, then x is a square root of  1 \mod N.
Note, x \equiv 1 \mod N and x \equiv -1 \equiv N-1 \mod N are always square roots of 1 \mod N. Any other square root is a nontrivial square root of 1 \mod N.

If x is prime, then there are no nontrivial square roots of 1 \mod x.


Take z where z^2 \equiv 1 \mod x. Then z^2 -1 \equiv 0 \mod x. Then z^2 -1 = kx. Note that z^2 = (z-1)(z+1). Then z-1 \equiv 0 \mod x or z+1 \equiv 0 \mod x. Then z \equiv 1\mod x or z \equiv -1 \mod x. Thus, z is a trivial square root of 1 \mod x.

Thus, to prove some number N is not prime, it suffices to find a nontrivial square root of 1 \mod x.

Suppose N is composite and odd (if N is even, then things are easy). Then N-1 is even, so N-1 = 2^t v, where v is odd (we take out as many factors of 2 as possible). We will use Fermat’s test, which checks if a^{N-1} \equiv 1 \mod N for a random a\in \{1,...,N-1\}. First, we compute a^{N-1} \mod N by repeated squares:

a^{v} \mod N
then  a^{2v} \mod N
a^{2^2v} \mod N

a^{2^tv} \mod N

If a^{n-1} \not \equiv 1 \mod N, then we know that N is composite by Fermat’s little theorem. Suppose a^{n-1} \equiv 1 \mod N. Then go back to the first point where a^{2^i v} \equiv 1 \mod N. We know that a^{2^{i-1} v} \mod N is a square root of 1\mod N. If this is non-trivial, then we have proved that N is composite.

Fact: At least 3/4 of the choices for a in \{1,...,x-1\} 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 i where a^{2^i v}\not\equiv 1 \mod N, but which is a square root of 1\mod N. If it is -1, output “prime”. Else, output “not prime”.