Answer the question
In order to leave comments, you need to log in
How to find the element with the desired order in the residue ring?
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 the question
In order to leave comments, you need to log in
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.
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question