# How to find primitive root modulo of 23? [duplicate]

These types of questions are repeated here zillionth time, but I am yet to find an useful process(hit and trial or any other process) to find primitive root modulo. Can you help me. I need this for network security, deffi helman algorithm so asking here.

• For cryptographic purposes, one often uses a fixed, large number for which an easy primitive root is known. For example, fiddling with powers of 2 can easily get you primes with a primitive root $2^{16}+1$, etc. Aug 21, 2021 at 6:37
• I want to find it myself so that I can be confident on my skills. So I am asking it here. Really thankful for the information. Aug 21, 2021 at 6:46
• There is no known way to find a primitive root efficiently. You basically have to apply trial and error. The good news : There are almost always very small bases doing the job, $2$ is already sufficient in the vast majority of the odd cases. Aug 21, 2021 at 6:56
• I don't even know the hit and trial method. I looked up to MIT tutorials but they were really confusing. So I am asking here in stackexchange. But I get it you mean there is no efficient way. So chances are likely that this won't be asked in our examinations. Thanks for clearing my confusion. Aug 21, 2021 at 7:01
• Try $2$. Is it a primitive root? If yes, success! If not, try $3$. Is it a primitive root? If yes, success! If not, try $5$ ($4=2^2$ is never a primitive root modulo anything odd). Keep going. That's what trial and error means. Aug 21, 2021 at 7:11

Here is an approach you might have not seen before:

$$\phi(23)=22 = 2\cdot11$$

Then find any element in modulo $$23$$ such that its order is $$2$$ and another with order $$11$$:

$$ord_{23} 3 = 11$$ and $$ord_{23} 22 = 2$$

Multiply these numbers: $$22\cdot3=66 \equiv 20 \pmod {23}$$

Then $$20$$ is a primitive root.

In general, for a prime $$p$$: Let $$\phi(p)=p-1=q_1^{a_1}...q_t^{a_t}$$ (where each $$q_i$$ is a prime factor of $$\phi(p))$$

Find integers $$b_1, ...,b_t$$ such that $$ord_{p}b_1=q_1^{a_1},...,ord_{p}b_t=q_t^{a_t}$$.

Then $$b=b_1...b_t$$ is a primitive root modulo $$p$$.

I prefer this method over trial and error as it is guaranteed to work. However, the main issue with this approach is to find integers $$b_1,...,b_t$$, which is not trivial. But I thought I'd share it with you as an alternative. There is no known "easy" formula for finding primitive roots in general.

• Lowest primitive root should be prime,as any residue a power of it, just jumps through it stepping by the exponent. Sep 10, 2021 at 14:31