Miller-Rabin素数测试Java代码实现

下面是一个简单的Miller-Rabin素数测试的Java代码实现：

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

public class MillerRabinPrimeTest {
    
    private static final int CERTAINTY = 10; // 检测次数，值越大越准确
    
    public static boolean isPrime(BigInteger n) {
        if (n.compareTo(BigInteger.ONE) == 0 || n.compareTo(BigInteger.valueOf(2)) == 0) {
            return true;
        }
        if (n.compareTo(BigInteger.valueOf(2)) < 0 || n.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
            return false;
        }
        int r = 0;
        BigInteger d = n.subtract(BigInteger.ONE);
        while (d.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
            d = d.divide(BigInteger.valueOf(2));
            r++;
        }
        Random rand = new Random();
        for (int i = 0; i < CERTAINTY; i++) {
            BigInteger a = new BigInteger(n.bitLength() - 1, rand).add(BigInteger.ONE);
            BigInteger x = a.modPow(d, n);
            if (x.equals(BigInteger.ONE) || x.equals(n.subtract(BigInteger.ONE))) {
                continue;
            }
            boolean isPrime = false;
            for (int j = 0; j < r - 1; j++) {
                x = x.modPow(BigInteger.valueOf(2), n);
                if (x.equals(BigInteger.ONE)) {
                    return false;
                }
                if (x.equals(n.subtract(BigInteger.ONE))) {
                    isPrime = true;
                    break;
                }
            }
            if (!isPrime) {
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        BigInteger n = new BigInteger("123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100");
        if (isPrime(n)) {
            System.out.println(n + " is a prime number.");
        } else {
            System.out.println(n + " is not a prime number.");
        }
    }
}

该示例代码使用了Java的BigInteger类来处理大数运算，实现了Miller-Rabin素数测试算法。代码中的isPrime()方法接收一个BigInteger类型的参数n，返回一个布尔值，用于判断n是否为素数。该方法的实现过程如下：

1. 如果n等于1或2，则返回true，因为1和2都是素数；
2. 如果n小于2或为偶数，则返回false，因为素数必须大于等于2且不能是偶数；
3. 计算$d=\frac{n-1}{2^r}$，其中$r$为一个正整数，$d$为一个奇数；
4. 对于$CERTAINTY$次循环，每次循环中，随机生成一个大于1且小于$n$的整数$a$，计算$x=a^d\mod n$；
5. 如果$x=1$或$x=n-1$，则跳过本次循环；
6. 对于$j=1$到$j=r-1$，计算$x=x^2\mod n$；
- 如果$x=1$，则$n$不是素数，返回false；
- 如果$x=n-1$，则跳过本次循环；
7. 如果以上循环中都没有返回false，则$n$很可能为素数，返回true。

在代码中，$CERTAINTY$的值设为10，这意味着进行10次Miller-Rabin测试，可以得到一个非常高的准确率。如果需要更高的准确率，可以增加$CERTAINTY$的值。