Miller-Rabin素数测试Java代码实现
时间: 2023-11-24 16:07:30 浏览: 40
以下是一个简单的 Miller-Rabin 算法的 Java 实现,用于测试一个数是否为素数:
```java
import java.math.BigInteger;
import java.util.Random;
public class MillerRabinTest {
/**
* 判断 n 是否为素数
*
* @param n 待判断的大整数
* @param k 测试次数
* @return 如果 n 可能是素数,则返回 true,否则返回 false
*/
public static boolean isPrime(BigInteger n, int k) {
// 如果 n <= 1 或者 n 是偶数,则不是素数
if (n.compareTo(BigInteger.ONE) <= 0 || n.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
return false;
}
// 将 n - 1 表示为 d * 2^r 的形式
BigInteger d = n.subtract(BigInteger.ONE);
int r = 0;
while (d.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
d = d.divide(BigInteger.TWO);
r += 1;
}
// 进行 k 次测试
Random rand = new Random();
for (int i = 0; i < k; 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 prime = 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))) {
prime = true;
break;
}
}
if (!prime) {
return false;
}
}
return true;
}
public static void main(String[] args) {
BigInteger n = new BigInteger("12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789");
int k = 10;
if (isPrime(n, k)) {
System.out.println(n + " is probably prime.");
} else {
System.out.println(n + " is composite.");
}
}
}
```
其中,`isPrime` 方法接受一个大整数 `n` 和一个测试次数 `k`,返回一个布尔值,表示 `n` 是否为素数。该方法使用 Miller-Rabin 算法进行测试。
在 `main` 方法中,我们使用一个 617 位的大整数 `n` 进行测试,测试次数 `k` 设置为 10。如果 `n` 可能是素数,则输出 `"n is probably prime."`,否则输出 `"n is composite."`。