Inverse sieve

Abstract. The paper suggests a method to speed up distributed primality testing by compressing the sieve table and so reducing data traffic. Since smaller primes sieve out most of the candidates, most of the sieving done by larger primes is redundant. Instead of doing such unnecessary sieving on a complete and uncompressed table (or an array of indices), one can eliminate most of the redundant offsets based on a compressed sieve table. The compression is done by “smearing” the exact locations of the potential primes, that is compressing the sieve to one \(N\)-th of its original size by encoding each \(N\) long interval of the table with a 0 bit if it contains no potential primes, and with a 1 bit otherwise. If \(N\) is chosen to be a power of two, calculating the offset in the compressed table requires virtually no extra effort.