Two Newbie Questions

[MichaelT162]

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!

[Uncwilly]

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

[LaurV]

Originally Posted by MichaelT162

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?)

[Nick]

Entertainingly written! I can't wait to see the LaurV guide to Fermat's other well-known theorem...

[LaurV]

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..