Pohlig–Hellman algorithm: Difference between revisions

Revision as of 01:10, 27 June 2019

Latest revision as of 18:44, 19 October 2024

(23 intermediate revisions by 18 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-HellmanPohlig–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 discoveredintroduced by Roland Silver, but first published by [[Stephen Pohlig]] and [[Martin Hellman]], (independentwho ofcredit Silver) with its earlier independent but unpublished discovery.<!--{{Citation needed}}Pohlig begin-->{{fixand |link=Wikipedia:CitationHellman neededalso |text=citationlist neededRichard |class=Template-FactSchroeppel }}<!--and H. Block as having found the same algorithm, later than Silver, but again without publishing it.{{Citation neededsfn|Pohlig|Hellman|1978}} end-->

== Groups of prime-power order ==

As an important special case, which is used as a subroutine in the general algorithm (see below), the Pohlig-HellmanPohlig–Hellman algorithm applies to [[Group_Group (mathematics)|groups]] whose order is a [[prime power]]. The basic idea of this algorithm is to iteratively compute the <math>p</math>-adic digits of the logarithm by repeatedly "shifting out" all but one unknown digit in the exponent, and computing that digit by elementary methods.

(Note that for readability, the algorithm is stated for cyclic groups — in general, <math>G</math> must be replaced by the subgroup <math>\langle g\rangle</math> generated by <math>g</math>, which is always cyclic.)

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/2})</math>]] when <math>e</math> is large.

== The general algorithm ==

In this section, we present the general case of the Pohlig-HellmanPohlig–Hellman algorithm. The core ingredients are the algorithm from the previous section (to compute a logarithm modulo each prime power in the group order) and the [[Chinese remainder theorem]] (to combine these to a logarithm in the full group).

(Again, we assume the group to be cyclic, with the understanding that a non-cyclic group must be replaced by the subgroup generated by the logarithm's base element.)

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>.

==Complexity==

The worst-case input for the Pohlig–Hellman algorithm is a group of prime order: In that case, it degrades to the [[babyBaby-step giant-step|Babybaby-step giant-step algorithm]], hence the worst-case time complexity is <math>\mathcal O(\sqrt n)</math>. However, it is much more efficient if the order is smooth: Specifically, if <math>\prod_i p_i^{e_i}</math> is the prime factorization of <math>n</math>, then the algorithm's complexity is <math display="block">\mathcal O\left(\sum_i {e_i(\log n+\sqrt {p_i})}\right)</math> group operations.<ref name="Menezes97p108">[[#Menezes97|Menezes, et. al. 1997]], pg. 108</ref>

==Notes==

Line 44 ⟶ 45:

==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|authorlink1author-link1=Alfred Menezes|first2=Paul C.|last2=van Oorschot|authorlink2author-link2=Paul van Oorschot|first3=Scott A.|last3=Vanstone|authorlink3author-link3=Scott Vanstone|title=Handbook of Applied Cryptography|url=httphttps://wwwarchive.cacr.math.uwaterloo.caorg/hacdetails/handbookofapplie0000mene/page/107|publisher=[[CRC Press]]|year=1997|pages=[https://archive.org/details/handbookofapplie0000mene/page/107 107–109]|chapter=Number-Theoretic Reference Problems|chapterurlchapter-url=http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf|isbn=0-8493-8523-7|ref=Menezes97|url-access=registration}}

{{Number-theoretic algorithms}}