Integer factorization: Difference between revisions

Revision as of 12:54, 20 June 2024

Revision as of 18:28, 21 June 2024

Line 7:

To factorize a small integer {{mvar|n}} using mental or pen-and-paper arithmetic, the simplest method is [[trial division]]: checking if the number is divisible by prime numbers {{math|2}}, {{math|3}}, {{math|5}}, and so on, up to the [[square root]] of {{mvar|n}}. For larger numbers, especially when using a computer, various more sophisticated factorization algorithms are more efficient. A prime factorization algorithm typically involves [[primality test|testing whether each factor is prime]] each time a factor is found.

When the numbers are sufficiently large, no efficient [[quantum computer|non-quantum]] integer factorization [[algorithm]] is known. However, it has not been proven that such an algorithm does not exist (maybe it is the recently introduced [[primorial sieve]]). The presumed [[Computational hardness assumption|difficulty]] of this problem is important for the algorithms used in [[cryptography]] such as [[RSA (cryptosystem)|RSA public-key encryption]] and the [[Digital Signature Algorithm|RSA digital signature]].<ref>{{Citation |last=Lenstra |first=Arjen K. |title=Integer Factoring |date=2011 |url=http://link.springer.com/10.1007/978-1-4419-5906-5_455 |encyclopedia=Encyclopedia of Cryptography and Security |pages=611–618 |editor-last=van Tilborg |editor-first=Henk C. A. |place=Boston, MA |publisher=Springer US |language=en |doi=10.1007/978-1-4419-5906-5_455 |isbn=978-1-4419-5905-8 |access-date=2022-06-22 |editor2-last=Jajodia |editor2-first=Sushil}}</ref> Many areas of [[mathematics]] and [[computer science]] have been brought to bear on the problem, including [[elliptic curve]]s, [[algebraic number theory]], and [[quantum computer|quantum computing]].

Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are [[semiprime]]s, the product of two prime numbers. When they are both large, for instance more than two thousand [[bit]]s long, randomly chosen, and about the same size (but not too close, for example, to avoid efficient factorization by [[Fermat's factorization method]]), even the fastest prime factorization algorithms on the fastest computers can take enough time to make the search impractical; that is, as the number of digits of the integer being factored increases, the number of operations required to perform the factorization on any computer increases drastically.