Redukcja Pohliga-Hellmana
Z Wikipedii
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 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 pα do kilku problemów w grupach rzędu p:
Załóżmy, że pi jest dużą liczbą pierwszą, dla której α > 1 oraz przyjmijmy q := pi oraz
jako:
wówczas:
Podnosząc obie strony kongruencji do potęgi qα-1 możemy obliczyć m0 następnie znów zapisujemy kongruencję:
i podnosząc obie strony do potęgi qα-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 liczbę postaci 2p+1, gdzie zarówno p jak i q są pierwsze. p które posiadają taką własność nazywa się liczbami pierwszymi Sophie Germain .
