求 高幂取模 的逆算法

来源：百度知道 编辑：UC知道 时间：2024/05/15 03:42:24
a^b=c（mod n)
已知a，c，n，求b
PS：
我知道怎么求c，现在需要的是已知a，c，n，求b的快速算法
如果各位感觉没有求b的好办法请给出论证，我不知道有没有算法求b

我刚才想了想。n比较小的情况下枚举b是可以实现的。算法复杂度是O(n)。
因为最多的(a^i) mod n的结果只有n种（己出现直接返回不可能）。
至于n比较大……唉。。算了。郁闷。。这几天傻。