Генерируя действительно большие простые числа

Question

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

Answer 1

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

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

Есть несколько способов проверить, является ли численность простого, одним из хороших является «тест на мельлер-рабин» Как указано в другом ответе на этот вопрос.

Кроме того, у OpenEnssl есть хорошая утилита для проверки на простые простые:

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime

Answer 2

Посмотрите, как Truecrypt Имеет ли это. Также взгляните на Рабин-Миллер Для тестирования больших псевдопримах.

Answer 3

Вы не упомянули, какой язык вы используете. У некоторых есть метод выполнения этого встроенного. NextProbablePrime () на Biginteger.

Answer 4

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

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

Answer 5

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

Answer 6

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