> Well, my question is very simple. How can we see that 2*k*p+1 is composite?
> Or is it composite for any special k like k=4*n ?
There is another constraint - 2kp+1 must be congruent to 1 or 7
modulo 8.
If p is congruent to 1 modulo 8, then for k = 0 (mod 4), 2kp+1 = 1
(mod 8); k = 1 (mod 4) gives 2kp+1 = 3 (mod 8); k = 2 (mod 4) gives
2kp+1 = 5 (mod 8) and k = 3 (mod 4) gives 2kp+1 = 7 (mod 8).
So only values of k congruent to 0 or 3 (mod 4) need to be
considered.
Working similarly, if p = 3 mod 8 then only look at k = 0 (mod 4) or
1 (mod 4); p = 5 mod 8 gives k = 0 or 3 (mod 4) & p = 7 (mod 8) gives
k = 0 or 3 (mod 8).
That cuts out half the cases straight away. Incidentally, since this
gives a nice "try two, then skip two" pattern, independent of the
value of p mod 8, we never actually need to calculate 2kp+1 mod 8,
this is another timesaver.
Now we can filter out multiples of small primes & reduce the number
of contenders needing to be trial factored some more. A good way of
doing this (eliminates multiples of all the small primes 3, 5, 7, 11,
13, 17) is to contruct a sieve table with 255,255 elements then index
into it with 2kp+1 mod 255255. This "modulo" operation can be done by
adding 2p mod 255255, or 6p mod 255255, depending on whether we're on
a "try next" or "try next but 3" cycle, and subtracting 255255 if
possible.
When we've eliminated enough candidates, just try the division. It
actually doesn't matter if the trial divisor is composite, it's a
question of whether it costs more to try the division anyway or to go
on to eliminate the candidate factor by proving it prime.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
