números primos Java BigInteger

Question

Eu estou tentando gerar um número primo aleatório de tipo BigInteger, que está entre um min e valor máximo que eu fornecer.

Estou ciente da BigInteger.probablePrime (bitlength int, aleatório), mas eu não sei como ou mesmo se o bitlength traduz em um valor / min max do Primeiro-emitidas.

Obrigado, Steven1350

Answer 1

BigInteger.probablePrime(bitLength, random) vai voltar a (provável) prime do comprimento de bits especificado. Isso se traduz em um valor máximo de 2 ^ bitlength - 1 e um mínimo de 2 ^ (bitlength - 1). Tanto quanto eu odeio isso como uma resposta, é provavelmente a sua melhor aposta, a menos que você quiser começar a se aprofundar em teoria dos números.

O que você tem a fazer é descobrir os comprimentos de bits que suas chamadas alcance para, em seguida, passá-las para probablePrime() até você voltar um primo que está na faixa direita.

Answer 2

A resposta de jprete é bom se o seu rácio de max / min não é próximo de 1.

Se você tem uma faixa estreita, a sua melhor aposta é provavelmente apenas para fazer algo como o seguinte:

// 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);

A densidade de primes é bastante elevado no geral, é basicamente 1 em log (x), para que você não deve ter que repetir muitas vezes para encontrar um número primo. (Apenas como exemplo: para números de cerca de 10 ²³ , um em cada 52 números inteiros, em média, é um número primo somente o código acima incomoda com 2 em cada 6 números, então você iria acabar. looping uma média de 17 vezes para os números em torno de 10 ²³ .)

Apenas certifique-se que você tem um bom teste primality, eo Java BigInteger tem um.

Como um exercício para o leitor, estender a função acima, de modo que filtra os números mais compostos antes do tempo utilizando 30k + x (módulo 30, existem 22 módulos que são sempre compósita, apenas 8 restantes que pode ser privilegiada) ou 210k + x.

edit: ver também US Patent # 7149763 (OMFG !!!)