# Day 25: Combo Breaker

(Povezava na nalogo)

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):
        n = 1
        for y in count():
            if n == x:
                return y
            else:
                n = (n * base) % m

    m = 20201227
    d = disc_log(7, 5764801, m)
    print(pow(17807724, d, m))

    14897079