Случайное простое число

Как быстро генерировать случайное простое число, это точно 1024 бит?

Ответы

Ответ 1

  • Генерировать 1024 случайных бита. Используйте случайный источник, который достаточно силен для вашей цели.

  • Установите наивысший и младший бит в 1. Это гарантирует, что нет нулевых нулей (главный кандидат достаточно большой), и это не четное число (определенно не простое).

  • Тест для примитивности. Если это не простое, вернитесь к 1.

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

Ответ 2

Используйте библиотечную функцию, такую ​​как OpenSSL. Там не нужно писать это самостоятельно.

Пример: http://ardoino.com/7-maths-openssl-primes-random/

Ответ 3

1024 - это много. Вы уверены, что вероятностный премьер не будет делать? Вероятностный первичный генератор является частью JDK

Ответ 4

Вы не указываете контекст/язык/платформу. Если вы хотите использовать систему и оболочку unix/linux, вы можете рассмотреть решение с использованием версии OpenSSL >= 1.0.0:

$ openssl prime -generate -bits 1024
140750877582727333214379261853877378646889234118675380673028200387281415297520423589261211081966230040412916644372766351028035798201654335110081318739796178745233127842988596480299276295476504358587725867882394416543075082108266054273016211760684113070285409887820598314292803190900634009988950624354964653677

Если вы получили тот же результат, что-то очень не так с вселенной.

Добавьте -hex вариант, если вам нужна шестнадцатеричная система.

Ответ 5

Чтобы обменять память на скорость, вы можете просто сгенерировать их и сохранить в списке, а затем произвольно выбрать один.

Изменить: Естественно, вы не можете сгенерировать их все, чтобы лучшее, что вы могли достичь, это псевдослучайность при высокой стоимости памяти. Также это плохо, если вы хотите его для безопасности.

Ответ 6

В PARI/GP:

randomprime([2^1023,2^1024])

Если вы хотите сделать это в "режиме библиотеки"

#include <pari/pari.h>
// ...
randomprime(mkvec2(int2u(1023), int2u(1024)))