A prime factorization algorithm which can be implemented in a single-step or double-step form. In the single-step
version, a prime factor 
of a number 
can be found if 
is a product of small primes
by finding an 
such that
 |
where 
,
with 
a large number and 
. Then since 
, 
, so 
. There is therefore a good chance that 
, in which case 
(where GCD is the greatest
common divisor) will be a nontrivial divisor of 
.
In the double-step version, a prime factor 
can be found if 
is a product of small primes
and a single larger prime.
