A babystep-giantstep method for faster deterministic integer factorization

DOI10.1090/mcom/3313zbMath1436.11147arXiv1608.08766OpenAlexW2511191713MaRDI QIDQ3177725

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

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

Related Items (9)

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

Cites Work

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

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