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

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

%d bloggers like this: