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(an − a, 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.
Programming Praxis 
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; } }