mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-12-25, 19:27   #12
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

22×33 Posts
Default

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.
ThiloHarich is offline   Reply With Quote
Old 2009-01-02, 08:53   #13
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

22·33 Posts
Default

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.
ThiloHarich is offline   Reply With Quote
Old 2009-01-04, 18:19   #14
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

22×33 Posts
Default

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.
ThiloHarich is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve mickfrancis Factoring 2 2016-05-06 08:13
Non-sieving version of Quadratic Sieve mickfrancis Factoring 5 2016-03-31 06:21
Finding B in Quadratic Sieve paul0 Factoring 3 2011-09-22 17:12
Using p=2 for sieving (Quadratic sieve algorithm) R1zZ1 Factoring 36 2007-11-02 15:59
Quadratic Sieve in wikipedia.de 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

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.

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