mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-08-05, 21:58   #1
RedGolpe
 
RedGolpe's Avatar
 
Aug 2006
Monza, Italy

10010012 Posts
Default Chance to find an n-digit factor with ECM

I've been looking for the formula giving the chance to find a factor with n digits running a curve with B1=m in GMP-ECM 6.0.1, but had no luck. I also tried to interpolate the results given with the verbose option on, but again I couldn't figure the correct formula. Anyone can help?
RedGolpe is offline   Reply With Quote
Old 2006-08-05, 22:44   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

There isn't really a simple formula... unless a properly weighted integral of the Dickman rho function counts as "simple." GMP-ECM prints the probability of finding a factor of n decimal digits for n a multiple of five, 20≤n≤65. If you want accurate probabilities for different factor sizes, you could use the rho.gp script at
http://home.in.tum.de/~kruppa/rho.gp
It does the same computations that the code in GMP-ECM does (in fact the code in GMP-ECM is a port of the Pari/GP script) and allows you to specify the factor size as you please. See the comments at the start of the script. Feel free to ask here if you have specific questions about the script.

Alex
akruppa is offline   Reply With Quote
Old 2006-08-06, 06:14   #3
RedGolpe
 
RedGolpe's Avatar
 
Aug 2006
Monza, Italy

73 Posts
Default

Thank you. That was exactly what I was looking for.
RedGolpe is offline   Reply With Quote
Old 2007-03-23, 15:07   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

33·239 Posts
Default Should I go on ECMing?

Suppose that I have a C110 on which I've run 100 curves at B1=10^7 without success.

I obviously now have some posterior information about the factors; by using rho.gp, I can see that it is very unlikely that there's a factor <10^30, and that there's about a 50% chance that I'd have missed a factor <10^35.

I now have a choice. In 24 hours, I can guarantee to find with ggnfs any factor that there might be. Or I could run a thousand curves at 10^7, which would reasonably reliably find any factor <10^40, and might quickly pop up a factor <10^35, but if it finds nothing I still have to run the ggnfs.

[I want to minimise expected time to solution. ggnfs takes 24 hours, one curve takes 90 seconds, so I should do the single curve if it has P>1/960 of finding a factor; if it succeeds I'm happy, if it doesn't succeed then I know the next curve has less chance of finding a factor]

I suspect the right strategy now is to go straight to ggnfs; I don't think that 500 curves at 10^7, which would run for 12 hours, has as much as a 50% chance of finding the factor; that is, I believe that the probability that a C110 with no factor <10^32 has a smallest factor between 10^32 and 10^40 is less that 0.5. But I don't know how to go about computing that probability ... it may be in the current edition of Knuth volume 2, but I have the first edition of that volume and it's not there.

I suppose I could quantise and use a Bayesian approach; what's a good reference to find what the prior probability distribution of the number of digits in the second-largest factor of a C110 looks like? Then I just run Bayes's theorem 100 times using rho.gp as probability(factorises with one ECM@1E7| factor of N digits) to get what probability (factor of N digits| does not factorise with 100 ECM@1e7), and then get a probability of success with the next curve as sum_N P(factor has N digits) P(one curve @1e7 factorises a number with a factor of N digits).
fivemack is offline   Reply With Quote
Old 2007-03-23, 15:24   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22·5·373 Posts
Default

Quote:
Originally Posted by fivemack View Post
Suppose that I have a C110 on which I've run 100 curves at B1=10^7 without success.

I obviously now have some posterior information about the factors; by using rho.gp, I can see that it is very unlikely that there's a factor <10^30, and that there's about a 50% chance that I'd have missed a factor <10^35.

<snip>

[I want to minimise expected time to solution. ggnfs takes 24 hours, one curve takes 90 seconds, so I should do the single curve if it has P>1/960 of finding a factor; if it succeeds I'm happy, if it doesn't succeed then I know the next curve has less chance of finding a factor]

I suspect the right strategy now is to go straight to ggnfs;

<snip>

I suppose I could quantise and use a Bayesian approach;

Read my joint paper with Sam Wagstaff: "A Practical
Analysis of the Elliptic Curve Factoring Algorithm". This paper does indeed
use Bayes' theorem to solve the problem of when to switch.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New 70 digit factor R.D. Silverman Cunningham Tables 16 2016-01-23 22:16
DC chance to find Mersenne Prime houding PrimeNet 1 2014-02-24 20:25
73 digit ECM factor akruppa Factoring 103 2010-11-27 20:51
160 digit factor found of 366 digit (PRP-1) AntonVrba Factoring 7 2005-12-06 22:02
How much ECM does it take to find a given factor? geoff Factoring 5 2004-09-29 20:14

All times are UTC. The time now is 11:46.


Tue Jul 5 11:46:32 UTC 2022 up 82 days, 9:47, 1 user, load averages: 1.53, 1.40, 1.25

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.

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