Detecting perfect powers in essentially linear time
From MaRDI portal
Publication:4396462
DOI10.1090/S0025-5718-98-00952-1zbMath0910.11057WikidataQ29302811 ScholiaQ29302811MaRDI QIDQ4396462
Publication date: 14 June 1998
Published in: Mathematics of Computation (Search for Journal in Brave)
Newton's method; fast multiplication; linear forms in logarithms; perfect powers; number theoretic algorithms; transcendental number theory
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