/*
* PrefactoredRandom.java
*
*/
import java.math.*;
import java.util.*;
import java.io.*;
/**
* Generate a uniformly random number in [1,n] such that n is prefactored
* As described by Adam Kalai in
* http://www.cc.gatech.edu/~atk/papers/old_papers/factorcryptology.pdf
*
* @author Reza Bosagh Zadeh
*/
public class PrefactoredRandom {
public final static int CERTAINTY = 10;
protected static Random RANDOM = new Random();
// Generates a random integer in [min, max]
public static BigInteger random(BigInteger min, BigInteger max) {
if(max.compareTo(min) < 0) {
BigInteger tmp = min;
min = max;
max = tmp;
} else if (max.compareTo(min) == 0) {
return min;
}
max = max.add(BigInteger.ONE);
BigInteger range = max.subtract(min);
int length = range.bitLength();
BigInteger result = new BigInteger(length, RANDOM);
while(result.compareTo(range) >= 0) {
result = new BigInteger(length, RANDOM);
}
result = result.add(min);
return result;
}
// Get a random number in [1,n], in factored form
public static Vector<BigInteger> GenerateRandom(BigInteger n) {
Vector<BigInteger> ret = new Vector<BigInteger>();
while(true) {
ret.clear();
BigInteger r = BigInteger.ONE;
BigInteger s = n;
while(s.compareTo(BigInteger.ONE) > 0) {
s = random(BigInteger.ONE, s);
if(s.isProbablePrime(CERTAINTY)) {
ret.add(s);
r = r.multiply(s);
}
}
// If r<=n, then accept with probability r/n
if(r.compareTo(n) <= 0 && random(BigInteger.ONE, n).compareTo(r) <= 0)
return ret;
}
}
public static void main(String[] args) {
BigInteger n = new BigInteger(args[0]);
System.out.println("Generating a random number in [1," + n + "]");
Vector<BigInteger> ret = PrefactoredRandom.GenerateRandom(n);
BigInteger r = BigInteger.ONE;
System.out.println("Here are the factors of a uniform random number in the requested range");
for(int i = 0; i < ret.size(); i++){
System.out.println(ret.get(i));
r = r.multiply(ret.get(i));
}
System.out.println("Final number is: " + r);
}
}
|