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

Ответ 1

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

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

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

Кроме того, OpenSSL имеет хорошую утилиту для тестирования простых чисел:

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

Ответ 6

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