Sorry, an error occurred while loading the content.

Query about sieve algorithm

Expand Messages
• 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
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.