Speed of P1 testing vs. Trial Factoring testing
Here's a question involving the efficiency of our factor testing algorithms. 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? Specifically, if we effectively test x factors after running P1 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?

Check out the eliptical curve thread [url=http://www.teamprimerib.com/gimps/viewtopic.php?t=197]here[/url]
It gets pretty long, but I believe it pretty much sums up p1 factoring and it's relation to regular brute force factoring while staying on the nontechnical side, as explanations go. 
Re: Speed of P1 testing vs. brute force factor testing
[quote="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?[/quote]
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,[/quote] 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. 
Re: Speed of P1 testing vs. brute force factor testing
[quote="cheesehead"]
Trial factoring (which I consider a more accurate term than "brute force factoring") [/quote] OK, I knew there was a better term. It's hard to think sometimes when you have a head cold. :( 
Horizontal calculations for primes.
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 [URL="http://freestatistics.altervista.org/click/fclick.php?fid=56"]http://freestatistics.altervista.org/click/fclick.php?fid=56[/URL] ), 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" 2count, 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. :whistle:
Oh, and here is what it looks like. :) [URL="http://www.twocircuits.com/setemp/prime.jpg"]http://www.twocircuits.com/setemp/prime.jpg[/URL] 
[QUOTE=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 [URL="http://freestatistics.altervista.org/click/fclick.php?fid=56"]http://freestatistics.altervista.org/click/fclick.php?fid=56[/URL] ), 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" 2count, 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. :whistle:
Oh, and here is what it looks like. :) [URL="http://www.twocircuits.com/setemp/prime.jpg"]http://www.twocircuits.com/setemp/prime.jpg[/URL][/QUOTE] This isn't really new. It's essentially the sieve of Eratosthenes, programmed into Excel. 
[QUOTE=Hatori27]This isn't really new. It's essentially the sieve of Eratosthenes, programmed into Excel.[/QUOTE]
Microsoft is probably busy filing for a patent on it as we speak... 
All times are UTC. The time now is 10:24. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.