Detecting perfect powers by factoring into coprimes

DOI10.1090/S0025-5718-06-01837-0zbMath1110.11038MaRDI QIDQ3420437

Jonathan Pila, Hendrik W. jun. Lenstra, Daniel J. Bernstein

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

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

Related Items (8)

New Characterization of the Factor Refinement Algorithm with Applications ⋮ Deterministic factoring with oracles ⋮ Improvements on non-interactive zero-knowledge proof systems related to quadratic residuosity languages ⋮ On completely factoring any integer efficiently in a single run of an order-finding algorithm ⋮ A characterization of nonprime powers ⋮ Primality testing with Gaussian periods ⋮ Detecting square numbers ⋮ Proving primality in essentially quartic random time

Cites Work

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

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