A babystep-giantstep method for faster deterministic integer factorization

DOI10.1090/MCOM/3313MaRDI QIDQ3177725zbMATHOpenAlexFDO

Authors Markus Hittmeir

Publication date 1 August 2018

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.08766

zbMATH Keywords

babystep-giantstep methoddeterministic integer factorization

Mathematics Subject Classification ID

Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16) Factorization; primality (11A51)

Abstract: In 1977, Strassen presented a deterministic and rigorous algorithm for solving the problem of computing the prime factorization of natural numbers $N$. His method is based on fast polynomial arithmetic techniques and runs in time $widetildeO(N^{1/4})$, which has been state of the art for the last forty years. In this paper, we will combine Strassen's approach with a babystep-giantstep method to improve the currently best known bound by a superpolynomial factor. The runtime complexity of our algorithm is of the form [ widetilde{O}left(N^{1/4}exp(-Clog N/loglog N) ight). ]

Recommendations

• Faster deterministic integer factorization
• Asymptotically Fast Factorization of Integers
• A deterministic algorithm for integer factorization
• An exponent one-fifth algorithm for deterministic integer factorisation
• A time-space tradeoff for Lehman's deterministic integer factorization method
• A Simple and Improved Algorithm for Integer Factorization with Implicit Hints
• A Rigorous Time Bound for Factoring Integers
• scientific article; zbMATH DE number 4077312
• scientific article; zbMATH DE number 1273636
• scientific article; zbMATH DE number 4045819

Cites work

• scientific article; zbMATH DE number 3841211 (Why is no real title available?)
• scientific article; zbMATH DE number 2204782 (Why is no real title available?)
• Approximate formulas for some functions of prime numbers
• Deterministic factorization of sums and differences of powers
• Even faster integer multiplication
• Faster deterministic integer factorization
• Faster integer multiplication
• Integer factoring
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Modular hyperbolas
• Prime numbers and computer methods for factorization.
• Sharper Bounds for the Chebyshev Functions θ(x) and ψ(x). II
• Some results on computational complexity
• The joy of factoring

Cited in

(13)

• Deterministic factorization of sums and differences of powers
• Deterministic factoring with oracles
• A reduction of integer factorization to modular tetration
• Supersingular j-invariants and the class number of ℚ(−p)
• Factoring with hints
• A generalization of Lehman's method
• Faster deterministic integer factorization
• A time-space tradeoff for Lehman's deterministic integer factorization method
• Integer factorization as subset-sum problem
• An exponent one-fifth algorithm for deterministic integer factorisation
• A \(\log\)-\(\log\) speedup for exponent one-fifth deterministic integer factorisation
• Smooth subsum search a heuristic for practical integer factorization
• Computation of orders and cycle lengths of automorphisms of finite solvable groups

This page was built for publication: A babystep-giantstep method for faster deterministic integer factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177725)