Integer factorization: Difference between revisions

Revision as of 23:27, 5 November 2023

Revision as of 23:28, 5 November 2023

Line 3:

{{unsolved|computer science|Can integer factorization be solved in polynomial time on a classical computer?}}

In [[number theory]], '''integer factorization''' is the decomposition, of a [[positive integer]] into a [[Product (mathematics)|product]] of integers. Every positive integer greater than 1 is either the product of two or more integer [Divisor[divisor|factors]], in which case it is called a [[composite number]], or it is not, in which case it is called a [[prime number]]. If one of the factors is composite, it can in turn be written as a product of smaller factors. Continuing this process until every factor is prime is called '''prime factorization'''; the result is always unique by the [[prime factorization theorem]]. A prime factorization algorithm typically involves [[primality test|testing whether each factor is prime]] after each step.

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. 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]].