20180509, 07:15  #1 
Feb 2012
Prague, Czech Republ
5×37 Posts 
Q: Reasonable time to find a factor
Can anybody please provide some overview of what are roughly the estimated average
times to find a factor of a Mp (prime p, Mp a known composite) as a function of p or a table of ranges and the respective times, using the best known software/algorithms running on contemporary commodity hardware? Something like up to x: in microseconds up to y: few seconds at most, usually up to z: few days/weeks etc from nn bits: no one knows for sure, expected propbably at least foo bars for p == xx Thanks in advance for any insight. 
20180509, 08:35  #2 
"Vincent"
Apr 2010
Over the rainbow
2^{3}·5·71 Posts 
You will have to be more specific. you want to completly factorise or just find one factor? With what kind of hardware?
For example M1277, wich has no factor know so far, has an estimated factoring time of 660 cpu year (see http://mersenneforum.org/showpost.ph...0&postcount=10) However M750,999,653 has a found factor, and it can be found ina few millisecond. Last fiddled with by firejuggler on 20180509 at 08:45 
20180509, 08:39  #3  
Feb 2012
Prague, Czech Republ
5×37 Posts 
Quote:
HW: For example, say a middle class, 2core Intel i56470 @3GHz, 16GB machine. 

20180509, 11:01  #4 
"Victor de Hollander"
Aug 2011
the Netherlands
2×19×31 Posts 
I assume you want to find new factors. If you have a half decent graphics cards you can use it for Trial Factoring and find multiple factors per day (depending on the range). With the CPU you can do P1 or ECM, but it can take days to find a factor (they're usually larger than the TF factors).

20180509, 16:38  #5  
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
3×11×157 Posts 
Quote:
A newer CPU will produce 510 GhzDays (A GIMPS unit of work) per core per day. A newer GPU doing TF will produce 5001000 GhzDays per day. At a high level:  If you have a GPU use it for TF and it could find a several factors daily.  If you only have a CPU and can allocate at least 1G+ of RAM use it for P1 and expect a couple factors per month per core.  If you have very little RAM to spare use the CPU for ECM and expect at best about 1 factor per month total.  You can use the CPU for TF as well (some do); expect a couple per week. It you want to do some deeper analysis read on.... This page http://www.mersenne.ca/credit.php can calculate the GzhDays required for whatever assignment you are doing.  Choose Trial, ECM or P1 Factoring  Enter the required parameters  For TF it will give the GhzDays required and the Chance of a Factor (About 1/x where x is the TF bit level)  For P1 it will give the GhzDays only: Then you can use this: http://www.mersenne.ca/prob.php to find the Chance of a Factor for P1  For ECM it gives GhzDays only. Change of a Factor for ECM is a little harder to find but it is quite low. Feedback from this forum suggests it is the least efficient method for actoring. Further it is really only worthwhile for small exponents (<20,000,000) Using the above you can calculate for your CPU/GPU the GhzDays for assignments of interest and the corresponding Chance of a Factor. 

20180509, 20:01  #6 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
2·3^{4}·5·13 Posts 
If your are running the LL test, it does not look for factors. So, it won't find them, no matter how long you run them.
If you are doing Trial Factoring, then the time does vary based upon the size of the exponent P ins 2^{P}1 and the bit level you are looking at. The lower the bit number, the faster the search and the higher the odds of finding a factor. The higher the exponent and the lowest possible bit level of a factor moves up. And thus larger bit numbers are processed faster on larger exponents. Your odds of finding a factor while doing TF are about 1/bit number. They are additive, so if you are going from 40 bits to 50 bits you add 1/41 + 1/42 .... 1/49 + 1/50. 
20180509, 20:40  #7  
If I May
"Chris Halsall"
Sep 2002
Barbados
3×5×17×41 Posts 
Quote:
GPU72 has been collecting empirical data on factoring attempts vs. factors found, and the actual percentage of factors found per depth attempted tends to be less than this formula gives. (Please also note that this query is against the raw database of a few million records, so it's rather expensive. Please give the server a few seconds to render the report.) 

20180509, 20:56  #8  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
The estimate has a solid logical basis underlying it. Just how large the error term is isn't very well understood (our understanding hinges on that most famous of hypotheses), but we do know conclusively that it's about as good as possible first approximation.
Quote:


20180509, 21:21  #9 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Some p ( those that are both 3 mod 4 and 2p+1) show that it depends on p.

20180509, 21:22  #10  
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
3×11×157 Posts 
Quote:
Could it also be that once P1 is done (since it "steals" a few factors) that the TF hit ratio for subsequent TF's will be lower than expected? Less so with a minimal P1 (i.e. B1B2); more so with a stronger P1? Your "emperical" report shows a hit ratio closer to this "unproven guestimate" for LL than for DC. I think that might be because by the time we are doing DCTF there is a much greater chance P1 has already been done. 

20180509, 21:23  #11 
If I May
"Chris Halsall"
Sep 2002
Barbados
3×5×17×41 Posts 
Trust a mathematician to reject the empirical...
Empirical: TF'ing from 72 to 73; 569,553 attempts, 7,682 factors found, 1.349% success rate. Predicted: 1.370% 73 to 74: 503,758 attempts, 6,403 factors found, 1.271%. Predicted: 1.351%. 74 to 75: 380,496, 4,611, 1.212%. Predicted: 1.333... I will agree that given an infinite sample set that /maybe/ the empirical and the theoretical would converge. On the other hand, maybe not.... "The most exciting phrase to hear in science, the one that heralds new discoveries, is not 'Eureka!' but 'That's funny...'"  Asimov 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Can Pollard Rho cycles be used to find a factor?  wwf  Factoring  26  20130930 04:24 
Chance to find an ndigit factor with ECM  RedGolpe  Factoring  4  20070323 15:24 
How much ECM does it take to find a given factor?  geoff  Factoring  5  20040929 20:14 
How large a factor can P1 testing find ?  dsouza123  Software  3  20031211 00:48 
Shortest time to complete a 2^67 trial factor (no factor)  dsouza123  Software  12  20030821 18:38 