Fermat素数测试的实现 [英] Implementation of Fermat's primality test

问题描述

谁想帮助我做作业?

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

I'm try to implement Fermat's primality test in Java using BigIntegers. My implementation is as follows, but unfortunately it doesn't work. Any ideas?

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

I'm new to BigIntegers.

谢谢！

推荐答案

您使用特定的BigInteger构造函数是合理的，但是您应该使用拒绝方法来选择费马基础a.这是在一个类中的方法的略微修改，该类也恰好使用一个Random对象:

Your use of the particular BigInteger constructor is reasonable, but you should use a rejection method to select a fermat base a. Here is a slight modification of your method in a class which also uses exactly one Random object:

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));
    }
}

这篇关于Fermat素数测试的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！