A deterministic algorithm for finding r-power divisors

DOI10.1007/S40993-022-00387-WMaRDI QIDQ2093686zbMATH OpenOpenAlexFDO

Authors David I. Harvey, Markus Hittmeir

Publication date 27 October 2022

Published in Research in Number Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Copersmith's methodfactorizationLLL

Mathematics Subject Classification ID

Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16) Symbolic computation and algebraic computation (68W30)

Abstract: Building on work of Boneh, Durfee and Howgrave-Graham, we present a deterministic algorithm that provably finds all integers $p$ such that $p^{r}mathrel|N$ in time $O(N^{1/4r+epsilon})$ for any $epsilon>0$. For example, the algorithm can be used to test squarefreeness of $N$ in time $O(N^{1/8+epsilon})$; previously, the best rigorous bound for this problem was $O(N^{1/6+epsilon})$, achieved via the Pollard--Strassen method.

Review text

In this paper under review the author provides a deterministic algorithm, where on input a positive integer \(N\), outputs all the positive integers \(d\) such that \(d^r|N,\) \(r\) positive integer. If we assume that \(r\ll \log_2{N},\) then the running time, in bit operations, is \(O\bigg(N^{1/4r}\frac{(\log_2{N})^{10+\varepsilon}}{r^3}\bigg), \) for any \(\varepsilon>0.\) The author remarks that, the algorithm is impractical for small \(r\), so it can not compete the general-purpose factorization algorithms. It is important to notice that, the algorithm is \textit{fully} deterministic, whereas in other factorization algorithms such as ECM and NFS, the algorithms are based on heuristic assumptions in order to be analyzed with respect to their running time. If we apply the algorithm of the paper in the squarefreeness problem of an integer \(N,\) the best algorithms have running time \(O(N^{1/6 +\varepsilon}) \), however the algorithm of the paper provides running time \(O(N^{1/8+\varepsilon}).\) As far as the case \(r=1\), the algorithm does not provide any improvement from the Coppersmith's algorithm, i.e. the running time remains \(O(N^{1/4+\varepsilon}).\) The proof of the Theorem builds on the work of Boneh, Durfee and Howgrave-Graham.

Recommendations

• A deterministic algorithm for integer factorization
• Detecting perfect powers by factoring into coprimes
• Detecting perfect powers in essentially linear time
• scientific article; zbMATH DE number 5972265
• A deterministic algorithm for computing divisors in an interval

Cites work

• A \(\log\)-\(\log\) speedup for exponent one-fifth deterministic integer factorisation
• Algorithmic Number Theory
• Approximate formulas for some functions of prime numbers
• Computing Rational Zeros of Integral Polynomials by p-Adic Expansion
• Detecting squarefree numbers
• Factoring polynomials with rational coefficients
• scientific article; zbMATH DE number 5532109 (Why is no real title available?)
• scientific article; zbMATH DE number 3936514 (Why is no real title available?)
• scientific article; zbMATH DE number 3974286 (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 1418303 (Why is no real title available?)
• Mathematics of public key cryptography.
• Modern computer algebra
• Modern computer arithmetic
• Probabilistic computation of integer polynomial GCDs
• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• Some results on computational complexity

Cited in

(5)

• scientific article; zbMATH DE number 3636092 (Why is no real title available?)
• A deterministic algorithm for computing divisors in an interval
• Computing prime divisors in an interval
• A generalization of Lehman's method
• Fast square-free decomposition of integers using class groups

Describes a project that uses

Uses Software

• GCDHEU

This page was built for publication: A deterministic algorithm for finding \(r\)-power divisors

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