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
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 factorizationA simple factorization algorithm
Description
Note we need only primes p1 to p√n.Time complexity