How to find primitive root modulo of 23?

Question

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.

Answer 1

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.