Integer factorization: Difference between revisions

Revision as of 22:26, 2 January 2024

Revision as of 09:31, 13 January 2024

Line 37:

No [[algorithm]] has been published that can factor all integers in [[polynomial time]], that is, that can factor a {{math|''b''}}-bit number {{math|''n''}} in time {{math|[[Big O notation|O]](''b''^''k'')}} for some constant {{math|''k''}}. Neither the existence nor non-existence of such algorithms has been proved, but it is generally suspected that they do not exist and hence that the problem is not in class P.<ref>{{citation |last=Krantz |first=Steven G. |author-link=Steven G. Krantz |doi=10.1007/978-0-387-48744-1 |isbn=978-0-387-48908-7 |___location=New York |mr=2789493 |page=203 |publisher=Springer |title=The Proof is in the Pudding: The Changing Nature of Mathematical Proof |url=https://books.google.com/books?id=mMZBtxVZiQoC&pg=PA203 |year=2011}}</ref><ref>{{citation |last1=Arora |first1=Sanjeev |author1-link=Sanjeev Arora |last2=Barak |first2=Boaz |doi=10.1017/CBO9780511804090 |isbn=978-0-521-42426-4 |___location=Cambridge |mr=2500087 |page=230 |publisher=Cambridge University Press |title=Computational complexity |url=https://books.google.com/books?id=nGvI7cOuOOQC&pg=PA230 |year=2009|s2cid=215746906 }}</ref> The problem is clearly in class NP, but it is generally suspected that it is not [[NP-complete]], though this has not been proven.<ref>{{citation |last1=Goldreich |first1=Oded |author1-link=Oded Goldreich |last2=Wigderson |first2=Avi |author2-link=Avi Wigderson |editor1-last=Gowers |editor1-first=Timothy |editor1-link=Timothy Gowers |editor2-last=Barrow-Green |editor2-first=June |editor2-link=June Barrow-Green|editor3-last=Leader |editor3-first=Imre |editor3-link=Imre Leader |contribution=IV.20 Computational Complexity |isbn=978-0-691-11880-2 |___location=Princeton, New Jersey |mr=2467561 |pages=575–604 |publisher=Princeton University Press |title=The Princeton Companion to Mathematics |year=2008}}. See in particular [https://books.google.com/books?id=ZOfUsvemJDMC&pg=PA583 p.&nbsp;583].</ref>

There are published algorithms that are faster than {{math|O((1 + ''ε'')^''b'')}} for all positive {{math|''ε''}}, that is, [[Time complexity#Sub-exponential time|sub-exponential]]. {{As of|2022}}, the algorithm with best theoretical asymptotic running time is the [[general number field sieve]] (GNFS), first published in 1993,<ref>{{cite book |last1=Buhler |first1=J. P. |last2=Lenstra |first2=H. W. Jr. |last3=Pomerance |first3=Carl |titlechapter=Factoring integers with the number field sieve |title=The development of the number field sieve |date=1993 |publisher=Springer |isbn=978-3-540-57013-4 |pages=50–94 |doi=10.1007/BFb0091539 |hdl=1887/2149 |series=Lecture Notes in Mathematics |volume=1554 |url=https://doi.org/10.1007/BFb0091539 |access-date=12 March 2021 |language=English}}</ref> running on a {{math|''b''}}-bit number {{math|''n''}} in time:

: <math>\exp\left( \left(\left(\tfrac83\right)^\frac23 + o(1)\right)\left(\log n\right)^\frac13\left(\log \log n\right)^\frac23\right).</math>