mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-01-07, 12:19   #1
eepiccolo
 
eepiccolo's Avatar
 
Dec 2002
Frederick County, MD

2·5·37 Posts
Default 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?
eepiccolo is offline   Reply With Quote
Old 2003-01-07, 14:09   #2
Deamiter
 
Deamiter's Avatar
 
Sep 2002

1658 Posts
Default

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.
Deamiter is offline   Reply With Quote
Old 2003-01-08, 02:38   #3
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default 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.
cheesehead is offline   Reply With Quote
Old 2003-01-10, 14:10   #4
eepiccolo
 
eepiccolo's Avatar
 
Dec 2002
Frederick County, MD

37010 Posts
Default 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. :(
eepiccolo is offline   Reply With Quote
Old 2006-03-28, 02:53   #5
Falkon303
 

11·359 Posts
Default 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
  Reply With Quote
Old 2006-03-28, 03:24   #6
Hatori27
 
Hatori27's Avatar
 
Jun 2005

22 Posts
Default

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.
Hatori27 is offline   Reply With Quote
Old 2006-03-28, 20:53   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2·5·1,129 Posts
Default

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...
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Anti-poverty drug testing vs "high" tax deduction testing kladner Soap Box 3 2016-10-14 18:43
Trial Factoring vs. LL-testing aketilander PrimeNet 18 2011-04-12 16:36
Trial factoring speed Unregistered Information & Answers 3 2009-03-01 02:43
Distributed Factoring and prime testing algorithms bunbun Software 6 2006-03-27 17:14
Hardware failure only detected on torture test or also when factoring/LL-testing...? Jasmin Hardware 10 2005-02-14 01:58

All times are UTC. The time now is 18:07.

Thu Jul 9 18:07:03 UTC 2020 up 106 days, 15:40, 1 user, load averages: 2.09, 1.88, 1.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.