蒙哥马利幂模运算 (快速幂取模算法) 的 JS （Javascript）实现 （注意用到了BigInt）

默认分类 2018/09/17 09:56

代码如下：

function rfs(a, b, c) {
    let res = 1n
    a = a % c
    while(b > 0n) {
        if(b % 2n == 1n) res = (res * a) % c
        a = (a * a) % c
        b = b / 2n
    }
    return res
}

示例如下：

>> 289898989n**1000000067676767676726372637674637264724736267n%29n
VM228:1 Uncaught RangeError: Maximum BigInt size exceeded
    at <anonymous>:1:11
(anonymous) @ VM228:1
>> rfs(289898989n,1000000067676767676726372637674637264724736267n,29n)
7n

说明：即便是在Chrome下使用BigInt也是有大小范围限制的即(2n ** 32n - 1n) ** (2n ** 30n - 1n) 也即4294967295n**1073741823n，详见https://www.jwz.org/blog/2018/08/dark-rock-of-mothrir-unsealed-javascript-has-integers-now/ 因此直接使用

289898989n**1000000067676767676726372637674637264724736267n%29n

是会超出范围限制，这时候就要求助 蒙哥马利幂模运算 (快速幂取模算法) 了， 原理很简单就是先将幂模运算转化为乘模运算，简化了除法的复杂度

>> 留言评论