模p的算法复杂度

来源：百度知道编辑：UC知道时间：2024/06/18 01:14:34

我想知道求一个数a模p用计算机如何实现，并且这种方法的算法复杂度是多少？谢谢各位了！

计算机CPU内有除法器，对一个普通的数球模复杂度O(1),比如32位的计算机，对于32位以内得整形做模运算可以直接通过硬件实现，复杂度O(1)；
对于高精度模低精度数，只能编程序计算，复杂度是O（n），n是被除数的位数
而对于高精度模高精度，复杂度很高，是O（N^2*logN)