mersenneforum.org Sieving polynoms in Quadratic Sieve
 Register FAQ Search Today's Posts Mark Forums Read

 2008-12-25, 19:27 #12 ThiloHarich     Nov 2005 22×33 Posts Of coarse we have to calculate \floor{q_i^2} mod N to determine the factors over the factor base. The squaring is very time consuming. Maybe we can improve here if we do some restrictions.
 2009-01-02, 08:53 #13 ThiloHarich     Nov 2005 22·33 Posts If we have a sieving interval M the resulting size of the values of q(x) is in O(M*sqrt (N)). For QS M is O(exp (sqrt (log (N) * log log (N))) and the values were bounded by O(N). So I expect the running time to be decreased only by an constant factor in the exponent (something like sqrt (2)), which is far away from the NFS. But for the CFRAC the same should hold as well?? I'm going to implement it. I already have a MPQS in place so lets see how it will be compared with it.
 2009-01-04, 18:19 #14 ThiloHarich     Nov 2005 22×33 Posts The answer to my first question is rather simple if q(x) is getting greater then N we have to reduce it by applying mod N on the result. But then we can not be sure that 'a' still divides q(x), so we have to limit M. and choose different a's.

 Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Factoring 2 2016-05-06 08:13 mickfrancis Factoring 5 2016-03-31 06:21 paul0 Factoring 3 2011-09-22 17:12 R1zZ1 Factoring 36 2007-11-02 15:59 ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 04:02.

Wed Feb 8 04:02:20 UTC 2023 up 174 days, 1:30, 1 user, load averages: 0.59, 0.67, 0.74

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.

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