20150529, 16:41  #1 
Feb 2012
Paris, France
5×31 Posts 
SNFS(27x) How much ECM before switching to NFS?
I'm actually thinking about factorization of two numbers one is SNFS 270.7
and the other is SNFS 273.7. The "2/9 of SNFS difficulty" rule suggests doing t60 before switching to NFS but I'm thinking to myself isn't that too much? Specially given the fact that one curve @260M takes ~1h and a t60 is 42000 curves @260M from which I deduce that t60 is ~42000 thread.hour which is not that far from the amount of sieving needed (based on the data I have a SNFS 271 is ~45000 thread.hour of sieving). What do you think? 
20150529, 16:53  #2  
Nov 2003
2^{6}·113 Posts 
Quote:
Start by computing the *expected* time to find the factor. How do you do this? Bayesian statistics. You have a known prior for the density function for the size of an unknown factor. The ECM data gives a sample density function. Convolve them to get the posterior. Look at the expected value of the posterior. Compute the expected time to find this (now presumed) factor with ECM. Ask: is it less than the time to run SNFS? Allow me to ask: Are you sure about your sieve time for the C271?? It seems low to me. 

20150529, 16:57  #3  
Nov 2003
2^{6}·113 Posts 
Quote:
Based upon how often this kind of question comes up, perhaps the paper should be required reading before anyone is allowed to ask questions of this kind (and related questions)???? 

20150529, 17:50  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×3^{3}×13^{2} Posts 

20150529, 19:31  #5  
"William"
May 2003
New Haven
2^{2}·3^{2}·5·13 Posts 
Quote:
Based on how often this suggestion is made, perhaps a corrected version of the paper should be made available? 

20150529, 20:19  #6  
Feb 2012
Paris, France
5·31 Posts 
Quote:
to build a (25.1M x 25.1M) matrix and as pointed out by Batalov above it is a deg 6 polynomial. 

20150529, 20:33  #7  
Nov 2003
2^{6}·113 Posts 
Quote:
It does not affect the results. 

20150529, 20:36  #8  
Nov 2003
2^{6}·113 Posts 
Quote:
corrigenda. (AFAIK) 

20150529, 21:20  #9  
"Bo Chen"
Oct 2005
Wuhan,China
A1_{16} Posts 
Quote:
Firstly,run 1/10 time of ecm compare to snfs,then judge whether it is enough. For snfs 270,I suppose t55 is achieved,then the question become to whether t60 is necessary. As you said,t60 need 40000 hours.t55 to t60 get a probability 0.1 to factor this number,snfs get a probability 1 to factor it. 0.1/40000 is less than 1/45000,so it is no need to do the t60. 

20150601, 09:28  #10  
Feb 2012
Paris, France
233_{8} Posts 
Quote:
I think I'll add a t55 by running 7600 curves @260M in order to reduce the probability of missing a 55 digits factor and doing so will complete ~0.2t60. 

20150601, 12:55  #11  
Nov 2003
2^{6}·113 Posts 
Quote:
from where the sun don't shine. BTW, what is so blanketyblank special about 55 digits??? The real issue is whether you will succeed faster *in expectation* by using NFS or by using ECM. I told you how to do that computation. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Switching digits test  PawnProver44  Puzzles  10  20160316 06:25 
Switching computers  esqrkim  Hardware  9  20100302 20:27 
Switching Boxes  Numbers  Hardware  7  20050912 19:10 
switching to doublechecking  tha  Lone Mersenne Hunters  11  20040517 15:43 
switching PC's for same exponent  sonjohan  Software  2  20031101 01:23 