Editing Integer factorization (section)

== Heuristic running time ==
In number theory, there are many integer factoring algorithms that heuristically have expected [[Time complexity|running time]]
: <math>L_n\left[\tfrac12,1+o(1)\right]=e^{(1+o(1))\sqrt{(\log n)(\log \log n)}}</math>
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 [[generalized Riemann hypothesis]].