Генерация ДЕЙСТВИТЕЛЬНО больших простых чисел

Question

Я играю вокруг и пытаюсь написать реализацию RSA. Проблема в том, что я застрял на генерации массивных простых чисел, которые участвуют в генерации пары ключей. Может ли кто-нибудь указать мне быстрый способ генерирования огромных простых чисел / вероятных простых чисел?

Answer 1

Вы не генерируете простые числа точно. Вы генерируете большое нечетное число случайным образом, затем проверяете, является ли это число простым, если не генерирует другое случайное число. Есть некоторые законы простых чисел, которые в основном утверждают, что ваши шансы «попасть» в простое число случайными попытками составляют (2 / ln n)

Например, если вы хотите 512-битное случайное простое число, вы найдете его в 2 / (512 * ln (2)) Таким образом, примерно 1 из каждых 177 чисел, которые вы попробуете, будет простым.

Есть несколько способов проверить, является ли число простым, один хороший - это "тест Миллера-Рабина" , как указано в другом ответе на этот вопрос .

Также в OpenSSL есть хорошая утилита для тестирования простых чисел:

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime

Answer 2

Посмотрите, как TrueCrypt делает это. Кроме того, взгляните на Рабина-Миллера для проверки больших псевдопраймов.

Answer 3

Предыдущий ответ неверен: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59.

Я думаю, что плакат неправильно запоминает (реальное) доказательство того, что существует несчетное количество простых чисел.

Answer 4

Вы не упомянули, какой язык вы используете. У некоторых есть способ сделать это встроенным. Например, в Java это так же просто, как вызов nextProbablePrime () для BigInteger.

Answer 5

Существует алгоритм У. Маурера, который генерирует случайные доказуемые (в отличие от статистически высокой вероятности) простые числа, которые почти равномерно распределены по набору всех простых чисел специального размера. У меня есть реализация Python, которая довольно эффективна в: http://s13.zetaboards.com/Crypto/topic/7234475/1/

Answer 6

Mono имеет класс BigInteger с открытым исходным кодом, как и Java. Вы могли бы взглянуть на них. Они, вероятно, портативны :) g'luck