mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-05-29, 16:41   #1
YuL
 
YuL's Avatar
 
Feb 2012
Paris, France

5×31 Posts
Default 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?
YuL is offline   Reply With Quote
Old 2015-05-29, 16:53   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by YuL View Post
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?
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-05-29, 16:57   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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)????
R.D. Silverman is offline   Reply With Quote
Old 2015-05-29, 17:50   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×33×132 Posts
Default

Quote:
Originally Posted by YuL View Post
I have a SNFS 271 is ~45000 thread.hour of sieving
Sounds just about right if it is a deg 6 without special circumstances.
Batalov is offline   Reply With Quote
Old 2015-05-29, 19:31   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·32·5·13 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
wblipp is offline   Reply With Quote
Old 2015-05-29, 20:19   #6
YuL
 
YuL's Avatar
 
Feb 2012
Paris, France

5·31 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post

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.
YuL is offline   Reply With Quote
Old 2015-05-29, 20:33   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by wblipp View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-05-29, 20:36   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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)
R.D. Silverman is offline   Reply With Quote
Old 2015-05-29, 21:20   #9
wreck
 
wreck's Avatar
 
"Bo Chen"
Oct 2005
Wuhan,China

A116 Posts
Default

Quote:
Originally Posted by YuL View Post
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.
wreck is offline   Reply With Quote
Old 2015-06-01, 09:28   #10
YuL
 
YuL's Avatar
 
Feb 2012
Paris, France

2338 Posts
Default

Quote:
Originally Posted by wreck View Post
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.
YuL is offline   Reply With Quote
Old 2015-06-01, 12:55   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by YuL View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Switching digits test PawnProver44 Puzzles 10 2016-03-16 06:25
Switching computers esqrkim Hardware 9 2010-03-02 20:27
Switching Boxes Numbers Hardware 7 2005-09-12 19:10
switching to doublechecking tha Lone Mersenne Hunters 11 2004-05-17 15:43
switching PC's for same exponent sonjohan Software 2 2003-11-01 01:23

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

Sun Oct 25 11:08:49 UTC 2020 up 45 days, 8:19, 0 users, load averages: 1.93, 1.59, 1.54

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