An algorithm that finds ord(a) in $O(\log n)$ Let $p$ be a Fermat prime ($p=2^m+1$) and $n=p2^k$ and $a∈Z^*_n$, I should suggest an algorithm that will find $\operatorname{ord}(a)$ in polynomial time (that is, in time polynomial in $\log n$).
I showed that if $n$ is the above then $φ(n)$ is power of 2.
For example:
let $m=k=2$ so $n=5\cdot4=20$ and $φ(20) = |{1, 3, 7, 9, 11, 13, 17, 19}| = 8 = 2^3$
Let $a=7$:
$7^1 \bmod 20 = 7$,
$7^2 \bmod 20 = 9$,
$7^3 \bmod 20 = 3$,
$7^4 \bmod 20 = 1$
so $\operatorname{ord}(7) = 4$
But I don't get how can I use that to find such algorithm.
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$.