Prime factorization algorithm

A prime factorization algorithm is an algorithm (a step-by-step process) by which an integer (whole number) is "decomposed" into a product of factorss that are prime numbers. The fundamental theorem of arithmetic guarantees that this decomposition is unique.

Table of contents

1 A simple factorization algorithm

1.1 Description
1.2 Time complexity

2 External link

A simple factorization algorithm

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₁. If it divides cleanly, recurse with the value n/p₁. If it does not divide cleanly, divide n by the next prime p₂, and so on.

Note that we need to test only primes p_i such that p_i≤ √n.

The algoithm described above works fine for small n, but becomes impractical as n gets larger. For example, for an 18-digit (or 60 bit) number, 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.