Content deleted Content added
Criminy! Not sure the previous author understood the algorithm. (How do we use the fact that |G| is smooth?) |
No edit summary |
||
Line 1:
In [[number theory]], the '''Pohlig–Hellman algorithm''' sometimes credited as the '''Silver-Pohlig-Hellman algorithm'''<ref>{{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> 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 22:
<math>O(\sum_i {e_i(\log n+\sqrt p_i)})</math>.
==References==
{{Reflist}}
# {{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 | authors=A. Menezes, P. van Oorschot, S. Vanstone | title=[http://www.cacr.math.uwaterloo.ca/hac/ Handbook of Applied Cryptography] | publisher=[[CRC Press]] | year=1997 | pages=107–109 | isbn=0-8493-8523-7}}
| |||