miller rabin素数测试Java代码实现

以下是 Miller-Rabin 素数测试的 Java 代码实现：

import java.math.BigInteger;
import java.util.Random;

public class MillerRabin {
    
    private static final int CERTAINTY = 50; // 确定性
    
    public static boolean isPrime(BigInteger n) {
        if (n.compareTo(BigInteger.ONE) == 0 || n.compareTo(BigInteger.TWO) == 0) {
            return true;
        }
        if (n.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
            return false;
        }
        BigInteger d = n.subtract(BigInteger.ONE);
        int r = 0;
        while (d.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
            r++;
            d = d.divide(BigInteger.TWO);
        }
        for (int i = 0; i < CERTAINTY; i++) {
            BigInteger a = getRandom(n.subtract(BigInteger.TWO)).add(BigInteger.ONE);
            BigInteger x = a.modPow(d, n);
            if (x.equals(BigInteger.ONE) || x.equals(n.subtract(BigInteger.ONE))) {
                continue;
            }
            boolean flag = false;
            for (int j = 0; j < r - 1; j++) {
                x = x.modPow(BigInteger.TWO, n);
                if (x.equals(BigInteger.ONE)) {
                    return false;
                }
                if (x.equals(n.subtract(BigInteger.ONE))) {
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                return false;
            }
        }
        return true;
    }
    
    private static BigInteger getRandom(BigInteger n) {
        Random rnd = new Random();
        BigInteger result = new BigInteger(n.bitLength(), rnd);
        while (result.compareTo(n) >= 0) {
            result = new BigInteger(n.bitLength(), rnd);
        }
        return result;
    }
    
}

其中，`isPrime` 方法接收一个 `BigInteger` 类型的数值作为输入，返回一个布尔值，表示输入的数值是否为素数。`CERTAINTY` 常量表示测试的确定性，即测试的正确率。一般来说，50 次测试足够保证正确性。