mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2019-08-21, 15:29   #1
MichaelT162
 
Aug 2019
St. Charles, MO

116 Posts
Default Two Newbie Questions

1) If a new Mersenne prime is discovered that is less than the current World Record Mersenne prime,

(a) Is this still a big deal in the community? Or is the focus mostly on world records?

(b) Is this eligible for awards? Or does it have to be a world record?

2) Is anyone aware of a tutorial or explainer for how PRP testing works, e.g., exactly what it does and how it determines if a number is prime or composite? I'm not a mathematician by any means, but have a general interest in the nuts and bolts.

Thank you!
MichaelT162 is offline   Reply With Quote
Old 2019-08-21, 17:08   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

9,497 Posts
Default

Here are a couple of answers with links to more complete answers:

1a) All Mersenne primes are a big deal. There are few enough of them to make each important (especially if there is one found by a double check.)

1b) Yes there are awards for all discoveries. https://www.mersenne.org/legal/#awards


2) The Wikipedia article on Probable Prime is a good place to start. https://en.wikipedia.org/wiki/Probable_prime
Uncwilly is online now   Reply With Quote
Old 2019-08-22, 15:31   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

100100101010012 Posts
Default

Quote:
Originally Posted by MichaelT162 View Post
2) Is anyone aware of a tutorial or explainer for how PRP testing works, e.g., exactly what it does and how it determines if a number is prime or composite? I'm not a mathematician by any means, but have a general interest in the nuts and bolts.
You need any kind of property which is true for all prime numbers, except possibly a well-delimited (known) set. Let's call this property P. Any number that has the property P is then called "P-probable prime".

Which numbers have property P? Well, obviously all primes (we just said, weren't you listening?). So, all primes are "P-probable primes". Some other numbers may also have the property P. If we know that they are not prime, we will call them "P-pseudoprimes". Ideally is that we find a property P which is "strong enough" to have as few as possible "pseudoprimes" (i.e. numbers that satisfy P but are not prime).

Example: (which I invented just now). All primes with the exception of 2 are odd. We could say that any number that is odd is "odd probable prime". Haha. This name I just invented now, and I want a copyright for it. In this case, even numbers, with the exception of 2, can not be prime (because, obviously, they "do not have the right property all primes have", i.e. they "are not odd"). All odd numbers are "odd-probable-primes", regardless of their status of being prime or not". Any odd number that we know is composite, we may call "odd-pseudoprime" (again, this is a name I invented just now, only for the sake of example).

Of course, this example sucks, because the property itself sucks, most odd numbers are not prime. But all primes larger than 2 are odd numbers. Such property is too weak. We would need some property which is satisfied by all primes, but only very few composites (ideally none!) satisfy it.

Let's make this property stronger.

Some time ago, Fermat observed, and proved, that if you take any prime p, and any number b larger than 1 and smaller then p, then b^p=b (mod p). This means that if you multiply b by itself a number of p times, and divide the result by p, and take the reminder of that division, then such reminder will always be b.

Example: Take p=7, and b=4. You have to multiply 4*4*..*4, seven times, you get 16384. When dividing this into 7 heaps, you get 2340 in each heap, and you are left with 4. Take p=5 and b=3, you get 3^5=243, which is 3 (mod 5). So, for primes 5 and 7 we have 3^5=3 (mod 5), and respective 4^7=4 (mod 7). And similar for all primes and all suitable b's. For p=11 and b=2 we will have 2^11=2 (mod 11). And so on.

The nicer part with modular calculus is that you can take the modulus after every operation, so you never run into numbers much larger than p. For example, in the first case: 4*4=16 which is 2 (mod 7) because 16=2*7+2. Then 2*4=8 which is 1 (mod 7) because 8=7+1. Then 1*4=4, and things repeat, so we have 4^7=4 (mod 7). We never need to go to 16384 or even close to it.

This "property" of prime numbers is called "Fermat's Little Theorem", and any number p that verifies this property (regardless of p being prime or not) is called Fermat Probable Prime.

Here, b is called "base", and when b=2, the numbers are called "Fermat probable prime base 2", or in short, 2-PRP. Sometime 2-PRPs are called Sarrus numbers. When b=3, they are called 3-PRP, and so on.

Let's check if 11 is a 2-PRP. So, 2^1=2, 2^2=2*2=4, 2^3=4*2=8, 2^4=8*2=16, which is 5 (mod 11), 2^5=5*2=10 (note that we use the result we just calculated, we do not need to multiply 16 times 2), 2^6=10*2=20 which is 9 (mod 11), 2^7=9*2=18=7 (mod 11), 2^8=7*2=14=3 (mod 11), 2^9=6, 2^10=1, and 2^11=2 (mod 11), QED, 11 is a 2-PRP number.

Let's check if 13 is a 2-PRP. So, we have in order, by multiplying each former result by 2 and getting the reminder to 13, the string of 13 powers of 2: 2, 4, 8, 16=3, 6, 12, 24=11, 22=9, 18=5, 10, 20=7, 14=1, 2, QED, 13 is a 2-PRP number, because 2^13=2 (mod 13).

Let's check if 21 is a 2-PRP. So, we have in order, by multiplying each former result by 2 and getting the reminder to 21, the string of 21 powers of 2: 2, 4, 8, 16, 32=11, 22=1, 2, 4, 8, 16, 32=11, 2, 4, 8, 16, 32=11, 22=1, 2, 4, 8, so we have 2^21=8 (mod 21). This tells us that 21 can not be prime, because it does not verify the Fermat condition which is verified by all primes.

Note that this method tells us nothing about the factors of 21. But it just tells us that 21 is not prime, with certitude. We know for sure, in this case, that 21 is composite.

How many numbers have this property? Well, first of all, all the primes. We just said above. But few composites also have this property. So, if we get a "positive" result (in our particular 2-PRP test, the reminder is 2, so the number is 2-PRP), then the number "might be prime". We still do not know, unless we do more tests.

But this method is extremely fast, and it will eliminate most of the composites. Note that you do not need to multiply b by itself the way I did it, there are methods which will reach the same result much faster (they are called "exponentiation" and you can google it). For example, to raise 2 at the power of 21, I could just square 2 four times and keep the intermediary results, and multiply them in a convenient way.

2^1=2
2^2=2*2=4
2^4=4*4=16
2^8=16*16=256=4 (mod 21)
2^16=4*4=16 (mod 21).

and now multiply first, third, and last, to get 2^21=2*16*16=2*4=8 (mod 21). Therefore 21 is certainly not prime, because 2^21 is not 2 (mod 21). If it would be prime, Fermat's result ensure us that the reminder should have been 2.

Now, if we repeat the same idea to check if 341 is a 2-PRP, we get:

2^1=2
2^2=2*2=4
2^4=4*4=16
2^8=256
2^16=256*256=65536=64 (mod 341)
2^32=4 (mod 341)
2^64=16 (mod 341)
2^128=256 (mod 341)
2^256=64 (mod 341)

Only 8 "squaring" operations. As 341=256+64+16+4+1, multiply the powers conveniently and get 2^341=64*16*64*16*2=2 (mod 341).

So, 341 is a 2-PRP, therefore it might be prime. In fact, it is not, 341=11*31 is a composite number, and it is the smallest composite number which is a 2-PRP. Numbers which verify this property, but are not prime, are called "(Fermat) pseudoprime", or in short, 2-PSP. In our case, 341 is the smallest 2-PSP. These numbers are rare, but they exist, and we can't ignore them when we test for primality.

Note that PRP means a number that we do not know for sure if it is composite. It might be prime or not. PSP means a number which we know for sure that it is composite, but it verifies the PRP property.

Note again that this method says nothing about the possible factors of 341. We must use other methods to find its factors.

The pseudoprimes are rare, millions* of times rarer than the prime numbers.

GIMPS uses PRP to eliminate composite candidates. If your PRP test turns a residue it means your number is composite for sure (assuming no computing errors during the test, do not play with the hammer or nunchaku around it when P95 is running!). If your PRP test says that your number is PRP, then you "almost sure" found a prime.

But somebody else still has to run a LL test (other kind of animal, I mean the LL test, not the person running it ) to make sure you didn't find a pseudoprime. If the LL says "prime", you will take the glory and the money (even if it was not you who run the LL test, but it was you who run the PRP test).

In fact, if you turn out a pseudoprime, I imagine you will be more famous than if you turn out a prime, as we don't know any mersenne pseudoprime yet, and some people believe they do not exist.

For criteria not concerning this post, we do not use base 2 when testing mersenne numbers for "PRP-ality". (do I get the bonus for the most invented words?)

Last fiddled with by LaurV on 2021-03-12 at 03:14 Reason: hating these spaces... Mike?
LaurV is offline   Reply With Quote
Old 2019-08-22, 17:04   #4
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

11·151 Posts
Default

Entertainingly written! I can't wait to see the LaurV guide to Fermat's other well-known theorem...
Nick is offline   Reply With Quote
Old 2019-08-22, 19:23   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5·1,877 Posts
Default

Thanks maestro! Coming from you is extraordinarily gratifying.

I just edited it to fix lots of typos and errors, and I am sure some of them managed to evade my correction marker right now, because it is 2:20 AM and my eyes have already fell into my mouth and I am looking to the monitor through the teeth...

Going to bed..

Last fiddled with by LaurV on 2019-08-22 at 19:27 Reason: s/felt/fell/
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A couple newbie questions evanmiyakawa Information & Answers 4 2017-11-07 01:37
Newbie problems/questions help needed please, thank you. Stephanie Information & Answers 9 2013-04-08 18:35
Two questions from a newbie Unregistered Information & Answers 9 2007-08-12 01:18
Some newbie questions AltiVec Studio Teams 1 2005-12-14 17:55
Linux and mprime pre-newbie questions eepiccolo Software 4 2003-02-11 09:20

All times are UTC. The time now is 21:09.

Wed Apr 21 21:09:38 UTC 2021 up 13 days, 15:50, 0 users, load averages: 1.98, 1.88, 1.87

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.