mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2016-02-19, 17:17   #1
mickfrancis
 
Apr 2014
Marlow, UK

23·7 Posts
Default 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 60-100 digit range? (Very) roughly how long might this take to factor an 80-digit number, say, on a standard desktop machine using a single thread? (Let's assume it uses GMP for bigint operations.)

Thanks in advance,

Mick.
mickfrancis is offline   Reply With Quote
Old 2016-02-19, 17:37   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

22·883 Posts
Default

The most powerful such algorithm known is ECM, in fact all the others are exponential-time.

The time needed to factor an 80-digit number using ECM can vary hugely; if it has two 40-digit factors it could take hours, while if it has a 10-digit factor it will be done in less than 1 second.
jasonp is offline   Reply With Quote
Old 2016-02-19, 17:41   #3
mickfrancis
 
Apr 2014
Marlow, UK

5610 Posts
Default

Quote:
Originally Posted by jasonp View Post
The most powerful such algorithm known is ECM, in fact all the others are exponential-time.

The time needed to factor an 80-digit number using ECM can vary hugely; if it has two 40-digit factors it could take hours, while if it has a 10-digit factor it will be done in less than 1 second.
Thanks Jason, but I was thinking of 'general' rather than 'special' algorithms. Obviously SIQS is the go-to algorithm for numbers up to around 110 digits, once ECM runs out of steam, but I was wondering about non-sieving algorithms?
mickfrancis is offline   Reply With Quote
Old 2016-02-19, 17:45   #4
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

24·5·29 Posts
Default

The quadratic sieve is a general-purpose factoring algorithm. Aside from that and ECM, other algorithms aren't too efficient.

Last fiddled with by ixfd64 on 2016-02-19 at 17:48
ixfd64 is offline   Reply With Quote
Old 2016-02-19, 17:51   #5
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

38A16 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2016-02-19, 18:13   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

64228 Posts
Default

Quote:
Originally Posted by danaj View Post
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.
I think he's after an algorithm where the runtime depends on the size of the input, and not on the size of the factor (?)

squfof is a non-sieving N^(1/4) algorithm. If a 20 digit number takes a millisecond, an 80 digit number would be 10^(80-20)^(1/4) times harder or about 1e15 milliseconds.
bsquared is offline   Reply With Quote
Old 2016-02-19, 18:24   #7
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

Quote:
Originally Posted by mickfrancis View Post
Thanks Jason, but I was thinking of 'general' rather than 'special' algorithms. Obviously SIQS is the go-to algorithm for numbers up to around 110 digits, once ECM runs out of steam, but I was wondering about non-sieving algorithms?
ECM, SIQS and GNFS are all 'general' purpose algorithms. They are essentially the golden trifecta for anything north of 20 digits, below which things like P-1, squfof, rho, etc are useful in finding small factors extremely quickly.

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 non-sieving, so that leaves ECM.
Dubslow is offline   Reply With Quote
Old 2016-02-19, 18:26   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by danaj View Post
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.
my guess on reading wikipedia is because: https://en.wikipedia.org/wiki/Intege...ing_algorithms has it under special purpose ?


quoting the whole thing gives eliminations that can be done:

Quote:
Originally Posted by https://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms
Special-purpose[edit]
A special-purpose factoring algorithm's running time depends on the properties of the number to be factored or on one of its unknown factors: size, special form, etc. Exactly what the running time depends on varies between algorithms.

An important subclass of special-purpose factoring algorithms is the Category 1 or First Category algorithms, whose running time depends on the size of smallest prime factor. Given an integer of unknown form, these methods are usually applied before general-purpose methods to remove small factors.[4] For example, trial division is a Category 1 algorithm.

Trial division
Wheel factorization
Pollard's rho algorithm
Algebraic-group factorisation algorithms, among which are Pollard's p βˆ’ 1 algorithm, Williams' p + 1 algorithm, and Lenstra elliptic curve factorization
Fermat's factorization method
Euler's factorization method
Special number field sieve
General-purpose[edit]
A general-purpose factoring algorithm, also known as a Category 2, Second Category, or Kraitchik family algorithm (after Maurice Kraitchik),[4] has a running time which depends solely on the size of the integer to be factored. This is the type of algorithm used to factor RSA numbers. Most general-purpose factoring algorithms are based on the congruence of squares method.

Dixon's algorithm
Continued fraction factorization (CFRAC)
Quadratic sieve
Rational sieve
General number field sieve
Shanks' square forms factorization (SQUFOF)
so of the general algorithms the only one's that don't have sieve in the name are dixon's ( related to fermat's factorization method),CFRAC, or SQUFOF ( which if my memory is correct was a method commonly used in calculators at least at one point if not currently),

Last fiddled with by science_man_88 on 2016-02-19 at 18:29
science_man_88 is offline   Reply With Quote
Old 2016-02-19, 19:03   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×5×1,039 Posts
Default

Quote:
Originally Posted by bsquared View Post
I think he's after an algorithm where the runtime depends on the size of the input, and not on the size of the factor (?)
ECM is a heuristic sub-exponential general purpose factoring algorithm

A factor p of N is expected to be found in time sub-exponential 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 non-deterministic.

Last fiddled with by xilman on 2016-02-19 at 19:05
xilman is online now   Reply With Quote
Old 2016-02-19, 19:46   #10
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

38A16 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
my guess on reading wikipedia is because: https://en.wikipedia.org/wiki/Intege...ing_algorithms has it under special purpose ?
Thanks, I bet this is it. I understand the distinction in terms of size-of-input vs. size-of-factor, but I think "special-purpose" is an odd name that isn't used in the literature. It looks like the names were added in 2004 when the first list of algorithms was added to the page.

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).
danaj is offline   Reply With Quote
Old 2016-02-19, 21:07   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by danaj View Post
80+ digits (correct me if this is wrong).
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.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
S9 and general sieving discussion Lennart Conjectures 'R Us 31 2014-09-14 15:14
What about general purpose sieving of k*b^n+/-1? jasong GPU Computing 1 2012-04-03 10:52
Implementing Factoring Algorithms Raman Hobbies 45 2009-05-11 05:11
design factoring algorithms koders333 Factoring 14 2006-01-25 14:08
factoring algorithms are patented? koders333 Factoring 1 2006-01-19 20:04

All times are UTC. The time now is 15:43.

Tue Dec 1 15:43:25 UTC 2020 up 82 days, 12:54, 3 users, load averages: 1.51, 1.73, 1.79

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.