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