Sieve algorithms for perfect power testing

DOI10.1007/BF01228507MaRDI QIDQ2366224zbMATH OpenOpenAlexFDO

Authors Eric Bach, Jonathan P. Sorenson

Publication date 29 June 1993

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01228507, http://digital.library.wisc.edu/1793/59134

zbMATH Keywords

average-case analysisNewton's methodparallel algorithmssieve algorithm

Mathematics Subject Classification ID

Primality (11Y11) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

Many tests for primality of \(n\) first require the elimination of the case where \(n\) is a perfect \(k\)-th power. This is negligible compared with the main primality routines, so it is usually ignored. There is a rich variety of methods including Newton's root extraction with starting value found by counting digits, modular tests for \(k\) power and search for small prime divisors (for elimination). On a more sophisticated level there is the (logarithmic number of) parallel processors, and the ERH to bound the trial moduli for power tests. (This requires a small table for efficiency.) The worst case is \(O(\log^ 3 n)\), the average is \(O(\log^ 2 n)\), and \(O(\log n)\) is the median.

Recommendations

• Perfect power testing
• Detecting perfect powers by factoring into coprimes
• Detecting perfect powers in essentially linear time
• Recent developments in primality testing

Cites work

• A new arithmetic function of combinatorial significance
• An improvement of Selberg's sieve method I
• Analysis of a simple factorization algorithm
• Approximate formulas for some functions of prime numbers
• Asymptotically Fast Factorization of Integers
• Computing Multiplicative Inverses in GF(p)
• Factoring integers with elliptic curves
• Factoring with Cyclotomic Polynomials
• Fast compact prime number sieves (among others)
• Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus
• How to Generate Factored Random Numbers
• scientific article; zbMATH DE number 4077312 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 3708485 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 3756556 (Why is no real title available?)
• scientific article; zbMATH DE number 3460351 (Why is no real title available?)
• scientific article; zbMATH DE number 3533996 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• Log Depth Circuits for Division and Related Problems
• On the deterministic complexity of factoring polynomials over finite fields
• On the distribution of running times of certain integer factoring algorithms
• Sums of Divisors, Perfect Numbers and Factoring

Cited in

(13)

• Perfect power testing
• The complexity of number-theoretic constants
• Fast generation of prime numbers and secure public-key cryptographic parameters.
• An algorithm to compute integer th roots using subtractions
• Lucas-Lehmer primality tests for certain prime curios
• Detecting perfect powers by factoring into coprimes
• Detecting perfect powers in essentially linear time
• A characterization of nonprime powers
• Some results on pseudosquares
• Detecting square numbers
• Improvements on non-interactive zero-knowledge proof systems related to quadratic residuosity languages
• Efficiently certifying non-integer powers
• Detecting lacunary perfect powers and computing their roots

This page was built for publication: Sieve algorithms for perfect power testing

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