GNU Info

(gmp.info)Perfect Power Algorithm

---

Prev: Perfect Square Algorithm Up: Root Extraction Algorithms

---

Enter node , (file) or (file)node

Perfect Power
-------------

   Detecting perfect powers is required by some factorization
algorithms.  Currently `mpz_perfect_power_p' is implemented using
repeated Nth root extractions, though naturally only prime roots need
to be considered.  (Note: Nth Root Algorithm.)

   If a prime divisor p with multiplicity e can be found, then only
roots which are divisors of e need to be considered, much reducing the
work necessary.  To this end divisibility by a set of small primes is
checked.