-2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Trebor
    Aug 21, 2021 at 6:37
  • $\begingroup$ 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. $\endgroup$
    – pazzah
    Aug 21, 2021 at 6:46
  • $\begingroup$ 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. $\endgroup$
    – Peter
    Aug 21, 2021 at 6:56
  • $\begingroup$ 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. $\endgroup$
    – pazzah
    Aug 21, 2021 at 7:01
  • 2
    $\begingroup$ 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. $\endgroup$
    – Arthur
    Aug 21, 2021 at 7:11

1 Answer 1

1
$\begingroup$

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.

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.