Revision as of 17:26, 3 April 2010 edit Michael Hardy (talk \| contribs) Administrators 210,577 edits further such cleanups: neither the parentheses nor the word "mod" should be italicized here; see WP:MOSMATH; also some other math notation edits ← Previous edit		Revision as of 04:57, 7 April 2010 edit undo 32.165.75.152 (talk) →Complexity Next edit →
Line 18: ==Complexity== The worst-~~came~~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_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>.

Pohlig–Hellman algorithm: Difference between revisions