Sieve algorithms for perfect power testing

DOI10.1007/BF01228507zbMath0771.11049OpenAlexW2061658683MaRDI QIDQ2366224

Jonathan P. Sorenson, Eric Bach

Publication date: 29 June 1993

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01228507

zbMATH Keywords

Newton's methodparallel algorithmsaverage-case analysissieve algorithm

Mathematics Subject Classification ID

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

Related Items (11)

Perfect power testing ⋮ Fast generation of prime numbers and secure public-key cryptographic parameters. ⋮ Improvements on non-interactive zero-knowledge proof systems related to quadratic residuosity languages ⋮ Some results on pseudosquares ⋮ Unnamed Item ⋮ Detecting lacunary perfect powers and computing their roots ⋮ An algorithm to compute integer ηth roots using subtractions ⋮ Detecting perfect powers in essentially linear time ⋮ Detecting square numbers ⋮ Detecting perfect powers by factoring into coprimes ⋮ The complexity of number-theoretic constants

Cites Work

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

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