Talk:Pohlig–Hellman algorithm

Polynomial time in what? Watson Ladd 23:38, 9 March 2006 (UTC)[reply]

Good point. Quuxplusone's remark at the end of Smooth number looks a bit more accurate. However, if you apply his comment to a sequence of groups with order 3, 9, 27,... then the time taken by Pohlig-Hellman should have a maximum, which is clearly not the case. Perhaps it should be O(B^1/2 log_B|G|) ? -- Nic Roets 19:36, 7 April 2006 (UTC)[reply]

This whole page is pretty cryptic; there are a few conceptual gaps that are left to the reader to have already known.