Есть ли метод генерации большого простого числа с факторизацией p — 1? Здравствуйте!
Есть задача - построить большое простое число(порядка 2-3к бит) с заранее известной факторизацией p - 1.
Это необходимо, чтобы найти первообразные корни(пытаюсь реализовать протокол Диффи-Хеллмана)

Предыдущий
вопрос Следующий
вопрос

Да, существует метод генерации большого простого числа с заранее известной факторизацией p - 1. Один из таких методов называется метод Ферма. Суть метода заключается в том, что мы выбираем случайное простое число p и затем проверяем, имеет ли оно нужную факторизацию p - 1. Если не имеет, то мы выбираем другое простое число и продолжаем проверку.

Другой метод, который также может быть использован, называется метод Полларда p - 1. Он позволяет быстро находить большое простое число с заданной факторизацией p - 1, используя алгебраические методы.

Оба эти метода могут быть полезны при реализации протокола Диффи-Хеллмана, так как они позволяют генерировать большие простые числа с заданной факторизацией для использования в криптографии.