大数模幂运算

Question

我将尝试实现SAFER+算法。该算法需要找到幂函数的模数，步骤如下：

pow(45, x) mod 257

变量x是一个字节，因此可以从0到255范围内取值。因此，如果使用32位或64位整数实现幂函数，结果可能非常大，导致计算出现错误值。

我该如何进行这个计算？

- Eng. Aws

---

如果我没有完全错记，并且记得在模空间中计算幂的特殊公式，那么模演算是问题的重要部分，因此这个问题与编程语言无关。 - thiton

入门阅读：整数的乘法群。这对我来说太久远了，但也许有人还记得。 - thiton

这里有一个用C语言编写的SAFER+实现，您可以在此处学习：http://www.schneier.com/book-applied-source.html - Robert Harvey

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)    

- esskar

Answer 2

使用反复平方法进行指数运算，在每次操作后对模数进行缩小。这是一种非常标准的技术。

以下是一个实例：45^13 mod 257:

1. 首先计算45的2、4、8次幂对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位整数类型上执行此操作。

- Stephen Canon

Answer 3

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

- Brett Hale

Answer 4

考虑以下简单的等式：

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

请注意，还有一点需要注意的是：

A^4 = (A^2)^2

如果您知道要计算的最终指数的二进制表示，那么其他幂可以很容易地计算出来。

- user85109