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

Query about sieve algorithm

Expand Messages
  • Kermit Rose
    Who has worked on developing a sieve algorithm to find primes for which all the integers in a pre-specified set are modulus square residues? To find for what
    Message 1 of 1 , Dec 26, 2007
    • 0 Attachment
      Who has worked on developing a sieve algorithm to find primes
      for which all the integers in a pre-specified set are modulus square
      residues?

      To find for what primes 6 is a modulus square residue

      I do the following.

      I determine the square non square status for 2

      For what primes is 2 a modulus square residue?
      (p represents a positive integer, and it's assumed that only primes
      encountered in the list are used.)

      For example, 8p + 1 includes 17 and 41, but not 9, 25, or 33.

      8 p + 1 yes
      8 p + 3 no
      8p + 5 no
      8p + 7 yes


      For what primes is 3 a modulus square residue?

      12 p + 1 yes
      12 p + 5 no
      12 p + 7 no
      12 p + 11 yes


      For what primes is 6 a modulus square residue

      24 p + 1 8 p + 1 12 p + 1 yes Both 2
      and 3 are square residues.
      24 p + 5 8 p + 5 12 p + 5 yes
      Neither 2 nor 3 are square residues.
      24 p + 7 8 p + 7 12 p + 7 no 2 is a
      square residue, 3 is not.
      24 p + 11 8 p + 3 12 p + 11 no 3 is a
      square residue, 2 is not.
      24 p + 13 8 p + 5 12 p + 1 no 3 is a
      square residue, 2 is not.
      24 p + 17 8 p + 1 12 p + 5 no 2 is a
      square residue, 3 is not.
      24 p + 19 8 p + 3 12 p + 7 yes Neither
      2 nor 3 are square residues
      24 p + 23 8 p + 7 12 p + 11 yes Both 2
      and 3 are square residues




      Kermit Rose < kermit@... >
    Your message has been successfully submitted and would be delivered to recipients shortly.