La mise en œuvre du test de primalité de Fermat

Question

Qui veut me aider à faire mes devoirs?

Je vais essayer de mettre en œuvre test de primalité de Fermat en Java en utilisant BigIntegers. Ma mise en œuvre est la suivante, mais malheureusement il ne fonctionne pas. Toutes les idées?

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

Je suis nouveau à BigIntegers.

Merci!

Answer 1

Votre utilisation du constructeur BigInteger particulier est raisonnable, mais vous devez utiliser une méthode de rejet sélectionner une base de Fermat. Voici une légère modification de votre méthode dans une classe qui utilise aussi exactement un objet au hasard:

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

devrait être « choisir un au hasard dans la gamme (1, n - 1] ».. Et je ne vois pas vraiment que cela se produise, vous pouvez imprimer pour vérifier que

En ce qui concerne la façon de le faire:

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

par exemple. Vous ne devriez pas utiliser le constructeur BigInteger avec un argument aléatoire; c'est juste une source de hasard, mais a devrait être aléatoire valeur .

Le 'Random.nextInt (n-1) 1' provient de la définition de nextInt qui, argument donné k, renvoie une valeur aléatoire 0 jusqu'à et y compris k-1. Et vous voulez a être supérieur à 1 et inférieur à n.