August 6, 2010
In our study of prime numbers, we have sometimes been lax in specifying the limitations of particular factoring methods; for instance, elliptic curve factorization only works where the number being factored is co-prime to six. Two conditions that arise from time to time are that the number must not be a perfect square and that the number may not be an integer power of a prime number. In today’s exercise we will write predicates to identify such numbers.
The usual test for whether a number is a perfect square is to find the integer square root by Newton’s method and then test if the square of that number is the original number. A better algorithm exploits a theorem of number theory which states that a number is a square if and only if it is a quadratic residue modulo every prime not dividing it. Henri Cohen, in his book A Course in Computational Algebraic Number Theory, describes the algorithm:
The following computations are to be done and stored once and for all.
1. [Fill 11] For k = 0 to 10 set q11[k] ← 0. Then for k = 0 to 5 set q11[k2 mod 11] ← 1.
2. [Fill 63] For k = 0 to 62 set q63[k] ← 0. Then for k = 0 to 31 set q63[k2 mod 63] ← 1.
3. [Fill 64] For k = 0 to 63 set q64[k] ← 0. Then for k = 0 to 31 set q63[k2 mod 64] ← 1.
4. [Fill 65] For k = 0 to 64 set q65[k] ← 0. Then for k = 0 to 32 set q63[k2 mod 65] ← 1.
Then the algorithm is:
Given a positive integer n, this algorithm determines whether n is a square or not, and if it is, outputs the square root of n.
1. [Test 64] Set t ← n mod 64 (using if possible only an
andstatement). If q64[t] = 0, n is not a square and terminate the algorithm. Otherwise, set r = n mod 45045.
2. [Test 63] If q63[r mod 63] = 0, n is not a square and terminate the algorithm.
3. [Test 65] If q65[r mod 65] = 0, n is not a square and terminate the algorithm.
4. [Test 11] If q11[r mod 11] = 0, n is not a square and terminate the algorithm.
5. [Compute square root] Compute q ← ⌊ √ n ⌋ using Newton’s method. If n ≠ q2, n is not a square and terminate the algorithm. Otherwise, n is a square, output q and terminate the algorithm.
Our second predicate is the prime-power test, which determines, for a given n, if there exist two numbers p and k such that pk = n, with p prime. Stephen Wolfram’s Mathematica program implements the prime-power test as
PrimePowerQ, which returns either
False. According to the manual,
The algorithm for
PrimePowerQinvolves first computing the least prime factor p of n and then attempting division by n until either 1 is obtained, in which case n is a prime power, or until division is no longer possible, in which case n is not a prime power.
(Note: they probably meant “attempting division by p.”) Wolfram gives the example
PrimePowerQ, which is
True, since 233 = 12167. That algorithm will take a while, as factoring is a non-trivial problem.
Cohen determines if n is a prime power by first assuming that n = pk, where p is prime. Then Fermat’s Little Theorem gives p | gcd(an − a, n). If that fails, n is not a prime power. Here is Cohen’s algorithm:
Given a positive integer n > 1, this algorithm tests whether or not n is of the form pk with p prime, and if it is, outputs the prime p.
1. [Case n even] If n is even, set p ← 2 and go to Step 4. Otherwise, set q ← n.
2. [Apply Rabin-Miller] By using Algorithm 8.2.2 show that either q is a probable prime or exhibit a witness a to the compositeness of q. If q is a probable prime, set p ← q and go to Step 4.
3. [Compute GCD] Set d ← (aq − a, q). If d = 1 or d = q, then n is not a prime power and terminate the algorithm. Otherwise set q ← d and go to Step 2.
4. [Final test] (Here p is a divisor of n which is almost certainly prime.) Using a primality test prove that p is prime. If it is not (an exceedingly rare occurrence), set q ← p and go to Step 2. Otherwise, by dividing n by p repeatedly, check whether n is a power of p or not. If it is not, n is not a prime power, otherwise output p. Terminate the algorithm.
We have been a little sloppy in this algorithm. For example in Step 4, instead of repeatedly dividing by p we could use a binary search analogous to the binary powering algorithm. We leave this as an exercise for the reader.
Cohen’s Algorithm 8.2.2 refers to the search for a witness to the compositeness of a number which we used in the exercise on the Miller-Rabin primality checker.
These two beautiful algorithms show the power and elegance of number theory. Cohen’s book is a fine example of the blend of mathematics and programming, and does an excellent job of explaining algorithms in a way that makes them easy to implement; most math textbooks aren’t so good.
Your task is to implement Cohen’s two powering predicates. 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.