Mise en œuvre du test de primalité de Fermat

Question

Qui veut m'aider avec mes devoirs?

Je suis d'essayer d'implémenter Fermat's primality test en Java en utilisant BigIntegers. Ma mise en œuvre est la suivante, mais malheureusement, cela ne fonctionne pas. Des 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 un rejection method pour sélectionner une base de fermat a. Voici une légère modification de votre méthode dans une classe qui utilise également exactement un objet aléatoire:

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 un « pick un hasard dans la gamme (1, n - 1] » et je ne vois vraiment pas que cela se produise Vous pouvez imprimer pour vérifier que

Quant à la façon de le faire.. :

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

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

le ra. ndom.nextInt (n-1) +1 'vient de la définition de nextInt qui, étant donné l'argument k, renvoie une valeur aléatoire de 0 jusqu'à k-1 inclus. Et vous voulez un être plus grand que 1 et plus petit que n.