Wheel factorization

Wheel factorization is an improvement of the trial division method for integer factorization. Wheel factorization is an improvement of the trial division method for integer factorization. The trial division method consists of dividing the number to be factorized successively by the first integers (2, 3, 4, 5, …) until finding a divisor. For 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 numbers of the basis. Then to find the smallest divisor of the number to be factorized, one divides it successively by the numbers in the basis, and in the wheel. With the basis {2, 3}, this method reduces the number of divisions to 1/3 < 34% of the number necessary for trial division. 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%.