Primality Tests

Generating Primes by Sieving#

A huge amount of what we have built so far leans on primes: unique factorisation, the fact that $\mathbb{Z}_p$ is a field, Fermat's Little Theorem, and the guarantee that $\mathbb{Z}_p^*$ has a primitive element. All of the applications in this topic (RSA, Diffie–Hellman, and friends in Cryptosystems) need us to actually get hold of primes. So there are two practical questions to answer: how do we generate a list of all the primes up to some bound, and how do we decide whether one particular number is prime?

The oldest answer to the first question is over two thousand years old and still the one we use.

Algorithm 6.1 (Sieve of Eratosthenes, or sieving). To generate a list of prime numbers less than or equal to a given number $N$:

• Start with a list $L$ of all integers from $2$ up to $N$.
• The first entry $p_1$ in the list (namely $2$) is prime. Mark every $p_1$th entry after $p_1$ in $L$ as composite.
• The next entry in the list not marked as composite is prime. Label it $p_i$, and mark every $p_i$th entry after $p_i$ in $L$ as composite.
• Repeat the previous step until the next non-composite entry $p_k$ is greater than $\sqrt{N}$. Then every non-composite entry remaining in the list is prime.

Basically, you walk along the list; the first number you have not already crossed out must be prime, and once you know it is prime you get to delete all of its multiples for free. Nothing in the algorithm ever divides anything — marking "every $p_i$th entry" is just counting — which is exactly why sieving is so cheap compared to testing numbers one at a time.

Why does the first surviving entry have to be prime? Suppose $k$ is the first entry not yet marked as composite at some stage. Every prime smaller than $k$ has already had its turn, and each of those turns crossed out all of that prime's multiples; so $k$ is not a multiple of any prime less than $k$, and hence has no factorisation at all other than $1 \times k$. That is precisely what it means for $k$ to be prime.

The other question is why we are allowed to stop so early, at $\sqrt{N}$ rather than $N$.

Proof. Since $n$ is composite we may write $n = ab$ with $1 < a \leq b < n$. If we had $a > \sqrt{n}$, then $b \geq a > \sqrt{n}$ as well, and so

$$\begin{align*} n &= ab \\ &> \sqrt{n} \times \sqrt{n} \\ &= n, \end{align*}$$

which is absurd; hence $a \leq \sqrt{n}$. Now $a > 1$, so $a$ has some prime factor $p$, and $p \leq a \leq \sqrt{n}$ with $p \mid a \mid n$. $\blacksquare$

This one was Q7(a) of the Topic 1 tutorial, so it should look familiar. Its consequence for sieving is immediate: if a number $m \leq N$ survives every pass up to $\sqrt{N}$, then $m$ has no prime factor $\leq \sqrt{N} $, and if $m$ were composite the Fact would hand us one. So $m$ is prime, and there is no work left to do. Stopping early is only legal because the crossing-out is exhaustive; if you skip a prime pass below $\sqrt{N}$, composites survive.

It is worth noticing where each pass starts doing genuinely new work. In the pass for $p$, the multiples $2p, 3p, \dots, (p-1)p$ have all already been crossed out, because each of $2, 3, \dots, p-1$ has a prime factor smaller than $p$ whose pass has already run. So the first new entry killed in the $p$ pass is $p^2$, and once $p^2 > N$ the pass achieves nothing at all — which is the $\sqrt{N}$ cutoff again, seen from the other side.

Sieving Out the Primes Below 50#

Example. Find all primes less than $50$ using the sieving technique.
We start with $L = 2, 3, 4, \dots, 50$ and note that $\sqrt{50} \approx 7.07$, so the passes will stop as soon as the next surviving entry exceeds $7.07$.

Pass 1. The first entry is $p_1 = 2$, which is prime. Mark every second entry after it:

$$4,\ 6,\ 8,\ 10,\ 12,\ 14,\ 16,\ 18,\ 20,\ 22,\ 24,\ 26,\ 28,\ 30,\ 32,\ 34,\ 36,\ 38,\ 40,\ 42,\ 44,\ 46,\ 48,\ 50.$$

Pass 2. The next surviving entry is $p_2 = 3$, which is therefore prime. Mark every third entry after it, namely $6, 9, 12, \dots, 48$; of these, the ones not already crossed out are

$$9,\ 15,\ 21,\ 27,\ 33,\ 39,\ 45.$$

Pass 3. The next surviving entry is $p_3 = 5$, so $5$ is prime. Mark $10, 15, 20, \dots, 50$; the newly killed entries are

$$25,\ 35.$$

Pass 4. The next surviving entry is $p_4 = 7$, so $7$ is prime. Mark $14, 21, 28, 35, 42, 49$; the only new casualty is

$$49.$$

Stop. The next surviving entry is $11$, and $11 > \sqrt{50} \approx 7.07$, so the algorithm halts and everything still standing is prime. Laying the list out in rows of ten, with a dot for every entry that has been crossed out (or was never in the list), the survivors are:

Therefore, the primes less than $50$ are

$$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47,$$

fifteen of them in total. Notice how little work the later passes did: pass $3$ killed two numbers and pass $4$ killed exactly one, consistent with the observation that the $p$ pass only starts biting at $p^2$ ($25$ and $49$ respectively).

Testing One Number at a Time#

Sieving is the right tool when you want all the primes up to some bound, but it is wildly wasteful if you only care about one number; to decide whether $10^{18} + 9$ is prime you would rather not first write down every prime below $10^9$. Algorithms that decide whether or not a single number is prime are called primality tests.

Algorithm 6.2 (Basic primality test). To test whether a given positive integer $n$ is prime:

• Start with a list $L$ of integers (or of primes, obtained via sieving) from $2$ up to $\lfloor \sqrt{n} \rfloor$.
• For each number $a$ in $L$, find $\gcd(a,n)$, for instance via the Euclidean algorithm. If $\gcd(a,n) \neq 1$, we know $n$ is not prime and can terminate the algorithm.
• If the list has been exhausted and the algorithm has not terminated, we know $n$ is prime and can terminate the algorithm.

This is just trial division dressed up, and it is correct for exactly the reason the sieve stops at $\sqrt{N}$: if $n$ is composite it has a prime factor $p \leq \sqrt{n}$, and that $p$ is somewhere in $L$, where it will show up as $\gcd(p, n) = p \neq 1$. In some cases it is faster to run a divisibility test for $a$ than to grind through the Euclidean algorithm; if $a$ is one of $2, 3, 5, 7, 11, 13$ you should just use the digit tricks.

Example. Use the basic primality test on $n = 97$ and on $n = 91$.
For $n = 97$, we have $9^2 = 81 \leq 97 < 100 = 10^2$, so $\lfloor \sqrt{97} \rfloor = 9$ and $L = 2,3,4,5,6,7,8,9$. Running down the list,

$$\begin{align*} \gcd(2,97) &= 1, \quad \gcd(3,97) = 1, \quad \gcd(4,97) = 1, \quad \gcd(5,97) = 1, \\ \gcd(6,97) &= 1, \quad \gcd(7,97) = 1, \quad \gcd(8,97) = 1, \quad \gcd(9,97) = 1, \end{align*}$$

so the list is exhausted without a hit. Therefore, $97$ is prime.
For $n = 91$, again $\lfloor \sqrt{91} \rfloor = 9$ since $81 \leq 91 < 100$. The first six entries give $\gcd(a,91) = 1$, but

$$\begin{align*} \gcd(7,91) &= 7 \neq 1, \end{align*}$$

so we terminate immediately. Therefore, $91$ is not prime; indeed $91 = 7 \times 13$. Notice that the test hands you a factor as a by-product, which no other test in this note does.

So why look any further? Because $\lfloor\sqrt{n}\rfloor$ is enormous for the $n$ we actually care about. A $2048$-bit RSA modulus has $\sqrt{n} \approx 2^{1024}$, and no amount of computing power gets you through a list of that length. The obvious patch is to stop being exhaustive and sample $a$ at random instead, but that fails badly too. There are exactly $n - \phi(n)$ integers between $1$ and $n$ that are not coprime with $n$, and that count can be tiny compared with $n$; so a randomly chosen $a$ almost never detects anything.

Example. For $n = p^2$ with $p$ prime, what is the chance that a randomly chosen integer between $1$ and $n$ fails to be coprime with $n$?
Recall from Fermats Little Theorem and Eulers Theorem that $\phi(p^2) = p^2 - p$. So

$$\begin{align*} \frac{p^2 - \phi(p^2)}{p^2} &= \frac{p^2 - (p^2 - p)}{p^2} \\ &= \frac{p}{p^2} \\ &= \frac{1}{p}. \end{align*}$$

Therefore, the chance of a random $a$ exposing $n = p^2$ as composite is only $\frac{1}{p}$, and the chance of $k$ independent random choices all missing is $\left(\frac{p-1}{p}\right)^k$. If $p$ has a hundred digits then $\frac{1}{p} \approx 10^{-100}$ and you would need on the order of $10^{100}$ attempts before seeing anything; the randomised basic test is worthless. The problem is not that the basic test is wrong — it is perfectly correct — it is that its evidence is far too rare to stumble across by chance. What we want is a test whose evidence for compositeness is common, so that random sampling actually finds it.

Fermat's Little Theorem as a Primality Test#

Recall Fermat's Little Theorem: if $p$ is prime, then for all integers $a$ with $p \nmid a$,

$$a^{p-1} \equiv 1 \pmod p.$$

Read forwards, this is a statement about primes. Read backwards — as its contrapositive — it becomes a statement about non-primes, and that is the version that does the work.

Basically, every prime $n$ is obliged to satisfy $a^{n-1} \equiv 1$ for every $a$ it does not divide; so a single value of $a$ that breaks the rule is a cast-iron proof that $n$ is composite. An $a$ like this is called a witness to the compositeness of $n$. The beauty of this is that computing $a^{n-1} \bmod n$ by repeated squaring is fast even for astronomically large $n$, and — unlike the basic test — witnesses turn out to be abundant rather than rare.

Algorithm 6.3 (Exhaustive Fermat primality test). To test whether a given positive integer $n$ is prime:

• Start with a list $L$ of integers from $2$ up to $n-2$.
• For each number $a$ in $L$, find $a^{n-1} \bmod n$. If $a^{n-1} \bmod n \neq 1$, we know $n$ is not prime and can terminate the algorithm.
• If the list has been exhausted and the algorithm has not terminated, we know $n$ is prime and can terminate the algorithm.

The list runs from $2$ to $n-2$ because the two endpoints it leaves out are useless: $1^{n-1} = 1$ always, and for odd $n$ we have $(n-1)^{n-1} = (-1)^{n-1} = 1$ in $\mathbb{Z}_n$ as well, since $n-1$ is even. Neither can ever be a witness, so there is no point testing them.

It is worth checking that the exhaustive version really is a genuine primality test in both directions, and the key observation is that non-units can never pass.

Proof. Suppose instead $a^{n-1} \equiv 1 \pmod n$, so $n \mid a^{n-1} - 1$. Since $d \mid n$, transitivity gives $d \mid a^{n-1} - 1$. But $d \mid a$ and $n - 1 \geq 1$, so $d \mid a^{n-1}$ too; subtracting, $d$ divides

$$a^{n-1} - (a^{n-1} - 1) = 1,$$

so $d = 1$, contradicting $d > 1$. $\blacksquare$

So if $n$ is composite it has some divisor $d$ with $1 < d < n$, and taking $a = d$ (which lies in the list, since $2 \leq d \leq n/2 \leq n-2$ for $n \geq 4$) gives a value that fails the test. Hence Algorithm 6.3 reports "prime" only for genuine primes. The catch, of course, is that running $n-3$ modular exponentiations is even worse than the $\sqrt{n}$ gcd computations of the basic test; the exhaustive version is a proof of concept, not a practical algorithm.

Example. Use the Fermat primality test to deduce that $7$ is prime.
Here $n = 7$, so the list is $L = 2, 3, 4, 5$ and we need $a^6$ in $\mathbb{Z}_7$ for each of them:

$$\begin{align*} 2^6 &= 64 \\ &= 9 \times 7 + 1 \\ &= 1, \\ 3^6 &= (3^3)^2 \\ &= 27^2 \\ &= 6^2 \\ &= 36 \\ &= 1, \\ 4^6 &= (2^2)^6 \\ &= (2^6)^2 \\ &= 1^2 = 1, \\ 5^6 &= (-2)^6 \\ &= 2^6 \\ &= 1 \text{ in } \mathbb{Z}_7. \end{align*}$$

The list has been exhausted and no $a$ failed. Therefore, $7$ is prime. Notice how writing $5$ as $-2$ and $4$ as $2^2$ meant we only ever really computed $2^6$; when running these by hand, always look for a way to recycle a power you have already found.

Example. Use the Fermat primality test to deduce that $8$ is not prime.
Here $n = 8$, so the list is $L = 2,3,4,5,6$ and we need $a^7$ in $\mathbb{Z}_8$. Taking the first entry $a = 2$,

$$\begin{align*} 2^7 &= 128 \\ &= 16 \times 8 \\ &= 0 \neq 1 \text{ in } \mathbb{Z}_8, \end{align*}$$

so we terminate at once. Therefore, $8$ is not prime. In this case every entry of the list is a witness, as you can check:

$$\begin{align*} 3^7 &= (3^2)^3 \times 3 = 1^3 \times 3 = 3 \neq 1, \\ 4^7 &= (4^2)^3 \times 4 = 0 \neq 1, \\ 5^7 &= (5^2)^3 \times 5 = 1^3 \times 5 = 5 \neq 1, \\ 6^7 &= 6^3 \times 6^4 = 0 \neq 1 \text{ in } \mathbb{Z}_8, \end{align*}$$

using $3^2 = 9 = 1$, $5^2 = 25 = 1$, $4^2 = 16 = 0$ and $6^3 = 216 = 27 \times 8 = 0$. So whichever $a$ the algorithm happens to try first, $8$ is exposed immediately — which is the behaviour we are hoping for in general.

When the Fermat Test Lies#

The exhaustive test is airtight but slow; the whole point of Fermat's test is that we would like to run only a handful of values of $a$ and draw a conclusion. That raises the obvious worry: can a composite number pass the Fermat test for some particular $a$? It absolutely can, and such numbers get a name.

The sequence of Carmichael numbers begins

$$561,\ 1105,\ 1729,\ 2465,\ 2821,\ 6601,\ \dots$$

Basically, a Fermat pseudoprime is a composite number that is impersonating a prime for one particular base, and a Carmichael number is a composite number that impersonates a prime for every base it possibly could. For a Carmichael number the Fermat primality test is no better than the basic primality test, since the only $a$ that can ever expose it are the ones with $\gcd(a,n) \neq 1$ — exactly the $a$ that the basic test was already looking for, and exactly the ones we showed are hopelessly rare.

Example. Show that $341$ is a Fermat pseudoprime to the base $2$, but not to the base $3$.
First, $341 = 11 \times 31$, so $341$ is certainly composite. For the base $2$, the key observation is

$$\begin{align*} 2^{10} &= 1024 \\ &= 3 \times 341 + 1 \\ &= 1 \text{ in } \mathbb{Z}_{341}, \end{align*}$$

and since $340 = 10 \times 34$ this gives

$$\begin{align*} 2^{340} &= (2^{10})^{34} \\ &= 1^{34} \\ &= 1 \text{ in } \mathbb{Z}_{341}. \end{align*}$$

So $341$ sails through the Fermat test to the base $2$; it is a Fermat pseudoprime to base $2$. For the base $3$ we repeatedly square:

$$\begin{align*} 3^2 &= 9, \\ 3^4 &= 81, \\ 3^8 &= 81^2 = 6561 = 19 \times 341 + 82 = 82, \\ 3^{16} &= 82^2 = 6724 = 19 \times 341 + 245 = 245, \\ 3^{32} &= 245^2 = 60025 = 176 \times 341 + 9 = 9 \text{ in } \mathbb{Z}_{341}. \end{align*}$$

Now notice something lovely: $3^{32} = 9 = 3^2$, and $\gcd(3,341) = 1$ so $3$ is a unit; cancelling $3^2$ gives $3^{30} = 1$, i.e. $\operatorname{ord}_{341}(3) = 30$ or a divisor of it. Since $340 = 11 \times 30 + 10$, we can reduce the exponent modulo the order:

$$\begin{align*} 3^{340} &= (3^{30})^{11} \times 3^{10} \\ &= 3^{10} \\ &= 3^8 \times 3^2 \\ &= 82 \times 9 \\ &= 738 \\ &= 2 \times 341 + 56 \\ &= 56 \neq 1 \text{ in } \mathbb{Z}_{341}. \end{align*}$$

Therefore, $341$ is a Fermat pseudoprime to base $2$ but not to base $3$; the single value $a = 3$ is a witness proving $341$ composite. Passing the Fermat test for one base proves nothing whatsoever; only a failure is conclusive.

Example. Find all integers $1 < a < 15$ such that $15$ is a Fermat pseudoprime to base $a$.
Certainly $15 = 3 \times 5$ is composite, so we just need every $a$ in range with $a^{14} = 1$ in $\mathbb{Z}_{15}$. By the Lemma above we may ignore any $a$ that is not a unit, so the candidates are

$$\mathbb{Z}_{15}^* \cap \{2,\dots,14\} = \{2, 4, 7, 8, 11, 13, 14\}.$$

Now $\phi(15) = \phi(3)\phi(5) = 2 \times 4 = 8$, so $\operatorname{ord}_{15}(a) \mid 8$ for every unit; and $a^{14} = 1$ happens exactly when $\operatorname{ord}_{15}(a) \mid 14$. Combining the two,

$$\operatorname{ord}_{15}(a) \mid \gcd(8, 14) = 2,$$

so $a^{14} = 1$ if and only if $a^2 = 1$. Squaring each candidate,

$$\begin{align*} 2^2 &= 4 \neq 1, \\ 4^2 &= 16 = 1, \\ 7^2 &= 49 = 3 \times 15 + 4 = 4 \neq 1, \\ 8^2 &= 64 = 4 \times 15 + 4 = 4 \neq 1, \\ 11^2 &= 121 = 8 \times 15 + 1 = 1, \\ 13^2 &= 169 = 11 \times 15 + 4 = 4 \neq 1, \\ 14^2 &= (-1)^2 = 1 \text{ in } \mathbb{Z}_{15}. \end{align*}$$

Therefore, $15$ is a Fermat pseudoprime exactly to the bases $a = 4, 11, 14$. Notice the count: $4$ of the $8$ units pass the test and the other $4$ are witnesses, i.e. exactly half — which is the worst case permitted by the next result.

The Randomised Fermat Test#

Running the Fermat primality test up to $n-3$ times is still hopeless for very large $n$. Instead we choose the test integers $a$ randomly and report whether $n$ is likely to be prime after a limited number of checks.

Algorithm 6.5 (Fermat primality test, randomised). To test whether a given positive integer $n$ is prime:

• Start with a list of integers from $2$ up to $n-2$.
• Repeat the following up to $k$ times:
  • Randomly choose (and remove) an integer $a$ from the list.
  • If $\gcd(a,n) \neq 1$, report that $n$ is not prime and terminate.
  • If $a^{n-1} \bmod n \neq 1$, report that $n$ is not prime and terminate.
• If the algorithm has not terminated after $k$ iterations, report that $n$ is probably prime and terminate.

The gcd check is strictly speaking redundant — by the Lemma, any $a$ with $\gcd(a,n) \neq 1$ automatically fails the exponentiation check too — but a gcd is much cheaper than a modular exponentiation, so it is worth doing first.

Everything now hinges on how likely a random $a$ is to be a witness. This is where the Fermat test decisively beats the basic test.

Proof. Split the unit group into the elements that pass the test and the elements that fail it:

$$\begin{align*} B &= \{b \in \mathbb{Z}_n^* : b^{n-1} = 1\}, \\ W &= \{c \in \mathbb{Z}_n^* : c^{n-1} \neq 1\}, \end{align*}$$

so that $|B| + |W| = \phi(n)$. Assume $W$ is non-empty and fix one witness $a \in W$. For each $b \in B$, the element $c = ab$ is a product of units and hence a unit, and

$$\begin{align*} c^{n-1} &= (ab)^{n-1} \\ &= a^{n-1} b^{n-1} \\ &= a^{n-1} \times 1 \\ &= a^{n-1} \neq 1 \text{ in } \mathbb{Z}_n, \end{align*}$$

so $c \in W$. Moreover the map $b \mapsto ab$ is injective, since $a$ is invertible and we can recover $b = a^{-1}c$; so distinct $b$ give distinct $c$. Hence $|B| \leq |W|$, and therefore

$$\phi(n) = |B| + |W| \leq 2|W|, \quad \text{i.e.} \quad |W| \geq \tfrac{1}{2}\phi(n). \qquad \blacksquare$$

Basically, the witnesses come for free in bulk: multiply every liar by a single witness and you get that many distinct witnesses back, so witnesses can never be the minority. This is the entire reason the randomised Fermat test is useful — evidence of compositeness is either completely absent or at least half the group, never merely rare.

Consequently each round of the loop, conditional on $n$ being composite with at least one witness in $\mathbb{Z}_n^*$, has probability at least $\frac{1}{2}$ of catching it, and so the algorithm has at worst a

$$\boxed{\frac{1}{2^k} \text{ chance of incorrectly reporting that } n \text{ is probably prime.}}$$

Contrast this with the $\left(\frac{p-1}{p}\right)^k$ worst-case false-positive rate we computed for the randomised basic test on $n = p^2$: that quantity barely moves as $k$ grows, while $\frac{1}{2^k}$ collapses. Twenty rounds already gives a false positive rate below one in a million, and $k = 100$ makes an error less likely than a hardware fault.

Two warnings before moving on. A report of "probably prime" is never a proof; a composite number that survives $k$ rounds is still composite, you were just unlucky $k$ times in a row. And more seriously: the $\frac{1}{2^k}$ bound assumes at least one witness exists in $\mathbb{Z}_n^*$, which is precisely what fails for a Carmichael number. For $n = 561$ every unit passes, so $W = \varnothing$ and the argument above says nothing at all; the randomised Fermat test will happily report that $561$ is probably prime no matter how large you make $k$, as long as it keeps drawing units.

Example. Run the randomised Fermat test on $n = 15$ with first random choice $a = 2$.
First $\gcd(2,15) = 1$, so we proceed to the exponentiation. Since $2^4 = 16 = 1$ in $\mathbb{Z}_{15}$,

$$\begin{align*} 2^{14} &= (2^4)^3 \times 2^2 \\ &= 1^3 \times 4 \\ &= 4 \neq 1 \text{ in } \mathbb{Z}_{15}. \end{align*}$$

Therefore, the test reports (correctly, and after a single round) that $15$ is not prime. Had it instead drawn $a = 4$, $11$ or $14$ first, that round would have passed and the loop would have continued; but as we counted above, those are only $3$ of the $13$ candidates in $\{2,\dots,13\}$, so the odds are heavily in our favour.

Certifying Primes with the Lucas Test#

The randomised Fermat test can prove a number composite but can never prove one prime. That is genuinely annoying if you are building a cryptosystem and want a guarantee. The fix is to stop asking for a symptom of primality and start asking for a certificate, and the order of a unit provides exactly the right one.

Recall two facts we already have. First, $\phi(p) = p-1$ if and only if $p$ is prime, so for any composite $n$ we must have $\phi(n) < n-1$. Second, if $p$ is prime then $\mathbb{Z}_p^*$ has a primitive element, i.e. a unit whose order is the full $\phi(p) = p-1$. Together these give a clean characterisation.

Proof. ($\Rightarrow$) Suppose $n$ is prime. Then $\phi(n) = n-1$, and $\mathbb{Z}_n^*$ has a primitive element $a$; by definition $\operatorname{ord}_n(a) = \phi(n) = n-1$.
($\Leftarrow$) Suppose $\operatorname{ord}_n(a) = n-1$ for some unit $a$. By the theorem that order divides the totient, $\operatorname{ord}_n(a) \mid \phi(n)$, and in particular

$$\begin{align*} n - 1 &\leq \phi(n). \end{align*}$$

But $\phi(n)$ counts the integers in $\{1,2,\dots,n\}$ coprime with $n$, and $n$ itself is never one of them (as $\gcd(n,n) = n > 1$), so $\phi(n) \leq n-1$ always. Hence $\phi(n) = n - 1$; that is, every one of $1, 2, \dots, n-1$ is coprime with $n$. So $n$ has no divisor $d$ with $1 < d < n$, and therefore $n$ is prime. $\blacksquare$

Basically, "$n$ is prime" and "$\mathbb{Z}_n^*$ contains an element of order $n-1$" are the same statement, so finding such an element is a proof of primality. And we already know how to check whether a given $a$ has full order without computing the order itself — it is the primitive-element test from Order and Primitive Elements.

Algorithm 6.6 (Lucas primality test, randomised). To test whether a given positive integer $n$ is prime:

• Start with a list of integers from $2$ up to $n-2$.
• Repeat the following up to $k$ times:
  • Randomly choose (and remove) an integer $a$ from the list.
  • If $\gcd(a,n) \neq 1$, report that $n$ is not prime and terminate.
  • If $a^{n-1} \bmod n \neq 1$, report that $n$ is not prime and terminate.
  • If $a^{\frac{n-1}{p_i}} \bmod n \neq 1$ for all primes $p_i$ that divide $n-1$, report that $n$ is prime and terminate.
• If the algorithm has not terminated after $k$ iterations, report that $n$ is probably not prime and terminate.

The first three bullets are identical to the randomised Fermat test; all the new content is in the fourth. Why does it detect $\operatorname{ord}_n(a) = n-1$? The condition $a^{n-1} = 1$ already forces $\operatorname{ord}_n(a) \mid n-1$. If the order were a proper divisor of $n-1$, its prime factorisation would be missing at least one copy of some prime $p_i \mid n-1$, so we would have $\operatorname{ord}_n(a) \mid \frac{n-1}{p_i}$ and hence $a^{(n-1)/p_i} = 1$ for that $p_i$. So the fourth bullet holding for every $p_i$ is precisely the statement that no proper divisor of $n-1$ is the order — i.e. $\operatorname{ord}_n(a) = n-1$, and by the characterisation theorem $n$ is prime.

Notice that the Lucas primality test can in some cases guarantee a number is prime, unlike the (non-exhaustive) Fermat primality test. The price is twofold. First, the Lucas test is only practical when $n-1$ can be easily factorised — and factorising a $2048$-bit $n-1$ is exactly the sort of problem we invented these tests to avoid. Second, a report of "probably not prime" is genuinely weak evidence: the test only certifies when the random draw lands on a primitive element, and a prime $n$ has only $\phi(n-1)$ of those among its $n-1$ units, which can be a modest fraction. A "prime" verdict from Lucas is a proof; a "probably not prime" verdict is just an admission that no certificate turned up in $k$ tries.

Example. Use the Lucas primality test to deduce that $7$ is prime.
Here $n-1 = 6 = 2 \times 3$, so the primes dividing $n-1$ are $p_1 = 2$ and $p_2 = 3$, and the two exponents to check are

$$\frac{6}{2} = 3 \quad \text{and} \quad \frac{6}{3} = 2.$$

The candidate list is $2, 3, 4, 5$. Suppose the first random draw is $a = 2$. Then $\gcd(2,7) = 1$, and $2^6 = 64 = 1$ in $\mathbb{Z}_7$ as computed earlier, so the first two checks pass; but

$$\begin{align*} 2^3 &= 8 \\ &= 1 \text{ in } \mathbb{Z}_7, \end{align*}$$

so the fourth bullet fails at $p_1 = 2$ and this round ends with no conclusion. Suppose the next draw is $a = 3$. Then $\gcd(3,7) = 1$, and

$$\begin{align*} 3^2 &= 9 = 2 \neq 1, \\ 3^3 &= 27 = 6 = -1 \neq 1, \\ 3^6 &= (3^3)^2 = (-1)^2 = 1 \text{ in } \mathbb{Z}_7. \end{align*}$$

So $3^6 = 1$, while $3^{6/2} = 3^3 \neq 1$ and $3^{6/3} = 3^2 \neq 1$. Therefore, $\operatorname{ord}_7(3) = 6 = n-1$ and the test reports that $7$ is prime — and this time that is a proof, not a probability. As a sanity check, we found in Order and Primitive Elements that the primitive elements of $\mathbb{Z}_7^*$ are exactly $3$ and $5$; those are the only two draws that can certify, and since $2$ and $4$ both fail, the worst possible ordering needs $k \geq 3$ iterations.

Example. Use the Lucas primality test to demonstrate that $23$ is prime, and find the maximum number of iterations the test could need.
Here $n - 1 = 22 = 2 \times 11$, so the primes dividing $n-1$ are $2$ and $11$, and the exponents to check are

$$\frac{22}{2} = 11 \quad \text{and} \quad \frac{22}{11} = 2.$$

Suppose the first draw is $a = 2$. Then $\gcd(2,23) = 1$ and

$$\begin{align*} 2^{11} &= 2048 \\ &= 89 \times 23 + 1 \\ &= 1 \text{ in } \mathbb{Z}_{23}, \end{align*}$$

so $2^{22} = (2^{11})^2 = 1$ passes the Fermat check, but $2^{22/2} = 2^{11} = 1$ kills the certificate. No conclusion; draw again. Suppose the next draw is $a = 5$, and build up the powers by squaring:

$$\begin{align*} 5^2 &= 25 = 2, \\ 5^4 &= 2^2 = 4, \\ 5^8 &= 4^2 = 16, \\ 5^{11} &= 5^8 \times 5^2 \times 5 \\ &= 16 \times 2 \times 5 \\ &= 160 \\ &= 6 \times 23 + 22 \\ &= 22 = -1 \text{ in } \mathbb{Z}_{23}. \end{align*}$$

Hence $5^{22} = (5^{11})^2 = (-1)^2 = 1$, so the Fermat check passes; and the two certificate checks give $5^{11} = -1 \neq 1$ and $5^2 = 2 \neq 1$. Therefore $\operatorname{ord}_{23}(5) = 22 = n-1$, and the test reports that $23$ is prime.
For the maximum number of iterations, note that the test can only terminate with "prime" when the drawn $a$ is a primitive element of $\mathbb{Z}_{23}^*$. By the corollary in Order and Primitive Elements there are exactly

$$\phi(\phi(23)) = \phi(22) = \phi(2)\phi(11) = 1 \times 10 = 10$$

primitive elements. Neither $1$ (order $1$) nor $22 = -1$ (order $2$) is one of them, so all $10$ sit inside the candidate list $\{2, 3, \dots, 21\}$, which has $20$ entries. In the worst case the first $10$ draws are the $10$ non-primitive candidates, and then the $11$th draw is forced to be primitive. Therefore, at most $11$ iterations are needed before the test concludes that $23$ is certainly prime.

Why Lucas Never Certifies a Carmichael Number#

Example. Suppose that when applying the Lucas primality test to $561$, all the chosen integers $a$ happen to be coprime with $561$. What will the test report?
First set up the numbers. We have

$$561 = 3 \times 11 \times 17, \qquad 560 = 2^4 \times 5 \times 7,$$

so $561$ is composite, the primes dividing $n - 1 = 560$ are $2$, $5$ and $7$, and the three certificate exponents are

$$\frac{560}{2} = 280, \quad \frac{560}{5} = 112, \quad \frac{560}{7} = 80.$$

The gcd check. By assumption every drawn $a$ satisfies $\gcd(a,561) = 1$, so this check never fires.
The Fermat check. Let $a \in \mathbb{Z}_{561}^*$, so $a$ is coprime with each of $3$, $11$ and $17$. Fermat's Little Theorem in each prime modulus gives

$$a^2 \equiv 1 \!\!\pmod 3, \qquad a^{10} \equiv 1 \!\!\pmod{11}, \qquad a^{16} \equiv 1 \!\!\pmod{17},$$

and since $560 = 2 \times 280 = 10 \times 56 = 16 \times 35$, each of $2$, $10$ and $16$ divides $560$. Raising to the appropriate powers,

$$a^{560} \equiv 1 \!\!\pmod 3, \qquad a^{560} \equiv 1 \!\!\pmod{11}, \qquad a^{560} \equiv 1 \!\!\pmod{17},$$

and as $3, 11, 17$ are pairwise coprime, the CRT glues these into $a^{560} \equiv 1 \pmod{561}$. So the Fermat check never fires either — and this is exactly the computation proving that $561$ is a Carmichael number.
The certificate check. Now run the identical argument with $80$ in place of $560$. Since

$$80 = 2 \times 40 = 10 \times 8 = 16 \times 5,$$