mersenneforum.org  

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

Reply
 
Thread Tools
Old 2013-01-10, 23:34   #1
dbaugh
 
dbaugh's Avatar
 
Aug 2005

11810 Posts
Default how much ECM without finding an existing factor

Using TF, I found a smallish factor of 1328447 (6765509895590355887). The following curves had already been run without finding this 63-bit factor. What is the worst case known of ECM missing a factor? How many hundred curves does theory say are needed to clear through 63 bits?

1 curves, B1=50000, B2=5000000 by "George Woltman" on 2007-12-18
3 curves, B1=50000, B2=5000000 by "Sturle Sunde" on 2008-10-13
3 curves, B1=50000, B2=5000000 by "Sturle Sunde" on 2009-02-21
3 curves, B1=50000, B2=5000000 by "Tapio Rajala" on 2009-07-26
3 curves, B1=50000, B2=5000000 by "SubPrime" on 2009-11-08
3 curves, B1=50000, B2=5000000 by "James Hintz" on 2010-06-11
3 curves, B1=50000, B2=5000000 by "Bruce" on 2011-02-23
1 curve, B1=50000, B2=5000000 by "Oscar Östlin" on 2011-11-19
3 curves, B1=50000, B2=5000000 by "James Hintz" on 2012-04-10
3 curves, B1=50000, B2=5000000 by "OS1" on 2012-10-30
dbaugh is offline   Reply With Quote
Old 2013-01-10, 23:37   #2
c10ck3r
 
c10ck3r's Avatar
 
Aug 2010
Kansas

547 Posts
Default

FWIW, P-1 would take FOREVER to find this, since its a prime k.
I lack sufficient understanding to answer the ECM question, however.
c10ck3r is offline   Reply With Quote
Old 2013-01-11, 00:01   #3
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

According to the well known GMP-ECM estimates, this is the ECM work data in that range:
Code:
t        B1   standard curves   Brent-Suyama curves
20     11e3           74                74
25      5e4          221               214
30     25e4          453               430
35      1e6          984               904
This indicates that t20 is 74 curves at B1=11000, while a t25 is 214 curves at 50000, the bounds reported there. A "t20" or "t30" or "t<number>" means that there's a exp(-1) ~ 37% chance of having missed a <number> sized factor. Doing twice the number of curves (or in general x times the number of curves) means that you have a exp(-2) ~ 14% (or exp(-x)) chance of having missed a factor of that size.

That data shows 25 curves done at the t25 level, which is well short of the 214 suggested (and still rather short of 74 curves at the lower t20). It's therefore well within the bounds of chance and reason that a 19 digit factor hadn't been found. One might guess that another 200 curves would *probably* find the factor (and maybe another factor closer to 25 digits than 20).

Last fiddled with by Dubslow on 2013-01-11 at 00:03 Reason: I accidentally a word
Dubslow is offline   Reply With Quote
Old 2013-01-11, 13:50   #4
Axon
 
Apr 2004
Russia

2×3 Posts
Default

If a big number has a factor between 262 and 263, then a probability of findind this factor with 26 ECM curves (B1=50000 and B2=100*B1) is about 0.75 (it may be inaccurate but I hope not very inaccurate).
Therefore it isn't so improbable that the factor was missed. To increase the probability of findind 63-bit factor up to 0.99 you should run about 90 ECM curves.
Axon is offline   Reply With Quote
Old 2013-01-11, 16:31   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

3·1,979 Posts
Default

Quote:
Originally Posted by Axon View Post
If a big number has a factor between 262 and 263, then a probability of findind this factor with 26 ECM curves (B1=50000 and B2=100*B1) is about 0.75 (it may be inaccurate but I hope not very inaccurate).
Therefore it isn't so improbable that the factor was missed. To increase the probability of findind 63-bit factor up to 0.99 you should run about 90 ECM curves.
These probabilities are based on an exponential distribution.
The probability of finding a 20 digit factor with 74 curves at 11e3 is 1-e^-1
With 37 curves 1-e^(-1/2). With n curves 1-e^(-n/74) etc.
99% chance of a 20 digit factor is 341 curves.
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Odds of Finding a Factor Gordon Factoring 18 2015-09-20 20:33
Probability of finding a factor JuanTutors Software 20 2004-09-26 09:47
Chances of finding a factor with ECM smh Factoring 16 2004-03-30 18:49
possibility of finding a factor there_is_no_spoon Math 10 2004-03-11 20:05
Probability of finding a factor in TF eepiccolo Math 4 2003-06-07 05:56

All times are UTC. The time now is 15:40.


Sun Nov 28 15:40:38 UTC 2021 up 128 days, 10:09, 0 users, load averages: 1.28, 1.22, 1.17

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