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

Question

[Ян]

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

Заранее спасибо.

Answer 1

[Wataru]

Найдите первообразный корень по модулю p. Возведите его в степень (p-1) / q. Это и будет искомое число с порядком q.

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