Pohlig–Hellman algorithm: Difference between revisions

Revision as of 16:32, 29 August 2010

Revision as of 19:17, 29 August 2010

Line 1:

In [[number theory]], the '''Pohlig–Hellman algorithm''' sometimes credited as the '''Silver-Pohlig-Hellman algorithm'''<ref>{{cite book|titlename=An Introduction To Cryptography"Mollin06p344">[[#Mollin06|last=Mollin|first= Richard|date=2006-09-18|publisher=Chapman1997]], andpg. Hall/CRC|edition=2nd|isbn=978-1584886181|page=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 9:

:#Determine the prime factorization of the order of the group (the [[totient]] in this case) : <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.)

:#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-''b'' 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]] inwhen somethe casesorder 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>

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

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

Line 24:

==References==

{{Reflist}}

{{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}}

# {{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}}