模数大数的力量

Question

我正在尝试实施SAFER +算法.该算法需要找到幂函数的模数,如下所示:

pow(45, x) mod 257

变量x是一个字节,因此可以在0到255之间.因此,如果使用32位或64位整数实现,则幂函数的结果可能非常大,从而导致不正确的值.

我该如何进行此计算？

Answer 1

一些伪代码

function powermod(base, exponent, modulus) {
    if (base < 1 || exponent < 0 || modulus < 1)
        return -1

    result = 1;
    while (exponent > 0) {
       if ((exponent % 2) == 1) {
           result = (result * base) % modulus;
       }
       base = (base * base) % modulus;
       exponent = floor(exponent / 2);
    }
    return result;
}

并打电话

powermod(45, x, 257)    

Answer 2

通过重复平方执行取幂,每次操作后减少模数.这是一种非常标准的技术.

一个有效的例子45^13 mod 257:

1. 首先计算45 ^ 2,45 ^ 4,45 ^ 8 mod 257:

   45 ^ 2 mod 257 = 2025 mod 257 = 226

   45 ^ 4 mod 257 = 226 ^ 2 mod 257 = 51076 mod 257 = 190

   45 ^ 8 mod 257 = 190 ^ 2 mod 257 = 36100 mod 257 = 120

2. 然后使用13的二进制扩展来组合这些以获得结果:

   45 ^ 13 mod 257 = 45 ^ 1*45 ^ 4*45 ^ 8 mod 257

   45 ^ 13 mod 257 = 45*190*120 mod 257

   45 ^ 13 mod 257 = 8550*120 mod 257

   45 ^ 13 mod 257 = 69*120 mod 257

   45 ^ 13 mod 257 = 8280 mod 257

   45 ^ 13 mod 257 = 56

请注意,计算的中间结果永远不会大于257*257,因此可以很容易地以32位整数类型执行.

Answer 3

基本方法是根据指数位进行平方或乘法,并在每一步执行模数减少.该算法称为(二进制)模幂运算.