@Stairdeck

Как найти элемент с нужным порядком в кольце вычетов?

Здравствуйте.
Есть следующая задача: имеется большое простое число p, а так же q | p - 1.
Необходимо найти g ∈ Zp порядка q. Есть ли рекомендации по теории или оптимальные алгоритмы по поиску таких элементов?

Заранее спасибо.
  • Вопрос задан
  • 64 просмотра
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Найдите первообразный корень по модулю p. Возведите его в степень (p-1) / q. Это и будет искомое число с порядком q.

Есть вот такой алгоритм поиска первообразного корня: проверяйте все числа подряд. Разложите p-1 на множители и возводите проверяемое число в степень (p-1)/k, где k - простой делитель p-1. Если везде получили не 1, то текущее число - первообразный корень.
Ответ написан
Ваш ответ на вопрос

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

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