View Single Post
Old 2006-12-01, 20:48   #10
maxal's Avatar
Feb 2005

11·23 Posts

There is a faster way to sieve out numbers of the form q*2^q+1 that are divisible by a given prime p>=3.

Suppose that q*2^q+1 is divisible by p. Then q*2^q = -1 (mod p) or alternatively q = - 2^(-q) (mod p).

Let q = -k (mod p-1) where 0 <= k < p-1, then q = - 2^(-q) = - 2^k (mod p).
From q = -k (mod p-1) and q = - 2^k (mod p) we can reconstruct q modulo p*(p-1) using Chinese theorem:
q = -k * p + 2^k * (p-1) (mod p*(p-1)) .............. (x)

In other words, for every k=0,...,p-2, there is an unique solution modulo p*(p-1) to the system of congruences
q*2^q + 1 = 0 (mod p)
q = -k (mod p-1)
and this solution is given by formula (x).

Therefore, sieving can be done as follows: for each prime p in selected range, let k go from 0 to p-2, compute
r = ((p-1-k) * p + (2^k mod p) * (p-1)) mod (p*(p-1)) (i.e., the smallest non-negative solution to (x)), and eliminate candidates
r, r + (p*(p-1)), r + 2*(p*(p-1)), ..., up to selected upper bound (for large p, it may appear that r is greater than the upper bound, in which case no actual elimination happens).

P.S. Of course, the powers (2^k mod p) can be computed incrementally as k goes from 0 to p-2:
having 2^k mod p=y computed, the value of 2^(k+1) mod p is computed as (y*2) mod p.

P.P.S. There is another speed up possible if we replace p-1 with the multiplicative order of 2 modulo p (that is a divisor of p-1). So, instead of letting k go from 0 to p-2, we compute incrementally and store values u[i]=2^i mod p, i=1,2,... until we get u[z]=1, meaning that z is the multiplicative order of 2 modulo p. Then we let k go from 0 to z-1, compute
r = ((z-k) * p + u[k] * z) mod (p*z), and eliminate candidates r, r + (p*z), r + 2*(p*z), ..., up to selected upper bound.

Last fiddled with by maxal on 2006-12-01 at 21:11
maxal is offline