mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2008-12-26, 08:52   #1
hj47
 
hj47's Avatar
 
Oct 2008

26 Posts
Question More questions about prime95

Hey all,

I still don't quite understand what p-1 factoring, trial factoring and first time checks are in relation to prime95. Could someone be gracious enough to explain these in simple terms? I've tried the wiki but it's out of my league. Furthermore, is it possible to discover a prime just by running a first time test, or a p-1 check, or do you have to use a combination (or not?).

Also, the client says that I have a 7.27% chance of finding a factor. Does this mean that if it is a factor, it cannot be prime?

And if I leave the option 'whatever makes the most sense' on, is it the best way of finding primes, or is there only one type of 'final' test that one can chose to determine whether or not a number is prime? Is there a prefered method of maximising your chance of finding a prime, or is everyone on the same level playing field?

Sorry for my noobishness, I'm still working my way up this massive learning curve :S

Thanks for any help you can provide :D
hj47 is offline   Reply With Quote
Old 2008-12-26, 10:10   #2
axn
 
axn's Avatar
 
Jun 2003

4,969 Posts
Default

Quote:
Originally Posted by hj47 View Post
Does this mean that if it is has a factor, it cannot be prime?
Yes. This is the key to answering the rest of your questions. It follows from the definition of prime numbers. A number is prime, if and only if it is not divisible by any other number (other than by itself and 1, which trivially divides every number). IOW, if a number has a factor it cannot be prime -- i.e. it is a composite. Eg:- 15 is composite because it has factors 3 and 5, where as 17 is composite because it has no factors.

Quote:
Originally Posted by hj47 View Post
I still don't quite understand what p-1 factoring, trial factoring and first time checks are in relation to prime95. Could someone be gracious enough to explain these in simple terms? I've tried the wiki but it's out of my league. Furthermore, is it possible to discover a prime just by running a first time test, or a p-1 check, or do you have to use a combination (or not?).
The GIMPS project uses different types of tests to determine whether a number is prime or composite. One approach is to try and find a factor, thereby disproving primeness (trial factoring and P-1 are two tests that belong to this class). Another one is the LL test. This one will, after a long series of computations, tell us definitively whether the number is prime or not. So why the two approaches? Well, due to practical considerations, trial factoring and P-1 can only discover small-ish factors, if it is there. But they are fast compared to LL test. So we perform trial factoring and P-1 initially in the hopes of finding a factor and thus avoid a costly LL test (LL is the costliest of the lot). It is a sort of a gamble. A lot of the times, these two will come up empty, in which case an LL test needs to be run to get a conclusive final verdict.

That was the simple version, with certain details deliberately left out.

Quote:
Originally Posted by hj47 View Post
And if I leave the option 'whatever makes the most sense' on, is it the best way of finding primes, or is there only one type of 'final' test that one can chose to determine whether or not a number is prime? Is there a preferred method of maximizing your chance of finding a prime, or is everyone on the same level playing field?
As answered, there is only one "final" test -- i.e. LL test. However, if your computer is not fast enough, the server won't assign you that type of test, due to its length (but if your comp is less than 3 years old, it should be fast enough). So slowish computers would get one of the other types -- TF, P-1, ECM etc.

Everyone has a level playing field. So to maximize your chance, just bring more firepower
axn is online now   Reply With Quote
Old 2008-12-26, 10:36   #3
hj47
 
hj47's Avatar
 
Oct 2008

26 Posts
Default

Hi axn, thanks for the helpful post.

So if I want to LL test, how do I go about doing that? And is this the test that takes about a month to complete on decent (ie core2) processors?

And do you know the statistical chance of actually finding a prime (just out of curiosity)?

Thanks again
hj47 is offline   Reply With Quote
Old 2008-12-26, 13:18   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by hj47 View Post
So if I want to LL test, how do I go about doing that? And is this the test that takes about a month to complete on decent (ie core2) processors?
Run Prime95 to LL test a number. You can use the Advanced menu to just LL test a specific exponent.
Quote:
Originally Posted by hj47 View Post
And do you know the statistical chance of actually finding a prime (just out of curiosity)?
http://web.archive.org/web/200612051...e.org/math.htm
At the bottom of the LL section there are formulas to approximate the chances of it being prime. If I'm not mistaken, at GIMPS's current level for first time tests, there's approximately a 1 in 300,000 chance of any specific number being prime, after being factored.
Mini-Geek is offline   Reply With Quote
Old 2008-12-26, 14:03   #5
MatWur-S530113
 
MatWur-S530113's Avatar
 
Apr 2007
Spessart/Germany

A216 Posts
Default

Hello,

just as an addition: Lucas-Lehmer-Tests (LLTs) are: First time tests, Double check tests, World record sized number to test and finally 100,000,000-digit number to test (but the last one will need years for finishing...).
If you want to maximize your chance to find a prime 'First time tests' and 'World record sized number tests' are the recommened choices.

Best regards,

Matthias
MatWur-S530113 is offline   Reply With Quote
Old 2008-12-26, 20:06   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by hj47 View Post
I still don't quite understand what p-1 factoring, trial factoring and first time checks are in relation to prime95.
Here's an alternative way (with a few of the details axn skipped for brevity) to think about them:

They're _all_ factor-finding tests, but their "vision" and speed differ.

The L-L test almost always (99.999+%) eventually proves that the number you are assigned has factors, but it has two BIG drawbacks: 1) it can't determine what any factor actually is (its "vision" looks everywhere but is fuzzy -- it determines only that some factors exist somewhere), and 2) it takes a l-o-n-g time.

The TF and P-1 are shorter (relative to L-L duration) tests that are capable of determining _exactly_ (sharp vision) what one factor is. They do so only some (e.g., that 7.27%) of the time (narrow field-of-view), but when they succeed, they eliminate the need to do the l-o-n-g L-L test!

If any of the three succeed in showing that the number has a factor, you just report that and go on to another assignment. However, having the L-L test show that the number has a factor takes a l-o-n-g time if the TF and P-1 don't.

Now, if (<0.001% of the time) the L-L test happens to find that the number is prime, you get eternal mathematical fame! ... But that's pretty rare -- so as soon as you and GIMPS find out in some way that the number is composite, you probably want to go on to another, possibly-fame-making assignment ASAP. The TF and P-1 attempt to shortcut the path to that finding, and sometimes succeed in doing so.

So far, we haven't explained the "first time" in "first time checks".

Modern computers have a lot of error-detection-and-prevention built into them, but it's still possible for an occasional glitch to occur in the circuitry. In most applications, a single glitch isn't all that important, and may not even be noticeable.

But the L-L test is very exacting -- even one glitch in the l-o-n-g calculation can ruin the result. Prime95 tries several ways to detect errors and can sometimes recover from them by automatically redoing part of the calculation, but occasionally an error goes undetected. The most practical way to determine whether that happened is to repeat (doublecheck) the L-L test on a different computer under different conditions, and compare a final value, called residue, that is produced by the L-L calculation.

Because the L-L test takes s-o-o-o long, the chance of a glitch causing an error in that residue is noticeable: 1-2% of test results reported to GIMPS turn out to be erroneous. If a later DC (doublecheck) test on the same number produces a residue that matches the first-time residue, we can be fairly sure that the factor/no-factor indication is correct.

Quote:
Sorry for my noobishness, I'm still working my way up this massive learning curve :S
We welcome your noobishness, commend you for your inquiries, and are glad to help!

Last fiddled with by cheesehead on 2008-12-26 at 20:18
cheesehead is offline   Reply With Quote
Old 2008-12-27, 00:39   #7
hj47
 
hj47's Avatar
 
Oct 2008

6410 Posts
Default

Thanks everyone for your help.

This is definitely clearing up my understanding of prime95.

So basically, old/ish computers should be assigned to P-1 and factoring tests while relatively modern computers should do LL tests? And do all returned results earn points?

Ooh, just out of curiosity, the primes that GIMPS have found so far, what test/s were the computers running? Is it basically a process of elimination when finding primes, ie. first time test => p-1 => LL etc?

Thanks again :D
hj47 is offline   Reply With Quote
Old 2008-12-27, 01:52   #8
starrynte
 
starrynte's Avatar
 
Oct 2008
California

22·59 Posts
Default

To find a prime, you MUST complete ALL of the long LL test on a number. However, as cheesehead said, before the long LL test is done, trial factoring and P-1 factoring attempt to eliminate numbers for LL testing. As soon as trial factoring or P-1 factoring find a factor, you know it's not prime, so there's no point running an LL test on a factored number. However, trial factoring and P-1 factoring cannot determine if a number is prime (or to be exact, it can, but it would take an unimaginably long time), so after some extent of attempting to eliminate a number, the LL test is run on that number.
The point being, ONLY LL tests can tell if a number is prime. However, trial factoring and P-1 factoring can tell if a number is NOT prime, saving the need to do LL.
starrynte is offline   Reply With Quote
Old 2008-12-27, 04:29   #9
hj47
 
hj47's Avatar
 
Oct 2008

4016 Posts
Default

Quote:
Originally Posted by starrynte View Post
To find a prime, you MUST complete ALL of the long LL test on a number. However, as cheesehead said, before the long LL test is done, trial factoring and P-1 factoring attempt to eliminate numbers for LL testing. As soon as trial factoring or P-1 factoring find a factor, you know it's not prime, so there's no point running an LL test on a factored number. However, trial factoring and P-1 factoring cannot determine if a number is prime (or to be exact, it can, but it would take an unimaginably long time), so after some extent of attempting to eliminate a number, the LL test is run on that number.
The point being, ONLY LL tests can tell if a number is prime. However, trial factoring and P-1 factoring can tell if a number is NOT prime, saving the need to do LL.
Ok, so if I were to run a p-1 test which showed no factors, would it be then when I would run an LL test?

+ Is it possible to run just LL tests on numbers that has no factors, or is finding such a number so uncommon it's only possible once or twice a year?

Thanks
hj47 is offline   Reply With Quote
Old 2008-12-27, 04:55   #10
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

958510 Posts
Default

Quote:
Originally Posted by hj47 View Post
So basically, old/ish computers should be assigned to P-1 and factoring tests while relatively modern computers should do LL tests? And do all returned results earn points?

Ooh, just out of curiosity, the primes that GIMPS have found so far, what test/s were the computers running? Is it basically a process of elimination when finding primes, ie. first time test => p-1 => LL etc?
The oldest computers should do the easy bits of trial factoring. The next oldest should do the harder bits of TF. Then the next oldest should do double checks (to verify that the first time LL tests were ok). P-1 is best suited to computers with lots of available RAM (like 3 Gb for the test).

The order is like this:

Trial factoring (this can be done in multiple chunks of work and will eliminate ~ 1/2 of all numbers)
any number that survives then has:
P-1 factoring (about 2-5% are eliminated here)
any number that survives then has:
LL primality testing (takes care of the rest)
if the number does not show up as prime then:
double check (happens much later, same as the LL)
else if prime:
verification is performed on several other types of computers with other programs.


All types of testing get credit. The credit amount is tracked by test type.
Uncwilly is offline   Reply With Quote
Old 2008-12-27, 10:50   #11
S485122
 
S485122's Avatar
 
Sep 2006
Brussels, Belgium

2×5×167 Posts
Default

Some of the numbers in previous posts are slightly off :

Trial factoring will eliminate round 60% of exponents.

P-1 factoring will eliminate a bit less than 3% (a bit more than 7% of the remaining exponents.)
In GIMPS the minimum requirement to be assigned independant P-1 work is 200MB. This means thet if you assign 512MB out of 2GB via the Options / CPU menu it should be enough. Of course more memory wil be more beneficial.

The aproximatively 37% of remaining exponents have to be LL tested.
There are about 10% of bad results during LL testing stressing the importance of the double checks. IMO most come from badly overclocked machines.

Unless you require a specific work type, on a sufficiently powerfull machine, you will be assigned LL tests. Most of those consist of first P-1 factoring then the LL test. For minimum requirements look at the page Assignment Thresholds.

Jacob
S485122 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime95 - suggest using B2 bound = GMP-ECM default and other questions Raman PrimeNet 34 2020-07-14 22:25
Prime95 Questions dimkadimon Software 19 2011-01-17 20:28
gmp-ecm questions yoyo GMP-ECM 34 2009-03-20 18:06
Questions about RAM and Prime95 Matthias C. Noc Software 2 2004-03-01 08:16
DNS questions Prime95 PrimeNet 2 2003-04-12 01:54

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

Tue May 18 05:16:47 UTC 2021 up 39 days, 23:57, 0 users, load averages: 1.94, 2.20, 2.23

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.