October | 2022 | Mathematical Cryptography

This is an attempt to look at the Fermat primality test in the context of the confusion matrix. This provides another view point of the Fermat Little Theorem and Carmichael numbers.

A primality test is an algorithm for determining whether a positive integer is a prime number. Primality testing is at heart a classification problem, which is to sort an observation (an integer) as prime or not prime or a set of observations into those that are prime and those not prime. The algorithms for primality testing are usually mathematical and not statistical. In predictive analytics, classification models are used to predict whether an outcome has occurred (e.g., whether a claim submitted to an insurer is a fraudulent claim). Medical testing is also a classification model (whether a person being tested has a disease or is healthy). A confusion matrix is a tool for evaluating the predictive performance of a classification model such as claim fraud detection and medical testing. In this post, we would like to view primality testing, as a classification model, in the context of the confusion matrix. The primality test is the Fermat test. The confusion matrix angle will help us gain insight on the Fermat test by seeing the Fermat Little Theorem and the Carmichael numbers in a new angle.

A confusion matrix is a 2×2 matrix displaying the 4 outcomes in a classification problem – in this instance, a prime number classified as a prime (true positive, abbreviated TP), a prime number classified as a composite (false negative, abbreviated FN), a composite number classified as a composite (true negative, abbreviated TN) and a composite number classified as a prime (false positive, abbreviated ad FP).

There are 2 rows and 2 columns in the confusion matrix (the above diagram), with the 4 cells displaying the counts of the observations in each of the 4 categories. The sum of a column is the total number of observations in a class in the actual classifications (prime or composite). The sum of a row is the total number of observations in a predicted class (prime or composite). The two light green cells represent the correct classifications (TN and TP). The light pink cells represent the incorrect classifications (FP and FN). The name confusion matrix stems from the fact that the 4 cells in the 2×2 matrix makes it easy to see whether the classification model is confusing the two classes, i.e., the matrix shows clearly the extent of the misclassifications.

The Fermat Little Theorem describes a property common to all prime numbers, which is the mathematical basis of the Fermat primality test. The following is the statement of the theorem.

Fermat Little Theorem (FLT)

$p$

$a$

$p$

$a^{p-1} \equiv 1 \ (\text{mod} \ p)$

The theorem does not say much about the base $a$ other than that $a$ and $p$ are relatively prime, i.e., there is no common divisor between the base $a$ and $p$ other than 1. Whenever the congruence relationship holds, i.e., $a^{p-1} \equiv 1 \ (\text{mod} \ p)$ , we say that $p$ is a probable prime to the base $a$ . Note that any prime number would be a probable prime to all bases $a$ . Whenever $p$ is a probable prime to the base $a$ and in reality $p$ is composite, we say $p$ is a pseudoprime to the base $a$ .

To use Fermat Little Theorem as a primality test, choose a base $a$ that is relatively prime to the $p$ in question. Raise $a$ to the power of $p-1$ modulo $p$ . If the result is not congruent to 1, then we prove conclusively that $p$ is composite (if $p$ were prime, the result would be congruent to 1 according to the FLT). If the result is congruent to 1, we declare that $p$ is a probable prime to the base $a$ . For the sake of simplicity just for the illustration here, we declare $p$ is prime if $p$ is a probable prime to the base $a$ . Ideally, the more bases we use, the more confidence we will have in the conclusion. If $p$ is probable prime to several bases (preferably randomly choses bases), then we will have more confidence in declaring $p$ is prime. To keep things simple, we use only one base, which is $a=2$ .

As discussed above, we will use a simplified form of the Fermat test. If $p$ is the number to be tested, the key calculation is to raise 2 to the power of $p-1$ modulo $p$ . If the result is not 1, we prove that $p$ is composite. If the result is congruent to 1, we declare that $p$ is prime. We perform the calculation for 20 10-digit positive integers. Two raised to a 10-digit number may look intimidating but it can be efficiently performed using a method called the fast powering algorithm or square-and-multiply (see here). The results are displayed in the following table.

Input Number	Actual	Predicted	2 raised to p-1 modulo p
1053594241	Composite	Composite	1044515830
1080787909	Prime	Prime	1
2030444287	Prime	Prime	1
2113733797	Composite	Composite	64
2124749677	Prime	Prime	1
3215031751	Composite	Prime	1
3575121289	Prime	Prime	1
4422322321	Composite	Composite	3609114070
4922894533	Prime	Prime	1
5748693121	Composite	Composite	1686537493
5971357789	Prime	Prime	1
6829547103	Composite	Composite	67108864
6979981769	Prime	Prime	1
7691546233	Composite	Composite	64
7971295931	Prime	Prime	1
8439563243	Composite	Composite	8264595133
8757193191	Composite	Composite	4317052243
8803424081	Prime	Prime	1
9876541023	Composite	Composite	256
9889920763	Prime	Prime	1

The first number in the table, 1053594241, is a composite number. The test confirmed that it is composite since the result of the congruence exponentiation is congruent to something other than 1 modulo $p$ . The number 1053594241 is counted as a True Negative (TN). The second number in the table, 1080787909, is known to be a prime number and the test predicted it as prime since the result of the congruence exponentiation is precisely 1, which is a property possessed by all prime numbers. As a result, the number 1080787909 is counted as a True Positive (TP). In the above table, all of the actual prime/composite status matches the predicted status, except for one number (the one highlighted in red). The input number 3215031751 is composite with prime factors 151, 751 and 28351. Yet the Fermat test (the simplified one used here) says that it is a prime. The number 3215031751 is then a False Positive (FP). The results are tabulated in the following confusion matrix.

Confusion Matrix

	Actual Composite	Actual Prime
Predicted Composite	9	0
Predicted Prime	1	10

The right column of the confusion matrix display all the actual prime numbers. The Fermat test would classify all actual prime numbers as prime. According to FLT, 2 raised to the power of $p-1$ would have to be 1 modulo $p$ for all primes $p$ . As a result, the cell for FN (top right) is 0. Therefore, the Fermat test is 100% accurate on the actual prime numbers. The accuracy of a test on the positive observations is called the sensitivity. For the Fermat test, the sensitivity is 1 (100%). In other words, the Fermat test will never produce a False Negative (FN). On the left column of the matrix, 9 of the 10 actual composite numbers are predicted correctly. The Fermat test in this instance is 90% correct on the actual composite numbers in the sample. The accuracy of a test on the negative observations is called the specificity. The Fermat test in this instance has a specificity of 0.9 (90%). In this example, the Fermat test makes 19 correct predictions (9 TNs and 10 TPs) out of 20. Thus, the overall accuracy (or just accuracy) is 0.95 (95%).

The confusion matrix provides many measures of prediction performance of a classifier. In this example, we focus on three measures – accuracy, sensitivity and specificity. Accuracy is the proportion of the observations that are predicted correctly (in this example, composite numbers predicted as composite numbers and prime numbers predicted as prime numbers). The accuracy is 0.95 (19 correct predictions out of 20). Sensitivity is the proportion of the positive observations that are predicted positive by the classifier. This measures how sensitive the test is to detect what it is supposed to (in this example detecting prime numbers). For the Fermat test, the sensitivity is 1 (100%) as noted above. This is because the Fermat Little Theorem guarantees that for any number being tested, if it is a prime number, the test will predict prime. Having a sensitivity of 1 means that the Fermat test is a perfectly accurate classifier in detecting prime numbers.

Specificity is the proportion of the negative observations that are predicted negative (in this example, composite numbers that are predicted composite). This measures how well the test is able to identify negative observations (in this example, to identify composite numbers). The specificity is 0.9 (of the 10 composite numbers, only 9 are predicted correctly).

This example shows that though the specificity is high at 90%, the test can produce false positive. An ideal classifier would be one that has both high sensitivity and high specificity. We know that the Fermat test has 100% sensitivity. In order to improve the specificity, it makes sense to examine the false positives that are produced by the Fermat test.

Consider the composite number 341 = 11 x 31. Using the simplified Fermat test used here, $2^{340} \equiv 1 \ (\text{mod } \ 341)$ . The number 341 is a pseudoprime to the base 2 and is a false positive. Using base 3 instead, we have $3^{340} \equiv 56 \ (\text{mod } \ 341)$ . Then the Fermat test would conclude that 341 is a composite number. This shows that the Fermat test is best carried out with multiple bases, preferably bases that are randomly chosen. Another example: $n$ = 25,326,001 = 2251 x 11251. Using the Fermat test, we have $a^{n-1} \equiv 1 \ (\text{mod } \ n)$ for $a = 2, 3, 5$ . Using the first 3 prime numbers as bases, the Fermat test would declare 25,326,001 as prime. However, using base 7, $7^{n-1} \equiv 5872860 \ (\text{mod } \ n)$ , proving that 25,326,001 is indeed a composite number. This example further shows that to use the Fermat test effectively, we need to apply it on several randomly choses bases $a$ .

The preceding paragraph seems to say that if the Fermat test is applied using enough bases, it will be able to detect composite numbers, hence raising the specificity to something close to 1 if not exactly 1. Let’s discuss the one false positive in this example, which is the number 3215031751. It is a composite number with 3 prime factors with 3215031751 = 151 x 751 x 28351. The simplified Fermat test used here shows that 2 raised to this number less 1 modulo this number is 1. This means that 3215031751 is a pseudoprime to the base 2. Using only base 2, the Fermat test gives a prediction of prime, which is incorrect. Would we be able to detect its compositeness if we use more bases? How about randomly choose 10 bases $a$ that are relatively prime to 3215031751. It turns out that numbers like 3215031751 are the biggest issue with the Fermat primality test. It does not matter what the base $a$ is, as long as it is relatively prime to 3215031751, this always holds: $a^{3215031750} \equiv 1 \ (\text{mod } \ 3215031751)$ .

The number 3215031751 is immune to detection by the Fermat test, regardless of how many bases are used. With the Fermat test, the only way to detect the compositeness of 3215031751 is to stumble upon a base $a$ that is not relatively prime to 3215031751. That means $a$ has a prime factor in common with 3215031751. In this case, we would need to keep trying different bases until we get to 151. This may be doable since the number 3215031751 is relatively small and its prime factors are relatively small. What if we are testing a number that is large with hundreds of decimal digits whose large prime factors are large? Then Fermat test is likely not a workable option for testing primality and compositeness.

Any number like 3215031751 is called a Carmichael number. A composite positive integer $n$ is a Carmichael number if $a^{n-1} \equiv 1 \ (\text{mod } \ n)$ always holds for any base $a$ that is relatively prime to $n$ . In other words, a Carmichael number is a composite number that always satisfies the conclusion of the Fermat Little Theorem. As a result, Carmichael numbers will always be classified as prime by the Fermat test.

Thus far, we have identified two types of false positives that can result from applying the Fermat test. One is like 341 or 25,326,001 discussed above. If these composite numbers are classified as prime, the issue can be fixed by applying the Fermat test using more bases. For these composite numbers, the Fermat test can potentially predict correctly if more calculation is done. The other type of false positives is the Carmichael numbers. With Carmichael numbers, the Fermat test is totally ineffective.

If the number being tested is a Carmichael number (but we do not know that in advance), the Fermat test will predict prime even if we use many randomly chosen bases. This will be a false positive that cannot be remedied by performing more calculation with more bases. The smallest Carmichael number is 561. Carmichael numbers are rare. A recent search found that there are $\text{20,138,200}$ Carmichael numbers between 1 and $10^{21}$ , about one in 50 trillion numbers (documented in this Wikipedia entry on Carmichael numbers). However, there are infinitely many Carmichael numbers across the entire number line. If the numbers being tested are random chosen, it is not likely for the test sample to include Carmichael numbers. But if the desire is to eliminate the nuisance of Carmichael numbers, another primality test that is more robust should be used, for example, the Miller-Rabin test.

See here for an introduction on Carmichael numbers. See here for a more indepth discussion of the Fermat test. See here for an introduction 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: October 2022

Fermat primality test and the confusion matrix