Faster deterministic integer factorization
From MaRDI portal
Abstract: The best known unconditional deterministic complexity bound for computing the prime factorization of an integer N is O(M_int(N^(1/4) log N)), where M_int(k) denotes the cost of multiplying k-bit integers. This result is due to Bostan--Gaudry--Schost, following the Pollard--Strassen approach. We show that this bound can be improved by a factor of (log log N)^(1/2).
Recommendations
- A \(\log\)-\(\log\) speedup for exponent one-fifth deterministic integer factorisation
- A babystep-giantstep method for faster deterministic integer factorization
- Deterministic factorization of sums and differences of powers
- A deterministic algorithm for integer factorization
- An exponent one-fifth algorithm for deterministic integer factorisation
Cites work
- A search for Wieferich and Wilson primes
- Faster integer multiplication
- scientific article; zbMATH DE number 3856407 (Why is no real title available?)
- scientific article; zbMATH DE number 3460351 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 2206373 (Why is no real title available?)
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- Multiplicative number theory. I. Classical theory
- On Schönhage's algorithm and subquadratic integer gcd computation
- Some results on computational complexity
Cited in
(16)- Detecting squarefree numbers
- Fast multivariate multi-point evaluation revisited
- Integer factorization as subset-sum problem
- A Simple and Improved Algorithm for Integer Factorization with Implicit Hints
- A deterministic algorithm for integer factorization
- Deterministic root finding over finite fields using Graeffe transforms
- A linear-time algorithm for the orbit problem over cyclic groups
- A babystep-giantstep method for faster deterministic integer factorization
- scientific article; zbMATH DE number 3872677 (Why is no real title available?)
- An exponent one-fifth algorithm for deterministic integer factorisation
- A time-space tradeoff for Lehman's deterministic integer factorization method
- A \(\log\)-\(\log\) speedup for exponent one-fifth deterministic integer factorisation
- Deterministic factorization of sums and differences of powers
- A reduction of integer factorization to modular tetration
- Deterministic factoring with oracles
- Finding normal binary floating-point factors efficiently
This page was built for publication: Faster deterministic integer factorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2862533)
