Re: Quadratic residue method for finding primes

jstevh@msn.com wrote:
> Sorry to start a new thread already but I already don't like the
> direction of the original thread.
>
> 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? 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".
Do you mean that for at least one such prime, say q1, 2 is a quadratic
residue mod q1?

Usually when one talks about quadratic residues, it's in relation to
some modulus, like, 2 is a quadratic residue modulo q (you've neglected
to specify the modulus).

In fact, to be sure we're talking about the same thing, here's a definition:

Let m and n be coprime integers with n > 0. Then m is said to be a
quadratic residue modulo n if and only if x^2 == m mod n is solvable for
some integer x. If x^2 == m mod n isn't solvable, then m is said to be a
quadratic nonresidue modulo n.

Is this what you mean by quadratic residue?

If so, then when n is prime the Legendre symbol is used to convey this
idea compactly:

For an odd prime p the Legendre symbol, notated (m/p) is defined as

(m/p) = 1 if m is a quadratic residue modulo p
(m/p) = -1 if m is a quadratic nonresidue modulo p
(m/p) = 0 if p | m.

>
> That means that for quite a distance p^2 - 2 is more likely to give you
> primes than not, and even when it starts to more likely give
> composites, they will most likely have 7 as a factor, and so on as you
> go up the distribution, so it's like a shifted prime distribution,
> where just a lot of primes are excluded, as they don't have 2 as a
> quadratic residue.
>
> Moving on to others you can use
>
> p^2 - 17
>
> where the behavior is different as first off, everything is even, but
> get this, the only other prime that does not have 17 as a quadratic
> residue that can be a factor is 13, so you end up for a while with a
> lot of composites with 2 and 13 as factors, until you get the rarer
> primes that have 17 as a quadratic residue.
>
> The shielding is so powerful that consider p=23, where you have
>
> 23^2 - 2 = 512 = 2^9
>
> as all that could fit.
>
> So used naively you could just iterate through primes by some quadratic
> residue, like p^2 - 2, or p^2 - 17, where you automatically divide off
> factors of 2, and also at times 13, with what will for some distance
> most likely be a prime until again, when you get to big enough numbers,
> the odds drop below 50%.
>
> But what are the limits? Don't know. How do the prime distributions
> around a particular rare residue behave? Don't know. Do they at all
> look like the main prime distribution that is so familiar? Don't know,
> except the distribution must be elongated, and flattened to some
> extreme degree.
>
> What is for sure is that it is a way to shift the odds for getting
> prime numbers.
>
> I've been looking for research in this area on the web and haven't seen
> squat.
>
> It may be a wide open research area, where grouping primes by certain
> quadratic residues, like with my start of 2, just didn't seem like
> something that was interesting, so no one bothered to do anything in
> this area, until now.
>
>
> James Harris
>
Received on Mon May 1 02:03:06 2006