20030107, 12:19  #1 
Dec 2002
Frederick County, MD
2·5·37 Posts 
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?

20030108, 02:38  #3  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Re: Speed of P1 testing vs. brute force factor testing
Quote:
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:
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. 

20030110, 14:10  #4  
Dec 2002
Frederick County, MD
370_{10} Posts 
Re: Speed of P1 testing vs. brute force factor testing
Quote:


20060328, 02:53  #5 
11·359 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" 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.
Oh, and here is what it looks like. :) http://www.twocircuits.com/setemp/prime.jpg 
20060328, 03:24  #6  
Jun 2005
2^{2} Posts 
Quote:


20060328, 20:53  #7  
∂^{2}ω=0
Sep 2002
República de California
2·5·1,129 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Antipoverty drug testing vs "high" tax deduction testing  kladner  Soap Box  3  20161014 18:43 
Trial Factoring vs. LLtesting  aketilander  PrimeNet  18  20110412 16:36 
Trial factoring speed  Unregistered  Information & Answers  3  20090301 02:43 
Distributed Factoring and prime testing algorithms  bunbun  Software  6  20060327 17:14 
Hardware failure only detected on torture test or also when factoring/LLtesting...?  Jasmin  Hardware  10  20050214 01:58 