A babystep-giantstep method for faster deterministic integer factorization

DOI10.1090/MCOM/3313zbMATH Open1436.11147arXiv1608.08766OpenAlexW2511191713MaRDI QIDQ3177725FDOQ3177725

Markus Hittmeir

Publication date: 1 August 2018

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

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

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

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

zbMATH Keywords

babystep-giantstep methoddeterministic integer factorization

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

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

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)