Editing Prime number (section)

=== Integer factorization ===
{{main|Integer factorization}}
Given a composite integer {{tmath|n}}, the task of providing one (or all) prime factors is referred to as ''factorization'' of {{tmath|n}}. It is significantly more difficult than primality testing,<ref>{{harvnb|Kraft|Washington|2014}}, [https://books.google.com/books?id=4NAqBgAAQBAJ&pg=PA275 p.&nbsp;275].</ref> and although many factorization algorithms are known, they are slower than the fastest primality testing methods. Trial division and [[Pollard's rho algorithm]] can be used to find very small factors of {{tmath|n}},<ref name="p. 220"/> and [[elliptic curve factorization]] can be effective when {{tmath|n}} has factors of moderate size.<ref>{{cite book|title=An Introduction to Mathematical Cryptography|series=Undergraduate Texts in Mathematics|first1=Jeffrey|last1=Hoffstein|first2=Jill|last2=Pipher|author2-link=Jill Pipher|first3=Joseph H.|last3=Silverman|author3-link=Joseph H. Silverman|edition=2nd|publisher=Springer|year=2014|isbn=978-1-4939-1711-2|page=329|url=https://books.google.com/books?id=cbl_BAAAQBAJ&pg=PA329}}</ref> Methods suitable for arbitrary large numbers that do not depend on the size of its factors include the [[quadratic sieve]] and [[general number field sieve]]. As with primality testing, there are also factorization algorithms that require their input to have a special form, including the [[special number field sieve]].<ref>{{cite journal | last = Pomerance | first = Carl | author-link = Carl Pomerance | issue = 12 | journal = [[Notices of the American Mathematical Society]] | mr = 1416721 | pages = 1473–1485 | title = A tale of two sieves | volume = 43 | year = 1996}}</ref> {{as of|2019|12}} the [[Integer factorization records|largest number known to have been factored]] by a general-purpose algorithm is [[RSA-240]], which has 240 decimal digits (795 bits) and is the product of two large primes.<ref>{{cite web |first1=Emmanuel |last1=Thomé |url=https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;fd743373.1912 |title=795-bit factoring and discrete logarithms |date= December 2, 2019 |website=LISTSERV Archives }}</ref>

[[Shor's algorithm]] can factor any integer in a polynomial number of steps on a [[quantum computer]].<ref>{{cite book|title=Quantum Computing: A Gentle Introduction|first1=Eleanor G.|last1=Rieffel|author1-link=Eleanor Rieffel|first2=Wolfgang H.|last2=Polak|publisher=MIT Press|year=2011|isbn=978-0-262-01506-6|contribution=Chapter 8. Shor's Algorithm|pages=163–176|title-link= Quantum Computing: A Gentle Introduction |contribution-url=https://books.google.com/books?id=iYX6AQAAQBAJ&pg=PA163}}</ref> However, current technology can only run this algorithm for very small numbers. {{As of|2012|10}}, the largest number that has been factored by a quantum computer running Shor's algorithm is 21.<ref>{{cite journal |last1=Martín-López |first1=Enrique  |first2=Anthony|last2=Laing|first3=Thomas|last3=Lawson  |first4=Roberto|last4=Alvarez  |first5=Xiao-Qi|last5=Zhou  |first6=Jeremy L.|last6=O'Brien |title=Experimental realization of Shor's quantum factoring algorithm using qubit recycling |journal=Nature Photonics |volume=6  |issue=11  |pages=773–776  |date=12 October 2012 |doi=10.1038/nphoton.2012.259 |arxiv = 1111.4147  |bibcode = 2012NaPho...6..773M |s2cid=46546101 }}</ref>