A log-log speedup for exponent one-fifth deterministic integer factorisation

DOI10.1090/MCOM/3708zbMATH Open1491.11110arXiv2105.11105OpenAlexW3165388365MaRDI QIDQ5070544FDOQ5070544

David I. Harvey, Markus Hittmeir

Publication date: 13 April 2022

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

Abstract: Building on techniques recently introduced by the second author, and further developed by the first author, we show that a positive integer $N$ may be rigorously and deterministically factored into primes in at most [ Oleft( frac{N^{1/5} log^{16/5} N}{(loglog N)^{3/5}} ight) ] bit operations. This improves on the previous best known result by a factor of $(loglogN{)}^{3/5}$.

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

zbMATH Keywords

latticedeterministic algorithminteger factorization

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Modern Computer Arithmetic
• Mathematics of public key cryptography.
• A time-space tradeoff for Lehman’s deterministic integer factorization method
• Modern computer algebra
• Faster deterministic integer factorization
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• An LLL-reduction algorithm with quasi-linear time complexity
• Prime numbers and computer methods for factorization.
• The Generalized Gauss Reduction Algorithm
• Integer factoring
• Integer multiplication in time \(O(n\log n)\)
• A deterministic algorithm for integer factorization
• Factoring Large Integers
• A babystep-giantstep method for faster deterministic integer factorization
• The joy of factoring
• An exponent one-fifth algorithm for deterministic integer factorisation

Cited In (7)

• Explicit methods in number theory. Abstracts from the workshop held July 18--24, 2021 (hybrid meeting)
• On oracle factoring of integers
• 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
• A deterministic algorithm for finding \(r\)-power divisors

This page was built for publication: A log-log speedup for exponent one-fifth deterministic integer factorisation

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