Fermat’s Little Theorem as a primality testing

Armed with an understanding a theorem of Fermat and a calculator or software that can handle large numbers, any interested individual can carry out exercises in primality testing – checking whether or not a number is prime. No advanced study in number theory is required. In this post, we explain how this is done. This post is built on two previous posts on detecting composite numbers and the fast powering algorithm.

___________________________________________________________________________

Fermat’s Little Theorem

This is called the little theorem so that it is not confused with the other theorem of Fermat whose proof took three and a half centuries. The little theorem of Fermat describes a property that is possessed by all prime numbers. It says: if n is a prime number, then a certain property is true for the number n. Turning this around, if that property is not true for a number n, that number n must not be prime (i.e. it must be composite). This approach is a great way to prove the compositeness of a number. It is also a great way to gather evidence to support the primality of a number.

Two number are relatively prime to each other if they do not have any common factor that is greater than 1. For example, 28 is relatively prime to 15 even though neither one of them is prime. Similarly 17 and 35 have no factors in common. So they are relatively prime to each other.

The notation P \equiv Q \ (\text{mod} \ n) means that P and Q differ by a multiple of n, i.e. P-Q=n k for some integer k. The notation is read P is congruent to Q modulo n. The statement of Fermat’s theorem uses the notation a^{n-1} \equiv 1 \ (\text{mod} \ n). This would mean that a^{n-1}-1=n k for some integer k. This means that a^{n-1}-1 divisible by n.

Here’s the statement of Fermat’s little theorem.

    Fermat’s Little Theorem
    If n is a prime number, then a^{n-1} \equiv 1 \ (\text{mod} \ n) for all numbers a that are relatively prime to n.

___________________________________________________________________________

Fermat’s Test

The theorem says that if n is a prime number, 2^{n-1} \equiv 1 \ (\text{mod} \ n) and 3^{n-1} \equiv 1 \ (\text{mod} \ n) and so on. The flip side is that if we can find a number a such that a^{n-1} \not \equiv 1 \ (\text{mod} \ n), then we have convincing proof that n is not a prime number.

When we need to determine whether or not a number n is prime, we pick a value a and calculate a^{n-1} \ (\text{mod} \ n). If the calculated result is not 1, then we have a convincing proof that the number n is not prime. If a^{n-1} \equiv 1 \ (\text{mod} \ n), then the number n is said to be a probable prime to base a. When n is a probable prime to base a, we also say that n passes the Fermat-a test. Fermat’s little theorem can then be restated as:

    Fermat’s Little Theorem
    If n is a prime number, then n passes Fermat-a test for all possible choices of a.

Example 1
This previous post discusses the following 204-digit number.

    N=
    34526903293921580314641092817369674040684481568423
    96721012992064214519445919256941544565276067662360
    10874972724155570842527652727868776362959519620872
    73561220060103650687168112461098659687818073890148
    6527

It can be verified that 2^{N-1} \equiv W \ (\text{mod} \ N) where W is not 1 and is the following 203-digit number.

    W=
    33345811005959530251539697392827903173946066773819
    70645616725285996925661000056829272733579262095715
    97827398131150054514508640724258354848985651127636
    92970799269335402819507605691622173717318335512037
    458

The number N in this example fails the Fermat-2 test and is thus a composite number. The calculation of 2^{N-1} \equiv W \ (\text{mod} \ N) is carried out by using the fast powering algorithm.

Example 2
Consider M= 982447387. Is it prime?

Calculate a^{M-1} \ (\text{mod} \ M) for several values of a. let’s start with 2. We find that 2^{M-1} \equiv 1 \ (\text{mod} \ M). So we say that the number M is a probable prime to base 2. It is very likely that M is a prime. Let’s try a few more values of a. We have the following results.

    3^{M-1} \equiv 1 \ (\text{mod} \ M)

    5^{M-1} \equiv 1 \ (\text{mod} \ M)

    7^{M-1} \equiv 1 \ (\text{mod} \ M)

Now M is a probable prime to the bases 2, 3, 5, and 7. It turns out that there are actually composite numbers that are probable primes to bases 2, 3, 5 and 7. But they are extremely rare. So the number M is a probable prime (meaning that the chance that it is not a prime is very negligible). For good measure, we generate 5 random values of a. They are:

    323064262
    866079494
    599071122
    773037193
    247321577

Calculating a^{M-1} \ (\text{mod} \ M) for all 5 values show that the number M passes the Fermat-a test for all 5 values of a. At this point we are willing to conclude that M is a prime. The conclusion is based on a probability argument and is not based on a mathematical proof.

Since the number M is a 9-digit number, we can actually conclude that it is a prime by looking it up in lists of primes that are published online. So this is a toy example that is meant for illustration only.

___________________________________________________________________________

Remarks

Example 1 shows that failing the Fermat-a test just for one value of a is enough to conclude that the number in question is not prime. In general, to test the primality of a number n, carry out the Fermat-a test for several values of a (preferably randomly chosen). If n fails the Fermat-a test for one of the values of a, then n is composite. On the other hand, if n passes the Fermat-a test for all the chosen values of a, then n is a probable prime.

The Fermat test is the “entry level” primality test. It is easy to use. It often works correctly. But it can produce incorrect results on rare occasions. For a more in depth discussion of the Fermat’s primality test, we refer you to an article in another blog.

___________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}

Advertisements

An easy method for detecting composite numbers

How do you test whether a number is a prime number? Trial division is in use since antiquity and is easy to understand. This is the process of dividing the number in question by each prime number that is smaller than it. If a smaller factor is found, then it is not a prime number (i.e. is a composite number). If no smaller factors can be found, then the number is a prime numbers. However numbers routinely used in encryption algorithms today have hundreds or even thousands of decimal digits. Factoring such large numbers is really a hard problem. If we just want to know whether a number is prime or not, the answer can be obtained very quickly. In this post we showcase a calculation that can be used for checking whether a whole number is prime or composite without actually finding any factor. This method is based on a theorem of Fermat and can be implemented using the fast powering algorithm.

___________________________________________________________________________

Examples

Example 1
The author of a recent article came across the following 204-digit number that he incorrectly asserted as a prime number.

    N=
    34526903293921580314641092817369674040684481568423
    96721012992064214519445919256941544565276067662360
    10874972724155570842527652727868776362959519620872
    73561220060103650687168112461098659687818073890148
    6527

It turns out that showing the number N is composite is not difficult. The idea is what can be called the Fermat-2 test: if N is a prime number, then 2^{N-1} \equiv 1 \ (\text{mod} \ N), meaning that 2^{N-1}-1 is divisible by N, or equivalently the remainder is 1 when 2^{N-1} is divided by N. Using the fast powering algorithm, the exponentiation 2^{N-1} modulo N is turned into a series of squarings and multiplying. The result is that 2^{N-1} \equiv W \ (\text{mod} \ N) where W is the following 203-digit number:

    W=
    33345811005959530251539697392827903173946066773819
    70645616725285996925661000056829272733579262095715
    97827398131150054514508640724258354848985651127636
    92970799269335402819507605691622173717318335512037
    458

If N were a prime number, then 2^{N-1} modulo N is 1. But 2^{N-1} modulo N is clearly not 1. Therefore N must be composite. We do not show the steps that produce the 203-digit number W. In carrying out the square-and-multiply algorithm, there are 676 squarings and 327 multiplications. The process runs quickly when it is implemented on a computer. In the next example, we work a small example to illustrate how the fast powering algorithm works.

Example 2
Let’s do a smaller example to demonstrate the idea of the Fermat-2 test and the calculation of the fast powering algorithm (also called the square-and-multiply algorithm). Consider the number 55289. Is it a prime number?

We show that 2^{55288} \equiv 8349 \ (\text{mod} \ 55289). So 55289 is not a prime (otherwise 2^{55288} would be 1 modulo 55289). To show 2^{55288} \ (\text{mod} \ 55289), the first step is to express the exponent 55288 in its binary expansion.

    55288=2^3+2^4+2^5+2^6+2^7+2^8+2^9+2^{10}+2^{12}+2^{14}+2^{15}

Step 2 is to perform a series of 15 squarings (15 is the highest power of 2 in the binary expansion of the exponent 55288). Step 3 is to perform a series of multiplications. Both steps are shown in the following table.

Example 2 Results

\left[\begin{array}{rrrrr}      i & \text{ } & \text{Squaring} & \text{ } & \text{Multiplying} \\      \text{ } & \text{ } \\      0 & \text{ } & 2 & \text{ } & \text{ } \\      1  & \text{ } & 4 & \text{ } & \text{ } \\      2  & \text{ } & 16 & \text{ } & \text{ } \\      3  & \text{ } & 256* & \text{ } & 256 \\      4  & \text{ } & 10247* & \text{ } & 24649 \\      5  & \text{ } & 7198* & \text{ } & 1101 \\      6  & \text{ } & 5411* & \text{ } & 41588 \\      7  & \text{ } & 31040* & \text{ } & 3948 \\      8  & \text{ } & 15486* & \text{ } & 44383 \\      9  & \text{ } & 27803* & \text{ } & 40647 \\      10  & \text{ } & 11300* & \text{ } & 25377 \\      11  & \text{ } & 27699 & \text{ } & \text{ } \\      12  & \text{ } & 44437* & \text{ } & 3305 \\      13  & \text{ } & 334 & \text{ } & \text{ } \\      14  & \text{ } & 978* & \text{ } & 25528 \\      15  & \text{ } & 16571* & \text{ } & 8349      \end{array}\right]

The column for squaring starts with 2, the base of the exponentiation 2^{55288}. Each number in that column is the square of the preceding number and is reduced modulo 55289. The numbers with asterisks refer to the positions that are 1s in the binary expansion of 55288. The third column shows the multiplications of the numbers with asterisks in the second column.

Example 3
Consider the following 309-digit number:

    RSA-1024
    13506641086599522334960321627880596993888147560566
    70275244851438515265106048595338339402871505719094
    41798207282164471551373680419703964191743046496589
    27425623934102086438320211037295872576235850964311
    05640735015081875106765946292055636855294752135008
    52879416377328533906109750544334999811150056977236
    890927563

This example is an RSA number called RSA-1024. It is a 1024-bit (309-digit in decimal). It is a product of two prime numbers and thus is not a prime number. Indeed, 2^{N-1} \equiv T \ (\text{mod} \ N) where N is RSA-1024 and T is the following number:

    T=
    12093909443203361586765059535295699686754009846358
    89512389028083675567339322020593385334853414711666
    28419681241072885123739040710771394053528488357104
    98409193003137847878952260296151232848795137981274
    06300472693925500331497519103479951096634123177725
    21248297950196643140069546889855131459759160570963
    857373851

Clearly, RSA-1024 does not pass the Fermat-2 test and is thus a composite number. Yet RSA-1024 has not yet been factored. It is not expected to be factored in decades to come barring a dramatic breakthrough in computing technology. This example points to the principle on which the RSA cryptosystem is based, that

    It is relatively easy to decide whether or not a number is prime. But it is hard to find the prime factors of a given composite number.

In short, primality testing is easy while factoring is hard. In any case, the examples of RSA-1024 and other RSA numbers are empirical evidence that factoring is a hard problem.

___________________________________________________________________________

Remarks

The Fermat-2 test used here is based on Fermat’s Little Theorem, which is discussed in the next post.

___________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}