Miller Rabin - Error probability of .5 a possibility?

Question

I'm testing the property of Miller Rabin that the error probability is at most 1/4 when only a single base a is chosen and we iterate only one time. We are testing odd integers 90,000 to 100,000.

I've written up the implementation in Java and as the test is running, I'm seeing a lot of probabilities of .5. This leads me to believe that there is an issue with my implementation.

Some of the odd integers in which I'm seeing a .5 error probability are: 90007 91571 94343

There are plenty more (the test is still running).

Update: Here is the Algorithm I've implemented

 Miller–Rabin Primality Test
 Input: prime candidate ˜ p with ˜ p−1 = 2ur and security parameter s
 Output: statement “ ˜ p is composite” or “ ˜ p is likely prime”
 Algorithm:
 FORi = 1 TO s
    choose random a ∈ {2,3, . . . , ˜ p−2}
    z ≡ ar mod ˜ p
       IF z ≡ 1 and z ≡ ˜ p−1
          FOR j = 1 TO u−1
             z ≡ z2 mod ˜ p
             IF z = 1
                RETURN (“ ˜ p is composite”)
          IF z = ˜ p−1
             RETURN (“ ˜ p is composite”)
 RETURN (“ ˜ p is likely prime”)

Here is the implementation, if anyone could take a look and determine what the problem is I would really appreciate it.

Thanks

public BigInteger mr(int x, int y){
    int u = 0;
    BigInteger p = BigInteger.valueOf(x);
    BigInteger r = p.subtract(ONE);
    BigInteger a = BigInteger.valueOf(y);

    while (r.mod(TWO).equals(ZERO)){
        u++;
        r = r.divide(TWO);
    }

    BigInteger z = a.modPow(r, p);
    if ((!z.equals(ONE) && !z.equals(p.subtract(ONE)))){
        int j = 1;
        for (; j < u; j++){
            z = z.modPow(TWO, p);
        }
    }
    return z;
}

public boolean isPrime(int n){
    if ( n % 2 == 0)
        return false;

    for (int i = 3; i <= Math.sqrt(n) + 1; i+=2){
        if (n % i == 0)
            return false;
    }
    return true;
}

public static void main(String[] args) {
    double ea;
    MillerRabin mr = new MillerRabin();
    int count = 0;
    BigInteger ans;
    for (int n = 90001; n< 100000; n+=2){
        count = 0;
        for (int a = 1; a < n; a++){
            ans = mr.mr(n, a);
            if (mr.isPrime(ans.intValue())){
                count++;    
            }

        }
        ea = ((double)count) / (n-1);
        System.out.println(ea);
    }
}

Answer 1

The problem is that you got the algorithm wrong. You use it to generate an integer (which is one of 1, $x-1$, or $y^{x-1} \bmod x$, and then say "prime" if that integer is prime.

That's not correct; in fact, the three integers you list (90007 91571 94343) are each prime, and Miller Rabin should always return prime when given a prime.

Instead, the correct implementation of MR should:

• if the initial computation is $y^{(x-1)/2^u}$ is 1 or $x-1$, conclude probably prime.

• do $u-1$ square operations, if the result of any of them is $x-1$, conclude probably prime, if it is 1, conclude "composite"

• if, after the $u-1$ square operations, you never hit $x-1$, conclude "composite"