If a prime q divides N=2^p+3 then :

2^p = -3 (mod q)

so (2^p/q) = (-3/q) where (a/b) is the Legendre symbol

it implies that (2/q) = (3/q).(-1/q) because p is odd, so q = 1, 5, 7, 11 (mod 24) (half of the primes)

In the same way, if N=2^p-3, one can prove that q = +/- 1, +/- 5 (mod 24) (half of the primes)

This speeds up a little bit the sieve...

Good hunt,

Renaud Lifchitz

[Non-text portions of this message have been removed]