Questions about P-1
 

I've read the description of the P-1 algorithm at [URL]http://www.mersenne.org/various/math.php[/URL], but there is no explanation of what the difference is between Stage 1 of P-1 and Stage 2 of P-1 that makes Stage 2 require so much more memory. My guess is that the same calculation is being performed in both stages, but there are many more primes to be included in the product E in Stage 2, and that the extra memory is used to hold these extra primes. I'm also guessing that the reason the save files for a P-1 double in size between Stages 1 and 2 is because of the (much) larger product that is being formed in Stage 2. Is that the right idea?

Also, in Stage 2, I've seen Prime95 display messages about processing "relative primes". What does this mean? Are these numbers that are relatively prime to one another? Typically, there is some number of relative primes - e.g. 480 - that are getting processed; are these selected out of the primes that lie between B1 and B2? And if so, how does Prime95 decide which primes get selected?

Finally, I've heard of users with lots of RAM performing a "Brent-Suyama Extension" of P-1 with a value of E, where E is something like 6, 8, or 12. What exactly is this, and how much more does it increase the chances of P-1 finding a factor? How much RAM does one need before this extension becomes feasible?

Enlightenment from the P-1 crowd is much appreciated! :smile:

[QUOTE=NBtarheel_33;253113]
Also, in Stage 2, I've seen Prime95 display messages about processing "relative primes". What does this mean?

[/QUOTE]

[url]http://www.google.ca/search?sourceid=chrome&ie=UTF-8&q=define:%22relatively+prime%22[/url]

I'm afraid I don't know too much myself, but this page has some more detail on P-1, including the best explanation of stage 2 I can find on the web (though I'm still not clear on why stage 2 needs lots of memory, if I were to work out an example using the math there, I'd probably see).
[url]http://mersennewiki.org/index.php/P-1_Factorization_Method[/url]

[QUOTE=NBtarheel_33;253113]I've read the description of the P-1 algorithm at [URL]http://www.mersenne.org/various/math.php[/URL], but there is no explanation of what the difference is between Stage 1 of P-1 and Stage 2 of P-1 that makes Stage 2 require so much more memory.[/QUOTE]Stage 2 involves repeated multiplications by powers of a certain set of numbers. To save time, it allocates as many work areas as it can to hold certain intermediate calculated powers and products that will be repeatedly used, so that each need be calculated only once. The more work areas it can allocate, the more time it can save by using singly-calculated intermediate products.

So, it's not so much a matter of Stage 2's [I]requiring[/I] lots of memory as it is a matter of a classic [I]space-time tradeoff that saves significant time if Stage 2 can allocate many work areas[/I].

[quote]Also, in Stage 2, I've seen Prime95 display messages about processing "relative primes".[/quote]Without saying anything about the math:

The number of work areas allocated limits the number of relative primes that can be processed in a single pass. For instance, for a certain allocation amount Stage 2 will process 40 relative primes (out of 480) in each of 12 passes. With slightly larger allocations it will process 41, 42, or 43 relative primes in each pass, but there will still be 12 passes (43 * 11 = 473, so a twelfth pass is required for the last 7 relative primes). If the allocation allows processing 44 relative primes in each pass, the number of required passes declines to 11 (44*10 + 40*1 = 480), which will be faster.

[quote]Finally, I've heard of users with lots of RAM performing a "Brent-Suyama Extension" of P-1 with a value of E, where E is something like 6, 8, or 12. What exactly is this, and how much more does it increase the chances of P-1 finding a factor? How much RAM does one need before this extension becomes feasible?[/quote]The Brent-Suyama extension (by mathematicians Brent and Suyama, not to be confused with the person Mr. Brent Suyama who's not a mathematician) involves yet still more multiplications (* surprise, surprise *) that are worthwhile only when still more work areas (* surprise, surprise *) can be allocated to hold singly-calculated intermediate products.

There's some formula for determining when the tradeoff (for increased probability of finding a factor) is worth the extra effort or not, but I can't find it handily right now. One could look at the source code (probably module ecm.c) to find it. :-)

[QUOTE=Mini-Geek;253131]I'm afraid I don't know too much myself, but this page has some more detail on P-1, including the best explanation of stage 2 I can find on the web (though I'm still not clear on why stage 2 needs lots of memory, if I were to work out an example using the math there, I'd probably see).
[url]http://mersennewiki.org/index.php/P-1_Factorization_Method[/url][/QUOTE]

The mersennewiki page describes a plan for stage two which includes primes 6*j +/-1 for successive values of j. This plan does not require much memory. Prime95 uses a plan which includes primes d*j +/- i for d a small multiple of a small primorial chosen dependent upon the available memory, and for i relatively prime to d.

See post #29 in [url=http://www.mersenneforum.org/showthread.php?t=14562&page=2]this thread[/url], and subsequent discussion.

[QUOTE=NBtarheel_33;253113]I've read the description of the P-1 algorithm at [URL]http://www.mersenne.org/various/math.php[/URL], but there is no explanation of what the difference is between Stage 1 of P-1 and Stage 2 of P-1 that makes Stage 2 require so much more memory. My guess is that the same calculation is being performed in both stages, but there are many more primes to be included in the product E in Stage 2, and that the extra memory is used to hold these extra primes. I'm also guessing that the reason the save files for a P-1 double in size between Stages 1 and 2 is because of the (much) larger product that is being formed in Stage 2. Is that the right idea?[/QUOTE]

Not really. In stage 1 you compute 3^E - 1. In stage 2 you compute (3^(E*q[sub]1[/sub])-1)*(3^(E*q[sub]2[/sub])-1)*(3^(E*q[sub]3[/sub])-1)*... where the q[sub]i[/sub] are all primes between B1 and B2. This product is not "larger" than the result of the stage 1 computation, because all calculations are done mod N.

The save file is larger, not because the numbers are larger, but because you need to save more of them, including the current running value of the stage 2 product, the last term that was multiplied into it and the original result of stage 1.

[QUOTE]Also, in Stage 2, I've seen Prime95 display messages about processing "relative primes". What does this mean? Are these numbers that are relatively prime to one another? Typically, there is some number of relative primes - e.g. 480 - that are getting processed; are these selected out of the primes that lie between B1 and B2? And if so, how does Prime95 decide which primes get selected?[/QUOTE]

See the post I linked to in my reply to Mini-Geek.

[QUOTE]Finally, I've heard of users with lots of RAM performing a "Brent-Suyama Extension" of P-1 with a value of E, where E is something like 6, 8, or 12. What exactly is this,...[/QUOTE]

See the description from the GMP-ECM readme file in the linked post.

[QUOTE]...and how much more does it increase the chances of P-1 finding a factor?[/QUOTE]

A little, but not much. Basically the extension throws in additional primes above the B2 limit for a little extra computation. The benefit is marginal.

[QUOTE]How much RAM does one need before this extension becomes feasible?[/QUOTE]

It's feasible without a huge amount of memory. However, unless you do have a huge amount of memory, its usually better to use the memory you do have to enable more relative primes per pass.