V bistvu je bilo potrebno razbiti Diffie-Hellmanov postopek izmenjave ključev za podano bazo, modul in javne ključe.
Za kaj gre, si lahko preberemo v originalni nalogi ali na Wikipediji.
Izračunati je potrebno diskretni logaritem in nato potenco z modulom.
Diskretni logaritem moramo sprogramirati sami in ker številke niso
prevelike, deluje hitro. Potenciranje z modulom pa Python že ima:
funkcija pow(x, y, m)
vrne x ** y % m
, le da
to izračuna hitrejše, kot če bi najprej računala potenco in potem
ostanek. Rešitev je torej:
from itertools import count
def disc_log(base, x, m):
= 1
n for y in count():
if n == x:
return y
else:
= (n * base) % m
n
= 20201227
m = disc_log(7, 5764801, m)
d print(pow(17807724, d, m))
14897079