How exactly does wheel factorization work and what is it used for?

Question

I would like to learn how to use wheel factorization but am having trouble understanding it. I tried reading the wikipedia article but found it confusing (even the talk page says it's a mess). What exactly is it and how is it used? To my understanding it eliminates some (but not all) composite numbers in a list up to a certain number. So in this sense it's a technique that can be used to speed up existing factorization algorithms? It seems to almost be the same as the sieve of Eratosthenes except it starts with a small list of known prime numbers?

If someone could please give the general procedure and a simple example that would be much appreciated.

Answer 1

Since trial division is mostly useless for factoring large numbers, and using a prime number sieve for factoring is just a minor refinement of trial division, you shouldn't think of it as a factorization algorithm. Instead, this is a prime-generating algorithm: the goal is to generate the list of primes in the set $[n] := \{1, 2, 3, \dots, n\}$ as quickly as possible.

We are trying to improve on the sieve of Eratosthenes in efficiency, which does $\Theta(n \cdot \log \log n)$ arithmetical operations on elements of $[n]$.

Wheel factorization does this by using the fact that for the first few primes, the sieve we're constructing is periodic, and there's no point in extending the periodic pattern all the way to $n$. Instead, we only generate the list of numbers not divisible by the first $k$ primes $p_1, p_2, \dots, p_k$ only up to their product $p_1 p_2 \dotsm p_k$. That is, we:

• Begin by generating the list of numbers in $\{1,2,3,4,5,6\}$ not divisible by $2$ or $3$: it is $\{1,5\}$.
• Extend this to the list of numbers in $\{1,2,3,\dots,30\}$ not divisible by $2$, $3$, or $5$: it is $\{1,7,11,13,17,19,23,29\}$.
• Extend this to the list of numbers in $\{1,2,3,\dots, 210\}$ not divisible by $2$, $3$, $5$, or $7$, and so on.

For each extension step, if the set we've generated is $S$ and the next prime we're adding is $p$, then the next set consists of $p$ translated copies of $S$, with $p \cdot S$ removed. For example, if $S = \{1,5\}$ and $p=5$, then we repeat $S$ $5$ times (to get $\{1,5\} \cup \{7,11\} \cup \{13,17\} \cup \{19, 23\} \cup \{25, 29\}$) and remove $5\cdot S = \{5,25\}$. By the way, $p$ is also easy to find: it is the element of $S$ after $1$.

Once $p_1 p_2 \dotsm p_k > n$, we no longer take repeated copies of $S$, and just remove $p \cdot S$ from $S$ to extend. We stop, as with the sieve of Eratosthenes, when $p_k > \sqrt n$. At this point, $S$ contains all the primes larger than $p_k$; the primes smaller than $p_k$ are the ones we used along the way, which we keep track of separately.

According to this paper, this only requires $\Theta(\frac{n}{\log \log n})$ arithmetical operations on elements of $[n]$, if implemented carefully.

Answer 2

The OP states

It seems to almost be the same as the sieve of Eratosthenes except it starts with a small list of known prime numbers?

That is correct. If you start off with just first two primes, $2$ and $3$ you can mark off all numbers that are a multiple of either one. For the theory here see

Is that true that all the prime numbers are of the form $6m \pm 1$?

Notice that $6 = 2 \times 3$ in the above Q/A thread.

What about screening for just $2$, $3$, and $5$? The core 'guts' for this $2 \times 3 \times 5 = 30$ wheel algorithm is it has to start 'spitting out' prime number candidates with the actual spot on prime number $7$. It employs a $\text{modulo-}30$ logic but after awhile it can output composite numbers. Still, more numbers will be excluded than by using only the simple $6m \pm 1$ screen.

The algorithm doesn't hit $30$, but the $2$, $3$, and $5$ Eratosthenes exclusions all simultaneously meet and are 'reset' at that number,

$\quad 30 = 2 \times 15 \; \text{exclude } 30 + 2, 30+4, \dots$
$\quad 30 = 3 \times 10 \; \text{exclude } 30+3, 30+6, \dots$
$\quad 30 = 5 \times 6 \; \;\,\text{exclude } 30+5, 30+10, \dots$

and we are ready to 'turn the wheel' again.

In a comment the OP states they are not confident about the programming for a wheel. The approach here always works. You know exactly where the primes are on your initial step by step traversal of length $30$ (or any other length wheel) and of course the exclusions are the complement of this set. So you just have to step over the composites and then program for the simultaneous meet/reset.

Following is a Python algorithm for the $2 \times 3 \times 5 = 30$ 'spit out'. We have it stopping when the output is $77$, which is a composite of the primes $7$ and $11$ which do not belong to $\{2,3,5\}$.

Python Program

def Z30_Sieve():
    spot = Z30_sieve_sv[0]
    pc = Z30_sieve_sv[spot] + 30
    Z30_sieve_sv[spot] = pc
    spot = spot + 1
    if spot < len(Z30_sieve_sv):
        Z30_sieve_sv[0] = spot
    else:
        Z30_sieve_sv[0] = 1       
    return pc

Z30_sieve_sv = [2, 1, -23, -19, -17, -13, -11, -7, -1]

for i in range(0, 20):
    print( Z30_Sieve() , Z30_sieve_sv)

OUTPUT

7 [3, 1, 7, -19, -17, -13, -11, -7, -1]
11 [4, 1, 7, 11, -17, -13, -11, -7, -1]
13 [5, 1, 7, 11, 13, -13, -11, -7, -1]
17 [6, 1, 7, 11, 13, 17, -11, -7, -1]
19 [7, 1, 7, 11, 13, 17, 19, -7, -1]
23 [8, 1, 7, 11, 13, 17, 19, 23, -1]
29 [1, 1, 7, 11, 13, 17, 19, 23, 29]
31 [2, 31, 7, 11, 13, 17, 19, 23, 29]
37 [3, 31, 37, 11, 13, 17, 19, 23, 29]
41 [4, 31, 37, 41, 13, 17, 19, 23, 29]
43 [5, 31, 37, 41, 43, 17, 19, 23, 29]
47 [6, 31, 37, 41, 43, 47, 19, 23, 29]
49 [7, 31, 37, 41, 43, 47, 49, 23, 29]
53 [8, 31, 37, 41, 43, 47, 49, 53, 29]
59 [1, 31, 37, 41, 43, 47, 49, 53, 59]
61 [2, 61, 37, 41, 43, 47, 49, 53, 59]
67 [3, 61, 67, 41, 43, 47, 49, 53, 59]
71 [4, 61, 67, 71, 43, 47, 49, 53, 59]
73 [5, 61, 67, 71, 73, 47, 49, 53, 59]
77 [6, 61, 67, 71, 73, 77, 49, 53, 59]