Thread: trial factoring and P-1 View Single Post
2006-01-08, 05:45   #3

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts

Quote:
 Originally Posted by cheesehead My understanding is that, in the Prime95 implementation of the P-1 algorithm, b1 is the upper limit on the prime factors of the "k" of potential factors 2kp+1 of 2p-1 that are to be found by the P-1 method. That is, stage 1 P-1 with b1 = 10000 performed on 2p-1 will find any factor 2kp+1 of 2p-1 in which the largest prime factor of k is less than (or equal to, if b1 were prime itself) 10000.
Correction:

My understanding is that, in the Prime95 implementation of the P-1 algorithm, b1 is the upper limit on the power-of-a-prime factors of the "k" of potential factors 2kp+1 of 2p-1 that are to be found by the P-1 method.

That is, stage 1 P-1 with b1 = 10000 performed on 2p-1 will find any factor 2kp+1 of 2p-1 in which the largest power-of-a-prime factor of k is less than (or equal to, if b1 were prime itself) 10000.

Example:

59704785388637019242567 is a factor of 26049993 - 1.

59704785388637019242567 = 2 * 4934285493275531 * 6049993 + 1.

Prime95's P-1 stage 1 with b1 = 4000 would find this factor because the largest prime-power factor of 4934285493275531 is less than 4000.

4934285493275531 = 612 * 593 * 983 * 1153 × 1973.

612 = 3721.

In this example the factor 59704785388637019242567 could have been found in stage 1 with b1 as low as 3721.

Also, Prime95's P-1 stage 2 with b1 = 2000 and b2 = 4000 would find this factor because the largest prime-power factor of 4934285493275531 is less than 4000 and all other prime-power factors are less than 2000. (In fact, b1/b2 as low as b1 = 1973, b2 = 3721 would have worked.)