Java BigInteger nombres premiers

Question

J'essaie de générer un nombre premier aléatoire de type BigInteger, compris entre une valeur minimale et maximale que je fournis.

Je connais le BigInteger.probablePrime (int bitlength, random), mais je ne suis pas sûr de savoir comment ou même si le bitlength se traduit par une valeur max / min du nombre premier émis.

Merci, Steven1350

Answer 1

BigInteger.probablePrime (bitLength, random) va renvoyer un nombre premier (probable) de la longueur en bits spécifiée. Cela se traduit par une valeur maximale de 2 ^ bitlength - 1 et un minimum de 2 ^ (bitlength - 1). Autant que je déteste ça comme une réponse, c'est probablement votre meilleur pari si vous ne voulez pas commencer à plonger dans la théorie des nombres.

Ce que vous devez faire est de déterminer les longueurs de bits appelées par votre plage, puis de les transmettre à probablePrime () jusqu'à ce que vous obteniez un nombre premier compris dans la bonne plage.

Answer 2

La réponse de jprete est correcte si votre rapport max / min n’est pas proche de 1.

Si vous avez une plage étroite, votre meilleure option est probablement de faire quelque chose comme ce qui suit:

// this is pseudocode:
//
// round min down to multiple of 6, max up to multiple of 6
min6 = floor(min/6);
max6 = ceil(max/6);
maybePrimeModuli = [1,5];
do 
{
   b = generateRandom(maybePrimeModuli.length);
   // generate a random offset modulo 6 which could be prime
   x = 6*(min6 + generateRandom(max6-min6)) + b;
   // generate a random number which is congruent to b modulo 6
   // from 6*min6 to 6*max6-1
   // (of the form 6k+1 or 6k+5)

   // the other choices 6k, 6k+2, 6k+3, 6k+4 are composite 
} while not isProbablePrime(x);

Le densité de Le nombre de nombres premiers est relativement élevé dans l'ensemble. Il s'agit en gros de 1 dans le journal (x). Vous ne devriez donc pas avoir à répéter plusieurs fois pour trouver un nombre premier. (à titre d’exemple: pour les nombres d’environ 10 ²³ , un nombre entier sur 52 est un nombre premier en moyenne. Le code ci-dessus ne dérange que avec 2 nombres sur 6, de sorte que boucler 17 fois en moyenne pour des nombres d’environ 10 ²³ .)

Assurez-vous simplement que vous avez un bon test de primalité et que Java BigInteger en a un.

Comme exercice pour le lecteur, étendez la fonction ci-dessus de façon à filtrer plus de nombres composés à l’avance en utilisant 30k + x (modulo 30, il y a 22 modules toujours composites, il n’en reste que 8 qui pourraient être premiers) ou 210k + x.

modifier: voir aussi brevet américain n ° 7149763 (OMFG !!!)