Detecting perfect powers by factoring into coprimes

DOI10.1090/S0025-5718-06-01837-0MaRDI QIDQ3420437zbMATHFDO

Authors Daniel J. Bernstein, H. W. jun. Lenstra, Jonathan Pila

Publication date 2 February 2007

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

zbMATH Keywords

perfect powersrun-timeDiscrete Fourier Transformnumber-theoretic algorithmsfactoring into coprimes

Mathematics Subject Classification ID

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

Recommendations

• On the Computation of g(k) in Waring's Problem
• Sieve algorithms for perfect power testing
• Perfect power testing
• A characterization of nonprime powers
• Detecting perfect powers in essentially linear time
• Algorithmic Number Theory
• Consecutive integers divisible by the square of their largest prime factors
• On the powerfull part of \(n^2+1\).

Cites work

• Detecting perfect powers in essentially linear time
• Factor Refinement
• Factoring into coprimes in essentially linear time
• Sieve algorithms for perfect power testing

Cited in

(13)

• A deterministic algorithm for finding \(r\)-power divisors
• Detecting square numbers
• Efficiently certifying non-integer powers
• Deterministic factoring with oracles
• A generalization of Lehman's method
• New Characterization of the Factor Refinement Algorithm with Applications
• A characterization of nonprime powers
• Proving primality in essentially quartic random time
• Primality testing with Gaussian periods
• Power detection over number fields
• Factoring into coprimes in essentially linear time
• On completely factoring any integer efficiently in a single run of an order-finding algorithm
• Improvements on non-interactive zero-knowledge proof systems related to quadratic residuosity languages

This page was built for publication: Detecting perfect powers by factoring into coprimes

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