Prime factorization algorithm
The prime factorization algorithm of an integer involves the process, or algorithm of "decomposing" a number into a product of factors that are prime numbers. The Fundamental Theorem of Arithmetic guarantees that this decomposition is unique.
| Table of contents |
|
2 Factorization time complexity 3 External links |
Factorization algorithm
We can describe a recursive algorithm to perform such factorizations:
given a number n
- if n is prime, this is the factorization and stop here.
- if n is composite, divide n by the first prime p1. If it divides cleanly, recurse with the value n/p1. If it does not divide cleanly, divide n by the next prime p2, and so on.
The described algoithm works fine for small n.
However, for an 18 decimal digits number (which is a 60 binary digits number), all primes between one and 1 000 000 000 should be tested, which is taxing to calculate, 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. (asymmetric keys).
See also: Euler's Theorem, Integer factorizationFactorization time complexity