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 ${\displaystyle p}$ elementach, rząd jego grupy multiplikatywnej wynosi ${\displaystyle p-1.}$ Szukamy takiego ${\displaystyle x,}$ że: ${\displaystyle g^{x}=h,}$ gdzie ${\displaystyle g}$ jest generatorem grupy multiplikatywnej tego ciała, a ${\displaystyle h}$ elementem tego ciała.

KROK 1: Redukujemy DLP (ang. discrete logarithm problem) do analogicznego zagadnienia w grupach rzędu ${\displaystyle p^{a}}$

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

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

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

Z kongruencji:

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

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

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

(poszczególne ${\displaystyle x_{i}}$ można otrzymać jako ${\displaystyle 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 ${\displaystyle p-1}$ występuje jakaś duża potęga liczby pierwszej ${\displaystyle q^{\alpha },}$ redukujemy DLP w grupie rzędu ${\displaystyle q^{\alpha }}$ do kilku problemów w grupach rzędu ${\displaystyle q{:}}$

Przyjmijmy ${\displaystyle q:=p_{i}}$ i

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

oraz

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

Wówczas:

${\displaystyle 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 ${\displaystyle q^{\alpha -1},}$ możemy obliczyć ${\displaystyle m_{0},}$ następnie znów zapisujemy kongruencję:

${\displaystyle 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 ${\displaystyle q^{\alpha -2},}$ otrzymamy ${\displaystyle m_{1}}$ itd.

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

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