Quote:
Originally Posted by eepiccolo
The impression I get is that P1 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 P1?

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. P1 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 P1 for 24 hours,

That's not quite how P1 progresses. It searches a different mathematical space than trial factoring searches. P1 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^p1 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 bruteforcing 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 P1 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 P1 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.