9

我正在尝试实现 SAFER+ 算法。该算法需要找到幂函数的模数，如下所示：

pow(45, x) mod 257

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

如何执行此计算？

4

4 回答 4

21

一些伪代码

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)
于 2011-11-27T16:56:40.913 回答
13

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

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

  1. 首先计算 45^2、45^4、45^8 mod 257：

    45^2 模 257 = 2025 模 257 = 226

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

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

  2. 然后使用 13 的二进制展开将这些组合起来得到结果：

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

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

    45^13 模 257 = 8550 * 120 模 257

    45^13 模 257 = 69 * 120 模 257

    45^13 模 257 = 8280 模 257

    45^13 模 257 = 56

请注意，计算的中间结果永远不会大于 257*257，因此可以轻松地以 32 位整数类型执行。

于 2011-11-27T17:00:20.493 回答
5

基本方法是根据指数位进行平方或相乘，并在每一步执行模归约。该算法称为（二进制）模幂运算。

于 2011-11-27T16:56:33.993 回答
3

考虑简单的身份：

mod(A^2,p) = mod(A,p)*mod(A,p)

另请注意

A^4 = (A^2)^2

如果您知道要计算的最终指数的二进制表示，则可以轻松计算其他幂。

于 2011-11-27T17:14:48.443 回答