Tag Archives: prime number

Fermat prime and Mersenne prime

Fermat prime

https://i1.wp.com/upload.wikimedia.org/wikipedia/commons/f/f3/Pierre_de_Fermat.jpg

In mathematics, a Fermat number, named after Pierre de Fermat who first studied them, is a positive integer of the form. Fn=22n+1, where n is a nonnegative integer. The first few Fermat numbers are: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617. And he is the first to investigate numbers of the form 22n.

There is the Pépin test which gives sufficient and necessary condition for the primality of the Fermat prime and this can only be implemented by use of modern computers. Pépin’s test is a primality test, which can be used to determine whether a Fermat number is prime. It is a variant of Proth’s test. The test is named for a French mathematician, Théophile Pépin.Let Fn be a Fermat number. Fn is prime if and only if 3(Fn-1)/2 = -1 (mod Fn).Here 3 can be replaced by any positive integer k for which the Jacobi symbol (k|Fn) is -1. These include k=3, 5, and 10.If Fn is prime, this primality can be shown by Pepin’s test, but when Fn is composite, Pepin’s test does not tell us what the factors will be (only that it is composite). For example, Selfridge and Hurwitz showed that F14 was composite in 1963, but we still do not know any of its divisors. (Chris K. Caldwell)

Mersenne numbers, which take the form of 2n-1, were named after Marin Mersenne, a French monk from the early 17 century, who corresponded with Fermat. We are particularly interested in the case when Mersenne number are prime. It is not doubt that the first 17 primes of the form 2n-1 match the following n values: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281 (Zegarelli 287).

The first 12 Mersenne primes were known since 1914 and the 12th, 2127-1, was established by Anatole Lucas in 1876. It was one of the largest-known prime number for over 75 years. The next 5 Mersenne primes (p=13 to 17)were discovered in 1952. It was in 1952 when the testing program for Mersenne numbers was began. This led to the establishment of three other primes. More testing has been carried out using modern day computers and the smallest Mersenne number that is untested is 22309-1 (~2013), and this has not been a case of great interest. There is a conjecture that 2n-1 is always prime when n is a Mersenne number. And the more interesting case is the 28191-1 because the 8191 also is the Mersenne number. (Křížek, Florian and Lawrence 214).

Works Cited

Chris K. Caldwell (2014). Pepin’s test . [ONLINE] Available at: http://primes.utm.edu/glossary/page.php?sort=PepinsTest.

Crandall, Richard E, and Carl Pomerance. Prime Numbers: A Computational Perspective. New York: Springer, 2005. Internet resource.

Zegarelli, Mark. Basic Math & Pre-Algebra Workbook for Dummies. Hoboken, N.J: Wiley, 2008. Internet resource.

Křížek, Michal, Florian Luca, and Lawrence Somer. 17 Lectures on Fermat Numbers:    From Number Theory to Geometry. New York, NY [u.a.: Springer, 2001. Print.

Advertisements

GIMPS: The Great Internet Mersenne Prime Search

The GIMPS Logo. Public domain, via Wikimedia Commons.

The GIMPS Logo. Public domain, via Wikimedia Commons.

Approximately two years ago, I decided to build my first desktop. From browsing various forums on the internet, I learned that many PC builders would run their hardware at higher speeds for more performance than the manufacturers specify when selling components. However, when doing this, one must run a program that uses 100% of a processor’s computing power to ensure the stability of the PC so that it will not shut down or encounter a Blue Screen of Death while playing video games or doing other important work. It was in this situation that I first encountered a program known as Prime95.

Prime95, in addition to being used to test overclocked processors, is used by the members of The Great Internet Mersenne Prime Search, or GIMPS, to search for large Mersenne primes.

Mersenne numbers have the form 2n-1, where n is a positive integer. Mersenne primes are those Mersenne numbers that are prime; the first four are 22-1, 23-1, 25-1, and 27-1. These special primes are named for the French theologian and mathematician Marin Mersenne. Born in 1588 in Oizé, France, Mersenne was always interested in studying mathematics, and published a paper in 1644 that included a statement about numbers of the form 2n-1. He claimed that for n less than 257, the values n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257 made the number prime. However, Mersenne admitted to not having tested all of the positive integers less than 257. With the use of many mathematical discoveries, it was shown that n = 67 and 257 did not make 2n-1 prime, and that n = 61, 89, and 107 also made it prime, making a total of five errors in Mersenne’s list for n < 257. This led to many individuals becoming interested in finding large Mersenne primes.

GIMPS was founded in 1996 by George Woltman, who graduated from MIT with a Master’s degree in Computer Science. GIMPS and Prime95 use a method to perform calculations known as “distributed computing.” Distributed computing is essentially an alternative to using supercomputers to perform difficult calculations – instead of using a small number of supercomputers to solve problems, people around the world “donate” time when their computer is not being used to work on small chunks of these large calculations.

Since 1996, Prime95 has been used to discover fourteen Mersenne Primes. The first of these was in November of the year GIMPS was founded, 21,398,269-1. On January 25th, 2013, the 48th known Mersenne prime was discovered, 257,885,161-1. On February 24th of this year (2014), it was verified that the 43rd known Mersenne prime, 230,402,457-1, was, in fact, the 43rd Mersenne prime, meaning that we know of every Mersenne prime smaller than this 43rd one, and there are exactly 42 Mersenne primes that are smaller.

How does GIMPS discover these large primes? Prime95 uses a method known as the Lucas-Lehmer Primality test, a recursive relation, to determine whether a Mersenne number (Mn = 2n – 1) is prime or not. If it is prime, it is therefore a Meresnne prime (Mp = 2p – 1) where n=p. The Lucas-Lehmer test uses the following relation:

sn ≡ (sn-1)2-2 mod Mn.

where s0 ≡ 4. The Lucas-Lehmer residue, sn-2 mod Mn, determines whether a Mersenne number is prime; a Mersenne number is prime if and only if the Lucas-Lehmer residue is congruent to 0 mod Mn.

If, for example, we want to determine whether the Mersenne number 211-1 is a prime, then p = 11 and M11 = 2047. We therefore need to find the Lucas-Lehmer residue, s9, to determine whether M11 is a Mersenne prime.

The first index is always congruent to 0, so we start with:
s0 ≡ 4 mod M11.

We then calculate the second residue using the formula.
s1 ≡ sn-12-2 mod M11 ≡ s02-2 mod M11.

Since s0 ≡ 4 mod M11:
s02 – 2 mod M11 ≡ 16-2 mod M11.

Which is then congruent to:
16-2 mod M11 ≡ 14 mod M11.

Therefore, our second residue s1 is:
s1 ≡ 14 mod M11.

We then use this second residue to calculate our third residue s2.
s2 ≡ s22-2 mod M11 ≡ 194 mod M11.

We then continue to use this formula to calculate the next six residues:

s3 ≡ 788 mod M11.
s4 ≡ 701 mod M11.
s5 ≡ 119 mod M11.
s6 ≡ 1877 mod M11.
s7 ≡ 240 mod M11.
s8 ≡ 282 mod M11.

We can now finally calculate s9, the Lucas-Lehmer residue. This tenth residue turns out to be:
s9 ≡ 1736 mod M11.

Because the Lucas-Lehmer residue must be congruent to 0 mod M11 for M11 to be a Mersenne prime, the Mersenne number M11 = 2047 is not a Mersenne prime, which matches GIMPS’ own list of the 48 known Mersenne primes.

While the search for these large primes may not seem particularly relevant at first, there is one important application: RSA encryption. In RSA encryption, a user can post a “public key” which is the product of two extremely large primes. A message can be encrypted to that user with the public key, but for the message to be decrypted, the public key has to be factored into the exact two primes used to get it. This is an extremely time consuming and difficult feat to accomplish – unless you happen to know what those two primes are. This makes large primes extremely effective in encryption, the most prevalent use of large primes in our world today. Click here for more information on RSA encryption.

The Great Internet Mersenne Prime Search has generated many primes with their distributed computing program Prime95, which primarily uses the Lucas-Lehmer primality test to test large Mersenne numbers. If you want to join in the search for the next Mersenne prime, you can sign up at http://www.mersenne.org and download Prime95.

But don’t try computing these by hand with a calculator. M48 is 17.4 million digits long.

Sources:

http://mathworld.wolfram.com/Lucas-LehmerTest.html

http://www.mersenne.org/

http://www.bacchae.co.uk/docs/dist.html

http://primes.utm.edu/bios/page.php?lastname=Woltman

http://primes.utm.edu/glossary/page.php?sort=MersennesConjecture

http://www-history.mcs.st-andrews.ac.uk/Biographies/Mersenne.html

http://arstechnica.com/science/2013/02/ask-ars-why-spend-time-and-money-finding-new-prime-numbers/