Redukcja Pohliga-Hellmana
![]() | Ten artykuł należy dopracować: od 2010-08 → zweryfikować treść i dodać przypisy, → poprawić styl – powinien być encyklopedyczny. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu. |
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.