A deterministic algorithm for finding \(r\)-power divisors

DOI10.1007/S40993-022-00387-WzbMATH Open1505.11155arXiv2202.12401OpenAlexW4307086467MaRDI QIDQ2093686

Author name not available (Why is that?)

Publication date: 27 October 2022

Published in: (Search for Journal in Brave)

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.

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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

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)