快速幂取模
这是一个被应用在很多加密算法中的一个小算法
比如我们熟知的RSA加密
那前面铺垫了两期
今天我们终于开始拆解这个算法了哈
其实它只解决了一个问题
也就是说我们需要对一个数
进行大数的指数运算
能大到什么程度呢
一般来说
RSA的私钥涉及的相关数据
都是几百倍的数字
我们先来看一下
在java里尝试计算123的1234次方试试哈
大家注意
Infinity
好我们再来看Js
我们用Node啊
还是Infinity
结果就已经是Infinity了
所以先不说算几百次方的效率问题
单就说找一个数据类型来参与计算
都是个问题
就更别提所消耗的内存
和CPU的算力了
所以呢我们就需要一个算法
来将这么巨大的任务拆分开
做这件事之前
我们先来了解一个基础公式哈
就是a乘以b乘以c
可以继续乘
然后最终取模m
其实它和a乘以(b%m), 乘以c
然后继续乘
或者把c取模m
最终在取模m
它们是相等的
也就说当我们计算多个数的乘积
来取模m的时候
如果我们把其中的一个或者多个数
先做了取模m
其实也不影响整体的结果
其实这个原理很简单
我们来看7 取模
结果是
那么两个7取模4呢
从这个图里我们看出
其实跟两个3取膜4的效果是一样的
就类似我们玩消消乐一样
每一行先消掉4个
这也就变成了：7取模
再乘以
再取模4了
那多个乘数也是一样的哈
大家感兴趣可以自己研究一下
我们再回到视频开始的问题
为了方便
我们先取一个特殊的指数
为什么说它特殊呢
因为它的二进制是
它每一位都是一
也就是所谓的梅森数
所以呢根据前两期视频的结论
x的15次方就等于这个
然后再拆开括号的话
就等于：x∙x²∙x⁴∙x⁸
大家注意哈
这里边的每一个指数
都是前面数的指数的二倍
然后我们继续应用
视频开始提到的基础公式啊
把所有的数都先取模一次
m对结果也没有影响
那么x的15次方取模m就可以变成这样
注意
15的二进制有几位
前半部分这个方括号里就有几个乘数
好那么我们就先看前半部分
如果我们把这第一部分的x取模m
先看作H
那么第二部分
就可以通过两个x相乘的方式
最终拆解成这样
那这两个x%m
就又可以用 H1代替了
也就等于H1乘以H1取模m了
同理
我们再把“x平方取模m”看作H2的话
那么X的4次方曲目m
就等于两个H2相乘再取模m
所以刚才的式子左半部分
我们只需要算出x%m
之后就可以依次地算出
后面各个因式的值了
非梅森数做指数
我们后面再说哈
那到这里
就已经有点代码循环的样子了哈
接下来我们还差一步取模m
因为
我们还是不能直接把这里面结果
做相乘再取模
因为它还是会很大
所以
如果我们再把这些数看成a b c d的话
就变成这个样子
如果我们把a乘b当成一个整体
就又可以把a乘b再取模m了
以此类推呢
就是这样
也就说我们可以把…
a b c d一个一个的跟结果相乘
并且每次相乘后再取模m
其实结果是一样的
包括我们最开始的a可以先跟1相乘
用代码表示呢
就是这样
这是一个快速幂取模的一个方法
我们先设result等于
最后return result
然后把中括号里每一部分取模m的值
放到这个base边量来存储
这里呢我们先取第一个
然后我们就开始循环
循环的条件就是指数还大于
中途每次循环我们都会让指数右移一位 （砍掉二进制右侧最后一位）
直到变成
终止循环
循环里，每次
我们先把base累积到result的结果中
也就说它乘以result
再取模 mod
然后我们再更新base变量的值哈
让它等于它刚才的平方取模 mod
最后每次循环结束
我们记得把指数右移一位（砍掉二进制的最右边一位）
这个也可以通过整出2来实现啊
原理我们就参考上期视频
这样看起来是OK了
但是前面说了
这只是针对梅森数做指数
那么非美森数呢
其实也简单
区别只是在二进制下并不都是
比如是
对应的二进制就是
那么相对于x的15次方
x的13次方就变成这样
只是这一位变成了
但后面的还是没有变化
跟刚刚一样
我们继续拆分
到了这里呢
因为是乘法
所以这里的“1”其实就相当于没有了
但是后面的运算规律
跟刚才梅森数做指数是一样的
所以对应的循环里
我们只要碰到二进之位是
我们就不计入result就可以了
其他的还保持不变
就变成了最终这样
到这里呢
我们三期的视频
就浓缩成了这么一个方法
我们再用JS来验证一下啊
然后呢
我们先去尝试计算一个大一点的指数哈
比如123的1234567次方
大家看：Infinity
但是我们用这快速幂取模的算法呢
大家看啊
123的1234567次方
然后取模1313（随便找个模数），大家看 514
最后更新于
这有帮助吗？