Content deleted Content added
fixed book citation |
m added ref |
||
Line 20:
==Complexity==
The worst-case time complexity of the Pohlig–Hellman algorithm is <math>O(\sqrt n)</math> for a group of order ''n'', but it is more efficient if the order is smooth. Specifically, if <math>\prod_i p_i^{e_i}</math> is the prime factorization of ''n'', then the complexity can be stated as
<math>O(\sum_i {e_i(\log n+\sqrt p_i)})</math>.<ref name="Menezes97p108">[[#Menezes97|Menezes, et. al 1997]], pg. 108</ref>
==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|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}}
| |||