返回列表

蒙哥马利幂模运算 (快速幂取模算法) 的 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

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