Prime Power Predicate

March 13, 2015

In today’s exercise we write a function that determines if a number n can be written as pk 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(ana, 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

One Response to “Prime Power Predicate”

1. Krishnan R said

Port of the given python code to Java:

However this solution has two drawbacks:
1) The input is of type “long”, so it cannot compute for big numbers like 1940255363782247**37
2) It does *not* compute logarithm by binary search but by repeated division only.

I am working on the proper solution with these drawbacks addressed. I will post it if and when i crack it :)

randLong method is copied shamelessly from http://stackoverflow.com/a/2546186

```package com.experiment;

import java.math.BigInteger;
import java.util.Random;

public class MillerRabinPrimTestFinal {

public static void main(String[] args) {
//System.out.println(findWitness(1940255363782247L));
primePower(7L);
primePower(25L);
primePower(271818611107L);
primePower(505447028499293771L);
}

private static long findWitness(long n) {
long d = n-1;
int s=0;
long a, x;
BigInteger xb;
Random rng = new Random();
int k = 5;

while(d%2==0) {
s = s+1;
d = d/2;
}

witnessloop:
for(int i=0;i<k;i++) {
a = randLong(rng, 2L, n-2);
x = new BigInteger(String.valueOf(a)).modPow(new BigInteger(String.valueOf(d)), new BigInteger(String.valueOf(n))).longValue();
if(x == 1 || x == (n-1)) continue;
for(int r=1;r<=s;r++) {
xb = new BigInteger(String.valueOf(x));
xb = xb.multiply(xb).mod(new BigInteger(String.valueOf(n)));
x = xb.longValue();
if(x == 1) return a;
if(x == (n-1)) continue witnessloop;
}
return a;
}
return 0L;
}

private static void checkP(long n, long p) {
int k = 0;
while(n>1 && n%p == 0) {
n = n/p;
k = k+1;
}
if(n==1) {
System.out.println(p+","+k);
} else {
System.out.println("0,0");
}
}

private static void primePower(long n) {
if(n%2 == 0) {
checkP(n, 2L);
return;
}
long q = n;
while (true) {
long a = findWitness(q);
if (a == 0) {
checkP(n, q);
return;
}
BigInteger ab = new BigInteger(String.valueOf(a));
BigInteger qb = new BigInteger(String.valueOf(q));
long d = ab.modPow(qb, new BigInteger(String.valueOf(n)))
.subtract(ab).gcd(qb).longValue();
if (d == 1 || d == q) {
System.out.println("0,0");
}
q = d;
}
}

private static long randLong(Random rng, long min, long max) {
long bits, val;

do {
bits = (rng.nextLong() << 1) >>> 1;
val = bits % max;
} while(bits-val+(max-1) < min);

return val;
}
}
```