Detecting perfect powers in essentially linear time

DOI10.1090/S0025-5718-98-00952-1zbMath0910.11057WikidataQ29302811 ScholiaQ29302811MaRDI QIDQ4396462

Daniel J. Bernstein

Publication date: 14 June 1998

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

zbMATH Keywords

Newton's method; fast multiplication; linear forms in logarithms; perfect powers; number theoretic algorithms; transcendental number theory

Mathematics Subject Classification ID

11Y16: Number-theoretic algorithms; complexity

65G50: Roundoff error

11J86: Linear forms in logarithms; Baker's method

Related Items

Improved Primality Proving with Eisenstein Pseudocubes, Detecting lacunary perfect powers and computing their roots, Detecting perfect powers by factoring into coprimes, Proving primality in essentially quartic random time, Factorization of the tenth Fermat number

Cites Work

• The development of the number field sieve
• On a problem of Oppenheim concerning Factorisatio Numerorum
• Sieve algorithms for perfect power testing
• Fast multiplication of large numbers
• Approximate formulas for some functions of prime numbers
• Fast polynomial transform algorithms for digital convolution
• Fast compact prime number sieves (among others)
• Some problems involving powers of integers
• Matrix Analysis
• Multiplicative dependence in number fields
• Fast Multiple-Precision Evaluation of Elementary Functions
• A hyperelliptic smoothness test. I
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item