0
$\begingroup$

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);
    }
}
$\endgroup$
  • $\begingroup$ If u=1 then your initial for loop will execute 0 times. ​ ​ $\endgroup$ – user991 Nov 24 '15 at 1:31
  • $\begingroup$ @RickyDemer The algorithm states for j=1 to u-1. Is that not what I did? $\endgroup$ – Talen Kylon Nov 24 '15 at 1:34
  • $\begingroup$ Huh, that does confuse me about the algorithm. ​ ​ $\endgroup$ – user991 Nov 24 '15 at 1:37
  • $\begingroup$ I've included the algorithm from the text book @RickyDemer $\endgroup$ – Talen Kylon Nov 24 '15 at 1:41
2
$\begingroup$

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"

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.