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 $p$ elementach, rząd jego grupy multiplikatywnej wynosi $p-1.$ Szukamy takiego $x,$ że: $g^{x}=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 $p^{a}$

$|G|=|F_{p}^{*}|=p-1=p_{1}^{\alpha _{1}}\cdot p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{n}^{\alpha _{n}}.$

Dla każdego $p_{i}$ obliczamy:

$r_{i}={\frac {|G|}{p_{i}^{\alpha _{i}}}}.$

Z kongruencji:

$(g^{x})^{r_{i}}\equiv h^{r_{i}}{\pmod {p}}$

możemy łatwo otrzymać układ kongruencji:

$x\equiv x_{i}{\pmod {p_{i}^{\alpha _{i}}}}$

(poszczególne $x_{i}$ można otrzymać jako $x_{i}=x\mod p^{\alpha _{i}}$),

które następnie możemy rozwiązać przy pomocy chińskiego twierdzenia o resztach.

KROK 2: Jeżeli w rozkładzie $p-1$ występuje jakaś duża potęga liczby pierwszej $q^{\alpha },$ redukujemy DLP w grupie rzędu $q^{\alpha }$ do kilku problemów w grupach rzędu $q{:}$

Przyjmijmy $q:=p_{i}$ i

$a:=g^{r_{i}}{\pmod {p}}$

oraz

$b:=h^{r_{i}}{\pmod {p}}.$

Wówczas:

$a^{m_{0}+m_{1}q+\ldots +m_{\alpha -1}q^{\alpha -1}}\equiv b{\pmod {p}}.$

Podnosząc obie strony kongruencji do potęgi $q^{\alpha -1},$ możemy obliczyć $m_{0},$ następnie znów zapisujemy kongruencję:

$a^{m_{1}q+\ldots +m_{\alpha -1}q^{\alpha -1}}\equiv ba^{-m_{0}}{\pmod {p}}$

i podnosząc obie strony do potęgi $q^{\alpha -2},$ otrzymamy $m_{1}$ itd.

Mając wszystkie $m_{i},$ otrzymamy:

$x\equiv m_{0}+m_{1}q+\ldots +m_{\alpha -1}q^{\alpha -1}{\pmod {q^{\alpha }}}.$

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 na zagadnieniu logarytmu dyskretnego ma być bezpieczny, jeżeli opiera się na grupach $GF(p),$ to $p-1$ musi mieć w rozkładzie na czynniki pierwsze co najmniej jedną dużą liczbę pierwszą. Stąd często obiera się jako $p$ liczbę postaci $2q+1,$ gdzie zarówno $p,$ jak i $q$ są pierwsze. $p,$ które posiadają taką własność, nazywa się liczbami pierwszymi Sophie Germain.