@Stairdeck

Есть ли метод генерации большого простого числа с факторизацией p — 1?

Здравствуйте!
Есть задача - построить большое простое число(порядка 2-3к бит) с заранее известной факторизацией p - 1.
Это необходимо, чтобы найти первообразные корни(пытаюсь реализовать протокол Диффи-Хеллмана)
  • Вопрос задан
  • 92 просмотра
Пригласить эксперта
Ответы на вопрос 2
@cicatrix
было бы большой ошибкой думать
Для изобретения велосипеда и обучения тому, как всё это работает, генерить большие числа не требуется.
Если уж очень хочется - то вот, ознакомьтесь. Ну и либо Решето Аткина, ну или того же Эратосфена.
Это первое.
Второе: никогда, никогда, никогда, никогда, никогда не пытайтесь реализовать криптографические алгоритмы для любых целей, кроме образовательных. Никогда не используйте собственную реализацию для защиты хоть чего-либо важного. Я вас, конечно, не знаю, но докторской степени по математике и нескольких лет опыта в криптографии и криптоанализе у вас, скорее всего, нет.
Ответ написан
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
Можно такой подход: Сгенерируйте два случайных простых числа длиной n/2 бит (Генерируйте случайное число, пока не получили простое). Потом перемножте их, прибавьте 1 и проверьте, что тоже результат простой.

Для этого надо уметь относительно быстро проверять что число простое. Можно использовать метод Миллера-Рабина. Он вероятностный, но увеличивая число итераций можно достичь произвольно маленькой вероятности ошибки.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы