I tried to implement the Miller-Rabin primitiveness test in Java and withstand its computational time using the class native primality test BigInteger. Given that I'm here, you probably guessed that my code was not working. The problem is that the error I get is that Lady Math says that this is not possible. I would like to know what I am doing wrong.
The idea of the Miller-Rabin primitive test, without much math, is that all primes satisfy decency. If this relevance is not satisfied, then the number is composite; however, if satisfaction is satisfied, the number may be simple, or it may belong to a subset of a composite number called pseudo-crimes. What definitely cannot be is a prime number that will be recognized as compound by the test. This is exactly what ever happens when running my code.
I was looking for my code for math errors, and I think there are none. I tried to find Java errors and I did not find them. Obviously, there is something (or a lot of something) that I do not see, so I would like to ask for help.
The following is a mainstatic class created only to host the implementation of the Miller-Rabin test, which is presented after main. This is not a probabilistic test, but deterministic: the method searches for all possible witnesses and, if it is found, returns false(that is, not easy); otherwise it returns true.
public static void main(String[] args) {
long start;
Random random = new Random();
int N = Integer.parseInt("10");
BigInteger a,b,c,d;
long stopMR, stopNative;
boolean answerMR, answerNative;
for(int i=0 ; i<6 ; i++, N*=3)
{
a = new BigInteger(N, random);
System.out.printf("\tTEST %d\n\nThe number to be checked is: \n\t %s\n" +
"Number of bits of a: %d \n", i,
a.toString(),
a.toString(2).length());
start = System.nanoTime();
answerMR = primalityTest_MillerRabin(a);
stopMR = System.nanoTime();
stopMR -= start;
start = System.nanoTime();
answerNative = a.isProbablePrime(40);
stopNative = System.nanoTime();
stopNative -= start;
System.out.printf("The test of Miller-Rabin said that the number %s.\n"
+ "The native test said that the number %s.\n"
+ "The time of MR is %d.\n"
+ "The time of the native is %d.\n"
+ "The difference Time(MR)-Time(native) is %d.\n",
answerMR ? "is prime" : "isn't prime" ,
answerNative ? "is prime" : "isn't prime" ,
stopMR, stopNative, stopMR - stopNative
);
a = BigInteger.probablePrime(N, random);
System.out.printf("\tTEST %d\n\nThe number to be checked is: \n\t %s\n" +
"Number of bits of a: %d \n", i,
a.toString(),
a.toString(2).length());
start = System.nanoTime();
answerMR = primalityTest_MillerRabin(a);
stopMR = System.nanoTime();
stopMR -= start;
start = System.nanoTime();
answerNative = a.isProbablePrime(40);
stopNative = System.nanoTime();
stopNative -= start;
System.out.printf("The test of Miller-Rabin said that the number %s.\n"
+ "The native test said that the number %s.\n"
+ "The time of MR is %d.\n"
+ "The time of the native is %d.\n"
+ "The difference Time(MR)-Time(native) is %d.\n=====\n",
answerMR ? "is prime" : "isn't prime" ,
answerNative ? "is prime" : "isn't prime" ,
stopMR, stopNative, stopMR - stopNative
);
}
}
public static boolean primalityTest_MillerRabin(BigInteger n){
if( n.intValue()%2== 0 || n.equals(TWO) )
{
System.out.printf("The number is even.\n");
return false;
}
BigInteger pMinus1 = n.subtract(ONE);
int s = 0;
while (pMinus1.mod(TWO).equals(ZERO))
{
s++;
pMinus1 = pMinus1.divide(TWO);
}
BigInteger d = pMinus1;
System.out.printf("%s is %s*2^%d+1.\n", n.toString(), d.toString(),s);
if(n.compareTo(LIMIT_2047)<0)
return ! isTWOWitnessOfCompositenessOfN_MR( n, d, s) ;
if(n.compareTo(LIMIT_9080191)<0)
return ! (
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(31) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(73) , n, d, s) );
if(n.compareTo(LIMIT_4759123141)<0)
return ! (
isTWOWitnessOfCompositenessOfN_MR( n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(7) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(61) , n, d, s) );
if(n.compareTo(LIMIT_1122004669633)<0)
return ! (
isTWOWitnessOfCompositenessOfN_MR( n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(13) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(23) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(1662803) , n, d, s) );
if(n.compareTo(LIMIT_2152302898747)<0)
return ! (
isTWOWitnessOfCompositenessOfN_MR( n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(3) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(5) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(7) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(11) , n, d, s) );
if(n.compareTo(LIMIT_3474749660383)<0)
return ! (
isTWOWitnessOfCompositenessOfN_MR( n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(3) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(5) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(7) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(11) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(13) , n, d, s) );
if(n.compareTo(LIMIT_341550071728321)<0)
return ! (
isTWOWitnessOfCompositenessOfN_MR( n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(3) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(5) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(7) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(11) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(13) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(17) , n, d, s) );
if(n.compareTo(LIMIT_3825123056546413051)<0)
return ! (
isTWOWitnessOfCompositenessOfN_MR( n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(3) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(5) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(7) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(11) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(13) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(17) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(19) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(23) , n, d, s) );
System.out.printf("The Miller-Rabin Test has no shortcuts.\n");
boolean witnessFound = false;
int logn = (int) log(n,2) +1;
BigInteger limit = ( n.subtract(ONE) ).min( BigInteger.valueOf(2*logn*logn) );
for(BigInteger a = TWO ; witnessFound && a.compareTo(limit)<=0 ; a.add(ONE))
witnessFound = isAWitnessOfCompositenessOfN_MR( a , n, d, s);
return !witnessFound;
}
public static boolean isAWitnessOfCompositenessOfN_MR(BigInteger a, BigInteger n, BigInteger d, int s){
System.out.printf("\t Verifying if %s is a witness of the compositness of %s.\n", a.toString(), n.toString());
if( a.gcd(n) == ONE )
{
BigInteger dMultiplyTwoPowR = a.modPow(d, n),
nMinusOne = NEGATIVE_ONE.mod(n);
boolean answer = dMultiplyTwoPowR != ONE;
for(int r=1 ; answer && r<s ; r++)
{
System.out.printf("\t\t Testing r=%d.\n", r);
answer = answer &&
dMultiplyTwoPowR.modPow(TWO, n) != nMinusOne;
}
System.out.printf("\t The number %s %s a witness of the compositness of %s.\n", a.toString(), answer ? "is" : "isn't", n.toString());
return answer;
}
else
{
System.out.printf("\t %s divides %s.\n", a.toString(), n.toString());
return true;
}
}
public static boolean isTWOWitnessOfCompositenessOfN_MR( BigInteger n, BigInteger d, int s){
System.out.printf("\t Verifying if 2 is a witness of the compositness of %s.\n", n.toString());
BigInteger dMultiplyTwoPowR = TWO.modPow(d, n),
nMinusOne = NEGATIVE_ONE.mod(n);
boolean answer = dMultiplyTwoPowR != ONE;
for(int r=1 ; answer && r<s ; r++)
{
System.out.printf("\t\t Testing r=%d.\n", r);
answer = answer &&
dMultiplyTwoPowR.modPow(TWO, n) != nMinusOne;
}
System.out.printf("\t The number 2 %s a witness of the compositness of %s.\n", answer ? "is" : "isn't", n.toString());
return answer;
}
Edit: The following lines are a method log(x,base).
public static double log(BigInteger x, float base){
String support = x.toString();
int n = support.length();
double log10 = n + Float.parseFloat("0."+support);
if(base==10) return log10;
else return log10 / Math.log10(base);
}