Content deleted Content added
m Open access bot: url-access updated in citation with #oabot. |
m url duplicates doi |
||
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 non-[[quantum computer|quantum]] integer factorization [[algorithm]] is known. However, it has not been proven that such an algorithm does not exist. 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
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 classical 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 classical computer increases drastically.
| |||