Случайное простое число
Как быстро генерировать случайное простое число, это точно 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)))