mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-09-02, 20:32   #1
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default 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
ThiloHarich is offline   Reply With Quote
Reply

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

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

Thu Apr 22 12:08:28 UTC 2021 up 14 days, 6:49, 0 users, load averages: 2.34, 2.11, 1.99

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