Question

Use the Pohlig–Hellman algorithm (Theorem 2.32) to solve the discrete logarithm problem gx = a in Fp in each of the following cases.(a) p = 433, g = 7, a = 166.(b) p = 746497, g = 10, a = 243278.(c) p = 41022299, g = 2, a = 39183497. (Hint. p =2·295 + 1.)(d) p = 1291799, g = 17, a = 192988. (Hint. p−1 has a factor of 709.)

Answer 1

Answer:

(a) The solution is x=47.

(b) The solution is x=223755.

(c) The solution is x=33703314.

(d) The solution is x=984414.

Step-by-step explanation:

(a) Step 1 is to solve  

             

q    e        $h = g^{ (p-1)} /q$     $b = a^{(p-1)} /q$     $h^{y} = b$

2   4        265                   250                 Calculation I

3   3       374                    335                  Calculation II

Now Solving for calculation I:

x≡$x_{0} +x_{1} q+…+x_{e-1} q^{e-1} (mod\ 2^{4} )$≡$0x_{0}+2x_{1} +4x_{2} +8x_{3} (mod\ 2^{4} )$

Solve (265)x=250(mod 433) for x0,x1,x2,x3.

x0:(26523)x0=25023(mod 433)⟹(432)x0=432⟹x0=1

x1:(26523)x1=(250×265−x0)22(mod 433)=(250×265−1)22(mod433)=(250×250)22(mod 433)⟹(432)x1=432⟹x1=1

x2:(26523)x2=(250×265−x0−2x1)21(mod 433)=(250×265−3)22(mod 433)=(250×195)21(mod 433)⟹(432)x2=432⟹x2=1

x3:(26523)x3=(250×265−x0−2x1−4x2)20(mod 433)=(250×265−7)20(mod 433)=(250×168)20(mod 433)⟹(432)x3=432⟹x3=1

Thus, our first result is:

        x≡x0+2x1+4x2+8x3(mod24)≡1+2+4+8(mod24)≡15(mod24)

Now for Calculation II:

        x≡$x_{0} +x_{1} q+…+x_{e-1} q^{e-1} (mod\ 3^{3} )$≡ $x_{0}*0+3x_{1} +9x_{2} (mod3^{3})$

 

Solve (374)x=335(mod 433) for x0,x1,x2.

x0:(37432)x0=33532(mod 433)⟹(234)x0=198⟹x0=2. Note: you only needed to test x0=0,1,2, so it is clear which one x0 is.

x1:(37432)x1=(335×374−x0)31(mod 433)=(335×374−2)31(mod 433)=(335×51)31(mod 433)=1(mod 433)⟹(234)x1=1(mod 433)⟹x1=0

x2:(37432)x2=(335×374−x0−3x1)30(mod 433)=(335×374−2)30(mod 433)=(335×51)30(mod 433)=198(mod 433)⟹(234)x2=198(mod 433)⟹x2=2. Note: you only needed to test x2=0,1,2, so it is clear which one x2 is.

Thus, our second result is:

           x≡x0+3x1+9x2(mod 33)≡2+0+9×2(mod 33)≡20(mod 33)

Step 2 is to solve

x ≡15 (mod 24 ),

x ≡20 (mod 33 ).

The solution is x=47.

(b) Step 1 is to solve

q       e              $h = g^{ (p-1)} /q$     $b = a^{(p-1)} /q$        $h^{y} = b$

2       10            4168                   38277              523

3        6              674719               322735           681  

$h^{y} = b$ is calculated using same steps as in part(a).

Step 2 is to solve

x ≡ 523 (mod 210 ),

x ≡ 681 (mod 36 ).

The solution is x=223755 .

(c) Step 1 is to solve

q             e         $h = g^{ (p-1)} /q$     $b = a^{(p-1)} /q$                $h^{y} = b$

2             1         41022298               1                             0

29           5        4                              11844727              13192165

 

In order to solve the discrete logarithm problem modulo 295 , it is best to solve  it step by step. Note that 429 = 18794375 is an element of order 29 in F∗p . To  avoid notational confusion, we use the letter u for the exponents.

¢294

First solve 18794375u0 = 11844727

                                        = 987085.

The solution is u0 = 7.

The value of u so far is u = 7.

¢293

Solve 18794375u1 = 11844727·4−7

                               = 8303208.

The solution is u1 = 8.

The value of u so far is u = 239 = 7 + 8 · 29.

¢292

Solve 18794375u2 = 11844727 · 4−239

                                = 30789520.

The solution is

u2 = 26. The value of u so far is u = 22105 = 7 + 8 · 29 + 26 · 292 .

¢291

Solve 18794375u3 = 11844727 · 4−22105

                               = 585477.

The solution is

u3 = 18. The value of u so far is u = 461107 = 7 + 8 · 29 + 26 · 292 + 18 · 293 .

¢290

Solve 18794375u4 = 11844727 · 4−461107

                                = 585477.

The solution is

u4 = 18. The final value of u is u = 13192165 = 7 + 8 · 29 + 26 · 292 + 18 · 293 +  18 · 294 , which is the number you see in the last column of the table.

 

Step 2 is to solve

x ≡ 13192165 (mod 295 ).

x ≡ 0 (mod 2),

The solution is x=33703314 .

(d) Step 1 is to solve

q               e        $h = g^{ (p-1)} /q$     $b = a^{(p-1)} /q$     $h^{y} = b$

2               1           1291798           1                       0

709           1          679773             566657           322

911             1          329472            898549           534

To solve the DLP’s modulo 709 or 911, they can be easily solved by an exhaustive search on a computer, and a collision  algorithm is even faster.

Step 2 is to solve

x ≡ 0 (mod 2),

x ≡ 322 (mod 709),

x ≡ 534 (mod 911).

The solution is x=984414