Pohlig–Hellman algorithm: Difference between revisions

Revision as of 15:11, 28 April 2022

Latest revision as of 18:44, 19 October 2024

(7 intermediate revisions by 6 users not shown)

Line 1:

{{Short description|Algorithm for computing logarithms}}

[[File:Pohlig-Hellman-Diagram.svg|thumb|350px|alt=Pohlig Hellman Algorithm|Steps of the Pohlig–Hellman algorithm.]]

In [[group theory]], the '''Pohlig–Hellman algorithm''', sometimes credited as the '''Silver–Pohlig–Hellman algorithm''',<ref name="Mollin06p344">[[#Mollin06|Mollin 2006]], pg. 344</ref> is a special-purpose [[algorithm]] for computing [[discrete logarithm]]s in a [[finite abelian group]] whose order is a [[smooth integer]].

The algorithm was introduced by Roland Silver, but first published by [[Stephen Pohlig]] and [[Martin Hellman]], who credit Silver with its earlier (independent ofbut unpublished discovery. Pohlig and Hellman also list Richard Schroeppel and H. Block as having found the same algorithm, later than Silver), but again without publishing it.{{citation neededsfn|date=October 2020Pohlig|Hellman|1978}}

== Groups of prime-power order ==

Line 18 ⟶ 19:

:## Set <math>x_{k+1}:=x_k+p^kd_k</math>.

:# Return <math>x_e</math>.

Assuming <math>e</math> is much smaller than <math>p</math>, theThe algorithm computes discrete logarithms in time complexity [[Big O notation|<math>O(e\sqrt p)</math>]], far better than the [[Baby-step giant-step|baby-step giant-step algorithm's]] [[Big O notation|<math>O(\sqrt{p^e})</math>]] when <math>e</math> is large.

== The general algorithm ==

Line 33 ⟶ 34:

:# Solve the simultaneous congruence <math display="block">x\equiv x_i\pmod{p_i^{e_i}}

\quad\forall i\in\{1,\dots,r\}

\text{.}</math>The [[Chinese remainder theorem]] guarantees there exists a unique solution <math>x\in\{0,\dots,n-1\}</math>.

:# Return <math>x</math>.

The correctness of this algorithm can be verified via the [[Abelian group#Classification|classification of finite abelian groups]]: Raising <math>g</math> and <math>h</math> to the power of <math>n/p_i^{e_i}</math> can be understood as the projection to the factor group of order <math>p_i^{e_i}</math>.

Line 45 ⟶ 46:

==References==

*{{cite book|title=An Introduction To Cryptography|url=https://archive.org/details/An_Introduction_to_Cryptography_Second_Edition|last=Mollin|first= Richard|date=2006-09-18|publisher=Chapman and Hall/CRC|edition=2nd|isbn=978-1-58488-618-1|page=[https://archive.org/details/An_Introduction_to_Cryptography_Second_Edition/page/n353 344]|ref=Mollin06}}

*{{cite journal | authorsfirst1=S. |last1=Pohlig and [[|author2-link=Martin Hellman|first2=M. |last2=Hellman]] | title=An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance | journal=IEEE Transactions on Information Theory | issue=24 | year=1978 | pages=106–110 | doi=10.1109/TIT.1978.1055817 | url=http://www-ee.stanford.edu/~hellman/publications/28.pdf}}

*{{cite book|first1=Alfred J.|last1=Menezes|author-link1=Alfred Menezes|first2=Paul C.|last2=van Oorschot|author-link2=Paul van Oorschot|first3=Scott A.|last3=Vanstone|author-link3=Scott Vanstone|title=Handbook of Applied Cryptography|url=https://archive.org/details/handbookofapplie0000mene/page/107|publisher=[[CRC Press]]|year=1997|pages=[https://archive.org/details/handbookofapplie0000mene/page/107 107–109]|chapter=Number-Theoretic Reference Problems|chapter-url=http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf|isbn=0-8493-8523-7|ref=Menezes97|url-access=registration}}