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 methodfast multiplicationlinear forms in logarithmsperfect powersnumber theoretic algorithmstranscendental number theory
Number-theoretic algorithms; complexity (11Y16) Roundoff error (65G50) Linear forms in logarithms; Baker's method (11J86)
Related Items
Embedding divisor and semi-prime testability in \(f\)-vectors of polytopes ⋮ Algorithms for the Multiplication Table Problem ⋮ Improvements on non-interactive zero-knowledge proof systems related to quadratic residuosity languages ⋮ On completely regular codes ⋮ Unnamed Item ⋮ Detecting lacunary perfect powers and computing their roots ⋮ Improved Primality Proving with Eisenstein Pseudocubes ⋮ A certain family of subgroups of \(\mathbb{Z}_{n}^{\star}\) is weakly pseudo-free under the general integer factoring intractability assumption ⋮ Detecting square numbers ⋮ 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
