Re: Quadratic residue method for finding primes



Arturo Magidin wrote:
In article <124gm0rbklunf96@xxxxxxxxxxxxxxxxxx>,
Bob Terwilliger <RobertUnderdunkTerwilliger@xxxxxxxxxxxxxxxxxxxxxx> wrote:

[.snip.]


What I have found is a simple to the point of trivial method for using
quadratic residues to greatly increase the odds of finding prime
numbers, with the primary idea being a method to quickly find very
large primes.

p^2 - 2

is what I started with where for a number to be a factor of that it
must be a prime with a quadratic residue of 2 or decomposable into
primes with 2 as a quadratic residue, where the first is 7.

Quadratic residue modulo what?


Instead of "with a quadratic residue of 2", you should read "which has
2 as a quadratic residue".

In other words: if q is a prime that divides p^2-2, where p is an odd
prime, then 2 is a quadratic residue modulo q. This, of course, is
simply noting that p^2 - 2 = 0 (mod q), so p^2=2 (mod q), so 2 is a
quadratic residue modulo q.

Yikes... that's easy! Thanks for the clarification Arturo... this is so obvious!




I think you're saying that if q is a prime factor of p^2 - 2, then x^2 == 2 mod q is solvable for some integer x, is this correct? I'm not sure what you mean by the second part: "... or decomposable into primes with 2 as a quadratic
residue".


p^2 - 2 will either be (i) a prime which has 2 as a quadratic residue;
or (ii) composite, and all its prime factors will have 2 as a
quadratic residue (i.e., if q is any prime factor of p^2-2, then 2 is
a quadratic residue modulo q).

Agreed, just like you said above (nice).



Do you mean that for at least one such prime, say q1, 2 is a quadratic residue mod q1?


All primes dividing p^2-2 will have 2 as a quadratic residue. In fact,
if m is odd, then all integers n dividing m^2-2 will have 2 as a
quadratic residue (i.e., if n divides m^2-2, then 2 is a quadratic
residue modulo n; we need m odd so that (2,n)=1).

Yes, as you say, m will be a solution... i.e., n | m^2 - 2 -> m^2 == 2 mod n.


Note that we know exactly which primes have 2 as a quadratic residue:
namely, those which are congruent to 1 or -1 modulo 8. Likewise, if we
replace 2 with any prime r, then we can figure out exactly which
primes have r as a quadratic residue by the use of Quadratic
Reciprocity; and they will all lie in certain arithmetic progressions
modulo r or modulo 4r (depending on whether r is congruent to 1 modulo
4 or to 3 modulo 4).


Yes, isn't this a result of Dirichlet? I'm starting to sense analytic number theory on the horizon!
.

Relevant Pages

  • Re: Quadratic residue method for finding primes
    ... quadratic residues to greatly increase the odds of finding prime ... primes with 2 as a quadratic residue, ... if q is a prime that divides p^2-2, where p is an odd ... then 2 is a quadratic residue modulo q. ...
    (sci.crypt)
  • Re: Quadratic residue method for finding primes
    ... primes with 2 as a quadratic residue, ... if q is a prime that divides p^2-2, where p is an odd ... then 2 is a quadratic residue modulo q. ... those which are congruent to 1 or -1 modulo 8. ...
    (sci.crypt)
  • Re: Quadratic residue method for finding primes
    ... What I have found is a simple to the point of trivial method for using ... primes with 2 as a quadratic residue, ... Usually when one talks about quadratic residues, it's in relation to some modulus, like, 2 is a quadratic residue modulo q. ... go up the distribution, so it's like a shifted prime distribution, ...
    (sci.crypt)
  • Re: Quadratic Residue -- proof or example
    ... quadratic residue modulo P+3 if and only if -3 is a quadratic residue ... Arturo Magidin ... Prev by Date: ...
    (sci.math)