Redukcja Pohliga-Hellmana

Redukcja Pohliga-Hellmana jest metodą obliczania logarytmu dyskretnego w ciele skończonym GF(p) wymyśloną przez Stephena Pohliga 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.