View Single Post
Old 2003-01-08, 02:38   #3
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default Re: Speed of P-1 testing vs. brute force factor testing

Quote:
Originally Posted by eepiccolo
The impression I get is that P-1 testing must be somehow more efficient than the brute force factoring we do (which goes up to testing factors to 2^68 for ten million digit numbers), but how much more efficient is P-1?
It's a matter of ranges.

Trial factoring (which I consider a more accurate term than "brute force factoring") is more efficient in low ranges. P-1 is more efficient in other ranges, and ECM and NFS have their own ranges of greater relative efficiency.

Maybe I can compile a table of relative efficiencies in certain ranges if I get energetic.

Quote:
Specifically, if we effectively test x factors after running P-1 for 24 hours,
That's not quite how P-1 progresses. It searches a different mathematical space than trial factoring searches. P-1 proceeds through a space whose coordinates are the prime factors of [(a potential Mersenne factor)-1], not the space whose coordinates are potential Mersenne factors themselves.

Let's assume for the moment that we didn't know that any factor of 2^p-1 has the form 2kp+1 and has to be +-1 mod 8 (did I get that right?), that we weren't looping through congruence classes, that the only shortcut we knew was that we could skip looking at composites or 2 as potential factors, so that we were simply brute-forcing our way through all the odd primes as possibilities.

Then such simplified trial factoring would test potential factors in the order 3, 5, 7, 11, ...

Such simplified P-1 factoring to stage 1 limit B1 would simultaneously test all potential prime factors of the form (product of [prime powers no greater than B1])+1. It would also catch composite factors which were products of prime factors of that form. That is, for B1 = 30 it would simultaneously test all potential prime factors of the form (product of [(2,4,8 or 16),(3,9 or 27),(5 or 25),7,11,13,17,19,23, and/or 29])+1 and all potential composite factors which were products of prime factors of that form. The maximum prime factor that this simplified P-1 stage 1 could potentially find with B1 = 30 would be 16*27*25*7*11*13*17*19*23*29 + 1 = 2329089562801 (that is, _if_ 2329089562801 were prime, which it's not, or _if_ all prime factors of 2329089562801 = 101*271*2311*36821 were of the above form, of which 36821 = 4*5*7*263 + 1 is not - so this isn't the greatest example in the world (but B1 = 263 would find it)), but it would not find any of the smaller prime factors which were not of the above form.
cheesehead is offline   Reply With Quote