An interesting observation

Expand Messages
• ... Hash: SHA1 Hello, I was trying to work out the complexity of the ``sieving for smooth numbers technique, employed for instance in the Quadratic Sieve
Message 1 of 1 , Mar 30, 2003
• 0 Attachment
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hello,

I was trying to work out the complexity of the ``sieving for smooth numbers''
technique, employed for instance in the Quadratic Sieve algorithm. A
reference is C&P section 3.2.5. The number of positions marked by this sieve,
when applied over an array of n elements, is n/p_1 + n/p_2 + n/p_3 + ...,
with p_i ranging over all prime _powers_ up to a bound B.

A well-known result (C&P Theorem 1.4.2, Hardy and Wright Theorem 427 for a
proof) states that the partial sum of reciprocals of primes (up to B) is
asymptotic to log log B. Thus, if the algorithm searched for squarefree
B-smooth numbers only, this result asserts that the complexity of the
algorithm would be O(n log log B). Interestingly enough, the sum of
reciprocals of prime powers p^a with a>1 converges to 0.773156669..., leaving
that bound unchanged if the prime powers are included.

So if one is already sieving for the primes, then sieving for prime powers is