Pohlig–Hellman algorithm: Difference between revisions

Revision as of 01:10, 27 June 2019

Revision as of 01:11, 27 June 2019

Line 38:

==Complexity==

The worst-case input for the Pohlig–Hellman algorithm is a group of prime order: In that case, it degrades to the [[babyBaby-step giant-step|Babybaby-step giant-step algorithm]], hence the worst-case time complexity is <math>\mathcal O(\sqrt n)</math>. However, it is much 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 is <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==