大数幂的模运算

题目

  我们知道对于像 7%2,3%5这样的题,计算机很容易算出它们的结果,但是如果我们需要计算 7123456789%65536这样的值呢,这时普通的计算方式可能就要花费很久的时间了,有没有简单的方法可以算出来这类大数的模呢?

分析

假设我们有整数a, b与除数m ,那么假设
a % m = j , b % m = t , 有整数 i , s , 使
a=im+jb=sm+t
所以有
a⋅b=(im+j)⋅(sm+t)=ism2+jsm+itm+jt
推出
(a⋅b)modm=(ism2+jsm+itm+jt)modm=jtmodm=((amodm)(bmodm))modm
所以
对于像7123456789%65536这样的大数幂模运算,我们可以把大数幂m拆分成形如m=m1+m2+...+mn这样的形式,那么nm=nm1+m2+...+mn=nm1nm2⋅...nmn,这样通过上面的公式我们就可以很容易算出大数幂了.
因为
abcmodm=((ab)⋅c)modm=(((ab)modm)(cmodm))modm=(((amodm)(bmodm)modm)(cmodm))modm
依次类推既可. 我们再考虑大数幂m要如何分解成形如m=m1+m2+...+mn的形式.
观察211