谁愿意帮我做作业?
我正在尝试实现 Fermat's primality test在 Java 中使用 BigIntegers。我的实现如下,但不幸的是它不起作用。有什么想法吗?
public static boolean checkPrime(BigInteger n, int maxIterations)
{
if (n.equals(BigInteger.ONE))
return false;
BigInteger a;
Random rand = new Random();
for (int i = 0; i < maxIterations; i++)
{
a = new BigInteger(n.bitLength() - 1, rand);
a = a.modPow(n.subtract(BigInteger.ONE), n);
if (!a.equals(BigInteger.ONE))
return false;
}
return true;
}
我是 BigIntegers 新手。
谢谢!
最佳答案
您对特定 BigInteger 构造函数的使用是合理的,但您应该使用 rejection method选择费马基 a.以下是对类中方法的轻微修改,该类也仅使用一个 Random 对象:
import java.math.BigInteger;
import java.util.Random;
public class FermatTestExample
{
private final static Random rand = new Random();
private static BigInteger getRandomFermatBase(BigInteger n)
{
// Rejection method: ask for a random integer but reject it if it isn't
// in the acceptable set.
while (true)
{
final BigInteger a = new BigInteger (n.bitLength(), rand);
// must have 1 <= a < n
if (BigInteger.ONE.compareTo(a) <= 0 && a.compareTo(n) < 0)
{
return a;
}
}
}
public static boolean checkPrime(BigInteger n, int maxIterations)
{
if (n.equals(BigInteger.ONE))
return false;
for (int i = 0; i < maxIterations; i++)
{
BigInteger a = getRandomFermatBase(n);
a = a.modPow(n.subtract(BigInteger.ONE), n);
if (!a.equals(BigInteger.ONE))
return false;
}
return true;
}
public static void main(String[] args)
{
System.out.printf("checkprime(2) is %b%n", checkPrime(BigInteger.valueOf(2L), 20));
System.out.printf("checkprime(5) is %b%n", checkPrime(BigInteger.valueOf(5L), 20));
System.out.printf("checkprime(7) is %b%n", checkPrime(BigInteger.valueOf(7L), 20));
System.out.printf("checkprime(9) is %b%n", checkPrime(BigInteger.valueOf(9L), 20));
}
}
关于java - 费马素性测试的实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4027225/