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

[QUOTE=hj47;155114]Does this mean that if it[strike] is [/strike]has a factor, it cannot be prime?[/quote]
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 [B]cannot[/B] 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=hj47;155114]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?).[/quote]
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 [I]dis[/I]proving 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 [I]costly[/I] 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=hj47;155114]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?[/QUOTE]
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 :smile:

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

[quote=hj47;155124]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?[/quote]
Run Prime95 to LL test a number. You can use the Advanced menu to just LL test a specific exponent.
[quote=hj47;155124]And do you know the statistical chance of actually finding a prime (just out of curiosity)?[/quote]
[url]http://web.archive.org/web/20061205191829/mersenne.org/math.htm[/url]
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.

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

[quote=hj47;155114]I still don't quite understand what p-1 factoring, trial factoring and first time checks are in relation to prime95.[/quote]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 [I]proves[/I] that the number you are assigned has factors, but it has two BIG drawbacks: 1) [I]it can't determine what any factor actually is[/I] (its "vision" looks everywhere but is fuzzy -- it determines only that [I]some[/I] factors exist [I]some[/I]where), 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, [U]if[/U] (<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 [I]residue[/I], 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[/quote]We [i]welcome[/i] your noobishness, commend you for your inquiries, and are glad to help!

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

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.

[quote=starrynte;155229]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.[/quote]

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

[QUOTE=hj47;155220]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?[/QUOTE]
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.

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 [url=www.mersenne.org/thresholds]Assignment Thresholds[/url].

Jacob