Thread: trial factoring and P-1 View Single Post
2006-01-08, 16:16   #5
jocelynl

Sep 2002

2×131 Posts

Quote:
 Originally Posted by cheesehead 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.)
I stand corrected!