## Two Powering Predicates

### 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 setq11[k] ← 0. Then fork= 0 to 5 setq11[k^{2}mod 11] ← 1.2. [Fill 63] For

k= 0 to 62 setq63[k] ← 0. Then fork= 0 to 31 setq63[k^{2}mod 63] ← 1.3. [Fill 64] For

k= 0 to 63 setq64[k] ← 0. Then fork= 0 to 31 setq63[k^{2}mod 64] ← 1.4. [Fill 65] For

k= 0 to 64 setq65[k] ← 0. Then fork= 0 to 32 setq63[k^{2}mod 65] ← 1.

Then the algorithm is:

Given a positive integer

n, this algorithm determines whethernis a square or not, and if it is, outputs the square root ofn.1. [Test 64] Set

t←nmod 64 (using if possible only an`and`

statement). Ifq64[t] = 0,nis not a square and terminate the algorithm. Otherwise, setr=nmod 45045.2. [Test 63] If

q63[rmod 63] = 0,nis not a square and terminate the algorithm.3. [Test 65] If

q65[rmod 65] = 0,nis not a square and terminate the algorithm.4. [Test 11] If

q11[rmod 11] = 0,nis not a square and terminate the algorithm.5. [Compute square root] Compute

q← ⌊ √n⌋ using Newton’s method. Ifn≠q^{2},nis not a square and terminate the algorithm. Otherwise,nis a square, outputqand 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 factorpofnand then attempting division bynuntil either 1 is obtained, in which casenis a prime power, or until division is no longer possible, in which casenis not a prime power.

(Note: they probably meant “attempting division by *p*.”) Wolfram gives the example `PrimePowerQ[12167]`

, which is `True`

, since 23^{3} = 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*−

^{n}*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 notnis of the formpwith^{k}pprime, and if it is, outputs the primep.1. [Case

neven] Ifnis even, setp← 2 and go to Step 4. Otherwise, setq←n.2. [Apply Rabin-Miller] By using Algorithm 8.2.2 show that either

qis a probable prime or exhibit a witnessato the compositeness ofq. Ifqis a probable prime, setp←qand go to Step 4.3. [Compute GCD] Set

d← (a−^{q}a,q). Ifd= 1 ord=q, thennis not a prime power and terminate the algorithm. Otherwise setq←dand go to Step 2.4. [Final test] (Here

pis a divisor ofnwhich is almost certainly prime.) Using a primality test prove thatpis prime. If it is not (an exceedingly rare occurrence), setq←pand go to Step 2. Otherwise, by dividingnbyprepeatedly, check whethernis a power ofpor not. If it is not,nis not a prime power, otherwise outputp. Terminate the algorithm.We have been a little sloppy in this algorithm. For example in Step 4, instead of repeatedly dividing by

pwe 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.