Pohlig–Hellman algorithm: Difference between revisions

Revision as of 09:16, 3 May 2010

Revision as of 01:42, 21 June 2010

Line 18:

==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>\sum_iprod_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>.