Pohlig–Hellman algorithm: Difference between revisions

Revision as of 08:17, 24 August 2016

Latest revision as of 18:44, 19 October 2024

(42 intermediate revisions by 32 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 [[numbergroup 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 [[multiplicativefinite abelian group]] whose order is a [[smooth integer]].

The algorithm was discoveredintroduced 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.{{sfn|Pohlig|Hellman|1978}}

== Groups of prime-power order ==

We will explain the algorithm as it applies to the group '''Z'''^*_''p'' consisting of all the elements of '''Z'''_''p'' which are [[coprime]] to ''p'', and leave it to the advanced reader to extend the algorithm to other groups by using [[Lagrange's theorem (group theory)|Lagrange's theorem]].

As an important special case, which is used as a subroutine in the general algorithm (see below), the Pohlig–Hellman algorithm applies to [[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.)

:'''Input''' Integers ''p'', ''g'', ''e''.

:'''Output''' An Integer ''x'', such that ''e'' ≡ ''g''^''x'' (mod ''p'') (if one exists).

:'''Input.''' A cyclic group <math>G</math> of order <math>n=p^e</math> with generator <math>g</math> and an element <math>h\in G</math>.

:#Determine the prime factorization of the order of the group : <br><center><math>\varphi(p)= p_1\cdot p_2 \cdots p_n</math></center> (All the ''p''_''i'' are considered small since the group order is smooth.)

:'''Output.''' The unique integer <math>x\in\{0,\dots,n-1\}</math> such that <math>g^x=h</math>.

:#From the [[Chinese remainder theorem]] it will be sufficient to determine the values of ''x'' modulo each prime power dividing the group order. Suppose for illustration that ''p''₁ divides this order but ''p''₁² does not. Then we need to determine ''x'' mod ''p''₁, that is, we need to know the ending coefficient ''b''₁ in the base-''p₁'' expansion of ''x'', i.e. in the expansion ''x'' = ''a''₁ ''p''₁ + ''b''₁. We can find the value of ''b₁'' by examining all the possible values between 0 and ''p''₁-1. (We may also use a faster algorithm such as [[baby-step giant-step]] when the order of the group is prime.<ref name="Menezes97p109">[[#Menezes97|Menezes, et. al 1997]], pg. 109</ref>) The key behind the examination is that:<br> <center><math>

:# Initialize <math>x_0:=0.</math>

\begin{align}e^{\varphi(p)/p_1} & \equiv (g^x)^{\varphi(p)/p_1} \pmod{p} \\

:# Compute <math>\gamma:=g^{p^{e-1}}</math>. By [[Lagrange's theorem (group theory)|Lagrange's theorem]], this element has order <math>p</math>.

& \equiv (g^{\varphi(p)})^{a_1}g^{b_1\varphi(p)/p_1} \pmod{p} \\

:# For all <math>k\in\{0,\dots,e-1\}</math>, do:

& \equiv (g^{\varphi(p)/p_1})^{b_1} \pmod{p}

:## Compute <math>h_k:=(g^{-x_k}h)^{p^{e-1-k}}</math>. By construction, the order of this element must divide <math>p</math>, hence <math>h_k\in\langle\gamma\rangle</math>.

\end{align}

:## Using the [[Baby-step giant-step|baby-step giant-step algorithm]], compute <math>d_k\in\{0,\dots,p-1\}</math> such that <math>\gamma^{d_k}=h_k</math>. It takes time [[Big O notation|<math>O(\sqrt p)</math>]].

</math></center><br> (using [[Euler's theorem]]). With everything else now known, we may try each value of ''b''₁ to see which makes the equation be true. If <math>g^{\varphi(p)/p_1} \not\equiv 1 \pmod{p}</math>, then there is exactly one ''b''₁, and that ''b''₁ is the value of ''x'' modulo ''p''₁. (An exception arises if <math>g^{\varphi(p)/p_1} \equiv 1 \pmod{p}</math> since then the order of ''g'' is less than φ(''p''). The conclusion in this case depends on the value of <math>e^{\varphi(p)/p_1} \mod p</math> on the left: if this quantity is not 1, then no solution ''x'' exists; if instead this quantity is also equal to 1, there will be more than one solution for ''x'' less than φ(''p''), but since we are attempting to return only one solution ''x'', we may use ''b''₁=0.)

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

:#The same operation is now performed for ''p''₂ through ''p_n''.<br>A minor modification is needed where a prime number is repeated. Suppose we are seeing ''p_i'' for the (''k''&nbsp;+&nbsp;1)st time. Then we already know ''c_i'' in the equation ''x'' = ''a''_''i'' ''p''_''i''^''k''+1 + ''b''_''i'' ''p''_''i''^''k'' + ''c''_''i'', and we find either ''b''_''i'' or ''c''_''i'' the same way as before, depending on whether <math>g^{\varphi(p)/p_i} \equiv 1 \pmod{p}</math>.

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

:# With all the ''b''_''i'' known, we have enough simultaneous [[congruence relation|congruence]]s to determine ''x'' using the [[Chinese remainder theorem]].

The 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 ==

In this section, we present the general case of the Pohlig–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.)

:'''Input.''' A cyclic group <math>G</math> of order <math>n</math> with generator <math>g</math>, an element <math>h\in G</math>, and a prime factorization <math display="inline">n=\prod_{i=1}^rp_i^{e_i}</math>.

:'''Output.''' The unique integer <math>x\in\{0,\dots,n-1\}</math> such that <math>g^x=h</math>.

:# For each <math>i\in\{1,\dots,r\}</math>, do:

:## Compute <math>g_i:=g^{n/p_i^{e_i}}</math>. By [[Lagrange's theorem (group theory)|Lagrange's theorem]], this element has order <math>p_i^{e_i}</math>.

:## Compute <math>h_i:=h^{n/p_i^{e_i}}</math>. By construction, <math>h_i\in\langle g_i\rangle</math>.

:## Using the algorithm above in the group <math>\langle g_i\rangle</math>, compute <math>x_i\in\{0,\dots,p_i^{e_i}-1\}</math> such that <math>g_i^{x_i}=h_i</math>.

:# 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 timeinput complexityfor the Pohlig–Hellman algorithm is a group of prime order: In that case, it degrades to the Pohlig–Hellman[[Baby-step giant-step|baby-step giant-step algorithm]], hence the worst-case time complexity is <math>\mathcal O(\sqrt n)</math>. for a group of order ''n''However, but 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 canis be<math stateddisplay="block">\mathcal asO\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>

<math>O\left(\sum_i {e_i(\log n+\sqrt p_i)}\right)</math>.<ref name="Menezes97p108">[[#Menezes97|Menezes, et. al 1997]], pg. 108</ref>

==Notes==

Line 27 ⟶ 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}}