Nitpick: Pollard's rho is unproven not because it relies on the birthday paradox, but because there's no way to prove that f(x) = x^2 + a behaves like a random

Nitpick: Pollard's rho is unproven not because it relies on the birthday paradox, but because there's no way to prove that f(x) = x^2 + a behaves like a random walk. It may not because, e.g, the length of the cycle may be the same for every prime divisor of the number being factored. 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-0595059-1/home.html http://www.ams.org/journals/mcom/1981-36-153/S0025-5718-1981... [2] https://math.dartmouth.edu/~carlp/hyperI.pdf https://math.dartmouth.edu/~carlp/hyperI.pdf [3] https://math.dartmouth.edu/~carlp/PDF/paper129.pdf https://math.dartmouth.edu/~carlp/PDF/paper129.pdf [4] https://openaccess.leidenuniv.nl/bitstream/handle/1887/3826/346_086.pdf?sequence=1 https://openaccess.leidenuniv.nl/bitstream/handle/1887/3826/...