Speed of P-1 testing vs. Trial Factoring testing

[eepiccolo]

Here's a question involving the efficiency of our factor testing algorithms. 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? Specifically, if we effectively test x factors after running P-1 for 24 hours, how many factors would have we have been able to test in this amount of time using the brute force method instead?

[Deamiter]

Check out the eliptical curve thread here

It gets pretty long, but I believe it pretty much sums up p-1 factoring and it's relation to regular brute force factoring while staying on the non-technical side, as explanations go.

[cheesehead]

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.

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.

[eepiccolo]

Originally Posted by cheesehead

Trial factoring (which I consider a more accurate term than "brute force factoring")

OK, I knew there was a better term. It's hard to think sometimes when you have a head cold. :(

Hi guys, I found something out about the prime system that I believe is very beneficial. If you write the numbers first vertically in excel (free version here http://freestatistics.altervista.org...ick.php?fid=56 ), and then across the top from Right to Left (or Left to Right if need be), and then assign the number values to the spaces counted vertically (ie - 2 spaces for 2, 3 for 3), and start with the horizontal 2 matching the vertical 2 as a "1" 2-count, and follow this patters, not only are primes revealed, but also the basis of multiplication and division. This could easily be assembled to win a cash prize if any of you have good uses for the cash, I'd recommend it.



Oh, and here is what it looks like. :)

http://www.twocircuits.com/setemp/prime.jpg

[Hatori27]

Originally Posted by Falkon303

Hi guys, I found something out about the prime system that I believe is very beneficial. If you write the numbers first vertically in excel (free version here http://freestatistics.altervista.org...ick.php?fid=56 ), and then across the top from Right to Left (or Left to Right if need be), and then assign the number values to the spaces counted vertically (ie - 2 spaces for 2, 3 for 3), and start with the horizontal 2 matching the vertical 2 as a "1" 2-count, and follow this patters, not only are primes revealed, but also the basis of multiplication and division. This could easily be assembled to win a cash prize if any of you have good uses for the cash, I'd recommend it.



Oh, and here is what it looks like. :)

http://www.twocircuits.com/setemp/prime.jpg

This isn't really new. It's essentially the sieve of Eratosthenes, programmed into Excel.

[ewmayer]

Originally Posted by Hatori27

This isn't really new. It's essentially the sieve of Eratosthenes, programmed into Excel.

Microsoft is probably busy filing for a patent on it as we speak...