Diskreta logaritmo
En matematiko, diskreta logaritmo estas grupa analogo de ordinara logaritmo.
Estu multiplika grupo de entjeroj module n (Zp)×, kiu estas la aro de entjeroj {1, …, p − 1} sub multipliko module la primo p.
Se oni bezonas trovi la k-an potencon de unu el la nombroj en ĉi tiu grupo, oni povas fari ĉi tion per trovo de ĝia k-a potenco kiel entjero kaj tiam trovo la resto post divido per p. Ĉi tiu procezo estas la diskreta potencigo. Ekzemple, estu (Z17)×. Por komputi 34 en ĉi tiu grupo, oni unue komputu 34 = 81, kaj tiam dividu 81 per 17, ricevante reston 13. Tial 34 = 13 en la grupo (Z17)×.
Diskreta logaritmo estas la inversa operacio. Estu donite ke 3k ≡ 13 (mod 17), kio estas la k? Reale, estas malfinie multaj respondoj, pro la modula naturo de la problemo; oni tipe strebas al la plej malgranda nenegativa respondo, kiu estas k=4.
La problemo de komputado de diskreta logaritmo similas al problemo de entjera faktorigo, ĉar
- Ambaŭ problemoj estas malfacilaj, ne estas sciataj kompetentaj algoritmoj (kun polinoma tempo por ne-kvantuma komputilo)
- Algoritmoj de unu problemo estas ofte adaptitaj al la alia
- La malfacileco de ambaŭ problemoj estas uzata por konstrui ĉifrikajn sistemojn.
La naiva algoritmo por komputado de diskreta logaritmo estas per testado de ĉiuj eroj de la grupo, la rula tempo estas lineara de amplekso de la grupo kaj tial eksponenta tempo de kvanto de ciferoj.