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 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 tn 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 nq2, 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 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 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(ana, 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 qn.

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 pq and go to Step 4.

3. [Compute GCD] Set d ← (aqa, q). If d = 1 or d = q, then n is not a prime power and terminate the algorithm. Otherwise set qd 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 qp 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.

About these ads

Pages: 1 2

One Response to “Two Powering Predicates”

  1. programmingpraxis said

    Something went wrong during editing of the exercise, and the code given for the square? function was incorrect. It has now been fixed.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 632 other followers

%d bloggers like this: