mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-05-09, 07:15   #1
jnml
 
Feb 2012
Prague, Czech Republ

5×37 Posts
Default 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.
jnml is offline   Reply With Quote
Old 2018-05-09, 08:35   #2
firejuggler
 
firejuggler's Avatar
 
"Vincent"
Apr 2010
Over the rainbow

23·5·71 Posts
Default

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
firejuggler is online now   Reply With Quote
Old 2018-05-09, 08:39   #3
jnml
 
Feb 2012
Prague, Czech Republ

5×37 Posts
Default

Quote:
Originally Posted by firejuggler View Post
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.
jnml is offline   Reply With Quote
Old 2018-05-09, 11:01   #4
VictordeHolland
 
VictordeHolland's Avatar
 
"Victor de Hollander"
Aug 2011
the Netherlands

2×19×31 Posts
Default

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).
VictordeHolland is offline   Reply With Quote
Old 2018-05-09, 16:38   #5
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

3×11×157 Posts
Default

Quote:
Originally Posted by jnml View Post
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.
petrw1 is offline   Reply With Quote
Old 2018-05-09, 20:01   #6
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2·34·5·13 Posts
Default

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.
Uncwilly is online now   Reply With Quote
Old 2018-05-09, 20:40   #7
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

3×5×17×41 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
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.)
chalsall is online now   Reply With Quote
Old 2018-05-09, 20:56   #8
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

Quote:
Originally Posted by chalsall View Post
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 View Post
...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.
Dubslow is offline   Reply With Quote
Old 2018-05-09, 21:21   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Some p ( those that are both 3 mod 4 and 2p+1) show that it depends on p.
science_man_88 is offline   Reply With Quote
Old 2018-05-09, 21:22   #10
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

3×11×157 Posts
Default

Quote:
Originally Posted by chalsall View Post
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.
petrw1 is offline   Reply With Quote
Old 2018-05-09, 21:23   #11
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

3×5×17×41 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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
chalsall is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Can Pollard Rho cycles be used to find a factor? wwf Factoring 26 2013-09-30 04:24
Chance to find an n-digit factor with ECM RedGolpe Factoring 4 2007-03-23 15:24
How much ECM does it take to find a given factor? geoff Factoring 5 2004-09-29 20:14
How large a factor can P-1 testing find ? dsouza123 Software 3 2003-12-11 00:48
Shortest time to complete a 2^67 trial factor (no factor) 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔