费马素性测试的实现

Question

谁愿意帮我做作业？

我尝试使用 BigIntegers 在 Java 中实现 Fermat 素性测试。我的实现如下，但不幸的是它不起作用。有什么想法吗？

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 的新手。

谢谢！

Answer 1

您对特定 BigInteger 构造函数的使用是合理的，但您应该使用 拒绝方法 来选择 fermat基地 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));
    }
}

Answer 2

a 应该是“在 (1, n − 1] 范围内随机选择一个”，我并没有真正看到这种情况发生。你可以打印 a 来检查。

至于如何做到这一点：

BigInteger a = BigInteger.valueOf(random.nextInt(n-2)+2);

例如，你不应该使用 ；这只是随机性的来源，但 a 应该是一个随机值。

带有 Random 参数的 BigInteger 构造函数 来自 nextInt 的定义，给定参数 k，返回一个随机值 0 到 k-1（包括 k-1），并且您希望 a 大于 1 且小于 n。