关于不基于 BSGS 的做法的复杂度

这题 @Determinant 和 @gxy001 讲了一个不基于 BSGS 的做法。大致是 Adleman–Manders–Miller 算法。这个做法的最终复杂度分析中，两位都忽略掉了 $\Theta(n)$ 这个项。

看起来这个因子人畜无害，毕竟指数能有多大呢？

但其实，对于素数 $p$，作为 $p-1$ 的一个素因子，$n$ 可以取到 $\Omega(p^{2/3})$。而且，根据 这里的结果，有正密度（即相当多）的素数可以做到这一点。

这意味着，这个算法的最差复杂度是 $\Omega(m^{2/3})$，甚至劣于基于 BSGS 的 $\Theta(m^{1/2})$。（忽略对模数做质因数分解和输出答案的复杂度）

如果这个分析有哪里出了问题，欢迎指出。