This exercise asks you to use the index calculus to solve a discrete logarithm p

Question

This exercise asks you to use the index calculus to solve a discrete logarithm problem. Let p = 19079 and g = 17.

(a) Verify that g^i (mod p) is 5-smooth for each of the values i = 3030, i = 6892, and i = 18312.

(b) Use your computations in (a) and linear algebra to compute the discrete loga- rithms log_g (2), log_g (3), and log_g (5). (Note that 19078 = 2 · 9539 and that 9539 is prime.)

(c) Verify that 19 · 17^12400 is 5-smooth.

(d) Use the values from (b) and the computation in (c) to solve the discrete loga-

rithm problem

17^x 19 (mod 19079).

Explanation / Answer

(a) Verify that g^i (mod p) is 5-smooth for each of the values i = 3030, i = 6892, and i = 18312.

g^i (mod p) is 14580 for i=3030 and al prime dividers of 14580 is ,<=5

g^i (mod p) is 18432 for i=6892 and al prime dividers of 18432 is ,<=5

g^i (mod p) is 6000 for i=18312 and al prime dividers of 6000 is ,<=5

(b) log_g (2)=17734

log_g (3)= 10838 , and

log_g (5)=17002

(c) Verify that 19 · 17^12400 is 5-smooth.

19 · 17^12400 mod( p)=7702

(d)

17^x 19 (mod 19079). ->13830 + 19078k

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.