Detecting perfect powers in essentially linear time

DOI10.1090/S0025-5718-98-00952-1MaRDI QIDQ4396462zbMATH OpenDBLPWikidataFDO

Authors Daniel J. Bernstein

Publication date 14 June 1998

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

Full work available at URL https://doi.org/10.1090/S0025-5718-98-00952-1

zbMATH Keywords

fast multiplicationlinear forms in logarithmsNewton's methodnumber theoretic algorithmsperfect powerstranscendental number theory

Mathematics Subject Classification ID

Linear forms in logarithms; Baker's method (11J86) Number-theoretic algorithms; complexity (11Y16) Roundoff error (65G50)

Recommendations

• Detecting perfect powers by factoring into coprimes
• Perfect power testing
• Sieve algorithms for perfect power testing

Cites work

• A hyperelliptic smoothness test. I
• Approximate formulas for some functions of prime numbers
• Fast compact prime number sieves (among others)
• Fast Multiple-Precision Evaluation of Elementary Functions
• Fast multiplication of large numbers
• Fast polynomial transform algorithms for digital convolution
• scientific article; zbMATH DE number 435565 (Why is no real title available?)
• scientific article; zbMATH DE number 3172038 (Why is no real title available?)
• scientific article; zbMATH DE number 3942888 (Why is no real title available?)
• scientific article; zbMATH DE number 3973001 (Why is no real title available?)
• scientific article; zbMATH DE number 3987351 (Why is no real title available?)
• scientific article; zbMATH DE number 4102053 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 44590 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 729452 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• scientific article; zbMATH DE number 3404329 (Why is no real title available?)
• Matrix Analysis
• Multiplicative dependence in number fields
• On a problem of Oppenheim concerning Factorisatio Numerorum
• Sieve algorithms for perfect power testing
• Some problems involving powers of integers
• The development of the number field sieve

Cited in

(21)

• A deterministic algorithm for finding \(r\)-power divisors
• A certain family of subgroups of \(\mathbb{Z}_{n}^{\star}\) is weakly pseudo-free under the general integer factoring intractability assumption
• Fast exponentiation using the truncation operation
• Sieve algorithms for perfect power testing
• Algorithms for the Multiplication Table Problem
• Lucas-Lehmer primality tests for certain prime curios
• Detecting perfect powers by factoring into coprimes
• Proving primality in essentially quartic random time
• Factorization of the tenth Fermat number
• Improved primality proving with Eisenstein pseudocubes
• Detecting square numbers
• On lacunary polynomial perfect powers
• On completely regular codes
• Embedding divisor and semi-prime testability in f-vectors of polytopes
• Improvements on non-interactive zero-knowledge proof systems related to quadratic residuosity languages
• Power detection over number fields
• Efficiently certifying non-integer powers
• Detecting lacunary perfect powers and computing their roots
• Geometry of the del Pezzo surface y^2=x^3+Am^6+Bn^6
• A generalization of Lehman's method
• Polynomial algorithms for primality testing in algebraic number fieldswith class number 1

This page was built for publication: Detecting perfect powers in essentially linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4396462)