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; that is, they 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 (usually the first few primes); 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%. The bigger the wheel, the larger the computational resources involved and the smaller the additional improvements, leading to quickly diminishing returns.
Introduction Natural numbers from 1 and up are enumerated by repeated addition of 1:
1, 2, 3, 4, 5, ... Considered by spans of two numbers each, they are enumerated by repeated additions of 2:
1, 2 ; 3, 4 ; 5, 6 ; ... Every second number thus generated will be even. Thus odds are generated by the repeated additions of 2:
1 ; 3 ; 5 ; 7 ; ... Considered by spans of three numbers each, they are enumerated by repeated additions of 2 × 3 = 6:
1, 3, 5 ; 7, 9, 11 ; ... 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 (2 and 3) will be generated by repeated additions of 6, starting from {1, 5}:
1, 5 ; 7, 11 ; 13, 17 ; ... 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:
1, 5, 7, 11, 13, 17, 19, 23, 25, 29 ; 31, 35, 37, ... Out of each ten of these 6-coprime numbers, two are multiples of 5, thus the remaining eight will be 30-coprime:
1, 7, 11, 13, 17, 19, 23, 29 ; 31, 37, 41, 43, 47, 49, ... This is naturally generalized. The above showcases first three wheels:
{1} (containing 1 = 2 − 1 number) with the "circumference" of 2 for generating the sequence of 2-coprimes by repeated addition of 2; {1, 5} (containing 2 = (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 8 = (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 3 prime numbers {2, 3, 5}, the "first turn" of the wheel consists of:
7, 11, 13, 17, 19, 23, 29, 31. 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. For implementing the method, one may remark that the increments between two consecutive elements of the wheel, that is
inc = [4, 2, 4, 2, 4, 6, 2, 6], remain the same after each turn. The suggested implementation that follows uses an auxiliary function div(n,k), which tests whether n is evenly divisible by k, and returns true in this case and false otherwise. In this implementation, the number to be factorized is n, and the program returns the smallest divisor of n – returning n itself if it is prime.
if div(n, 2) = true then return 2 if div(n, 3) = true then return 3 if div(n, 5) = true then return 5 k := 7; i := 0 while k * k ≤ n do if div(n, k) = true, then return k k := k + inc[i] if i < 7 then i := i + 1 else i := 0 return n
For getting the complete factorization of an integer, the computation may be continued without restarting the wheel at the beginning. This leads to the following program for a complete factorization, where the function add adds its first argument at the end of the second argument, which must be a list.
factors := [ ] while div(n, 2) = true do factors := add(2, factors) n := n / 2 while div(n, 3) = true do factors := add(3, factors) n := n / 3 while div(n, 5) = true do factors := add(5, factors) n := n / 5 k := 7; i := 0 while k * k ≤ n do if div(n, k) = true then add(k, factors) n := n / k else k := k + inc[i] if i < 7 then i := i + 1 else i := 0 if n > 1 then add(n, factors) return factors
… excerpt ends here. Continue reading the full article.
