mersenneforum.org SNFS(27x) How much ECM before switching to NFS?
 Register FAQ Search Today's Posts Mark Forums Read

 2015-05-29, 16:41 #1 YuL     Feb 2012 Paris, France 7×23 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?
2015-05-29, 16:53   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by YuL 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?

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.

2015-05-29, 16:57   #3
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by R.D. Silverman Read my paper: A Practical Analysis of ECM. It tells you how to answer your question. 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.
A Modest Proposal:

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

2015-05-29, 17:50   #4
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

24DC16 Posts

Quote:
 Originally Posted by YuL I have a SNFS 271 is ~45000 thread.hour of sieving
Sounds just about right if it is a deg 6 without special circumstances.

2015-05-29, 19:31   #5
wblipp

"William"
May 2003
New Haven

3·787 Posts

Quote:
 Originally Posted by R.D. Silverman A Modest Proposal: 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)????
A modest amendment to the proposal:

Based on how often this suggestion is made, perhaps a corrected version of the paper should be made available?

2015-05-29, 20:19   #6
YuL

Feb 2012
Paris, France

7×23 Posts

Quote:
 Originally Posted by R.D. Silverman Allow me to ask: Are you sure about your sieve time for the C271?? It seems low to me.
Yes I am. 45000 thread.hour of sieving produced 350M relations which was enough
to build a (25.1M x 25.1M) matrix and as pointed out by Batalov above it is a deg 6
polynomial.

2015-05-29, 20:33   #7
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by wblipp A modest amendment to the proposal: Based on how often this suggestion is made, perhaps a corrected version of the paper should be made available?
There is indeed one typo. Part of the expression for the Dickman rho_2 function was omitted. It is readily found in Knuth Vol II.

It does not affect the results.

2015-05-29, 20:36   #8
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by R.D. Silverman There is indeed one typo. Part of the expression for the Dickman rho_2 function was omitted. It is readily found in Knuth Vol II. It does not affect the results.
I would have sent the correction to the AMS, but Math Comp does not publish
corrigenda. (AFAIK)

2015-05-29, 21:20   #9
wreck

"Bo Chen"
Oct 2005
Wuhan,China

2508 Posts

Quote:
 Originally Posted by YuL 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?
I have a simple method to judge how many hour is enough for the ecm if the snfs time is known.
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.

2015-06-01, 09:28   #10
YuL

Feb 2012
Paris, France

101000012 Posts

Quote:
 Originally Posted by wreck I have a simple method to judge how many hour is enough for the ecm if the snfs time is known. 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.
Thank you for your input. Indeed a t55 has already been done.
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.

2015-06-01, 12:55   #11
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by YuL Thank you for your input. Indeed a t55 has already been done. 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.
"wreck" is not knowledgeable in this area. He seems to have pulled his ".1" constant
from where the sun don't shine.

BTW, what is so blankety-blank 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post PawnProver44 Puzzles 10 2016-03-16 06:25 esqrkim Hardware 9 2010-03-02 20:27 Numbers Hardware 7 2005-09-12 19:10 tha Lone Mersenne Hunters 11 2004-05-17 15:43 sonjohan Software 2 2003-11-01 01:23

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

Wed May 19 00:17:54 UTC 2021 up 40 days, 18:58, 0 users, load averages: 1.98, 1.97, 1.75