J
J
Jan2021-04-02 20:32:42
Mathematics
Jan, 2021-04-02 20:32:42

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

1 answer(s)
W
Wataru, 2021-04-02
@wataru

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 question

Ask a Question

731 491 924 answers to any question