Wheel factorization

Wheel factorization is a method for generating a sequence of natural numbers by repeated additions, as determined by a number of the first few primes, so that the generated numbers are coprime with these primes, by construction. For a chosen number n (usually no larger than 4 or 5), the first n primes determine the specific way to generate a sequence of natural numbers which are all known in advance to be coprime with these primes, i.e. are all known to not be multiples of any of these primes. This method can thus be used for an improvement of the trial division method for integer factorization, as none of the generated numbers need be tested in trial divisions by those small primes. The trial division method consists of dividing the number to be factorized by the integers in increasing order (2, 3, 4, 5, ...) successively. A common improvement consists of testing only by primes, i.e. by 2, 3, 5, 7, 11, ... . With the wheel factorization, one starts from a small list of numbers, called the basis — generally the first few prime numbers; then one generates the list, called the wheel, of the integers that are coprime with all the numbers in the basis. Then, for the numbers generated by "rolling the wheel", one needs to only consider the primes not in the basis as their possible factors. It is as if these generated numbers have already been tested, and found to not be divisible by any of the primes in the basis. It is an optimization because all these operations become redundant, and are spared from being performed at all. When used in finding primes, or sieving in general, this method reduces the amount of candidate numbers to be considered as possible primes. With the basis {2, 3}, the reduction is to 1/3 < 34% of all the numbers. This means that fully 2/3 of all the candidate numbers are skipped over automatically. Larger bases reduce this proportion even further; for example, with basis {2, 3, 5} to 8/30 < 27%; and with basis {2, 3, 5, 7} to 48/210 < 23%.