An algorithm that finds ord(a) in $O(\log n)$
Suppose that $\phi(n) = 2^m$; note $m \leq \log n$. The order of $a$ is thus $2^k$ for some $k \leq m$; in fact, it is the minimal $k$ such that $a^{2^k} \equiv 1 \pmod{n}$. You find find this $k$ by repeatedly squaring $a$.