J'essaie de générer un nombre premier aléatoire de type BigInteger, c'est-à-dire entre une valeur min et max que je fournis.Java nombres premiers BigInteger
Je suis conscient du BigInteger.probablePrime (int bitlength, random), mais je ne suis pas sûr comment ou même si le bitlength se traduit par une valeur max/min du premier sorti.
Merci, Steven1350
BigInteger.probablePrime(bitLength, random) va retourner un premier (probable) de la longueur de bit 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 comme une réponse, c'est probablement votre meilleur pari à moins que vous vouliez commencer à plonger dans la théorie des nombres. Ce que vous auriez à faire est de déterminer les longueurs de bits que votre gamme appelle, puis passez-les à probablePrime() jusqu'à ce que vous obteniez un prime qui est dans la bonne gamme.
La réponse de jprete est très bien si votre rapport max/min est pas près de 1.
Si vous avez une gamme étroite, votre meilleur pari est probablement juste 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 density of primes est assez élevé dans l'ensemble, c'est en gros 1 dans log (x), donc vous ne devriez pas avoir à répéter trop de fois pour trouver un nombre premier. (à titre d'exemple: pour les nombres autour de 10 , un entier sur 52 en moyenne est un nombre premier.Le code ci-dessus dérange seulement avec 2 sur 6 nombres, de sorte que vous finissez par boucler une moyenne de 17 temps pour les nombres autour de 10 .)
Assurez-vous juste que vous avez un bon test de primalité, et le Java BigInteger en a un. Comme exercice pour le lecteur, étendez la fonction ci-dessus afin de filtrer plus de nombres composites à l'avance en utilisant 30k + x (modulo 30, il y a 22 modules qui sont toujours composites, seulement 8 qui restent peuvent être premiers), ou 210k + x.
éditer: voir aussi US patent #7149763 (OMFG !!!)
Intéressant. Du Doc, "la probabilité que le BI retourné soit composé est <2^-100", assez improbable en effet! Connaîtriez-vous par hasard la complexité de cette méthode? –
Au lieu d'appeler probalePrime avec un bitlength, la plage appelle un pour créer un grand nombre aléatoire dans la plage et invoquer nextProbablePrime. Cela générera le nombre premier plus rapidement en invoquant plusieurs fois problePrime. Bien sûr, vous devrez faire face à la situation où le reult est plus grand que la valeur maximale de votre gamme. –