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! 
 A: 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$.
A: 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.$
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...
