计算 a^p modulo m
的标准技巧是使用连续平方。其思想是将 p
展开为二进制,例如
p = e0 * 2^0 + e1 * 2^1 + ... + en * 2^n
其中(e0,e1,...,en)
是二进制数(0
或1
),且en = 1
。然后使用指数法则得到以下a^p
的展开式:
a^p = a^( e0 * 2^0 + e1 * 2^1 + ... + en * 2^n )
= a^(e0 * 2^0) * a^(e1 * 2^1) * ... * a^(en * 2^n)
= (a^(2^0))^e0 * (a^(2^1))^e1 * ... * (a^(2^n))^en
记住每个
ei
都是
0
或
1
,因此它们告诉您要取哪些数字。因此,您只需要进行以下计算。
a, a^2, a^4, a^8, ..., a^(2^n)
你可以通过对前一项进行平方来生成这个序列。由于你想要计算答案mod m
,所以你应该先进行模运算。这意味着你想要计算以下内容:
A0 = a mod m
Ai = (Ai)^2 mod m for i>1
答案就是这样
a^p mod m = A0^e0 + A1^e1 + ... + An^en
因此,计算需要log(p)
个平方和调用mod m
。
我不确定阶乘是否有类似的模运算,但一个好的起点是威尔逊定理。此外,您应该为m <= n
设置一个测试,在这种情况下,n!mod m = 0
。