An exponent one-fifth algorithm for deterministic integer factorisation

10/12/2020
by   David Harvey, et al.
0

Hittmeir recently presented a deterministic algorithm that provably computes the prime factorisation of a positive integer N in N^2/9+o(1) bit operations. Prior to this breakthrough, the best known complexity bound for this problem was N^1/4+o(1), a result going back to the 1970s. In this paper we push Hittmeir's techniques further, obtaining a rigorous, deterministic factoring algorithm with complexity N^1/5+o(1).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset