Генерация именно простого числа с помощью Java

Question

Мне известна функция BigInteger.probablePrime (int bitLength, Random rnd), которая выводит, вероятно, простое число любой битовой длины. Я хочу НАСТОЯЩЕЕ простое число в Java. Есть ли какая-либо библиотека FOSS для этого с приемлемой производительностью? Заранее спасибо!

EDIT:

Я смотрю на 1024 и 2048-битные простые числа.

Answer 1

• используйте вероятное простое число для генерации кандидата
• используйте быстрый детерминистический тест , такой как тест простоты AKS , чтобы проверить, действительно ли кандидат является простым.

---

edit: Или, если вы не доверяете isProbablePrime с достаточной степенью достоверности, используйте конструктор BigInteger BigInteger(int bitLength, int certainty, Random rnd), который позволяет настроить порог достоверности:

уверенность - мера неопределенности, которую звонящий готов терпеть. Вероятность того, что новый BigInteger представляет простое число, будет превышать (1 - 1/2 ^{достоверность} ). Время выполнения этого конструктора пропорционально значению этого параметра.

Вероятностные тесты, используемые в криптографических целях, гарантированно ограничивают вероятность ложных срабатываний - это не значит, что существуют какие-то числа Гоча, которые будут пробираться, это просто вопрос, насколько низка вероятность того, чтобы вероятность была. Если вы не доверяете классу Java BigInteger, чтобы использовать их (было бы хорошо, если бы они документировали, какой тест использовался), используйте тест Rabin-Miller .

Answer 2

Существуют некоторые методы для генерации очень больших простых чисел с приемлемой производительностью, но не с достаточной плотностью для большинства целей, кроме попадания в Книгу рекордов Гиннеса.

Посмотрите на это так: вероятность того, чточисло, возвращаемое probablePrime() не простое, меньше, чем вероятность того, что вы и все, кого вы знаете, будут поражены освещением.Дважды.В один день.

Только не беспокойся об этом.

Answer 3

Вы также можете использовать конструктор BigInteger для генерации реального простого числа:

BigInteger(int bitLength, int certainty, Random rnd)

Время выполнения пропорционально определенности, но на моем Core i7 это не проблема.

Answer 4

Создайте метод и оберните его.

BigInteger definitePrime(int bits, Random rnd) {
    BigInteger prime = new BigInteger("4");
    while(!isPrime(prime)) prime = BigInteger.probablePrime(bits,rnd);
    return prime;
}

Answer 5

Random rnd = new SecureRandom();
System.out.println(BigInteger.probablePrime(bitLength, rnd));

Вероятность того, что BigInteger, возвращенный методом <a href="http://www.tutorialspoint.com/java/math/biginteger_probableprime.htm" rel="nofollow">probablePrime()</a>, является составной, не превышает 2 ^ -100.