Внедрение критерия примарности Ферма - PullRequest
Новая
       12

Внедрение критерия примарности Ферма

1 голос
/ 26 октября 2010

Кто хочет помочь мне с домашним заданием?

Я пытаюсь реализовать тест простоты Ферма в 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.

Спасибо!

Ответы [ 2 ]

2 голосов
/ 27 октября 2010

Вы используете конкретный конструктор BigInteger разумно, но вы должны использовать метод отклонения , чтобы выбрать базу ферма а.Вот небольшая модификация вашего метода в классе, который также использует ровно один объект 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));
    }
}
1 голос
/ 26 октября 2010

a должно быть "выбрать случайным образом в диапазоне (1, n - 1]"), и я не вижу, чтобы это произошло. Вы можете напечатать a, чтобы проверить это.

Что касается того, как это сделатьчто: 

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

Например, вы не должны использовать конструктор BigInteger со случайным аргументом, это просто источник случайности, но a должно быть случайным значением .

'random.nextInt (n-1) +1' происходит из определения nextInt , которое при заданном аргументе k возвращает случайное значение от 0 до k включительно1. И вы хотите, чтобы a был больше 1 и меньше n.

...