Programming Praxis

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[k² mod 11] ← 1.

2. [Fill 63] For k = 0 to 62 set q63[k] ← 0. Then for k = 0 to 31 set q63[k² mod 63] ← 1.

3. [Fill 64] For k = 0 to 63 set q64[k] ← 0. Then for k = 0 to 31 set q63[k² mod 64] ← 1.

4. [Fill 65] For k = 0 to 64 set q65[k] ← 0. Then for k = 0 to 32 set q63[k² 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 and statement). 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 ≠ q², 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 p^k = n, with p prime. Stephen Wolfram’s Mathematica program implements the prime-power test as PrimePowerQ, which returns either True or False. According to the manual,

The algorithm for PrimePowerQ involves 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[12167], which is True, since 23³ = 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 = p^k, where p is prime. Then Fermat’s Little Theorem gives p | gcd(aⁿ − 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 p^k 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 ← (a^q − 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.

Pages: 1 2