mersenneforum.org Overview of Factoring Algorithms
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-09-02, 20:32 #1 ThiloHarich     Nov 2005 22×33 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 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 20:40.

Mon Jan 30 20:40:00 UTC 2023 up 165 days, 18:08, 0 users, load averages: 1.07, 1.19, 1.05

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔