mersenneforum.org Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2016-05-04, 14:39 #1 mickfrancis   Apr 2014 Marlow, UK 3816 Posts Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve As I understand it, in the Small Prime Variation of the Quadratic Sieve, primes less than a threshold (Pmin, say) are not used for sieving, as the cost of sieving is disproportionately high given the contribution of these primes. Sieving with powers of primes that are themselves used in sieving is also less beneficial than sieving with other primes of size comparable to these powers (e.g. the contribution for p^2 is the same as for p). However, it seems to me that for primes in the factor base less than Pmin it ought still to make sense to sieve with the lowest powers that are Pmin or above, as the contribution is just as high as that of similarly-sized primes (why would I sieve with the prime 257 but not 256 (28), for example)? In the implementations I've looked at, this does not appear to be done, and I was wondering why; is the benefit outweighed by the added complexity?
 2016-05-06, 02:19 #2 jasonp Tribal Bullet     Oct 2004 2·1,789 Posts Once the problem size gets above a fairly small threshold, the runtime needed for sieving small primes becomes insignificant compared to sieving everything else; there are only a few such, and they cache nicely, so they're done in a flash compared to the thousands of larger primes you must also sieve with.
2016-05-06, 08:13   #3
mickfrancis

Apr 2014
Marlow, UK

708 Posts

Quote:
 Originally Posted by jasonp Once the problem size gets above a fairly small threshold, the runtime needed for sieving small primes becomes insignificant compared to sieving everything else; there are only a few such, and they cache nicely, so they're done in a flash compared to the thousands of larger primes you must also sieve with.
Makes sense - thanks Jason.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Prime Gap Searches 47 2022-11-15 18:53 mickfrancis Factoring 5 2016-03-31 06:21 ThiloHarich Factoring 13 2009-01-04 18:19 Housemouse Math 2 2008-06-04 05:23 R1zZ1 Factoring 36 2007-11-02 15:59

All times are UTC. The time now is 00:00.

Tue Sep 26 00:00:04 UTC 2023 up 12 days, 21:42, 0 users, load averages: 1.22, 1.28, 1.20

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.

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