Sieving

Sieving is an algorithm to discover smooth numbers and prime numbers from a sequence of integers much faster than trial factoring, even when trial factoring runs quickly for a member of the sequence.

The most used sieves are linear and quadratic: in the first case the sequence forms an arithmetic progression, so it has the form [math]\displaystyle{ m\, =\, an + b }[/math], while in the second the sequence has the form [math]\displaystyle{ m\, =\, an^2 + bn + c }[/math].

The idea is to have an array where each element represents a member of the sequence initializing it to zeros indicating that a factor was not found yet.

The next step depends on whether we need to find prime number or smooth numbers.

If we need to find prime numbers, for all primes between 2 and the square root of the maximum member of the sequence, set to 1 those elements of the array that correspond to the multiples of the current prime. After this procedure ends, all elements of the array that still have the value zero are prime.

Notice that if the sequence has values less than the computed square root, this procedure can fail, because all primes less than that value will be marked as composites. But this can be fixed easily by do not setting that element to 1 if the member of the sequence is equal to the prime used in the loop.

If we need to determine which members of the sequence are smooth, for all primes between 2 and the smoothness bound, add the logarithm of the prime (which must be computed before this loop) to the elements of the array that correspond to the multiples of the current prime. After this procedure ends, we walk through the array searching for elements of the array whose values are near to the logarithm of the member of the sequence.

In order to determine the elements of the array that correspond to members of the sequence that are multiple of the prime inside the loop, we have two procedures, depending whether the sieve is linear or quadratic.

For linear sieves the sequence has the form [math]\displaystyle{ m\, =\, an + b }[/math], where [math]\displaystyle{ n }[/math] is the element number of the array. We have to compute [math]\displaystyle{ k = -b/a \,\pmod p }[/math]. Then the elements of the array [math]\displaystyle{ k }[/math], [math]\displaystyle{ k+p }[/math], [math]\displaystyle{ k+2p }[/math], [math]\displaystyle{ k+3p }[/math], and so on correspond to multiples of the prime.

For quadratic sieves the sequence has the form [math]\displaystyle{ m\, =\, an^2 + bn + c }[/math], where [math]\displaystyle{ n }[/math] is the element number of the array. We have to solve [math]\displaystyle{ an^2 + bn + c \,\equiv \,0\,\pmod p }[/math] which can have zero, one or two solutions depending on the values of the discriminant [math]\displaystyle{ b^2 - 4ac }[/math]. When there are solutions, these solutions plus a multiple of the prime number correspond to multiples of the prime in the sequence. A subroutine for computing modular square roots will be needed in this case, because we have to compute the square root of the discriminant.

See also

• Sieving program