Rational sieve

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.

Suppose we are trying to factor the composite number n. We choose a bound B, and identify the factor base (which we will call P), the set of all primes less than or equal to B. Next, we search for positive integers z such that both z and z+n are B-smooth — i.e. all of their prime factors are in P. We can therefore write, for suitable exponents ${\displaystyle a_{k}}$,

${\displaystyle z=\prod _{p_{i}\in P}p_{i}^{a_{i}}}$

...
Wikipedia