 mersenneforum.org Overview of Factoring Algorithms
 Register FAQ Search Today's Posts Mark Forums Read 2007-09-02, 20:32 #1 ThiloHarich   Nov 2005 1548 Posts Overview of Factoring Algorithms Is there a List of Factoring Algorithms and running timings, which answers the Question in which case should we use which Algorithm? Interesting parameter of the Algorithms might be: - Memory used - Length of the numbers occurring while calculation the Factorization - it is the fastest Algorithm under the following conditions I start a short List here let p be the biggest prime of a factorization. Trial Division time: L_n(1,1/2), p memory: O (ln(n)) bits:ln (n) very small n or p very small (how small?) Fermat time: L_n(1,1/2), (sqrt (n)-p)^2/sqrt(n) memory: O (ln(n)) bits: ln (n) p near sqrt(n) Pollard Rho time:L_n(1,1/4), sqrt (p) memory: O (ln(n)) bits: ln (n) small n, small p SQUFOF time:L_n(1,1/4), sqrt (p) memory: O (ln(n)) bits: 1/2 ln (n) ? SIQS time:L_n(1/2,1) memory: L_n(1/2,1) bits: log (n) (only for sieving) for general number up to 110 digits. gcd time: L_n(1,1/2), p*ln (p)^2, amortized ln (p)^2 memory: p bits: p if the sum of lengths of the numbers we want to factorize is longer then the length of the product of possible factors. The gcd method is the method described by bernstein in http://cr.yp.to.mirror.dogmap.org/fa...s-20040510.pdf with amortized I denote the time needed for each bit of an set of integers (which has more then p bits). A special question is which is the best method for factorizing Integers that remain after a sieving phase? If we have p Integers with less then ln (n) bits which have passed the sieving phase, we have the following theoretical timings: Trial Division and Resieving: p^2, Pollard Rho and SQUFOF: p^1.5 gcd: p * ln (p)^2 In practice Resieving is fast, since we have rather simple Operations. The gcd method is slower then Pollard Rho for p < 30,000. Since FFT beats Karatsuba (running time p^1.585) for inputs greater then 30,000 digits. So the gdc method should be faster then PollarRho for n around 10^40. I read that SQUFOF is faster then Pollard Rho. How much? Last fiddled with by ThiloHarich on 2007-09-02 at 21:32  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Romuald Factoring 75 2016-08-27 09:46 mickfrancis Factoring 21 2016-02-22 19:38 Raman Hobbies 45 2009-05-11 05:11 koders333 Factoring 14 2006-01-25 14:08 koders333 Factoring 1 2006-01-19 20:04

All times are UTC. The time now is 18:32.

Fri Mar 31 18:32:33 UTC 2023 up 225 days, 16:01, 0 users, load averages: 0.71, 0.63, 0.76