Pohlig–Hellman algorithm: Difference between revisions

Revision as of 12:48, 21 March 2017

Revision as of 13:06, 21 March 2017

Line 20:

==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 <math>n</math> butHowever, it is 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 can be stated asis <math display="block">\mathcal O\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>

==Notes==