Thread: Cullen prime problem View Single Post
 2006-12-01, 20:48 #10 maxal     Feb 2005 FC16 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