mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Speed of P-1 testing vs. Trial Factoring testing (https://www.mersenneforum.org/showthread.php?t=291)

 eepiccolo 2003-01-07 12:19

Speed of P-1 testing vs. Trial Factoring testing

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 2003-01-07 14:09

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 p-1 factoring and it's relation to regular brute force factoring while staying on the non-technical side, as explanations go.

Re: Speed of P-1 testing vs. brute force factor testing

[quote="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?[/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. 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,[/quote]
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 2003-01-10 14:10

Re: Speed of P-1 testing vs. brute force factor testing

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. :(

 Falkon303 2006-03-28 02:53

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" 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. :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]

 Hatori27 2006-03-28 03:24

[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" 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. :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.

 ewmayer 2006-03-28 20:53

[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.