An exponent one-fifth algorithm for deterministic integer factorisation

2020/10/12 by David Harvey, Harvey, David · 1 voice · 2 citations
#math.NT #cs.DS

paper · pdf · doi:10.48550/arxiv.2010.05450

Abstract

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).

Cited by

• On Factoring and Power Divisor Problems via Rank-3 Lattices and the Second Vector
• A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization

Discussions

• An exponent one-fifth algorithm for deterministic integer factorisation [hn, 99 points, 20 comments]

Related

• Deterministic Integer Factorization Algorithms
• Faster deterministic integer factorization
• A deterministic algorithm for integer factorization
• Digit Polynomials and their application to integer factorization
• Note Integer Factoring Methods III