Mersenne Prime

A Mersenne number is an integer that is one less than a power of 2, i.e. it is of the form 2^n-1 where n is a positive integer. A Mersenne prime number (or a Mersenne prime) is a Mersenne number that happens to be a prime number. This post is a brief discussion on Mersenne prime.

Because Mersenne numbers are exponential, they increase very rapidly. The first several Mersenne numbers 2^n-1 starting with n = 2.

    3, 7, 15, 31, 63, 127, 255, 511, 1,023, 2,047, 4,095, 8,191, 16,383, 32,767, ……

It is clear from these examples that not all Mersenne numbers are prime (e.g. 15 and 63). In the above list, the numbers in red are prime and the ones in blue are composite. Note that the ones with composite exponent n are composite: 15 (n = 4), 63 (n = 6), 255 (n = 8), 511 (n = 9) …. This is no coincidence.

Whenever n is composite, the Mersenne number 2^n-1 is also composite.

The fact follows from the following identity.

    \displaystyle \begin{aligned} 2^{ab}-1&=(2^a-1) \ (1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a}) \\&=(2^b-1) \ (1+2^b+2^{2b}+2^{3b}+\cdots+2^{(a-1)b})  \end{aligned}

Thus if we are interested in finding numbers 2^n-1 that are prime, we must start with an exponent n that is prime. For ease of discussion, define M_p=2^p-1 and assume that p is prime.

Mersenne primes have a long history. Long before the computer age, people had been doing primality testing on Mersenne numbers. The first four Mersenne primes M_p, for p = 2, 3, 5, and 7, were known in antiquity. The next Mersenne prime M_{13} was discovered before 1461. People at that time thought that M_p is prime whenever p is prime. In 1536, Hudalricus Regius found that M_{11}=2^{11}-1=2047=23 \times 89. In 1603, Pietro Cataldi showed that M_p is prime for p = 17 and 19.

The name of Mersenne prime was due to the connection with the French monk Marin Mersenne. In his 1644 book Cognita Physico-Mathematica, Mersenne stated that M_p is prime when p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257. Some of these claims were later determined to be wrong. His list also missed some correct Mersenne primes. From then on, his name was attached to this particular type of prime numbers.

The next discovery of a Mersenne prime (after Pietro Cataldi), M_{31}, was made by Leonhard Euler in 1772. The one found after Euler’s, M_{127}, was made by Edouard Lucas in 1876. There were three more Mersenne primes discovered before the computer age – M_{61} in 1883 by Ivan Pervushin, M_{89} and M_{107} by R. E. Powers in 1911 and 1914, respectively.

In the pre-computer age, there were long stretches of time in between discoveries of Mersenne primes. For example, it took almost 200 years after Pietro Cataldi for the next Mersenne prime to emerge (discovered by Euler). There were about 100 years in between Euler’s discovery and Lucas’ discovery.

Another important contribution made by Lucas is a test that he developed to test Mersenne numbers to see if they are prime. The test was originally developed in 1856 and later improved by him in 1878. It was further improved by Derrick Henry Lehmer in the 1930s. The test is now known as the Lucas-Lehmer test.

Lucas-Lehmer Test. Define a sequence of positive integers S_0, S_1, S_2, S_3, \cdots such that S_0=4 and S_j=S_{j-1}^2-2 where j \ge 1. Suppose that p \ge 3. Then M_p=2^p-1 is a Mersenne prime if and only if M_p divides S_{p-2}.

To perform the test, start with S_0=4 and recursively calculate S_j=S_{j-1}^2-2 until S_{p-2} is obtained. Then perform the division of S_{p-2} by M_p. If S_{p-2} is divisible by M_p, then M_p is prime. If S_{p-2} is not divisible by M_p, then M_p is composite. It is interesting that when M_p is found to be composite in this manner, the compositeness of M_p is established without finding any prime factors of M_p.

The computer discoveries of Mersenne primes began in 1952 by Raphael Robinson. The Lucas–Lehmer test is the primality test used by the Great Internet Mersenne Prime Search (GIMPS) to discover large primes. GIMPS is a distributed computing project on the Internet for finding large prime numbers.

As of the writing of this post (May 25, 2017), a total of 49 Mersenne primes had been discovered. The latest one is M_{74207281}, with over 22 million digits, which was found in January 2016.

Despite of the computation advance, there are still many fundamental questions that are still not known about Mersenne primes. For example, how many Mersenne primes are there? It is not even known whether the set of Mersenne primes is finite or infinite. It is also not known whether infinitely many Mersenne numbers with prime exponents are composite.

Because of the Lucas-Lehmer test, whenever someone finds a new largest prime number, it is usually a Mersenne prime. So every few years or so, Mersenne prime is on the news for the reason of being discovered. For up-to-date information or to learn more about basic facts, go to the Mersenne prime website and the Wikipedia entry on Mersenne primes.

____________________________________________________________________________
\copyright 2017 – Dan Ma

Advertisements

Using Fermat’s Little Theorem to Test Primality

Fermat’s little theorem describes a property that is common to all prime numbers. This property can be used as a way to detect the “prime or composite” status of an integer. Primality testing using Fermat’s little theorem is called the Fermat primality test. In this post, we explain how to use this test and to discuss some issues surrounding the Fermat test.

___________________________________________________________________

Describing the test

The Fermat primality test, as mentioned above, is based on Fermat’s little theorem. The following is the statement of the theorem.

    Fermat’s little theorem
    If n is a prime number and if a is an integer that is relatively prime to n, then the following congruence relationship holds:

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

The above theorem indicates that all prime numbers possess a certain property. Therefore if a given positive integer does not possess this property, we know for certain that this integer is not prime. Suppose that the primality of an integer n is not known. If we can find an integer a that is relatively prime to n such that a^{n-1} \not \equiv 1 \ (\text{mod} \ n), then we have conclusive proof that n is composite. Such a number a is said to be a Fermat witness for (the compositeness of) n.

The Fermat test is closedly linked to the notations of probable primes and pseudoprimes. If the congruence relation (1) is true for n and a, then n is said to be a probable prime to base a. Furthermore, if n happens to be a composite number, then n is said to be a pseudoprime to base a. Pseudoprime prime is a composite number that possesses the prime-like property as indicated by (1) for one base a.

The Fermat primality test from a compositeness perspective is about looking for Fermat witnesses. If a Fermat witness is found, the number being tested is proved to be composite. On the other hand, the Fermat primality test, from a primality perspective, consists of checking the congruence relation (1) for several bases that are randomly selected. If the number n is found to be a probable prime to all the randomly chosen bases, then n is likely a prime number.

If the number n is in reality a prime number, then the Fermat test will always give the correct result (as a result of Fermat’s little theorem). If the number n is in reality a composite number, the Fermat test can make the mistake of identifying the composite number n as prime (i.e. identifying a pseudoprime as a prime). For most composite numbers this error probability can be made arbitrarily small (by testing a large number of bases a). But there are rare composite numbers that evade the Fermat test. Such composite numbers are called Carmichael numbers. No matter how many bases you test on a Carmichael number, the Fermat test will always output Probably Prime. Carmichael numbers may be rare but there are infinitely many of them over the entire number line. More about Carmichael numbers below.

The following describes the steps of the Fermat primality test.

    Fermat primality test
    The test is to determine whether a large positive integer n is prime or composite. The test will output one of two results: n is Composite or n is Probably Prime.

  • Step 1. Choose a random integer a \in \left\{2,3,\cdots,n-1 \right\}.
  • Step 2. Compute \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 a.
      • Output n is Probably Prime and stop.

    \text{ }

The exponentiation in Step 3 can be done by the fast powering algorithm. This involves a series of squarings and multiplications. Even for numbers that have hundreds of digits, the fast powering algorithm is efficient.

One comment about Step 2 in the algorithm. Step 2 could be called the GCD test for primality. If you can find an integer a such that 1<a<n and such that \text{GCD}(a,n) \ne 1, then the integer n is certainly composite. Such a number a is called a GCD witness for the compositeness of n. So the Fermat test as described above combines the GCD test and the Fermat test. We can use the Euclidean algorithm to find the GCD. If we happen to stumble upon a GCD witness, then we can try another n for a candidate of a prime number. For most composite numbers, it is not likely to stumble upon a GCD witness. Thus when using the Fermat test, it is likely that Step 3 in the algorithm is used.

An example of Fermat primality testing is the post called A primality testing exercise from RSA-100.

____________________________________________________________________________

More about the test

When using the Fermat test, what is the probability of the test giving the correct result? Or what is the probability of making an error? Because the Fermat test is not a true probabilistic primality test, the answers to these questions are conditional. In one scenario which covers most of the cases, the test works like an efficient probabilistic test. In another scenario which occurs very rarely, the Fermat test fails miserably.

As with most diagnostic tests, the Fermat test can make two types of mistakes – false positives or false negatives. For primality testing discussed in this post, we define a positive result as the outcome that says the number being tested is a prime number and a negative result as the outcome that says the number being tested is a composite number. Thus a false positive is identifying a composite number as a prime number and a false negative is identifying a prime number as a composite number.

For the Fermat test, there is no false negative. If n is a prime number in reality, the statement of Fermat’s little theorem does not allow the possibility that n be declared a composite number. Thus if the Fermat test gives a negative result, it would be a true negative. In other words, finding a Fermat witness for n is an irrefutable proof that n is composite.

However, there can be false positives for the Fermat test. This is where things can get a little tricky. A composite number n is said to be a Carmichael number if the above congruence relationship (1) holds for all bases a relatively prime to n. In other words, n is a Carmichael number if a^{n-1} \equiv 1 (\text{mod} \ n) for all a that are relatively prime to n. Saying it in another way, n is a Carmichael number if there exists no Fermat witness for n.

The smallest Carmichael number is 561. Carmichael numbers are rare but there are infinitely many of them. The existence of such numbers poses a challenge for the Fermat test. If you apply the Fermat test on a Carmichael number, the outcome will always be Probably Prime. So the Fermat test will always give a false positive when it is applied on a Carmichael number. To put it in another way, with respect to Carmichael numbers, the error probability of the Fermat test is virtually 100%!

So should a primality tester do? To keep things in perspective, Carmichael numbers are rare (see this post). If the primality testing is done on randomly chosen numbers, choosing a Carmichael number is not likely. So the Fermat test will often give the correct results. For those who are bothered by the nagging fear of working with Carmichael numbers, they can always switch to a Carmichael neutral test such as the Miller-Rabin test.

___________________________________________________________________

One bright spot about the Fermat test

There is one bright spot about the Fermat test. When applying the Fermat test on numbers that are not Carmichael numbers, the error probability can be made arbitrarily small. In this sense the Fermat test works like a true probabilistic primality test. Consider the following theorem.

    Theorem 1
    Let n be a composite integer such that it is not a pseudoprime to at least one base (i.e. n has a Fermat witness). In other words, n is not a Carmichael number. Then n is not a pseudoprime to at least half of the bases a (1<a<n) that are relatively prime to n. In other words, n is a pseudoprime to at most half of the bases a (1<a<n) that are relatively prime to n.

Theorem 1 means that the Fermat test can be very accurate on composite numbers that are not Carmichael numbers. As long as there is one base to which the composite number is not a pseudoprime (i.e. as long as there is a Fermat witness for the composite number in question), there will be enough of such bases (at least 50% of the possible bases). As a result, it is likely that the Fermat test will find a witness, especially if the tester is willing to use enough bases to test and if the bases are randomly chosen. When a base is randomly chosen, there is at least a 50% chance that the number n is not a pseudoprime to that base (i.e. the Fermat test will detect the compositeness) or putting it in another way, there is at most a 50% chance that the Fermat test will not detect the compositeness of the composite number n. So if k values of a are randomly selected, there is at most 0.5^k probability that the Fermat test will not detect the compositeness of the composite number n (i.e. making a mistake). So the probability of a false positive is at most 0.5^k. For a large enough k, this probability is practically zero.

Proof of Theorem 1
A base to which n is a pseudoprime or not a pseudoprime should be a number in the interval 1<a<n that is relatively prime to n. If n is a pseudoprime to base a, then a raised to some power is congruent to 1 modulo n. For this to happen, a must be relatively prime to the modulus n. For this reason, when we consider a base, it must be a number that is relatively prime to the composite integer n (see the post on Euler’s phi function).

Let a be a base to which n is not a pseudoprime. We make the following claim.

    Claim
    If b is a number such that 1<b<n and such that n is a pseudoprime to base b, then n is not a pseudoprime to base a \cdot b.

Since both integers a and b are assumed to be relatively prime to n, the product a \cdot b is also relatively prime to n (see Lemma 4 in this post). Now consider the congruence (ab)^{n-1} \ (\text{mod} \ n), which is derived as follows:

    (ab)^{n-1} \equiv a^{n-1} \cdot b^{n-1} \equiv a^{n-1} \not \equiv 1 \ (\text{mod} \ n)

In the above derivation, we use the fact that n is not a pseudoprime to base a and n is a pseudoprime to base b. The above derivation shows that n is not a pseudoprime to base ab.

If n is not a pseudoprime to all bases in 1<w<n, then we are done. So assume that n is a pseudoprime to at least one base. Let b_1,b_2,\cdots,b_k enumerate all bases to which n is a pseudoprime. We assume that the b_j are all distinct. So b_i \not \equiv b_j \ (\text{mod} \ n) for all i \ne j. By the above claim, the composite number n is not a pseudoprime to all the following k numbers:

    a \cdot b_1, \ a \cdot b_2, \cdots, \ a \cdot b_k

It is also clear that a \cdot b_i \not \equiv a \cdot b_j \ (\text{mod} \ n) for i \ne j. What we have just shown is that there are at least as many bases to which n is not a pseudoprime as there are bases to which n is a pseudoprime. This means that n is not a pseudoprime to at least 50% of the bases that are relatively prime to n. In other words, as long as there exists one Fermat witness for n, at least 50% of the bases are Fermat witnesses for n. It then follows that n is a pseudoprime to no more than 50% of the bases relatively prime to n. \blacksquare

There is another way to state Theorem 1. Recall that Euler’s phi function \phi(n) is defined to be the number of integers a in the interval 1<a<n that are relatively prime to n. With this in mind, Theorem 1 can be restated as the following:

    Corollary 2
    Let n be a composite integer such that it is not a pseudoprime to at least one base. Then n is not a pseudoprime to at least \displaystyle \frac{\phi(n)}{2} many bases in the interval 1<a<n.

___________________________________________________________________

Concluding remarks

Of course, Theorem 1 works only for the composite numbers that are not pseudoprime to at least one base (i.e. they are not Carmichael numbers). When you test the compositeness of a number, you do not know in advance if it is Carmichael or not. On the other hand, if the testing is done on randomly chosen numbers, it is not likely to randomly stumble upon Carmichael numbers. The Fermat test works well for the most part and often give the correct results. If one is concerned about the rare chance of a false positive in the form of a Carmichael number, then the Miller-Rabin test will be a good alternative.

Note:
The original post was written in August 10, 2013. On March 29, 2015, this post is replaced with a blog post called The Fermat primality test from the companion math crypto blog.

___________________________________________________________________
\copyright \ \ 2013 - 2015 \ \text{Dan Ma}

An observation about Mersenne primes

This post concerns an observation about Mersenne primes. The observation will be made after presenting an example.

Mersenne numbers are integers of the form M_n=2^n-1 where n is a positive integer. If M_n is a prime number, then M_n is said to be a Mersenne primes. Not all Mersenne numbers are prime. Are there infinitely many Mersenne primes? No one has yet been able to resolve this question. As of the writing of this post, there are only 48 known Mersenne primes, the largest of which is M_p where p=57885161, discovered in January 25, 2013. The current largest known Mersenne prime is also the current largest known prime number.

___________________________________________________________________________________________________________________

Example

In this example, p=57885161. Since M_p is prime, it is obviously not divisible by any other prime numbers. In particular, M_p is not divisible by any smaller Mersenne primes. We demonstrate this using congruence modulo arithmetic.

We wish to point out that we are not trying to establish the primality of M_p (doing that would take a great amount of super computing resources). This is merely a simple example of working with Mersenne primes and an exercise in doing congruence modulo calculation.

First, show that M_p=2^p-1 is not divisible by the Mersenne prime 2^{19}-1=524287.

If M_p=2^p-1 is divisible by 2^{19}-1, M_p \equiv 0 \ (\text{mod} \ 2^{19}-1). So we need to show 2^p-1 \not \equiv 0 \ (\text{mod} \ 2^{19}-1) or 2^p \not \equiv 1 \ (\text{mod} \ 2^{19}-1).

Note that 2^{19} \equiv 1 \ (\text{mod} \ 2^{19}-1). So it is a matter of subtracting the largest multiple of 19 out of the exponent p=57885161. We have p=57885161=3046587 \cdot 19+8. We have the following congruence calculation.

    2^{57885161}=(2^{19})^{3046587} \cdot 2^8 \equiv (1)^{3046587} \cdot 2^8=2^8=256 \ (\text{mod} \ 2^{19}-1)

Since 2^p \equiv 256 \ (\text{mod} \ 2^{19}-1) and 256 \ne 1, M_p=2^p-1 is not divisible by 2^{19}-1=524287.

The number 2^{3217}-1 is also a Mersenne prime. To show that M_p=2^p-1 is not divisible by 2^{3217}-1, we only need to show 2^p \not \equiv 1 \ (\text{mod} \ 2^{3217}-1).

Note that 2^{3217} \equiv 1 \ (\text{mod} \ 2^{3217}-1). We have p=57885161=17993 \cdot 3217 + 1680. After subtracting multiple of 3217, we have the remainder 1680. Thus 2^{57885161} congruence modulo 2^{3217}-1 is reduced to 2^{1680} congruence modulo 2^{3217}-1.

    2^{57885161} \equiv 2^{1680} \ (\text{mod} \ 2^{3217}-1)

Since 2^{1680}>1, 2^p \not \equiv 1 \ (\text{mod} \ 2^{3217}-1). Thus M_p=2^p-1 is not divisible by 2^{3217}-1.

___________________________________________________________________________________________________________________

An Observation

The above examples lead to the following observation.

    If a and b are prime numbers such that a<b, then 2^a-1 is not a divisor of 2^b-1.

As in the examples, we need to show 2^b \not \equiv 1 \ (\text{mod} \ 2^a-1). Note that 2^a \equiv 1 \ (\text{mod} \ 2^a-1). According to the division algorithm, we have b=r + a \cdot k where k is some integer and r is the remainder with 0 \le r <a. The remainder r cannot be zero. If it is, a would divide b. But this cannot be since both of them are prime numbers. Since r \ne 0, 2^r>1. We have the following congruence calculation.

    2^b = (2^a)^{k} \cdot 2^r \equiv 2^r \ (\text{mod} \ 2^a-1)

Since 2^r>1, 2^b \not \equiv 1 \ (\text{mod} \ 2^a-1). Thus 2^b-1 is not divisible by 2^a-1.

The above derivation is definitely a much cleaner demonstration than the derivations shown in the above examples.

Another way to state the above statement is that no Mersenne number can be divisible by any smaller Mersenne number.

Note that in the above statement, 2^a-1 and 2^b-1 do not need to be primes. Only the exponents a and b need to be primes. There are many Mersenne numbers that are not prime numbers. The smallest is 2^{11}-1=28*89. Other smaller non-prime Mersenne numbers are 2^{23}-1 and 2^{29}-1.

So the above statement says that even when a Mersenne number is composite, it cannot have factors of the form 2^a-1. It can certainly not have factors in the form of a Mersenne prime. In testing whether 2^b-1 is a prime, it can be safe to skip any smaller number of the form 2^a-1. This fact could be useful in testing the primality of a Mersenne number (at least marginally useful).

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}