O(1)如果您使用硬件实现，则模运算处于打开状态。（原因是，对同一组有限的输入值集的每个操作都在 中O(1)）\n否则，任意长度整数的任何软件实现都应具有与相同输入数字的除法类似的复杂性。我不确定那到底是什么。
编辑：我有一种预感，O(n\xc2\xb2)但我还没有准备好证据。
EDIT2：确实很难对此提供完整且正确的答案，因为复杂性并不取决于问题而是取决于实现，因此不同的实现具有不同的复杂性，并且问题只能给出可实现性能的下限的求解算法。
\n\n然而，乘法复杂度尚不存在下限。由于模数的下界实际上取决于乘法的下界（请参阅评论中发布的链接。我读过它，这是好东西！），模数实现的复杂性也没有下界，并且因此我们无法准确估计模数可实现的性能。
\n\n但既然我们谈论的是 Big-O 表示法，我可以有把握地说 in 中任何像样的模实现O(n\xc2\xb2)，并且大多数都在 的较小子集中O(n\xc2\xb2)。