mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-02-09, 06:41   #1
Rodrigo
 
Rodrigo's Avatar
 
Jun 2010
Pennsylvania

13·71 Posts
Default 'Verifying' a Mersenne prime vs. 'proving' it

Hi,

I'm not sure which subforum is the best place to ask this, but I have a question about the GIMPS procedures for confirming a Mersenne prime.

I read here (http://primes.utm.edu/mersenne/index.html#known) that 20996011 was discovered in 2003, and the associated link (http://primes.utm.edu/notes/20996011/index.html) informs the reader that the new prime was "verified" by two other folks back then.

So far, so good: I understand the process. But then there is this page (http://mersenne.org/report_milestones/) which reports that 20996011 wasn't "proven" to be the 40th Mersenne prime until July 2010 -- that is, close to seven years after it was "verified."

What's the difference between "verifying" and "proving" a Mersenne prime? I can understand each process separately (the wavefront for LL-D is far behind that for LL, and one would like to confirm a new MP ASAP), but not how the two concepts relate to each other. If a MP isn't "proven," has it really been "verified"? Or, if it has been "verified," why does it need to be "proven"?

Thanks in advance for elucidating these concepts for me.

Rodrigo

Last fiddled with by Rodrigo on 2011-02-09 at 06:41
Rodrigo is offline   Reply With Quote
Old 2011-02-09, 06:51   #2
ckdo
 
ckdo's Avatar
 
Dec 2007
Cleves, Germany

52910 Posts
Default

You verify that a number is prime, and prove its place in the sequence of Mersenne primes (by not verifying any previously unknown lower ones, so to speak).
ckdo is offline   Reply With Quote
Old 2011-02-09, 07:08   #3
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3×2,083 Posts
Default

Quote:
Originally Posted by ckdo View Post
You verify that a number is prime, and prove its place in the sequence of Mersenne primes (by not verifying any previously unknown lower ones, so to speak).
To further clarify, the term "prove" can also be used to refer to the same thing as a "verification". A Mersenne number is considered to be proven prime beyond reasonable doubt once a few separate tests are done on it (at least two with Prime95, plus a few with other programs on other hardware to discount the possibility of hardware/software errors or logic bugs). This process is also referred to as the "verification" of the number's primality. Later, when all numbers below the prime have been doublechecked, its place in the sequence of Mersenne primes is considered to be proven as well.

Note that for other, smaller (non-Mersenne) primes, the standard of what's considered "proof" for a prime is not often so stringent. In such cases, two separate tests with the same program on different computers (usually both x86-based) that both agree are considered sufficient proof for the number to be accepted on the List of the 5000 Largest Known Primes. (At least one test is assumed to have been done by the person submitting the prime, and a second test is done by the top-5000 site's internal verification machines.)

For Mersenne primes, due to their immense size and the correspondingly long tests involved (i.e. greater chance of a hardware error having occurred during the test), additional tests are routinely performed by non-Prime95 software on non-x86 hardware to eliminate the chance of a false positive due to a Prime95 bug or a glitch in the x86 microarchitecture in general. Both are rather unlikely, but because of the large amount of attention given to Mersenne primes (as they have traditionally been tested to sizes much higher than other forms), it's good to make "extra sure". That way you don't have to issue an embarrassing retraction of the proclaimed momentous discovery.
mdettweiler is offline   Reply With Quote
Old 2011-02-09, 17:35   #4
Rodrigo
 
Rodrigo's Avatar
 
Jun 2010
Pennsylvania

13·71 Posts
Default

@ckdo
@mdettweiler

Thanks a bunch for explaining!

I think I get it now. First somebody finds a (possible) Mersenne prime, and soon thereafter George verifies that it's "a" Mersenne prime. Then, years later, doublechecking establishes definitively that it's "the" Xth Mersenne prime.

Right?

Rodrigo
Rodrigo is offline   Reply With Quote
Old 2011-02-09, 17:42   #5
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3×2,083 Posts
Default

Yep! One quick note, though: it's generally not George himself who does the verification of prospective primes. He does a quick run of the last few iterations from the save file which Prime95 will save in case of a prime, and which he'll ask the finder to email him right away; but the full verifications are done by a couple of supercomputers that some members of this forum have access to. They usually manage to get the verification done in a week or so, which is pretty quick considering that the original test at leading-edge-first-pass-LL size generally would take about a month, and that the supercomputers are at somewhat of a disadvantage since Prime95 is a lot better optimized than all the non-x86 LL testing programs currently out there.

Next time a Mersenne prime is found, there will probably be at least one or two people running the verification on a GPU with CUDALucas (possibly also with the forthcoming GPULucas if it's out by then--as with CPUs, the more different programs you can test it with, the better to reduce the probability of software bugs). A modern GPU like a GTX 460 or GTX 580 is able to test a leading-edge number at least as quickly as one of the aforementioned supercomputers.

Last fiddled with by mdettweiler on 2011-02-09 at 17:59
mdettweiler is offline   Reply With Quote
Old 2011-02-09, 18:58   #6
axn
 
axn's Avatar
 
Jun 2003

121916 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
but the full verifications are done by a couple of supercomputershigh-end servers that some members of this forum have access to.
FTFY
axn is online now   Reply With Quote
Old 2011-02-09, 19:00   #7
Rodrigo
 
Rodrigo's Avatar
 
Jun 2010
Pennsylvania

39B16 Posts
Default

mdettweiler,

Thanks for elaborating on the process, it's very much clearer in my head now. It IS amazing that a modern GPU could compete with a supercomputer on something like this!

Rodrigo
Rodrigo is offline   Reply With Quote
Old 2011-02-09, 19:12   #8
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

624910 Posts
Default

Quote:
Originally Posted by axn View Post
FTFY
Hmm, I thought they were actually (low-end) supercomputers...or is it that they were "supercomputers" 5-6 years ago and now they're just high-end servers?
mdettweiler is offline   Reply With Quote
Old 2011-02-09, 22:17   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25×233 Posts
Default

Quote:
Originally Posted by Rodrigo View Post
Hi,

I'm not sure which subforum is the best place to ask this, but I have a question about the GIMPS procedures for confirming a Mersenne prime.

I read here (http://primes.utm.edu/mersenne/index.html#known) that 20996011 was discovered in 2003, and the associated link (http://primes.utm.edu/notes/20996011/index.html) informs the reader that the new prime was "verified" by two other folks back then.

So far, so good: I understand the process. But then there is this page (http://mersenne.org/report_milestones/) which reports that 20996011 wasn't "proven" to be the 40th Mersenne prime until July 2010 -- that is, close to seven years after it was "verified."
It was proven to be prime in 2003. It wasn't proven that it was the
40th such prime until 2010 when all other possible candidates
had been eliminated.
R.D. Silverman is offline   Reply With Quote
Old 2011-02-10, 00:31   #10
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2·4,111 Posts
Default

Sounds like an entry in the Wiki is needed.
Uncwilly is offline   Reply With Quote
Old 2011-02-10, 03:13   #11
Rodrigo
 
Rodrigo's Avatar
 
Jun 2010
Pennsylvania

13·71 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
It was proven to be prime in 2003. It wasn't proven that it was the
40th such prime until 2010 when all other possible candidates
had been eliminated.
Thank you, this makes sense now. What threw me was that the 2003 press release called it the "40th known Mersenne prime," but then that wasn't actually proven till 2010.

It was when I honed in on the key word "known" that it really clicked: That was the fortieth time that a Mersenne prime was ever discovered, but as to whether it was Number 40 in the sequence of positive integers defined as Mersenne primes -- that's what didn't get proven till seven years later.

Hopefully, this thread will help to make this aspect of the project clearer for at least a few people out there.

Rodrigo
Rodrigo is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Use Pepin's Tests for proving primality of Mersenne numbers ? T.Rex Math 12 2016-04-03 22:27
NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED! dabaichi News 561 2013-03-29 16:55
The 40th known Mersenne prime, 220996011-1 is not PRIME! illman-q Miscellaneous Math 33 2004-09-19 05:02
Introducing GIMPS, Now Verifying M10,000,000+! E_tron Lounge 7 2003-09-16 21:30
Verifying factors... Xyzzy Math 13 2002-09-15 03:51

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

Sat Jul 11 09:16:19 UTC 2020 up 108 days, 6:49, 0 users, load averages: 1.36, 1.39, 1.39

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.