Redukcja Pohliga-Hellmana

Redukcja Pohliga-Hellmana jest metodą obliczania logarytmu dyskretnego w ciele skończonym GF(p) wymyśloną przez i Martina Hellmana. Jeżeli mamy ciało skończone o elementach, rząd jego grupy multiplikatywnej wynosi Szukamy takiego że: gdzie jest generatorem grupy multiplikatywnej tego ciała, a elementem tego ciała. KROK 1: Redukujemy DLP (ang. discrete logarithm problem) do analogicznego zagadnienia w grupach rzędu Dla każdego obliczamy: Z kongruencji: możemy łatwo otrzymać układ kongruencji: (poszczególne można otrzymać jako ), które następnie możemy rozwiązać przy pomocy chińskiego twierdzenia o resztach. KROK 2: Jeżeli w rozkładzie występuje jakaś duża potęga liczby pierwszej redukujemy DLP w grupie rzędu do kilku problemów w grupach rzędu Przyjmijmy i oraz Wówczas: Podnosząc obie strony kongruencji do potęgi możemy obliczyć następnie znów zapisujemy kongruencję: i podnosząc obie strony do potęgi otrzymamy itd. Mając wszystkie otrzymamy: Redukcja P-H pozwala na szybkie rozwiązanie DLP, o ile ma w rozkładzie na czynniki pierwsze małe liczby pierwsze. Stąd jeżeli kryptosystem oparty na zagadnieniu logarytmu dyskretnego ma być bezpieczny, jeżeli opiera się na grupach to musi mieć w rozkładzie na czynniki pierwsze co najmniej jedną dużą liczbę pierwszą. Stąd często obiera się jako liczbę postaci gdzie zarówno jak i są pierwsze. które posiadają taką własność, nazywa się liczbami pierwszymi Sophie Germain.