In my cryptography course our teacher said that solving the discrete logarithm problem in a group of order $2^e$ is easy, and he gave us the following algorithm:
Let $G$ be a cyclic group with $|G|=2^e$ and $g\in G$ a generator. The following algorithm computes $x$ such that $h=g^x$:
Precomputation: $g^{-1}=g^{n-1}$.
Inicialization: $x_0=0$, $b_0=h$, $m_0=\log_2(ord(h))$.
Iterations:
while $m_i> 0$:
$x_{i+1}=x_i+2^{e-m_i}$
$b_{i+1}=b_i(g^{-1})^{2^{e-m_i}}$
$m_{i+1}=\log_2(\text{ord}(b_{i+1}))$
Output: $x=x_i$
What I want to do is to prove that the algorithm stops, that $x$ is indeed the discrete logarithm and that it works in polynomial time. In order for the algoritm to stops we only have to check that $m_{i+1}<m_i~\forall~i$, which is equivalent to show that $\text{ord}(b_{i+1})<\text{ord}(b_i)$. If $\text{ord}(b_i)=2^l$ then:
$$b_{i+1}^{2^l}=(b_i(g^{-1})^{2^{e-m_i}})^{2^l}=b_i^{2^l}(g^{-1})^{2^{e-l}2^l}=1$$
which proves that $\text{ord}(b_{i+1})\leq\text{ord}(b_i)$, but I am not able to get the strict inequality. For the other two parts I don't have any good idea on how to solve it...
I am a matematician who is a beginer in cryptography, so I don't mind if you assume math knowledge, which is what I am used to. Thanks for your help.
