How to find the smallest $r$ such that $o_r(n) > ($log$_2 n)^2$? AKS Algorithm I know that $r < ($log$_2 n)^5$, but since it is a mod function and you can't reverse the equation ($o_r(n) = $min {$ k|n^k=1 ($mod $ r)$}) to solve for $k$, how would you test whether $k > $ (log$_2 n)^2$? I also don't understand why the algorithm on Wikipedia (https://en.wikipedia.org/wiki/AKS_primality_test), that loops $k$ until (log$_2 n$)$^2$ since it's the minimum, and anything below that shouldn't matter?
 A: The best runtime bound claimed on Wikipedia for the overall algorithm is $\tilde O(\log_2(n)^{7.5})$, so for the step you're asking about, I just need to provide a method that fits within that complexity bound.
There are only $(\log_2(n)^5$ possible values of $r$ that we might need to try. For any such value of $r$, I can test whether it works in $\log_2(n)^2$ steps, just by computing $n, n^2, n^3, \cdots, n^{\log_2(n)^2}$ modulo $r$ and checking whether any of those residues are $1$. That gives me an overall runtime cost of $O(\log_2(n)^7)$ for this step which is more than fast enough.
This is the same logic used in the algorithm on Wikipedia. You wrote that you don't understand why it checks only up to $\log_2(n)^2$, but the equation $o_r(n) > \log_2(n)^2$ exactly requires that $n^k$ is NOT 1 mod $r$ for any $k \le \log_2(n)^2$. I think that might be the point you're missing: we don't need to actually compute $o_r(n)$, we just need to check that the order is not $1, 2, 3, \cdots, \log_2(n)^2$. If we finish that check and we haven't gotten residue $1$ yet then we don't know exactly what the order is but it's obviously bigger than $\log_2(n)^2$.
