Как быстро генерировать случайное простое число, это точно 1024 бит?
Генерировать 1024 случайных бита. Используйте случайный источник, который достаточно силен для вашей цели.
Установите наивысший и младший бит в 1. Это гарантирует, что нет нулевых нулей (главный кандидат достаточно большой), и это не четное число (определенно не простое).
Тест для примитивности. Если это не простое, вернитесь к 1.
В качестве альтернативы используйте библиотечную функцию, которая генерирует для вас простые числа.
Используйте библиотечную функцию, такую как OpenSSL. Там не нужно писать это самостоятельно.
1024 - это много. Вы уверены, что вероятностный премьер не будет делать? Вероятностный первичный генератор является частью JDK
Вы не указываете контекст/язык/платформу. Если вы хотите использовать систему и оболочку unix/linux, вы можете рассмотреть решение с использованием версии OpenSSL >= 1.0.0:
$ openssl prime -generate -bits 1024
140750877582727333214379261853877378646889234118675380673028200387281415297520423589261211081966230040412916644372766351028035798201654335110081318739796178745233127842988596480299276295476504358587725867882394416543075082108266054273016211760684113070285409887820598314292803190900634009988950624354964653677
Если вы получили тот же результат, что-то очень не так с вселенной.
Добавьте -hex вариант, если вам нужна шестнадцатеричная система.
Чтобы обменять память на скорость, вы можете просто сгенерировать их и сохранить в списке, а затем произвольно выбрать один.
Изменить: Естественно, вы не можете сгенерировать их все, чтобы лучшее, что вы могли достичь, это псевдослучайность при высокой стоимости памяти. Также это плохо, если вы хотите его для безопасности.
В PARI/GP:
randomprime([2^1023,2^1024])
Если вы хотите сделать это в "режиме библиотеки"
#include <pari/pari.h>
// ...
randomprime(mkvec2(int2u(1023), int2u(1024)))