模幂算法：快速求幂模运算

运算a mod n被称为模运算。像普通的运算一样，模运算也对应有加、减、乘、除、乘方等运算，而且满足交换律、结合律和分配律。

消去律：如果（a+b）≡（a+c）（mod n），则b≡c（mod n）；

如果（a×b）≡（a×c）（mod n）且gcd（a，n）=1（a与n互素），则b≡c（mod n）。

即加法的消去律是无条件的，乘法的消去律是有条件的。

另外，对每一个中间结果进行模n运算之后再进行普通运算等价于先进行普通运算之后的结果进行模n运算。例如

[a（mod n）±b（mod n）]（mod n）=（a±b）（mod n）

[a（mod n）×b（mod n）]（mod n）=（a×b）（mod n）

[（a×b）（mod n）+（a×c）（mod n）]（mod n）=[a×（b+c）]（mod n）

以上性质也说明在模运算过程中，同余的数完全可以被看做是等价的。因此，可以将模运算中较大的数用相对较小的同余数代替，简化计算，这在模的乘方运算（也称为模幂运算）中非常有用。模幂运算往往被分解为多次的模乘运算，以避免中间出现大的数。

【例11-12】 求2¹⁰⁰⁰的十进制表示中的最后两位数字。

【解析】 依题意，需要求2¹⁰⁰⁰mod 100。

因为 2²⁰=1024²≡76（mod 100）

76ⁿ≡76（mod 100）

所以 2¹⁰⁰⁰=（20²⁰）50≡76⁵⁰（mod 100）≡76（mod 100）

即2¹⁰⁰⁰的十进制表示中的最后两位数字是76。

下面考虑对于模幂运算a^mmod n的一般快速算法。

1.求a^mmod n的快速算法之一

设m的二进制表示为b_kb_k-1…b₁b₀，其中b_i为0或1，则

从而

【例11-13】 求9¹³mod 11的值。

【解析】 由于 13=（1101）₂

可按照下式计算：

9²=81≡4（mod 11）

9⁴=（9²）2≡4²（mod 11）≡5（mod 11）(www.xing528.com)

9⁸=（9⁴）2≡5²（mod 11）≡3（mod 11）

9¹³=9×9⁴×9⁸≡9×5×3（mod 11）=[（9×5）（mod 11）×3]（mod 11）≡3（mod 11）

即9¹³mod 11=3。

【例11-14】 求16⁷mod 4731的值。

【解析】 由于7=（111）₂

则i=0，16²⁰=16i=1，16²¹=256i=2，16²²=（256）2=65536≡4033（mod 4731）

所以16⁷≡16×256×4033（mod 4731）≡4096×4033（mod 4731）≡3247（mod 4731）

2.求a^mmod n的快速算法之二

算法步骤如下：

1）（X，M，Y）←（a，m，1）；

2）如果M=0，则输出Y，算法终止；

3）如果M为正的偶整数，则X←X²（mod n）；M←M/2；否则转4）；

4）Y←X×Y（mod n）；M←M-1，转2）。

【例11-15】 求16¹⁵mod 4731的值。

1）X←16，M←15，Y←1；

2）Y←16×1≡16（mod 4731），M←15-1=14；

3）X←16²≡256（mod 4731），M←14/2=7；

4）Y←256×16≡4096（mod 4731），M←7-1=6；

5）X←256²≡4033（mod 4731），M←6/2=3；

6）Y←4033×4096≡3247（mod 4731），M←3-1=2；

7）X←4033²≡4642（mod 4731），M←2/2=1；

8）Y←4642×3247≡4339（mod 4731），M←1-1=0；

9）M=0，输出16¹⁵≡4339（mod 4731）。