# Miller Rabin - Error probability of .5 a possibility?

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

• If u=1 then your initial for loop will execute 0 times. ​ ​ – user991 Nov 24 '15 at 1:31
• @RickyDemer The algorithm states for j=1 to u-1. Is that not what I did? – Talen Kylon Nov 24 '15 at 1:34
• Huh, that does confuse me about the algorithm. ​ ​ – user991 Nov 24 '15 at 1:37
• I've included the algorithm from the text book @RickyDemer – Talen Kylon Nov 24 '15 at 1:41

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.
• 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"