A **prime factorization algorithm** is an algorithm (a step-by-step process) by which an integer (whole number) is "decomposed" into a product of factors that are prime numbers. The Fundamental Theorem of Arithmetic guarantees that this decomposition is unique.

Table of contents |

2 External link |

We can describe a recursive algorithm to perform such factorizations:
given a number *n*

- if
*n*is prime, this is the factorization, so stop here. - if
*n*is composite, divide*n*by the first prime*p*_{1}. If it divides cleanly, recurse with the value*n*/*p*_{1}. If it does not divide cleanly, divide*n*by the next prime*p*_{2}, and so on.

The described algoithm works fine for small *n*. However, for an 18-digit number (which has 60 digits in binary), all primes below about 1,000,000,000 may need to be tested, which is taxing even for a computer.

Adding two decimal digits to the original number will multiply the computation time by 10.

The difficulty (large time complexity) of factorization makes it a suitable basis for modern cryptography.

*See also:* Euler's Theorem, Integer factorization