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.
f
ilters 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.