mersenneforum.org Q: Reasonable time to find a factor
 Register FAQ Search Today's Posts Mark Forums Read

 2018-05-09, 07:15 #1 jnml   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.
 2018-05-09, 08:35 #2 firejuggler     "Vincent" Apr 2010 Over the rainbow 23·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 2018-05-09 at 08:45
2018-05-09, 08:39   #3
jnml

Feb 2012
Prague, Czech Republ

5×37 Posts

Quote:
 Originally Posted by firejuggler You will have to be more specific. you want to completly factorise or just find one factor? With what kind of hardware?
Not completely factorize, just find any divisor, prime or not.

HW: For example, say a middle class, 2-core Intel i5-6470 @3GHz, 16GB machine.

 2018-05-09, 11:01 #4 VictordeHolland     "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 P-1 or ECM, but it can take days to find a factor (they're usually larger than the TF factors).
2018-05-09, 16:38   #5
petrw1
1976 Toyota Corona years forever!

"Wayne"
Nov 2006

3×11×157 Posts

Quote:
 Originally Posted by jnml Not completely factorize, just find any divisor, prime or not. HW: For example, say a middle class, 2-core Intel i5-6470 @3GHz, 16GB machine.
Depends on if you have a GPU (Graphics Card) or only the CPU.

A newer CPU will produce 5-10 GhzDays (A GIMPS unit of work) per core per day.
A newer GPU doing TF will produce 500-1000 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 P-1 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 P-1 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 P-1 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 P-1
- 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.

 2018-05-09, 20:01 #6 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 2·34·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 2P-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.
2018-05-09, 20:40   #7
chalsall
If I May

"Chris Halsall"
Sep 2002

3×5×17×41 Posts

Quote:
 Originally Posted by Uncwilly Your odds of finding a factor while doing TF are about 1/bit number.
Please note that this is an unproven guestimate.

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

2018-05-09, 20:56   #8
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts

Quote:
 Originally Posted by chalsall Please note that this is an unproven guestimate.
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:
 Originally Posted by chalsall ...the actual percentage of factors found per depth attempted tends to be less than this formula gives.
I believe this follows as well from the same underlying mathematics, see e.g. Skewes' number.

 2018-05-09, 21:21 #9 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 Posts Some p ( those that are both 3 mod 4 and 2p+1) show that it depends on p.
2018-05-09, 21:22   #10
petrw1
1976 Toyota Corona years forever!

"Wayne"
Nov 2006

3×11×157 Posts

Quote:
 Originally Posted by chalsall Please note that this is an unproven guestimate. 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.
Just a theory:

Could it also be that once P-1 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 P-1 (i.e. B1-B2); more so with a stronger P-1?

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 DC-TF there is a much greater chance P-1 has already been done.

2018-05-09, 21:23   #11
chalsall
If I May

"Chris Halsall"
Sep 2002

3×5×17×41 Posts

Quote:
 Originally Posted by Dubslow The estimate has a solid logical basis underlying it.
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

 Similar Threads Thread Thread Starter Forum Replies Last Post wwf Factoring 26 2013-09-30 04:24 RedGolpe Factoring 4 2007-03-23 15:24 geoff Factoring 5 2004-09-29 20:14 dsouza123 Software 3 2003-12-11 00:48 dsouza123 Software 12 2003-08-21 18:38

All times are UTC. The time now is 00:50.

Wed May 25 00:50:43 UTC 2022 up 40 days, 22:52, 0 users, load averages: 1.76, 1.75, 1.89