Integer factorization: Difference between revisions

Revision as of 22:01, 24 February 2024

Revision as of 02:53, 19 March 2024

Line 111:

in [[Big O notation|little-o]] and [[L-notation]].

Some examples of those algorithms are the [[elliptic curve method]] and the [[quadratic sieve]].

Another such algorithm is the '''class group relations method''' proposed by Schnorr,<ref name=1982-schnorr>{{cite journal | last=Schnorr|first=Claus P.|year=1982|title=Refined analysis and improvements on some factoring algorithms|journal=Journal of Algorithms|volume=3|pages=101–127 | doi=10.1016/0196-6774(82)90012-8 | issue=2 | mr=0657269|url=http://www.dtic.mil/get-tr-doc/pdf?AD=ADA096348|archive-url=https://web.archive.org/web/20170924140543/http://www.dtic.mil/get-tr-doc/pdf?AD=ADA096348|url-status=dead|archive-date=September 24, 2017}}</ref> Seysen,<ref name=1987-seysen>{{cite journal| last=Seysen|first=Martin|year=1987|title=A probabilistic factorization algorithm with quadratic forms of negative discriminant|journal=Mathematics of Computation|volume=48|pages=757–780| doi=10.1090/S0025-5718-1987-0878705-X| issue=178 | mr=0878705|doi-access=free}}</ref> and Lenstra,<ref name=1988-lenstra >{{cite journal|last=Lenstra|first=Arjen K|year=1988|title=Fast and rigorous factorization under the generalized Riemann hypothesis|journal=Indagationes Mathematicae|volume=50|issue=4|pages=443–454|doi=10.1016/S1385-7258(88)80022-2|url=https://infoscience.epfl.ch/record/164491/files/nscan9.PDF }}</ref> which they proved only assuming the unproved [[Generalizedgeneralized Riemann hypothesis|Generalized Riemann Hypothesis (GRH)]].

== Rigorous running time ==