Loading ...
Sorry, an error occurred while loading the content.

An interesting observation

Expand Messages
  • Décio Luiz Gazzoni Filho
    ... 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
      performed ``for free'' (asymptotically speaking). An interesting result, in
      my opinion, and I thought that I'd share with you.

      Décio
      -----BEGIN PGP SIGNATURE-----
      Version: GnuPG v1.2.1 (GNU/Linux)

      iD8DBQE+hy92ce3VljctsGsRAmg2AKDCa2ELJlAS0eAHcqMG4zxnuxl7SQCfSLD0
      aVjOOZnQVF3iXvsAUSx1s8w=
      =KvuO
      -----END PGP SIGNATURE-----
    Your message has been successfully submitted and would be delivered to recipients shortly.