Huh -- I had always assumed when people talked about e.g. GNFS being the fastest known, they meant proven. I had no idea about this, thank you.
Re:A New Provable Factoring Algorithm
by ColinWright on Thursday October 23, 2014 @08:53AM
(#8497843)
Perfect - thank you.
Similarly, the complexity of the quadratic sieve is heuristic because there is no known way to prove that (sqrt(n) + i)^2 - n results in the same distribution of smooth integers than that of a random sequence of the same size. Dixon's algorithm [1] turns the quadratic sieve provable (but much slower in practice) by sampling randomly instead of sequentially. Sieving is thus no longer possible, but we get a subexponential running time of L_n[1/2, 2 sqrt(2)]. The hyperelliptic curve factorization algorithm [2, 3] is another probabilistic but provable algorithm with a more efficient but not provable counterpart, the elliptic curve method [4].
The blog post only seems to care about deterministic factoring algorithms, though. There are indeed no known deterministic factorization algorithms with better than exponential complexity.
[1] http://www.ams.org/journals/mcom/1981-36-153/S0025-5718-1981...
[2] https://math.dartmouth.edu/~carlp/hyperI.pdf
[3] https://math.dartmouth.edu/~carlp/PDF/paper129.pdf
[4] https://openaccess.leidenuniv.nl/bitstream/handle/1887/3826/...