2007-09-02, 20:32 | #1 |
Nov 2005
101 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 | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Factoring projects algorithms - What is Aliqueit ? | Romuald | Factoring | 75 | 2016-08-27 09:46 |
General factoring algorithms not using sieving | mickfrancis | Factoring | 21 | 2016-02-22 19:38 |
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 |