# Computing $\operatorname{ord}_p(a)$ for a big $p$ without computing all the $p-1$ options?

I'd love your help with understanding how should I compute the order of a number modulo some prime number $p$ without going through all of the options.

Let me explain:

I defined $\operatorname{ord}_p(a)= \min (i>0 | a^i=1(p))$. I know that for every prime $\varphi(p)=p-1$ where $\varphi(p)=|(\mathbb{Z} /_p\mathbb{Z})^x|$, but I look for the minimial i which satisfies the condition, but sometimes I have a big $p$ to work with, for example: the number 3 and the $p=29$. Is there any way to know what is $\operatorname{ord}(3)$ for this p without computing all the options $4,5,\ldots,28$? Is there any theorem which may help me with that and I'm missing it?

Thanks a lot!

-
The order must divide $\phi(p)$ so in your case, you need to check 2, 4, 7 and 14 (if none of those work, then ord = 28 – deinst Apr 7 '12 at 19:38

You know that $a^{p-1}\equiv 1(p)$. From this you can deduce that the order of $a$ must divide $p-1$ (if $a^q\equiv 1(p)$ then $a^{\gcd(p-1,q)}\equiv 1(p)$). So you only need to check the divisors of $p-1$.

-
+1 As a corollary to that: If $a^{(p-1)/q}\not\equiv 1\pmod p$ for all prime divisors $q$ of $p-1$, then the order of $a$ is equal to $p-1$. Often comes in handy when proving primitivity. Sophie Germaine primes are a case in point. This method does have the drawback that it is necessary to be able to factor $-1$. – Jyrki Lahtonen Apr 7 '12 at 19:50
As a further addition, by starting at the highest powers that divide 28 (14, 4) you get some more speedup. You work your way down in the tree until at some point you don't get $a^q = 1$ anymore. – TMM Apr 7 '12 at 19:54

Hint $\$ Keep removing prime factors $\rm\:q\:$ from $\rm\:p-1\:$ till you reach a number $\rm\:n\:$ such that $\rm\:mod\ p\!:\ a^n\equiv 1,\:$ but $\rm\:a^{n/q}\not\equiv 1\:$ for all primes $\rm\:q\ |\ n.\:$ Then $\rm\:n\: =\: ord_p\:a.$

-

Few things can help.

1) As deinst mentioned, $\operatorname{ord}_p(n)$ is a divisor of $p-1$. So all you need to do is list all divisors of $p-1$, and calculate only $n^d$ up to $\frac{p-1}{2}$. The smallest which is $1$ is the order, otherwise the order is $p-1$.

2) You can prove that the $\operatorname{ord}_p(10)$ is the same as the number of digits in the period of $\frac{1}{p}$, of course for $p\neq 2,5$. Same way, $\operatorname{ord}_{p}(n)$ is the same as the number of digits in the period of $\frac{1}{p}$ in base $n$.

Computationally it might look easier to figure what is the period of $\frac{1}{29}$ than to figure $\operatorname{ord}_{29} (10)$ but it is not...

3) The Jacobi symbol $\left( \frac{n}{p} \right)$ is usually easy to calculate. It is $1$ if and only if $\operatorname{ord}_p(n)$ is a divisor of $\frac{p-1}{2}$ (this follows from Euler Criteria). For large primes this is an easy computation which eliminates half of the possibilities in $1)$...

4) Keep in mind that $\operatorname{ord}_p a^k=\frac{\operatorname{ord}_p(a)}{ \gcd (\operatorname{ord}_p a, k)}$. This sometimes helps. For example, in the problem you listed with $p=29$ and $n=3$, you might find it easier to calculate $\operatorname{ord}_{29} 2$ and use the fact that $3 \equiv 32 \equiv 2^5 \mod 29$. This helps very rarely though...

-