Miller-Rabin won't work: problem with the base and the exponent

Question

I'm using strong known bases {2, 7, 61} to solve Miller-Rabin. Assume I take a = 2 in this piece of code and n = 5 to test its primality. The factorization of n-1, so 4, is 2*2*1 so my m is 1. If I test 2^1 = x mod 5, I of course get 2, which will make my Miller-Rabin test fail even if 5 is prime.

while(m > 0) {
        if(m%2 == 0) {
            pow *= a*a;
            pow %= n;
            m -= 2;
        }

        else {
            pow *= a;
            pow %= n;
            m -= 1;
        }
    }

    if(miller_rabin_single_base(pow, n) == 0) {
        return 0;
    }

...

The method I call at the end just checks if pow%n = 1 or n-1.

I can't understand if I misunderstood Miller-Rabin algorithm, or if there's some problem in the code. The code works with some primes only.

I'm also a C neophyte so I apologise if the error was just given by a bad coding.

Update:

declaration of the the single_base method:

int miller_rabin_single_base(int16 a, int16 n) {
    if(a%n == n-1 || a%n == 1) {
        return 1;
    }

    else {
        return 0;
    }
}

declaration of m and pow:

int16 nmu = n-1;
int16 m;
int16 k = 0;
while((nmu/2)%2 == 0) {
    k++;
    nmu = nmu/2;
}

m = nmu/2;
k++;

int16 pow = 1;

int16 is an unsigned short, I'm using it to test.

The n is an unsigned short number chosen by anyone who can run the code.

If I test for n = 5, 13 or 29 I get it is not prime, but If I test 7, 11 or 31 I get it's prime:

./p_test miller 17
composite number

./p_test miller 23
prime number

Answer 1

You've left out half of M-R. Given witness a=2 and n=5 with n-1=4 decomposed to 2²·1 you need to:

• compute a¹ mod n = 2 and compare to 1 and n-1 (-1 mod n); if equal to either this witness would say prime and you advance to the next witness, but it is not, and you had more than one factor of 2 in n-1, so keep going

• compute a^1·2 mod n = 4 and compare to n-1 (only, not 1); it is equal, so this witness says prime; in general you would advance to the next witness (or if no more declare n probably prime). If it were not equal, since you have reached k-1=1 factors of 2, you declare n composite and stop, but for n-1 values containing more factors of 2 you would iterate this step multiple times.

In this case, your other witnessess are unnecessary; 7 mod 5 = 2 so it produces exactly the same result, and 61 mod 5 = 1 and 1 as a witness says every number is prime, which is useless. For a more realistic (larger) n, they would be useful.

Note computing a^m, a^m·2, a^m·2·2, a^m·2·2·2, etc all mod n can be done more efficiently by first computing x = a^m mod n then repeatedly computing x = x² mod n .

See example in wikipedia (although they use different variable names).