Argonath
Reputation: 63
Miller-Rabin test: impossible result
I was trying to implement the Miller-Rabin primality test on Java and confront its computational time with the native primality test of the BigInteger class. Given that I'm here, you will probably have guessed that my code doesn't work. Problem is, the error I obtain is one that Lady Math says to be impossible. I would like to know what I'm doing wrong.
The idea behind the Miller-Rabin primality test, without much math, is that all primes satisfy a propriety. If that propriety is not satisfied, than the number is composite; if the propriety is satisfied, however, the number may be a prime or it may belong to a subset of the composite number called pseudoprimes. What definitely cannot happen is for a prime number to be recognized by the test as composite.
That is precisely what sometime happens while running my code.
I searched my code for math errors and I think there are none. I tried searching for Java mistakes and I found none. Obviously there is something (or many something) I am not seeing, so I would like to ask for help.
Below is the main of a static class created just to house the implementation of the Miller-Rabin test, which is presented after the main. It is not the probabilistic test, but the deterministic one: the method searches for all possible witnesses and, if one is found, returns false (i.e. not prime); 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" +
// "Written in 2-base: \n\t %s\n" +
"Number of bits of a: %d \n", i,
a.toString(),
// a.toString(2),
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" +
// "Written in 2-base: \n\t %s\n" +
"Number of bits of a: %d \n", i,
a.toString(),
// a.toString(2),
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
);
}
}
/** Tests {@code n} for primality using the <i>Miller-Rabin algorithm</i>.
*
* <p><br> For {@code n} minor than <b>3,825,123,056,546,413,051</b> (i.e. roughtly four millions of millions of millions,
* i.e. 4·10<sup>18</sup>) the test is deterministic and have time complexity of Θ<font size=+1>(</font>10·modPow(·,n)<font size=+1>)</font>.
* <br> For {@code n} greater than <b>3,825,123,056,546,413,051</b> the test is deterministic and have time complexity of
* Θ<font size=+1>(</font>2·log<sub>2</sub><sup>2</sup>(n)·modPow(·,n)<font size=+1>)</font>.
*
* @param n
* @return
*/
public static boolean primalityTest_MillerRabin(BigInteger n){
// If n is divided by 2 or is less than 2, then n is not prime.
if( n.intValue()%2== 0 || n.equals(TWO) )
{
System.out.printf("The number is even.\n");
return false;
}
// n = d*2^s +1
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);
// Old code:
// pMinus1.divide(BigInteger.valueOf(2L << r - 1));
// For some n is known what witness one has to choose in order to verify is n is composite.
// While the code for EVERY known limit is shown, only those not-redundant is not comment.
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) );
// ...otherwise the program does an exaustive search for witness
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;
}
/** Return {@code true} if and only if {@code a} is a witness for the compositeness of {@code n}, i.e. if and only if:
* <ol> n = d·2<sup>s</sup> + 1 <br>
* gcd(a,n) = 1 (i.e. a doesn't divide n) <br>
* _<br>
* a<sup>d</sup> ≠ 1 (mod n) <br>
* a<sup>(d·2^r)</sup> ≠ -1 (mod n) for all rϵ[0,s) </ol>
*
* If the method returns {@code true} then {@code n} is definitely a composite number. However if the method returns {@code false} it
* still may be possible for {@code n} to be composite.
*
* <p>If this method recognize {@code a} as a witness for the compositeness of {@code n}
*
* @param a
* @param n
* @param d
* @param s
* @return
*/
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;
}
}
/** Returns {@code isAWitnessOfCompositenessOfN_MR(TWO, n, d, s)}.
*
* <p><u><b>Warning:</b></u> This method avoids to control if gcd(2, {@code n})=1.
*
* @param n
* @param d
* @param s
* @return
*/
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 the method log(x,base).
/** Returns the logarithm of a number {@code x} in the selected {@code base}.
* <p>
* <b>Time Complexity:</b> Θ(1). <br>
* <b>Space Complexity:</b> Θ(log<sub>10</sub>(x)). <br>
*
* @param x
* @param base
* @return
*/
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);
}
Upvotes: 4
Views: 426
Answers (1)
laune
Reputation: 31300
You have several expressions comparing BigInteger objects using == and !=. This must be replaced by calls to equals, negating the result for !=.
Also, I think that there is a copy-paste error in isAWitnessOfCompositenessOfN_MR:
! dMultiplyTwoPowR.modPow(TWO, n).equals( nMinusOne );
I think that TWO should be replaced by a.
Edit A bug in log. Use the code below:
public static double log(BigInteger x, base b){
String support = x.toString();
int n = support.length();
double log10 = n + Math.log10( Double.parseDouble("0."+support) );
return log10/Math.log10(b);
}
I suppose that there's more errors, but these fixes should help a little.
Upvotes: 1
Related Questions
- Miller Rabin primality test two types?
- Miller-Rabin code runs for extended period for some numbers. Bug?
- Miller-Rabin Scheme implementation unpredictable output
- Miller-Rabin primality test gives wrong answer
- Miller Rabin Primality test in C++ bug?
- Miller-Rabin Primality test in Java
- Miller Rabin Primality test
- Why is my Miller Rabin algorithm not working (Haskell)?
- Miller-Rabin primality test issue in C++
- Stackoverflow exception while testing Miller Rabin