Return to Question

added 632 characters in body

Source Link

edited Nov 24, 2015 at 1:41

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.

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.

Source Link

asked Nov 24, 2015 at 1:21

Talen Kylon

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).

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

prime-numbers