 | This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: The computer implementation algorithm, pseudocode, further performance analysis, and computation complexity are not complete.(February 2015) |
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; 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.
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 number thus generated 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 (2 and 3) 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:
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
With a given basis of the first 3 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.
For implementing the method, one may remark that the increments between two consecutive elements of the wheel, that is
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 thenreturn 2 if div(n, 3) = true thenreturn 3 if div(n, 5) = true thenreturn 5 k := 7; i := 0 whilek * k ≤ ndoif div(n, k) = true, then return kk := k + inc[i] ifi < 7 theni := i + 1 elsei := 0 returnn
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 whilek * k ≤ ndoif div(n, k) = true then add(k, factors) n := n / kelsek := k + inc[i] ifi < 7 theni := i + 1 elsei := 0 ifn > 1 then add(n, factors) return factors
Wheel factorization is used for generating lists of mostly prime numbers from a simple mathematical formula and a much smaller list of the first prime numbers. These lists may then be used in trial division or sieves. Because not all the numbers in these lists are prime, doing so introduces inefficient redundant operations. However, the generators themselves require very little memory compared to keeping a pure list of prime numbers. The small list of initial prime numbers constitute complete parameters for the algorithm to generate the remainder of the list. These generators are referred to as wheels. While each wheel may generate an infinite list of numbers, past a certain point, the numbers cease to be mostly prime.
The method may further be applied recursively as a prime number wheel sieve to generate more accurate wheels. Much definitive work on wheel factorization, sieves using wheel factorization, and wheel sieve, was done by Paul Pritchard [1] [2] [3] [4] in formulating a series of different algorithms. To visualize the use of a factorization wheel, one may start by writing the natural numbers around circles as shown in the adjacent diagram. The number of spokes is chosen such that prime numbers will have a tendency to accumulate in a minority of the spokes.
1 2 3 4 5 6
1 2 3 <s>4</s> 5 <s>6</s>
<nowiki/> 1 2 3 <s>4</s> 5 <s>6</s> 7 8 9 10 11 12
<nowiki/> 1 2 3 <s>4</s> 5 <s>6</s> 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
<nowiki/> <s>1</s> 2 3 <s>4</s> 5 <s>6</s> 7 <s>8</s> <s>9</s> 10 11 12 13 <s>14</s> <s>15</s> 16 17 18 19 <s>20</s> <s>21</s> 22 23 24 25 <s>26</s> <s>27</s> 28 29 30
<nowiki/> <s>1</s> 2 3 <s>4</s> 5 <s>6</s> 7 <s>8</s> <s>9</s> <s>10</s> 11 <s>12</s> 13 <s>14</s> <s>15</s> <s>16</s> 17 <s>18</s> 19 <s>20</s> <s>21</s> <s>22</s> 23 <s>24</s> 25 <s>26</s> <s>27</s> <s>28</s> 29 <s>30</s>
2 3 5 7 11 13 17 19 23 29
Note that by using exactly the next prime number of 5 wheel cycles and eliminating the multiple(s) of that prime (and only that prime) from the resulting list, we have obtained the base wheel as per step 4 for a factorization wheel with base primes of 2, 3, and 5; this is one wheel in advance of the previous {2,3} factorization wheel. One could then follow the steps to step 10 using the next succeeding prime of 7 cycles and only eliminating the multiples of 7 from the resulting list in step 10 (leaving some "relative" primes in this case and all successive cases – i.e. some not true fully qualified primes), to get the next further advanced wheel, recursively repeating the steps as necessary to get successively larger wheels.
Formally, the method makes use of the following insights: first, that the set of base primes unioned with its (infinite) set of coprimes is a superset of the primes; second, that the infinite set of coprimes can be enumerated easily from the coprimes to the base set between 2 and the base set product. (Note that 1 requires special handling.)
As seen in the example above, the result of repeated applications of the above recursive procedure from steps 4 through 10 can be a wheel list which spans any desired sieving range (to which it can be truncated) and the resulting list then includes only the multiples of primes higher than one past the last-used base primes.
Once a wheel spans the desired upper limit of the sieving range, one can stop generating further wheels and use the information in that wheel to cull the remaining composite numbers from that last wheel list using a Sieve-of-Eratosthenes-type technique but using the gap pattern inherent to the wheel to avoid redundant culls; some optimizations may be able to be made based on the fact that (will be proven in the next section) there will be no repeat culling of any composite number: each remaining composite will be culled exactly once. Alternatively, one can continue to generate truncated wheel lists using primes up to the square root of the desired sieve range, in which case all remaining number representations in the wheel will be prime; however, although this method is as efficient as to never cull composite numbers more than once, it loses much time external to the normally considered culling operations in processing the successive wheel sweeps so as to take much longer. The elimination of composite numbers by a factorization wheel is based on the following: Given a number k > n, we know that k is not prime if k mod n and n are not relatively prime. From that, the fraction of numbers that the wheel sieve eliminates can be determined (although not all need be physically struck off; many can be culled automatically in the operations of copying of lesser wheels to greater wheels) as 1 − φ(n) / n, which is also the efficiency of the sieve.
It is known that
where γ is Euler's constant. [5] Thus φ(n) / n goes to zero slowly as n increases to infinity, and it can be seen that this efficiency rises very slowly to 100% for infinitely large n. From the properties of φ, it can easily be seen that the most efficient sieve smaller than x is the one where n = p1p2…pi < x and npi+1≥x (that is, wheel generation can stop when the last wheel passes or has a sufficient circumference to include the highest number in the sieving range).
To be of maximum use on a computer, we want the numbers that are smaller than n and relatively prime to it as a set. Using a few observations, the set can easily be generated:
In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is called a composite number, or it is not, in which case it is called a prime number. For example, 15 is a composite number because 15 = 3 · 5, but 7 is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example 60 = 3 · 20 = 3 · (5 · 4). Continuing this process until every factor is prime is called prime factorization; the result is always unique up to the order of the factors by the prime factorization theorem.
In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form Mn = 2n − 1 for some integer n. They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century. If n is a composite number then so is 2n − 1. Therefore, an equivalent definition of the Mersenne primes is that they are the prime numbers of the form Mp = 2p − 1 for some prime p.
A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.
In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, 10 = 2 ⋅ 5 is square-free, but 18 = 2 ⋅ 3 ⋅ 3 is not, because 18 is divisible by 9 = 32. The smallest positive square-free numbers are
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Accordingly it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, or the unit 1, so the composite numbers are exactly the numbers that are not prime and not a unit. E.g., the integer 14 is a composite number because it is the product of the two smaller integers 2 × 7 –ut the integers 2 and 3 are not because each can only be divided by one and itself.
In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, 3 × 5 is an integer factorization of 15, and (x – 2)(x + 2) is a polynomial factorization of x2 – 4.
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.
The tables contain the prime factorization of the natural numbers from 1 to 1000.
The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.
In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS) was derived from it.
In number theory, an n-smooth (or n-friable) number is an integer whose prime factors are all less than or equal to n. For example, a 7-smooth number is a number in which every prime factor is at most 7. Therefore, 49 = 72 and 15750 = 2 × 32 × 53 × 7 are both 7-smooth, while 11 and 702 = 2 × 33 × 13 are not 7-smooth. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography, which relies on factorization of integers. 2-smooth numbers are simply the powers of 2, while 5-smooth numbers are also known as regular numbers.
Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The prototypical example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the prototypical example of a sieve is the sieve of Eratosthenes, or the more general Legendre sieve. The direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms. In one of the major strands of number theory in the twentieth century, ways were found of avoiding some of the difficulties of a frontal attack with a naive idea of what sieving should be.
In modular arithmetic, the integers coprime to n from the set of n non-negative integers form a group under multiplication modulo n, called the multiplicative group of integers modulo n. Equivalently, the elements of this group can be thought of as the congruence classes, also known as residues modulo n, that are coprime to n. Hence another name is the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it is described as the group of units of the ring of integers modulo n. Here units refers to elements with a multiplicative inverse, which, in this ring, are exactly those coprime to n.
In mathematics, the sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieve of Eratosthenes, which marks off multiples of primes, the sieve of Atkin does some preliminary work and then marks off multiples of squares of primes, thus achieving a better theoretical asymptotic complexity. It was created in 2003 by A. O. L. Atkin and Daniel J. Bernstein.
In computational number theory, a variety of algorithms make it possible to generate prime numbers efficiently. These are used in various applications, for example hashing, public-key cryptography, and search of prime factors in large numbers.
In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. It is a special case of the general number field sieve. While it is less efficient than the general algorithm, it is conceptually simpler. It serves as a helpful first step in understanding how the general number field sieve works.
In computational number theory, a factor base is a small set of prime numbers commonly used as a mathematical tool in algorithms involving extensive sieving for potential factors of a given integer.
In mathematics, the sieve of Sundaram is a variant of the sieve of Eratosthenes, a simple deterministic algorithm for finding all the prime numbers up to a specified integer. It was discovered by Indian student S. P. Sundaram in 1934.
In mathematics, the sieve of Pritchard is an algorithm for finding all prime numbers up to a specified bound. Like the ancient sieve of Eratosthenes, it has a simple conceptual basis in number theory. It is especially suited to quick hand computation for small bounds.
