Prime Power Predicate

March 13, 2015

In today’s exercise we write a function that determines if a number n can be written as p^k 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(aⁿ − 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.

Posted by programmingpraxis

Filed in Exercises

1 Comment »

One Response to “Prime Power Predicate”

Krishnan R said

April 8, 2015 at 7:37 PM

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;
	}
}

Programming Praxis