Integer factorization: Difference between revisions

Revision as of 21:12, 18 February 2025

Revision as of 11:39, 19 April 2025

Line 11:

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.

Many cryptographic protocols are based on the presumed difficulty of factoring large composite integers or a related problem—forproblem {{Ndash}}for example, the [[RSA problem]]. An algorithm that efficiently factors an arbitrary integer would render [[RSA (algorithm)|RSA]]-based [[public-key]] cryptography insecure.

== Prime decomposition ==