Diskreetse logaritmi lahendaja

Kuidas töötab

See tööriist teostab otsingupõhise kontrolli: alustades astendajast 0 ja väärtusest 1, korrutab see järjest alusega g ja võtab mooduli p. Iga sammu järel võrreldakse tulemust h-ga (normaliseerituna mooduli p järgi). Kui leitakse vaste, tagastatakse vastav astendaja; kui p kontrolli jooksul vastet ei leita, teatatakse, et lahend puudub.

Näide

Vaikimisi väärtused on g=2, h=8, p=13. Arvutus: 2^0=1, 2^1=2, 2^2=4, 2^3=8. Seega x=3, sest 2^3 mod 13 = 8.

Piirangud

• Moodul p peab olema täisarv vahemikus 2 kuni 1 000 000.
• Otsing on ammendav (O(p)), seega suurte p väärtuste korral võib arvutus olla aeglane.
• Tööriist ei eelda, et p oleks algarv, ega tõesta, et g genereerib multiplikatiivse rühma.
• Kui g ja p ei ole ühistegurita, võib jada lüheneda, kuid piiratud otsing leiab siiski esimese sobiva astendaja.

Korduma kippuvad küsimused

Kas see tööriist sobib krüptograafiliste võtmete murdmiseks?

Ei. See on õppeotstarbeline ammendav otsing, mis on piiratud mooduliga kuni 1 000 000. Reaalsed krüptograafilised moodulid on nii suured, et selline otsing pole teostatav.

Mida teha, kui h on negatiivne või suurem kui p?

Tööriist normaliseerib h väärtuse mooduli p järgi, seega võrreldakse jääki. Näiteks h = -5 ja p = 13 korral kasutatakse jääki 8.

Kas tulemus on alati õige?

Jah, piiratud vahemikus. Kui lahend eksisteerib, leiab tööriist esimese astendaja, mis rahuldab võrduse. Kui lahendit pole, teatab ta sellest.