Pminus1 - Bug report and feature request

[ewmayer]

Originally Posted by axn

Stage 1 of P-1 is implemented in two steps, a fast(er) Stage 0 and a slow(er) regular Stage 1.

That says nothing about the algorithmic differences between the 2 sub-stages - if I had to guess, I would surmise that:

[0] 'Stage 0' is the classic fixed-upper-bound p-1 stage 1 implemented using fast left-to-right [LR] binary modexp, which for a roughly equal mix of 0s and 1s in the small-primes-powers product runs in around 2/3 the time of the right-to-left [RL] variant of binary modexp which we turn to next.

[1] The disadvantages to [0] is that the small-primes product must be precomputed and should the ensuing GCD fail to find a factor, and subsequent stage 2 also fail to find a factor, we cannot "deepen" Stage 0 to a large primes bound using the LR modexp algorithm. Thus we introduce a 'Stage 1' based on an RL modexp, which can take a Stage 0 output residue and power it to any desired larger small-primes bound, at a cost of ~1.5x per powering bit compared to Stage 0's LR modexp.

If in fact George's 'Stage 0' and 'Stage 1' refer to something different, I would appeciate a description of that.

[Prime95]

Originally Posted by ewmayer

If in fact George's 'Stage 0' and 'Stage 1' refer to something different, I would appeciate a description of that.

Your understanding is correct.

[axn]

Just an update.

Since switching to the new build, I've completed 60 P-1 test without any factors found. About 5 factors are expected. Could be just luck of the draw, I guess. But, if I get to 100 without factors, I might have to QC them with previous version :-(

Probably I will run some with known factors first.

[axn]

Originally Posted by axn

Probably I will run some with known factors first.

A run with the new version found 16 of 17 known factors, only missing 25766609245631959384399, which is a B-S factor (different bounds between first and second run). So, everything looks fine. Just the luck of the draw, then.