CODEWITHSUNDEEP
javaprimesnumber-theory
Juan Sebastian Lozano
Juan Sebastian Lozano

Reputation: 473

Miller-Rabin Primality test in Java

I am currently working on Project Euler and thought that it might be more interesting (and a better learning experience) if don't just brute force all of the questions. On question 3 it asks for prime factors of a number and my solution will be to factor the number (using another factoring algorithm) and then test the factors for primality. I came up with this code for a Miller-Rabin Primality test (after thoroughly researching primality test) and it returns true for all the composite odd number I have put in. Can anybody help me to figure out why? I thought I had coded the algorithm correctly.

    public static boolean isPrime(long num)
{
if(num % 2 == 0)
    return false;
else
{
    double d;
    int r=0;
    while((num-1) % Math.pow(2,r+1) == 0)
        r++;
    d = (num-1) % Math.pow(2,r);
    int[] a = {2,3,5,7,11,13,17,23,31,62,73,1662803};
    boolean primality = true;
    for(int k = 0; k < a.length; k++)
    {
        if((Math.pow(a[k],d)-1) % num != 0)
        {
            for(int s = 0; s < r-1; s++)
            {
                if((Math.pow(a[k],Math.pow(2,s)*d)+1) % num != 0)
                    primality = false;

            }
        }
    }
    return primality;
}

Upvotes: 3

Views: 6425

Answers (1)

Brett Hale
Brett Hale

Reputation: 22328

Given num > 3, you want: d, r s.t. pow(2,r) * d = num - 1, where d is odd.

You are effectively counting trailing zeroes from num - 1, to remove factors of 2. However, after that loop, you know pow(2,r) is a factor of num - 1. Hence: 

d = (num-1) % Math.pow(2,r);

will always yield: d = 0. I suspect you meant to replace % (mod) with / (div) here; otherwise, Math.pow(a[k],d)-1 will always yield (0), and the inner loop will never be executed.

As others pointed out, some simple trace statements or assertions would have found these errors. I think you have other issues, such as integer overflow. The loop for testing against the a[] candidates (the a-SPRP test) looks completely wrong to me.

Perhaps you've got the algorithm from Wikipedia, I prefer the more detailed reference in The Handbook of Applied Cryptography: 4.2.3: Miller-Rabin test, Algorithm: 4.24.

Upvotes: 4

Related Questions