Miller-Rabin Primality Test

Posted on November 19, 2022 by Dan Ma

This post is about the Miller-Rabin primality test.

Fermat Primality Test

The calculation behind the Miller-Rabin primality test is closely related to that of the Fermat primality test. It is instructive to recall the calculation of the Fermat test. The Fermat test is based on the modular exponentiation $a^{n-1}$ modulo $n$ , where $n$ is the odd positive integer being tested and $a$ is a positive integer that is relatively prime to $n$ . According to the Fermat Little Theorem, if $n$ is prime, then $a^{n-1} \equiv 1$ modulo $n$ . This fact is the basis of the Fermat primality test. If $a^{n-1} \equiv 1$ modulo $n$ , this provides evidence that $n$ may be prime since this is a property that is shared by all prime numbers. Thus, any integer $n$ is called a probable prime to base $a$ if $a^{n-1} \equiv 1$ modulo $n$ . If $n$ is a probable prime to base $a$ and if $n$ is composite, then $n$ is said to be a pseudoprime to base $a$ . Furthermore, if $n$ is not a probable prime to base $a$ , i.e., $a^{n-1} \not \equiv 1$ modulo $n$ , then the base $a$ is said to be a Fermat witness for (the compositeness of) $n$ .

This is how the Fermat test is run. Given a positive integer whose “prime or composite” status is not known, choose several bases $a$ that are relatively prime to $n$ at random. Compute $a^{n-1} \equiv 1$ modulo $n$ for the chosen bases $a$ . If for one base $a$ , $a^{n-1} \not \equiv 1$ modulo $n$ , we have conclusive proof that $n$ is composite. If $a^{n-1} \equiv 1$ modulo $n$ for all the chosen bases $a$ , we have very strong evidence for the primality of $n$ . The Fermat test is discussed in the two preceding posts (here and here).

The Miller-Rabin Calculation

The Miller-Rabin test rests on the following idea.

Lemma 1 (Roots of Unity Modulo a Prime)
Let $n$ be a prime number. Suppose that $u^2 \equiv 1$ modulo $n$ . Then $u \equiv 1$ modulo $n$ or $u \equiv -1$ modulo $n$ .

Clearly, both $u \equiv 1$ and $u \equiv -1$ modulo $n$ are solutions to the congruence equation $u^2 \equiv 1$ modulo $n$ . These two solutions are the trivial solutions to the equation. We claim that there is no other solution (no non-trivial solution) when the modulus is prime. To this end, we show that if $t^2 \equiv 1$ modulo $n$ , then $t \equiv 1$ or $t \equiv -1$ modulo $n$ . Let $t$ be such that $t^2 \equiv 1$ modulo $n$ . Then $n$ divides $(t-1) \cdot (t+1)$ . Since $n$ is prime, either $n$ divides $t-1$ or divides $t+1$ (due to Euclid’s Lemma). If $n$ divides $t-1$ , then $t \equiv 1$ modulo $n$ . If $n$ divides $t+1$ , then $t \equiv -1$ modulo $n$ . $\square$

The calculation for the Miller-Rabin test is the same modular exponentiation but built up in several steps. Let $n$ be an odd positive integer. Express $n-1=2^T \times Q$ where $T \ge 1$ and $Q$ is odd. Let $a$ be a base relatively prime to $n$ . Instead of computing the exponentiation $a^{n-1}$ directly, we compute $a^Q$ and then square $T$ times to obtain $a^{n-1}=a^{2^T \times Q}$ . In other words, we calculate the terms in the following sequence modulo $n$ .

(1)

…………….

$\displaystyle a^Q,a^{2 \cdot Q},a^{2^2 \cdot Q},\cdots,a^{2^{T-1} \cdot Q},a^{2^T \cdot Q}$

The first term in the sequence is $a^Q$ modulo $n$ . Each subsequent term is the square of the preceding term. This is done until we obtain $a^{n-1}$ . For all odd primes $n$ , the above sequence follows a certain pattern, which is described in the following theorem.

Theorem 2
Let $n$ be an odd prime number. Let $a$ be a positive integer that is relatively prime to $n$ . Then either one of the following holds.

$a^Q \equiv 1$ modulo $n$ .……………………………………………………………….(a)
$a^{2^J \cdot Q} \equiv -1$ modulo $n$ for some $J$ with $0 \le J \le n-1$ .………………….(b)

The first bullet point says that the first term in the sequence (1) is congruent to 1 modulo $n$ . The second bullet point says that the term immediately preceding the first 1 in the sequence is congruent to -1 modulo $n$ .

The proof of Theorem 2 relies on Lemma 1. The proof goes something like this. First, the last term in the sequence must be a 1 due to the Fermat Little Theorem. If $a^Q \equiv 1$ modulo $n$ , then the entire sequence consists of 1’s. Then (a) is satisfied. Suppose the sequence is not entirely 1’s. Then the term that is the first 1 must have a preceding term. Then the square of the preceding term is congruent to 1 modulo $n$ . Since $n$ is prime, that preceding term can only be 1 or -1. However, the preceding term can only be a -1 since it precedes the term that is the first value of 1. $\square$

Two Pieces of Information About Primality

Theorem 2 describes a property possessed by all old primes. Whenever an odd positive integer satisfies this property with a certain base $a$ , i.e., the sequence (1) satisfied either (a) or (b), we consider that as evidence that $n$ may be a prime. Hence, we have this definition. Suppose $n$ is an odd positive integer with the “prime or composite” status not known. Let $a$ be a base that is relatively prime to $n$ . Compute the sequence (1). If either condition (a) or condition (b) holds, then $n$ is said to be a strong probable prime to base $a$ .

The underlying calculation in the sequence (1) attempts to capture two pieces of information about primality. The first piece is based on the Fermat Little Theorem (whether $a^{n-1}$ is congruent to 1). The second piece of information is the roots of unity modulo a prime (Lemma 1). If the Miller-Rabin calculation indicates a probable prime, the evidence is stronger than that from the Fermat test. Two pieces of evidence is more corroborative than just one piece of evidence.

The Millar-Rabin test will be more capable to differentiate composite numbers. This is because there are two ways to detect compositeness embedded in the calculation of the sequence (1) described above. The compositeness of a number can be revealed by the Fermat Little theorem (whether $a^{n-1}$ is congruent to 1 or not) and by whether there exists a non-trivial square root of 1 modulo $n$ . This is demonstrated in the examples in the next section.

Examples of the Millar-Rabin Calculation

In this section, we demonstrate how the Miller-Rabin calculation can detect the compositeness of Carmichael numbers, which the Fermat test fails to do.

Example 1
Consider $n=$ 29,341. This is a composite number with 29,341 = 13 x 37 x 61. This is a Carmichael number. Thus, $a^{29340} \equiv 1$ modulo 29341 for any coprime base $a$ . As a result, the Fermat test will not be able to detect the compositeness of this and other Carmichael numbers. Note that $29341=2^2 \cdot 7335=2^2 \cdot Q$ . We first perform base 2 calculation, which produces the sequence $2^Q,2^{2 \cdot Q},2^{4 \cdot Q}$ . The resulting sequence is:

26424, 29340, 1

The last term is 1 (due to 29341 being a Carmichael number). The term preceding the last term is 29340, which is congruence to -1. Thus, condition (b) is satisfied. This means that 29341 is a strong probable prime to base 2. Let’s try base 3 calculation, which is the sequence $3^Q,3^{2 \cdot Q},3^{4 \cdot Q}$ . The resulting sequence is:

22569, 1, 1

The term preceding the first 1 is 22569, which is neither 1 nor -1. This violates conditions (a) and (b) described above. This gives a conclusive proof that 29341 is a composite number. The number 22569 is a non-trivial square root of 1 modulo 29341. The existence of the non-trivial square root shows that the modulus 29341 cannot be prime.

Example 2
Consider $n=$ 172,947,529. This is a Carmichael number with 172,947,529 =307 x 613 x 919. First, we have $n-1=2^3 \cdot Q$ where $Q=$ 21,618,441. Let’s try the base 2 calculation, producing the sequence $2^Q,2^{2 \cdot Q},2^{4 \cdot Q},2^{8 \cdot Q}$ , resulting in:

40063806, 2257065, 1, 1

Note that the term preceding the first 1 is 2,257,065, which is neither 1 nor -1. This means that the conclusion of Theorem 2 is not satisfied. As a result, the Carmichael number 172,947,529 is shown to be composite.

The two examples demonstrate that the Miller-Rabin works correctly where the Fermat test fails. Referring back to the point about the two pieces of evidence for primality, the first way of detecting compositeness does not work in both Example 1 and Example 2, i.e., the congruence $a^{n-1}$ is 1. However, the second piece of evidence enables the Miller-Rabin calculation to detect the compositeness. Two pieces of evidence is better than just one. Therefore, the Miller-Rabin test is superior than the Fermat test.

For the Miller-Rabin calculation to work correctly, we need to find the right bases to use. In Example 1, using base 2 does not detect the compositeness. Luckily, trying base 3 works. How likely is it to find a base that will detect a composite number? If a number $n$ is composite, the calculation described in Theorem 2 will detect the compositeness of $n$ with at least 75% of the bases coprime to $n$ . See Theorem 3 below.

The Implementation

To implement the Miller-Rabin test, randomly select several bases that are relatively prime to $n$ , the number to be tested. For each chosen base $a$ , compute the sequence (1).

If, for one chosen base $a$ , both conditions (a) and (b) in Theorem 2 do not hold, then $n$ is proven to be composite.
If, for all chosen bases $a$ , one of the conditions (a) and (b) holds, then $n$ is a strong probable prime to all the chosen bases, which indicates that we have obtained strong evidence for primality and $n$ is likely a prime number.

Strong Pseudoprime and Miller-Rabin Witness

Additional terminology will help the discussion. For a given base $a$ , if neither condition (a) nor condition (b), as described in Theorem 2, holds, then $n$ is proven to be composite, in which case, the base $a$ is said to be a Miller-Rabin witness for (the compositeness of) $n$ . For simplicity, we use the term witness for Miller-Rabin witness in the remainder of this article. If $n$ is a strong probable prime to base $a$ and if $n$ is composite, then $n$ is said to be a strong pseudoprime to base $a$ .

Between the Fermat test and the Miller-Rabin test, there are two notions of probable primes, two notions of pseudoprimes and two notions of witnesses. How do they relate? We go back to the above section on the two pieces of evidence for primality. A probable prime under the Miller-Rabin test must also be a probable prime under the Fermat since having two pieces of evidence is stronger than one piece of evidence. Therefore, we have the following implications.

Strong probable prime to base $\bold a$

$\longrightarrow$

Probable prime to base $\bold a$

Strong pseudoprime to base $\bold a$

$\longrightarrow$

Pseudoprime to base $\bold a$

The above implications cannot be reversed. The number $n$ in Example 1 is a Carmichael number, hence is a pseudoprime to base 3. However, it is not a strong pseudoprime to base 3. In general, a number can be a weaker form of pseudoprime and not be a stronger form of pseudoprime.

Strong pseudoprime to base $\bold a$

$\not \longleftarrow$

Pseudoprime to base $\bold a$

How do the two notions of witnesses relate? We have the following implications.

Fermat witness

$\longrightarrow$

Miller-Rabin witness

Fermat witness $\not \longleftarrow$ Miller-Rabin witness

A Fermat witness violates one piece of evidence of primality, namely that from the Fermat Little Theorem. It means that it would be a witness from the point of view of the Miller-Rabin test. On the other hand, a Miller-Rabin witness does not have to be a Fermat witness. It is possible that a Miller-Rabin witness is to violate the second piece of evidence by producing a non-trivial square root of 1 while satisfying the Fermat Little Theorem. In Example 1, 3 is a (Miller-Rabin) witness for the integer 29,341 and 3 is not a Fermat witness for 29,341. In Example 2, the base 2 is a witness for 172,947,529, while base 2 is not a Fermat witness. It is because in both examples, the Miller-Rabin calculation produces a non-trivial square root of unity.

Performance

The above discussion and examples indicate that the Miller-Rabin test is superior than the Fermat test in that it can detect the Carmichael numbers as composite. The advantage of the Miller-Rabin test is real. For any composite number $n$ , there is at least one base $a$ that is a witness for $n$ , even when $n$ is a Carmichael number (as shown in the above examples). In fact, if $n$ is composite, at least 75% of the possible choices for bases are (Miller-Rabin) witnesses for $n$ . Consider the following theorem.

Theorem 3
Let $n$ be an odd composite number. Then at least 75% of the numbers with $1<a<n$ are (Miller-Rabin) witnesses for $n$ . In other words, the composite number $n$ is a strong pseudoprime to at most 25% of the possible bases $a$ .

With Theorem 3, the Miller-Rabin test can be made a truly probabilistic test for primality. This means that the test can be implemented in such a way that the error probability can be made as small as we wish. When we randomly select a base $a$ out of all the bases coprime with the composite $n$ , there is at least a 0.75 probability that $a$ is a witness, which means that the probability of error is at most 0.25. If we choose 50 or so bases at random and if the test indicates prime, the error probability is practically zero. Thus, the Miller-Rabin test is an efficient and practical test for finding large numbers that are prime with high probability.

$\text{ }$

Dan Ma Fermat primality test

Dan Ma Miller-Rabin primality test

Daniel Ma Fermat primality test

Daniel Ma Miller-Rabin primality test

Dan Ma Carmichael numbers

Daniel Ma Carmichael numbers

$\copyright$ 2022 – Dan Ma

The Fermat Test of Primality

Posted on November 13, 2022 by Dan Ma

This and the next post concern with two primality tests – Fermat test (this post) and the Miller-Rabin test (next post). Each of these two tests is based on a theorem that describes a property that is true for all prime numbers. We discuss the theorems and the surrounding issues of using the tests.

A primality test is an algorithm for determining whether a given positive integer is a prime number. Given a positive odd integer whose “prime or composite” status is not known, the algorithm gives an indication whether the number is prime or composite. As indicated above, each algorithm (the Fermat test or the Miller-Rabin test) is based on a theorem describing a property that holds for all prime numbers. Whenever the given test number satisfies this property, the test gives evidence that the number is prime. When the given test number does not satisfy the property, we have definite proof that the number is composite. Let’s start with the Fermat test, which is based on the Fermat Little Theorem.

The Fermat Primality Test

Fermat Little Theorem (FLT)
If $p$ is a prime number and $a$ is a positive integer that is relatively prime to $p$ , then $a^{p-1} \equiv 1 \ (\text{mod} \ p)$ .

The theorem centers on the exponentiation $a^{p-1}$ modulo $p$ , which can be computed efficiently using the fast powering algorithm, also called square-and-multiply (see here). In this exponentiation, the number $a$ is referred to as the base. The fact the exponentiation $a^{p-1}$ is congruent to 1 modulo $p$ is strong evidence that the number $p$ is a prime since the number $p$ is exhibiting a property that is shared by all prime numbers. Thus, whenever this exponentiation is congruent to 1, we say that $p$ is a probable prime to the base $a$ . The following is a description of the Fermat test.

Fermat primality test

$n$

Composite

$n$

Probable Prime

Step 1. Choose a base $a$ at random from the set $\left\{2,3,\cdots,n-1 \right\}$ .
Step 2. Compute the greatest common divisor of $a$ and $n$ , denoted by $\text{GCD}(a,n)$ . If it is greater than 1, then stop and output $n$ is Composite. Otherwise go to the next step.
Step 3. Compute $a^{n-1} \ (\text{mod} \ n)$ .

If $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$ , then stop and output $n$ is Composite.
If $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ , then $n$ may be a prime number. Do one of the following:

Return to Step 1 and repeat the process with a new base $a$ .
Output $n$ is a Probable Prime and stop.

$\text{ }$

If the number $n$ satisfies the congruence relation $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ , the number $n$ satisfies a property possessed by all prime numbers, which leads us to believe that we have evidence that $n$ is prime. As a result, we say that $n$ is a probable prime to the base $a$ if $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ holds. The above algorithm gives a hint that the test should be performed using multiple bases. In fact, the bases should be randomly chosen. If $n$ is shown to be a probable prime to multiple randomly selected bases, the evidence for primality is very strong. On the other hand, if $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$ to one base $a$ , we have definitive proof that $n$ is composite (otherwise the exponentiation would be congruent to 1 based on the Fermat Little Theorem).

Though the Fermat algorithm as discussed here is not a statistical algorithm, it is informative to view it as such in this introduction. The Fermat test is at heart a classification problem. It “predicts” whether a given number is prime or composite. There can be four possible outcomes in the classification scheme. They are True Positive (a prime number predicted as prime), False Positive (a composite number predicted as prime), False Negative (a prime number predicted as composite), and True Negative (a composite number predicted as composite). The greens are the correct outcomes and the reds are the incorrect outcomes.

If $n$ is indeed a prime number, the Fermat will always give the result of probable prime. In other words, the Fermat test will never identify a prime number as composite. This is because for any prime number $n$ , the Fermat Little Theorem guarantees that $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ always holds. This means that there can never be a False Negative when using the Fermat test. On the other hand, if $n$ is “predicted” to be composite, the number $n$ must be a composite number. This is because if $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$ for the base $a$ , the number $n$ must be composite (otherwise, the exponentiation would be 1 instead).

Pseudoprimes

In applying the Fermat test (or any other primality test), we do not know in advance whether the number being tested is an actual prime or an actual composite number. All we know are the predicted results. It thus makes sense to focus the accuracy of the predicted results.

When the Fermat test says that the number $n$ is composite, we know for sure that the result is correct, as discussed above. When the test says that $n$ is a probable prime to one base or multiple bases, the result is strong evidence for primality. However, the positive result can be wrong on rare occasions (a False Positive is possible).

The preceding paragraph indicates that a predicted positive can be a True Positive or a False Positive. Thus, the probable primes to a given base consist of two mutually exclusive sets – the true primes (True Positive) and the false primes (False Positive). Instead of calling the incorrect test results false primes, we use a more standard terminology to facilitate the discussion. If $n$ is a probable prime to base $a$ and if $n$ is composite, we say $n$ is a pseudoprime to base $a$ . The term Fermat pseudoprime can be used. However, if it is clear that Fermat test is being used, we simply refer to the False Positive as pseudoprime.

Consider two small examples, the integers 341 and 561. We know that 341 is composite since 341 = 11 x 31. We also know that $2^{340} \equiv 1 \ (\text{mod} \ 341)$ . Thus, 341 is a pseudoprime to the base 2. However, using base 3, we see that $3^{340} \equiv 56 \not \equiv 1 \ (\text{mod} \ 341)$ . This shows that 341 is a composite number (not a pseudoprime to base 3). On the other hand, the integer 561 is also composite, with 561 = 3 x 11 x 17. Using various bases $a$ coprime to 561, we notice that $a^{560} \equiv 1 \ (\text{mod} \ 561)$ . In fact, numbers like 561 represent a major flaw of the Fermat test.

Fermat Witnesses

Another notion is useful for understanding the Fermat primality testing. If the positive integer $n$ is not a probable prime to base $a$ , we say that the base $a$ is a Fermat witness for (the compositeness of) $n$ . In other words, the base $a$ is a Fermat witness for $n$ if the Fermat test, using the base $a$ , proves that $n$ is composite. Here, the witness $a$ provides evidence that $n$ , the number being tested, is a composite number. The notion of witness here is called Fermat witness since it is tied to the Fermat test. The term witness without any qualifier will be reserved for the notion of witness with respect to the Miller-Rabin test.

Fermat witness and pseudoprime are opposite concepts. A pseudoprime to base $a$ is a composite number that is prime-like (satisfying a property possessed by prime numbers). A Fermat witness is a base $a$ that shows that the number $n$ does not possess the property possessed by the prime numbers. Using these two notions, we can recast the Fermat test.

Fermat test from the pseudoprime perspective
To test the “Prime or Composite” status of the number $n$ , randomly select several bases $a$ . If $n$ is not a probable prime to one of the chosen bases, then $n$ is for certain a composite number. If $n$ is a probable prime to all the chosen bases, then we have very strong evidence for the primality of $n$ .

Fermat test from the Fermat witness perspective
To test the “Prime or Composite” status of the number $n$ , randomly select several bases $a$ . If one of the chosen bases is a Fermat witness for $n$ , then $n$ is for certain a composite number. If none of the chosen bases is a Fermat witness for $n$ , then we have a very strong evidence for the primality of $n$ .

It seems that the essence of the Fermat test can be more naturally described using the notion of Fermat witness. The Fermat test is a process of finding Fermat witnesses. The lack of witnesses gives strong evidence of primality.

Carmichael Numbers

Let’s consider the examples of 341 and 561 again. These two examples tells us that there are two types of false positives in the Fermat test. That is, there are two types of pseudoprimes. The number 341 is an example of the first type. These are the composite numbers that are pseudoprimes to some bases but not to all bases. In other words, these composite numbers have at least one Fermat witness. The number 561 is an example of the second type of false positives. These numbers are resistant to the Fermat test.

A composite number $n$ is said to be a Carmichael number if $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ for any base $a$ relatively prime to $n$ . These numbers always satisfy the conclusion of the Fermat Little Theorem. As a result, the Fermat test will never work correctly with these numbers. No matter how many coprime bases are used, the result is always probable prime, which, on the surface, seems to be overwhelming evidence for primality.

The number 561 is the smallest Carmichael number. Carmichael numbers are rare. For example, there are only 20,138,200 Carmichael numbers below $10^{21}$ . Randomly picking one number below $10^{21}$ , the chance of picking a Carmichael number is roughly 1 in 50 trillion. However, it was proven in 1994 that there exists infinitely many Carmichael numbers. The small Carmichael numbers are not an issue. There is no risk that we will mistake 561 as a prime number. There are large Carmichael numbers with large prime factors. For example, the following 397-digit number is a Carmichael number.

The above number is a strong pseudoprime to all the prime bases up to 300 (large Carmichael numbers are discuseed here).

The only way to deal with the Carmichael numbers would be through factoring, which can be difficult if the number is large or through finding a common divisor between the Carmichael number and the modulus $n$ as described in Step 2 in the Fermat algorithm.

A Limited Probabilistic Primality Test

Though Carmichael numbers present a huge challenge for the Fermat test, the Fermat test is actually quite effective with the first type of pseudoprimes, which are integers that are pseudoprimes to some bases but not to all bases, i.e., integers that have at least one Fermat witness. A natural question is this. For a given composite number of this type, how many bases are there to which the given composite number is not a pseudoprime? Given one Fermat witness for $n$ , how many other coprime bases are also Fermat witnesses? It turns out that if $n$ is not a pseudoprime to at least one base, there is at least a 50% chance of finding another one if the base is chosen at random. This is described in the following theorem, which is given in two versions, one in terms of pseudoprimes and one in terms of Fermat witnesses.

Theorem 1
Let $n$ be a composite positive integer such that it is not a pseudoprime to at least one base. In other words, $n$ is not a Carmichael number. Then $n$ is not a pseudoprime to at least half of the coprime bases within the interval $\{2, 3, \cdots,n-1 \}$ . In other words, $n$ can be a pseudoprime to at most half of the coprime bases within the interval $\{2, 3, \cdots,n-1 \}$ .

Theorem 1 (Fermat witness version)
Let $n$ be a composite positive integer such that there exists a Fermat witness for $n$ . In other words, $n$ is not a Carmichael number. Then at least half of the coprime bases within the interval $\{2, 3, \cdots,n-1 \}$ are Fermat witnesses for $n$ . In other words, at most half of the coprime bases within the interval $\{2, 3, \cdots,n-1 \}$ are not Fermat witnesses for $n$ .

The proof of Theorem 1 is found in a previous post (see Theorem 1 here). The theorem shows that the Fermat test is quite good at producing a correct result when testing a composite number that is not a Carmichael number. Simply apply the Fermat test using several random chosen bases. When a base is chosen at random, there is at least a 50% chance that $n$ will be detected as composite (if $n$ is composite). In other words, there is at most a 50% error probability of not finding a Fermat witness. Using $k$ randomly chosen bases, the error probability is at most $0.5^k$ , which is practically zero if $k$ is reasonably large. The Fermat test is efficient and accurate when testing compositeness as long as the test number is the first type of false positives (there is at least one base to which the number is not a pseudoprime; there is at least one Fermat witness). In this limited sense, the Fermat test is a Monto Carlo algorithm. Of course, the Fermat test is not truly a randomized algorithm since it is not able to handle the Carmichael numbers.

There is a slightly different way to view Theorem 1. Recall that the Euler’s Phi function $\Phi(n)$ is the number of integers in the set $\{ a: 1 \le a<n \}$ that are coprime to $n$ (relatively prime to $n$ ). Theorem 1 can be restated as follows.

Theorem 1a
Let $n$ be a composite positive integer such that it is not a pseudoprime to at least one base. Then $n$ is not a pseudoprime to at least $\frac{\Phi(n)}{2}$ many bases in the set $\{ a: 1 \le a<n \}$ .

When $\Phi(n)$ is known, we can have a more precise bound on the number of bases that may prove the compositeness of the integer $n$ .

To illustrate Theorem 1a, we use a small composite integer of 21. The value of the Phi function is $\Phi(12)=12$ . The 12 numbers that are coprime to 21 are 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, and 20. Of these 12 numbers, Theorem 1a says that at least 6 of these numbers are Fermat witnesses for 21.

Base	Base Raised to 20 Modulo 21	Fermat Witness
1	1
2	$2^{20} \equiv 4 \ (\text{mod} \ 21)$	Yes
4	$4^{20} \equiv 16 \ (\text{mod} \ 21)$	Yes
5	$5^{20} \equiv 4 \ (\text{mod} \ 21)$	Yes
8	$8^{20} \equiv 1 \ (\text{mod} \ 21)$
10	$10^{20} \equiv 16 \ (\text{mod} \ 21)$	Yes
11	$11^{20} \equiv 16 \ (\text{mod} \ 21)$	Yes
13	$13^{20} \equiv 1 \ (\text{mod} \ 21)$
16	$16^{20} \equiv 4 \ (\text{mod} \ 21)$	Yes
17	$17^{20} \equiv 16 \ (\text{mod} \ 21)$	Yes
19	$19^{20} \equiv 4 \ (\text{mod} \ 21)$	Yes
20	$20^{20} \equiv 1 \ (\text{mod} \ 21)$

Theorem 1a indicates that there are at least 6 Fermat witnesses for 21. The above table shows that there are 8 Fermat witnesses, which exceeds the the lower bound of 6. Theorem 1 indicates that there 21 is a pseudoprime to at most 6 bases. The above table shows that 21 is a pseudoprime to 4 bases.

The Fermat test works well. It is a good introduction to primality testing. The Fermat test is very accurate for the all prime numbers and for the composite numbers with at least one Fermat witness. However, it will completely fail to detect the Carmichael numbers. Any one who is concerned about the rare chance of a false positive in the form of a Carmichael number should use a more robust test such as the Miller-Rabin test.

See here for an introduction on Carmichael numbers. A prior discussion of the Fermat test can be found here. See here for a discussion on the Miller-Rabin test.

$\text{ }$

Dan Ma Fermat primality test

Daniel Ma Fermat primality test

Dan Ma Carmichael numbers

Daniel Ma Carmichael numbers

Mathematical Cryptography

focusing on the math in public key cryptography

Monthly Archives: November 2022

Miller-Rabin Primality Test

The Fermat Test of Primality