What's a half on the clock?

Jelly, 6 bytes

R2*%i1

Try it online!

How it works

R2*%i1  Input: n

R       Range; yield [1, ..., n].
 2*     Compute [2**1, ..., 2**n].
   %    Hook; take all powers modulo n.
    i1  Get the index of the first 1.
        Indices are 1-based, so index k corresponds to the natural number k.

Pyth - 9 8 bytes

f!t.^2TQ

Test Suite.

filters from default of 1 till it finds some x such that modular exponentiation with 2 and the input equals 1.


Python, 32 bytes

f=lambda n,t=2:t<2or-~f(n,2*t%n)

Starting with 2, doubles modulo n until the result is 1, recursively incrementing each time, and ending with a count of 1 for the initial value of 2.