An algorithm that finds ord(a) in $O(\log n)$

Question

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.

Answer 1

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$.