Implementing a Fast Fourier Transform in a Rabin-Miller Primality test.
I feel like one of those people that calls into a radio station, "Hi, I'm a long time listener, first time caller, my question is..."
I'm an undergraduate CS student working on a program that determines the primality of a number, and opted to use the Rabin-Miller test to check. On Wikipedia (http://en.wikipedia.org/wiki/Rabin-Miller_primality_test#Algorithm_and_running_time) it is mentioned that "FFT-based multiplication can push the running time down to ?k ?log^2 n)" but I can't find any resources online that explain how the FFT applies to multiplication and how it would fit into the algorithm I have already. I know there's methods already present in the API that will test primality, but I'd like to be able to write the code myself. Does anyone happen to have knowledge on this topic or where I can look to for more information?
Just in case, my code thus far is tagged below:
// Evan Senter, CS 20 HW 1, 04/07
// An implementation of the Miller-Rabin Pseudo-Primality Test.
// ************************************************************
// As a note, 3215031751 is the smallest number to falsely
// fail less than 2.5E13 due to no witnesses in the
// set of ints Z {2, 3, 5, 7}.
// The probability of an error is at most 4^(-confidence)
import java.math.BigInteger;
import java.math.BigDecimal;
publicclass BigIntegerPrimalityTest{
BigInteger zero = BigInteger.ZERO;
BigInteger one = BigInteger.ONE;
BigInteger two =new BigInteger("2");
public BigIntegerPrimalityTest(){}// The greatest constructor ever!
publicboolean is_a_prime (String aNumber,int aConfidence){
int powerCount = 0;
int compositeCounter = 0;
int confidence = aConfidence;// confidence = # of randNums to test for primality
BigInteger prime =new BigInteger(aNumber);
BigInteger primeMinusOne =new BigInteger(prime.subtract(one).toString());// prime - 1
BigDecimal doubleprimeM1 =new BigDecimal(primeMinusOne.toString());
BigInteger oddDivisor =new BigInteger(primeMinusOne.toString());
BigInteger randNum, randModPowerified;
if (prime.equals(two))returntrue;// Time management at its best
while ((oddDivisor.mod(two)).equals(zero)){// (2^powerCount)*oddDivisor == prime - 1
oddDivisor = oddDivisor.shiftRight(1);
powerCount++;
}
for (int i = 0; i < confidence; i++){// Repeat for i # of randNums where i = confidence
BigDecimal aRandomDouble =new BigDecimal(Double.toString(Math.random()));
BigDecimal tempRandomDouble =
new BigDecimal(((aRandomDouble.multiply(doubleprimeM1.subtract(BigDecimal.ONE))).add(BigDecimal.ONE)).toString());
randNum =new BigInteger((tempRandomDouble.toBigInteger()).toString());//1 < randNum < prime
randModPowerified =new BigInteger((randNum.modPow(oddDivisor, prime).toString()));// modPow returns y = (a^b)%n
if (randModPowerified.equals(one) ==false && randModPowerified.equals(primeMinusOne) ==false){
int loopCounter = 1;
while (loopCounter < powerCount && randModPowerified.equals(primeMinusOne) ==false){
randModPowerified = randModPowerified.modPow(two, prime);
if (randModPowerified.equals(one)) compositeCounter++;
loopCounter++;
}
if (randModPowerified.equals(primeMinusOne) ==false) compositeCounter++;
}
}
if (compositeCounter > 0)returnfalse;
elsereturntrue;
}
public String primeGenerator(String baseSize){
BigInteger probablePrime =new BigInteger(baseSize);
return (probablePrime.nextProbablePrime()).toString();
}
publicstaticvoid main (String[] console){
int conf = 7;
boolean isPrime =false;
String value ="1";
for (int c = 1; c < 1499; c++) value +="0";
value +="1";
BigIntegerPrimalityTest p =new BigIntegerPrimalityTest();
long time1 = System.currentTimeMillis();
String aPrime = p.primeGenerator(value);
long time2 = System.currentTimeMillis();
long time3 = System.currentTimeMillis();
isPrime = p.is_a_prime(aPrime, conf);
long time4 = System.currentTimeMillis();
System.out.println("The value you are testing for primality is: " +
aPrime +"\nThe length of the value is: " + aPrime.length());
if (isPrime) System.out.println("The value is prime with a total error of at most " + Math.pow(4, -conf));
else System.out.println("The value is composite with a total error of at most " + Math.pow(4, -conf));
System.out.println("The time to generate a prime larger than the input was " + (time2 - time1) +" ms");
System.out.println("The time to search for the value's primality was " + (time4 - time3) +" ms");
}
}
