20160219, 17:17  #1 
Apr 2014
Marlow, UK
2^{3}·7 Posts 
General factoring algorithms not using sieving
Can anyone tell me what the best general factoring algorithm is, that doesn't use sieving, for numbers in the 60100 digit range? (Very) roughly how long might this take to factor an 80digit number, say, on a standard desktop machine using a single thread? (Let's assume it uses GMP for bigint operations.)
Thanks in advance, Mick. 
20160219, 17:37  #2 
Tribal Bullet
Oct 2004
2×3×19×31 Posts 
The most powerful such algorithm known is ECM, in fact all the others are exponentialtime.
The time needed to factor an 80digit number using ECM can vary hugely; if it has two 40digit factors it could take hours, while if it has a 10digit factor it will be done in less than 1 second. 
20160219, 17:41  #3  
Apr 2014
Marlow, UK
2^{3}·7 Posts 
Quote:


20160219, 17:45  #4 
Bemusing Prompter
"Danny"
Dec 2002
California
2364_{10} Posts 
The quadratic sieve is a generalpurpose factoring algorithm. Aside from that and ECM, other algorithms aren't too efficient.
Last fiddled with by ixfd64 on 20160219 at 17:48 
20160219, 17:51  #5 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2^{2}×227 Posts 
Can you elaborate on why ECM is 'special'? I keep reading your question and nodding along with Jason's answer of ECM, given that QS and NFS are taken away.

20160219, 18:13  #6  
"Ben"
Feb 2007
3,371 Posts 
Quote:
squfof is a nonsieving N^(1/4) algorithm. If a 20 digit number takes a millisecond, an 80 digit number would be 10^(8020)^(1/4) times harder or about 1e15 milliseconds. 

20160219, 18:24  #7  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×29×83 Posts 
Quote:
So for any number of reasonable size, like the 80 digits you mention, the only (reasonable) options are ECM, SIQS and NFS, and you specified nonsieving, so that leaves ECM. 

20160219, 18:26  #8  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
quoting the whole thing gives eliminations that can be done: Quote:
Last fiddled with by science_man_88 on 20160219 at 18:29 

20160219, 19:03  #9  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10587_{10} Posts 
Quote:
A factor p of N is expected to be found in time subexponential of the size of p. At least one factor is not greater than sqrt(N). The result follows. ECM is not a deterministic algorithm but it is not clear that the question requires such. The sieving algorithms are equally nondeterministic. Last fiddled with by xilman on 20160219 at 19:05 

20160219, 19:46  #10  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2^{2}·227 Posts 
Quote:
The word special is typically used to denote an input of a particular form. E.g. the special quadratic sieve (Crandall/Pomerance p. 276) or special number field sieve (ibid p. 299). Similar for primality testing. Quoting from page 173 of Riesel 1994 "Firstly, there are certain special factorization methods (or adaptations of general methods), which are advantageous if the number to be factored has a particular mathematical form." It goes on to mention that general factorization methods have two kinds  those that find factors of N in approximate order of magnitude and those whose time does not depend on the size of the factors. IMO the wikipedia page should be changed, but that's another topic. Back to the main topic, CFRAC would be a decent choice, except development of it basically stopped as soon as QS came out  are there any current implementations? I remember trying a few in 2009 but they were all student projects, most weren't very usable, and none had decent performance. ECM has a number of quite good implementations. I like SQUFOF for small numbers, but it seems impractical at 80+ digits (correct me if this is wrong). 

20160219, 21:07  #11 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
I don't think you are wrong because google searching suggest that even on this forum with some implementations it only seemed good to 55 bits and online comments suggest 2^60 as roughly that suggested numbers to test with it.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
S9 and general sieving discussion  Lennart  Conjectures 'R Us  31  20140914 15:14 
What about general purpose sieving of k*b^n+/1?  jasong  GPU Computing  1  20120403 10:52 
Implementing Factoring Algorithms  Raman  Hobbies  45  20090511 05:11 
design factoring algorithms  koders333  Factoring  14  20060125 14:08 
factoring algorithms are patented?  koders333  Factoring  1  20060119 20:04 