Redukcja Pohliga-Hellmana

Szablon:Dopracować 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 \dots \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}(\mathrm{mod}p)$

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

$x\equiv x_i(\mathrm{mod}{p}_i^{{\alpha }_i})$

(poszczególne $x_i$ można otrzymać jako $x_i=xmod{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}(\mathrm{mod}p)$

oraz

$b:=h^{r_i}(\mathrm{mod}p).$

Wówczas:

$a^{m_0+m_{1}q+\dots +m_{\alpha -1}{q}^{\alpha -1}}\equiv b(\mathrm{mod}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+\dots +m_{\alpha -1}{q}^{\alpha -1}}\equiv b{a}^{-m_0}(\mathrm{mod}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+\dots +m_{\alpha -1}{q}^{\alpha -1}(\mathrm{mod}{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.