How does the Pohlig-Hellman algorithm work?

[mathmari]

Hey!

I am studying Cryptology right now and I am facing some difficulties to understand the Pohlig-Hellman algorithm.

Could you explain to me how the algorithm works??

Could you give me a step by step example??

(Wondering)

 

[mathmari]

I read an example... Could you tell me if I have understood it correct??

If we want to find for example $x$ such that $7=2^x$ in $\mathbb{Z}_{29}^{\star}$ we do the following:

The order of the group os $28=2^2 \cdot 7$.

- $y_0=7^7\equiv 1 \pmod {29}, g_0=2^7\equiv 12 \pmod {29}, g_1=g_0^{2^{2-1}}=g_0^2=12^2\equiv 28 \pmod {29}$

We write $x$ in the basis $2$, $x=a_0+2a_1, a_0, a_1 \in \{0, 1\}$.

$ord(12) \mid 28 \Rightarrow ord(12) \mid 2^2 \cdot 7$

$12^{\frac{28}{2}}=12^{14}=28\neq 1 \Rightarrow 2^2 \mid ord(12) \ \ , \ \ 12^{\frac{28}{7}}=12^4=1$

Can we conclude from here that $ord(12)=4$ ??

$1=12^x \Rightarrow 1=12^{a_0+2a_1} \Rightarrow 1=12^{2a_0+4a_1} \Rightarrow 1=(12^2)^{a_0}(12^4)^{a_1} \Rightarrow 1=(12^2)^{a_0} \Rightarrow 1=28^{a_0} \Rightarrow 1=(-1)^{a_0} \Rightarrow a_0=0$

$1=12^{2a_1} \Rightarrow 1=(12^2)^{a_1} \Rightarrow 1=(-1)^{a_1} \Rightarrow a_1=0$

So, we have that $$x \equiv 0+2 \cdot 0 \pmod 4 \Rightarrow x \equiv 0 \pmod 4$$

- $y_0=7^4\equiv 23 \pmod {29}, g_0=2^4=16, g_1=g_0=16$

$23=16^x$

$16^0=1, 16^1=16, 16^2=24, 16^3=7, 16^4=25, 16^5=23$

So, we have that $$x \equiv 5 \pmod 7$$

We have $$x \equiv 0 \pmod 4 \\ x \equiv 5 \pmod 7$$ From the Chinese remainder theorem we get $$x \equiv 12 \pmod {28}$$

Is this correct?? (Wondering)