Detecting perfect powers by factoring into coprimes

DOI10.1090/S0025-5718-06-01837-0zbMATH Open1110.11038MaRDI QIDQ3420437FDOQ3420437

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)

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\).

zbMATH Keywords

perfect powersrun-timeDiscrete Fourier Transformnumber-theoretic algorithmsfactoring into coprimes

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

• New Characterization of the Factor Refinement Algorithm with Applications
• Detecting square numbers
• Factoring into coprimes in essentially linear time
• Primality testing with Gaussian periods
• Efficiently certifying non-integer powers
• A characterization of nonprime powers
• A generalization of Lehman's method
• Proving primality in essentially quartic random 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
• Deterministic factoring with oracles
• A deterministic algorithm for finding \(r\)-power divisors
• Power detection over number fields

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)