使用加法链计算 (a^x)mod n。 C++中的算法

Question

unsigned long qe2(unsigned long x, unsigned long y , unsigned long n)
{
    unsigned long s,t,u;

    s=1; t=x; u=y;

    while(u)
    {
        if(u&1)
            s = (s*t)%n;
        u>>=1;
        t= ( t*t)%n;
    }
    return s;
}

我正在阅读密码学，在 Bruice Schneier 的 Applied Cryptography 一书中，我发现上述算法可以以较低的计算成本计算 (x^y)mod n。它基本上使用一种称为加法链接的算法来减少计算中的乘法量。我可以在笔和纸上使用这个过程，但是尽管一遍又一遍地阅读上面的代码，我还是无法理解它是如何工作的。所以请给我指出正确的方向（某种 link 到一篇文章），我可以在那里分析上面的算法，或者如果你能在这里给出解释，那将非常有帮助。

P.S。 : 书中没有解释代码

Answer 1

指数y写成二的幂之和，即二进制。

考虑一个实际例子：(x**11) % M。数学上，

(x**11) % M == ((((((x**1) % M) * x**2) % M) * x**8) % M)

这很有用，因为一个简单的循环就足以计算 x 的幂，即 2 的幂。例如，如果你想计算 x**(2**i):

for (j = 0; j < i; j++)
    x = x * x;

如果我们看一下计算 basis**exponent:

的函数，我们可以详细检查逻辑

unsigned long power(unsigned long basis,
                    unsigned long exponent)
{
    unsigned long result = 1u;
    unsigned long factor = basis;
    unsigned long i;

    for (i = 1u; i < exponent; i = i * 2u) {
        /* i is some power of two,
           and factor = basis**i.
        */

        /* If i is in the sum (of powers of two) for exponent,
           we include the corresponding power of basis
           in the product. */
        if (i & exponent)
            result = result * factor;

        /* Update factor for the next i. */
        factor = factor * factor;
    }

    return result;
}

注意测试(i & exponent)是二元与运算，如果结果非零则为真，为零则为假。因为 i 是 2 的幂，所以在二进制中它有一个 1 而所有其他二进制数字为零，所以它本质上是测试以二进制写的指数是否有一个 1那个位置。

OP 的代码更简单，因为它没有使用单独的变量 i 和 factor，而是将 exponent 右移（删除最右边的二进制数字），并使用 basis 本身。也就是说，

unsigned long power(unsigned long basis,
                    unsigned long exponent)
{
    unsigned long result = 1u;

    while (exponent > 0u) {
        if (exponent & 1u)
            result = result * basis;
        basis = basis * basis;
        exponent = exponent >> 1;
    }

    return result;
}

模运算是最后一个问题，但它也是微不足道的。如果计算乘积对某个正整数取模，则可以将取模运算符应用于每个项和每个临时结果，而不影响结果：

(a * b * c * d * ... * z) % m
= ( (a % m) * (b % m) * (c % m) * ... * (z % m) ) % m
= ( ... (((((a % m) * (b % m)) % m) * (c % m)) % m) * ... * (z % m)) % m

这显然很有用，因为您可以计算任意数量项的乘积，所有项都小于 m，所有中间项都小于 m*m。

这种求幂的时间复杂度是O(log N)，其中N是指数。

使用加法链计算 (a^x)mod n。 C++中的算法

Computing (a^x)mod n using addition chaining. Algorithm in C++

c++

math

cryptography

modular-arithmetic