На моем курсе криптографии наш учитель сказал, что решение задачи дискретного логарифмирования в группе порядка $2^e$ легко, и он дал нам следующий алгоритм:
Позволять $G$ быть циклической группой с $|G|=2^e$ и $г\в G$ генератор. Следующий алгоритм вычисляет $х$ такой, что $ч=г^х$:
Предварительный расчет: $г^{-1}=г^{n-1}$.
Инициализация: $х_0=0$, $b_0=ч$, $m_0=\log_2(орд(ч))$.
Итерации:
пока $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}))$
Вывод: $х=х_i$
Я хочу доказать, что алгоритм останавливается, что $х$ действительно является дискретным логарифмом и работает за полиномиальное время. Чтобы алгоритм остановился, нам нужно только проверить, что $m_{i+1}<m_i~\forall~i$, что эквивалентно тому, чтобы показать, что $\text{орд}(b_{i+1})<\text{орд}(b_i)$. Если $\text{орд}(b_i)=2^l$ тогда:
$$b_{i+1}^{2^l}=(b_i(g^{-1})^{2^{e-m_i}})^{2^l}=b_i^{2^l} (г^{-1})^{2^{e-l}2^l}=1$$
что доказывает, что $\text{ord}(b_{i+1})\leq\text{ord}(b_i)$, но я не могу получить строгое неравенство. Что касается двух других частей, у меня нет хорошей идеи о том, как ее решить...
Я математик, новичок в криптографии, поэтому я не возражаю, если вы предполагаете математические знания, к которым я привык. Спасибо за вашу помощь.
