Pohlig–Hellman algorithm: Difference between revisions

Revision as of 22:25, 29 August 2010

Revision as of 16:11, 28 May 2011

Line 1:

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

The algorithm was discovered by Roland Silver, but first published by [[Stephen Pohlig]] and [[Martin Hellman]] (independent of Silver).

Line 14:

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

\end{align}

</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; precisely one will work, 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.)<br><br>

:#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 ''b''_''i'' the same way as before. <br>

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

Line 27:

==References==

*{{cite book|title=An Introduction To Cryptography|last=Mollin|first= Richard|date=2006-09-18|publisher=Chapman and Hall/CRC|edition=2nd|isbn=978-1584886181|page=344|ref=Mollin06}}

*{{cite journal | authors=S. Pohlig and [[Martin Hellman|M. Hellman]] | title=[http://www-ee.stanford.edu/~hellman/publications/28.pdf 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 | url=http://www-ee.stanford.edu/~hellman/publications/28.pdf}}

*{{cite book|first1=Alfred J.|last1=Menezes|authorlink1=Alfred Menezes|first2=Paul C.|last2=van Oorschot|authorlink2=Paul van Oorschot|first3=Scott A.|last3=Vanstone|authorlink3=Scott Vanstone|title=[http://www.cacr.math.uwaterloo.ca/hac/ Handbook of Applied Cryptography]|publisher=[[CRC Press]]|year=1997|pages=107–109|chapter=Number-Theoretic Reference Problems|chapterurl=http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf|isbn=0-8493-8523-7|ref=Menezes97}}

{{Number-theoretic algorithms}}

{{Numtheory-stub}}

[[Category:Number theoretic algorithms]]

{{Numtheory-stub}}

[[de:Pohlig-Hellman-Algorithmus]]