A deterministic algorithm for finding \(r\)-power divisors
type: Item
instance of: scholarly article
title: A deterministic algorithm for finding \(r\)-power divisors
zbMATH Open document ID: 1505.11155
author: David I. Harvey
author: Markus Hittmeir
published in: Research in Number Theory
publication date: 2022-10-27T00:00:00Z
full work available at URL: https://arxiv.org/abs/2202.12401
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.
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 11Y05
zbMATH DE Number: 7608407
zbMATH Keywords: factorization
zbMATH Keywords: LLL
zbMATH Keywords: Copersmith's method
reviewed by: Konstantinos A. Draziotis
describes a project that uses: GCDHEU
MaRDI profile type: Publication
OpenAlex ID: W4307086467
arXiv ID: 2202.12401
cites work: Q4941863
cites work: Q3615929
cites work: Detecting squarefree numbers
cites work: Modern Computer Arithmetic
cites work: Q3707405
cites work: Small solutions to polynomial equations, and low exponent RSA vulnerabilities
cites work: Q3740227
cites work: Mathematics of public key cryptography.
cites work: A log-log speedup for exponent one-fifth deterministic integer factorisation
cites work: Factoring polynomials with rational coefficients
cites work: Computing Rational Zeros of Integral Polynomials by p-Adic Expansion
cites work: Q4298260
cites work: Q4046106
cites work: Approximate formulas for some functions of prime numbers
cites work: Probabilistic computation of integer polynomial GCDs
cites work: Some results on computational complexity
cites work: Algorithmic Number Theory
cites work: Modern computer algebra
DOI: 10.1007/S40993-022-00387-W
description: scientific article