În cursul meu de criptografie, profesorul nostru a spus că rezolvarea problemei logaritmului discret într-un grup de ordine $2^e$ este ușor și ne-a dat următorul algoritm:
Lăsa $G$ fie un grup ciclic cu $|G|=2^e$ și $g\în G$ un generator. Următorul algoritm calculează $x$ astfel încât $h=g^x$:
Precalcul: $g^{-1}=g^{n-1}$.
Inițializare: $x_0=0$, $b_0=h$, $m_0=\log_2(ord(h))$.
Iterații:
in timp ce $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}))$
Ieșire: $x=x_i$
Ce vreau să fac este să demonstrez că algoritmul se oprește, că $x$ este într-adevăr logaritmul discret și că funcționează în timp polinomial. Pentru ca algoritmul să se oprească, trebuie doar să verificăm asta $m_{i+1}<m_i~\forall~i$, ceea ce este echivalent cu a arăta că $\text{ord}(b_{i+1})<\text{ord}(b_i)$. Dacă $\text{ord}(b_i)=2^l$ atunci:
$$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$$
ceea ce demonstrează că $\text{ord}(b_{i+1})\leq\text{ord}(b_i)$, dar nu reușesc să obțin inegalitatea strictă. Pentru celelalte două părți nu am nicio idee bună despre cum să o rezolv...
Sunt un matematician care este începător în criptografie, așa că nu mă deranjează dacă îți asumi cunoștințe de matematică, cu care sunt obișnuit. Multumesc pentru ajutor.
