Redukcja Pohliga-Hellmana
Z Wikipedii
Redukcja Pohliga-Hellmana jest metodą obliczania logarytmu dyskretnego w GF(p) wymyśloną przez Stephena Pohliga i Martina Hellmana.
Jeżeli mamy ciało skończone o p elementach, rząd jego grupy multiplikatywnej wynosi p-1. Szukamy takiego x, że: gx = h, gdzie g jest generatorem grupy multiplikatywnej tego ciała, a h elementem tego ciała.
- KROK 1: Redukujemy DLP (ang. Discrete logarithm problem) do analogicznego zagadnienia w grupach rzędu pa
Dla każdego pi obliczamy: 
z kongruencji: 
możemy łatwo otrzymać układ kongruencji: 
Które następnie możemy rozwiązać przy pomocy chińskiego twierdzenia o resztach.
- KROK 2: Jeżeli w rozkładzie p występuje jakaś duża liczba pierwsza, redukujemy DLP w grupie rzędu pa do kilku problemów w grupach rzędu p:
Załóżmy, że pi jest dużą liczbą pierwszą, dla której a > 1 oraz przyjmijmy q := pi oraz 
jako: 
wówczas: 
Podnosząc obie strony kongruencji do potęgi qa-1 możemy obliczyć m0 następnie znów zapisujemy kongruencję: 
i podnosząc obie strony do potęgi qa-2 otrzymamy m1 , itd. Mając wszystkie mi otrzymamy: 
Redukcja P-H pozwala na szybkie rozwiązanie DLP o ile p-1 ma w rozkładzie na czynniki pierwsze małe liczby pierwsze. Stąd jeżeli kryptosystem oparty o zagadnienie logarytmu dyskretnego ma być bezpieczny, jeżeli opiera się na grupach GF(a), to q-1 musi mieć w rozkładzie na czynniki pierwsze co najmniej jedną dużą liczbę pierwszą. Stąd często obiera się jako q, 2p+1, gdzie zarówno p jak i q są pierwsze.
