Programming Praxis

In today’s exercise we write a function that determines if a number n can be written as p^k with p prime and k > 0 an integer. We looked at this function in a previous exercise where we tested each prime exponent up to the base-2 logarithm of n.

Henri Cohen describes a better way to make that determination in Algorithm 1.7.5 of his book A Course in Computational Algebraic Number Theory. He exploits Fermat’s Little Theorem and the witness to the compositeness of n that is found by the Miller-Rabin primality tester. Cohen proves that if a is a witness to the compositeness of n, in the sense of the Miller-Rabin test, then gcd(aⁿ − a, n) is a non-trivial divisor of n (that is, it is between 1 and n).

Your task is to write a program that determines if a number can be written as a prime power and, if so, returns both the prime and the exponent. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2