PrimeGrid Wiki

A fixed-N sieve is a type of sieve application for Proth or Riesel numbers, of the form K*bN+/-1. It is best suited to testing ranges with many K's and few N's. Sieving more K's does not impact the speed of a fixed-N sieve, assuming sufficient memory is available.

Given we are testing numbers of the format:

K*bN-1 = 0 (mod P)

If N is fixed, we want to find a K where P divides the entire number. To do this, we rearrange the equation:

K*bN = 1 (mod P)

K = b-N (mod P)

So now for every prime P we sieve against, we just have to calculate b-N (mod P) to find a K. We then see if that number is within the range of K's we're testing, and whether it has been sieved before. If not, the sieve has found a new factor of K*bN-1.

The same procedure applies for numbers of the form K*bN+1 = 0 (mod P), except that K must be negated at the end. (-K (mod P) = P-K (mod P))