MHB How does the Pohlig-Hellman algorithm work?

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Algorithm
AI Thread Summary
The discussion focuses on the Pohlig-Hellman algorithm, specifically how to solve for \( x \) in the equation \( 7 = 2^x \) within the group \( \mathbb{Z}_{29}^{\star} \). The user outlines their understanding of the algorithm, detailing the steps taken to determine the order of the group and the calculations involving modular arithmetic. They conclude with a series of congruences, ultimately applying the Chinese remainder theorem to find \( x \equiv 12 \pmod{28} \). The user seeks confirmation on the correctness of their approach and results. The discussion highlights the algorithm's application in discrete logarithm problems.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Last edited by a moderator:
Mathematics news on Phys.org
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)
 
Last edited by a moderator:
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Back
Top