mersenneforum.org > Math Speed of P-1 testing vs. Trial Factoring testing
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2003-01-07, 12:19 #1 eepiccolo     Dec 2002 Frederick County, MD 37010 Posts 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?
 2003-01-07, 14:09 #2 Deamiter     Sep 2002 1658 Posts 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.
2003-01-08, 02:38   #3

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
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.

2003-01-10, 14:10   #4
eepiccolo

Dec 2002
Frederick County, MD

2×5×37 Posts
Re: Speed of P-1 testing vs. brute force factor testing

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

 2006-03-28, 02:53 #5 Falkon303   24CB16 Posts 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 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
2006-03-28, 03:24   #6
Hatori27

Jun 2005

48 Posts

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

2006-03-28, 20:53   #7
ewmayer
2ω=0

Sep 2002
República de California

263768 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post kladner Soap Box 3 2016-10-14 18:43 aketilander PrimeNet 18 2011-04-12 16:36 Unregistered Information & Answers 3 2009-03-01 02:43 bunbun Software 6 2006-03-27 17:14 Jasmin Hardware 10 2005-02-14 01:58

All times are UTC. The time now is 13:05.

Thu Sep 24 13:05:36 UTC 2020 up 14 days, 10:16, 2 users, load averages: 1.56, 1.87, 1.80