Talk:Pohlig-Hellman algorithm

From Wikipedia, the free encyclopedia

This article is within the scope of WikiProject Mathematics.
Mathematics grading:	Stub Class	Importance unassessed.	Field unassessed.

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

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)