How to find the element with the desired order in the residue ring?

Question

Mathematics

Hello.
There is the following problem: there is a large prime number p, as well as q | p - 1.
It is necessary to find g ∈ Zp of order q. Are there any theoretical recommendations or optimal algorithms for finding such elements?

Thanks in advance.

Answer 1

Find a primitive root modulo p. Raise it to the power (p-1) / q. This will be the desired number with order q.
There is such an algorithm for finding a primitive root: check all numbers in a row. Factor p-1 and raise the number to be tested to the power (p-1)/k, where k is a prime divisor of p-1. If not 1 is received everywhere, then the current number is a primitive root.