Генерация точно простого числа с Java
Я знаю о функциональном BigInteger.probablePrime (интервал bitLength, Случайный rnd) что выводы, вероятно, простое число любой длины в битах. Я хочу РЕАЛЬНОЕ простое число в Java. Там какая-либо библиотека FOSS должна сделать так с приемлемой производительностью?Заранее спасибо!
Править:
Я смотрю на начала на 1024 и 2 048 битов.
3 ответа
- используйте вероятное простое для генерации кандидата
- используйте быстрый детерминированный тест, такой как тест на первичность AKS, чтобы проверить, действительно ли кандидат является простым.
edit: Или, если вы не доверяете достаточно большой определенности isProbablePrime, используйте конструктор BigInteger BigInteger(int bitLength, int certainty, Random rnd) который позволяет настроить порог определенности:
certainty - мера неопределенности, которую готов терпеть вызывающий. Вероятность того, что новое BigInteger представляет простое число, превысит (1 - 1/2certainty). Время выполнения этого конструктора пропорционально значению этого параметра.
Вероятностные тесты, используемые для криптографических целей, гарантированно ограничивают вероятность ложных срабатываний - это не значит, что существуют какие-то числа, которые проскочат, это просто вопрос того, насколько низкой вы хотите видеть эту вероятность. Если вы не доверяете классу Java BigInteger (было бы неплохо, если бы они документировали, какой тест был использован), используйте тест Рабина-Миллера.
Создайте метод и оберните его.
BigInteger definitePrime(int bits, Random rnd) {
BigInteger prime = new BigInteger("4");
while(!isPrime(prime)) prime = BigInteger.probablePrime(bits,rnd);
return prime;
}
Есть несколько методов для генерации очень больших простых чисел с приемлемой производительностью , но не с достаточной плотностью для большинства целей, кроме попадания в Книгу рекордов Гиннеса.
Посмотрите на это так: вероятность того, что число, возвращаемое функцией probablePrime () , не является простым, ниже, чем вероятность того, что вы и все ваши знакомые пострадают от молнии. Дважды. В один день.
Только не беспокойтесь об этом.