Miller-Rabin Primality test in Java

Question

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;
}

Feast

Did you try tracing the code? – Menorah

This doesn't relate to your code, and I don't claim much expertise, but "factoring the number (using another factoring algorithm)" is a harder problem then identifying primes. You can avoid brute-forcing the factorization by getting a list of primes. The easiest way to get a list of primes (as apposed to testing one) is to use a sieve. – Adelaideadelaja

Math.pow(a[k],d)-1) % num -- i'd say your doubles are way over the range where they can represent every integer in that range. – Menorah

@JanDvorak: Makes a great point. You should look into replacing the use of long with the BigInteger class. – Nomography

I'm not sure what tracing the code means. As to the sieve vs. my method: I agree, it would be more efficient, and I actually have a sieve method written, but this solution was attractive not because of efficiency but because to use it I had to explore some number theory and modular arithmetic, which is teaching me a lot more than a sieve implementation. @ Jan: Okay, but even with small values (22, for example) it returns prime... But yes, I agree this could be a problem. – Feast

@JuanSebastianLozanoMuñoz: 22? That sounds very strange. I would expect the first if-condition to catch that. Are you sure you're calling the correct function? – Nomography

I'm sorry, I meant 25 :P – Feast

Shouldn't while(num % Math.pow(2,r+1) == 0) be while((num-1) % Math.pow(2,r+1) == 0) or better still (for my eyes) while((num-1) % (1<<r+1) == 0) And then d = ((num-1) % (1<<r)); – Adelaideadelaja

Thank you for that correction :) However, it does not change the outcome of the program. – Feast

"It might be more interesting if don't just brute force all of the questions" : you wouldn't go far anyway if you stick to this approach ! – Thorium

That is fair... but like I said above, I don't mean "do the most efficient way" I mean "Do the way that I would learn the most". Simply dividing the number by all the natural numbers below it and checking those that are factors by doing the same wouldn't be efficient or teach me anything. – Feast

Answer 1

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.

Hang

Thank you for this very informative answer :) I will look into the resources you provided, as they seem extremely useful, and next time will be more careful to use trace statements (now that I know what those are). – Feast

@JuanSebastianLozanoMuñoz - since you're going through the Project Euler problems, I thought you might find an efficient Miller-Rabin test useful, so I have snippet for you here. – Hang

Wow, thank you so much :) That will definitely help me on my way through the PE problems. – Feast