|
Ten artykuł należy 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
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
![{\displaystyle |G|=|F_{p}^{*}|=p-1=p_{1}^{\alpha _{1}}\cdot p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{n}^{\alpha _{n}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4bd97205d7e4e99238c690f62e8afe2a2cd51886)
Dla każdego
obliczamy:
![{\displaystyle r_{i}={\frac {|G|}{p_{i}^{\alpha _{i}}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55e1c7c784556cd00245990c4eeda6a4e3da5068)
Z kongruencji:
![{\displaystyle (g^{x})^{r_{i}}\equiv h^{r_{i}}{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96934f8ea69a3c0dc74a7d747ff2dc5ddc6e4480)
możemy łatwo otrzymać układ kongruencji:
![{\displaystyle x\equiv x_{i}{\pmod {p_{i}^{\alpha _{i}}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bd91e7e4ce08ca876112cd067c575d66b83f9c81)
(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
![{\displaystyle a:=g^{r_{i}}{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/baad7c876d30da25b06b51bcb293f42c59e35df2)
oraz
![{\displaystyle b:=h^{r_{i}}{\pmod {p}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b7562ceff28ce4ea5df469665ec946f7d5fff64)
Wówczas:
![{\displaystyle a^{m_{0}+m_{1}q+\ldots +m_{\alpha -1}q^{\alpha -1}}\equiv b{\pmod {p}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81b72df1e6243234dc3f00aef5caf0c19d116ace)
Podnosząc obie strony kongruencji do potęgi
możemy obliczyć
następnie znów zapisujemy kongruencję:
![{\displaystyle a^{m_{1}q+\ldots +m_{\alpha -1}q^{\alpha -1}}\equiv ba^{-m_{0}}{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/77c3f928235de897374119b2799fe201e137bae6)
i podnosząc obie strony do potęgi
otrzymamy
itd.
Mając wszystkie
otrzymamy:
![{\displaystyle x\equiv m_{0}+m_{1}q+\ldots +m_{\alpha -1}q^{\alpha -1}{\pmod {q^{\alpha }}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a23a6d2c45092f08398661fe1d4f06cfad47da41)
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.