View Single Post
Old 2021-11-03, 23:37   #1
Bemusing Prompter
ixfd64's Avatar
Dec 2002

1001101000102 Posts
Default an idea to extend P-1 stage 1 to find more factors

For the first stage, the P-1 algorithm uses the highest power of each prime less than or equal to B1 when computing the product of the primes. However, this means we'll miss factors where k has a repeated factor greater than sqrt(B1).

102646067 and 105144859 are two examples with such factors. P-1 cannot normally find these without the now-unsupported Brent-Suyama extension. So my idea is to add an option to increase the power of each prime by 1 (or more) up to a percentage of the given value. For example, B1=1000000+50000 means that we do the first stage as normal, and then multiply E (or m) again by each prime up to 50000.

I just don't know how successful this method may be as there is no data on how many known factors there are where k has a repeated factor greater than the square root of the suggested B1 value. James could probably run some database queries on his website and find out for us.

Last fiddled with by ixfd64 on 2021-11-03 at 23:44
ixfd64 is offline   Reply With Quote