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.
Description
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 of all the numbers. This means that fully of all the candidate numbers are skipped over automatically. Larger bases reduce this proportion even further; for example, with basis { 2, 3, 5} to ; and with basis { 2, 3, 5, 7} to .
The bigger the wheel the larger the computational resources involved and the smaller the additional improvements, though, so it is the case of quickly diminishing returns.
Introduction
Natural numbers from 1 and up are enumerated by repeated addition of 1:
Considered by spans of two numbers each, they are enumerated by repeated additions of 2:
Every second thus generated number will be even. Thus odds are generated by the repeated additions of 2:
Considered by spans of three numbers each, they are enumerated by repeated additions of 2 * 3 = 6:
Every second number in these triplets will be a multiple of 3, because numbers of the form 3 + 6k are all odd multiples of 3. Thus all the numbers coprime with the first two primes i.e. 2 and 3, i.e. 2 * 3 = 6–coprime numbers, will be generated by repeated additions of 6, starting from { 1, 5}:
The same sequence can be generated by repeated additions of 2 * 3 * 5 = 30, turning each five consecutive spans, of two numbers each, into one joined span of ten numbers:
Out of each ten of these 6–coprime numbers, two are multiples of 5, thus the remaining eight will be 30–coprime:
This is naturally generalized.
The above showcases first three wheels:
{ 1} (containing one i.e. (2-1) number) with the "circumference" of 2 for generating the sequence of 2–coprimes i.e. odds by repeated addition of 2; { 1,5} (containing two i.e. (2-1)*(3-1) numbers) with the "circumference" of 2 * 3 = 6, for generating the sequence of 6–coprime numbers by repeated additions of 6; { 1, 7, 11, 13, 17, 19, 23, 29} (containing eight i.e. (2-1)*(3-1)*(5-1) numbers) with the "circumference" of 2*3*5 = 30, for generating the sequence of 30–coprime numbers by repeated additions of 30; etc.
Another representation of these wheels is by turning a wheel's numbers, as seen above, into a circular list of the differences between the consecutive numbers, and then generating the sequence starting from 1 by repeatedly adding these increments one after another to the last generated number, indefinitely. This is the closest it comes to the "rolling the wheel" metaphor.
For instance, this turns { 1, 7, 11, 13, 17, 19, 23, 29, 31} into { 6, 4, 2, 4, 2, 4, 6, 2}, and then the sequence is generated as n=1; n+6=7; n+4=11; n+2=13; n+4=17; n+2=19; n+4=23; n+6=29; n+2=31; n+6=37; n+4=41; n+2=43; etc.
A typical example
With a given basis of the first few prime numbers { 2, 3, 5}, the "first turn" of the wheel consists of: .
The second turn is obtained by adding 30, the product of the basis, to the numbers in the first turn. The third turn is obtained by adding 30 to the second turn, and so on.