c++ - 2的幂的模幂

因此，最近我在使用modpow函数进行了一些工作。当模量为2的幂时，我需要的一种形式是模幂运算。因此，我启动了代码并开始运行。很好，没问题。然后我读到，可以更快地获得它的一个技巧是，使模数超过模数的总和，而不是使用正指数。

现在，当模数是2的幂时，答案就是比当前的1小2的幂。好吧，这很简单。所以我进行了编码，并且.....有时有效。

由于某些原因，有些值不起作用，我只是不知道它是什么。

uint32 modpow2x(uint32 B, uint32 X, uint32 M)
{
    uint32 D;

    M--;
    B &= M;
    X &= (M >> 1);
    D = 1;
    if ((X & 1) == 1)
    {
        D = B;
    }

    while ((X >>= 1) != 0)
    {
        B = (B * B) & M;
        if ((X & 1) == 1)
        {
            D = (D * B) & M;
        }
    }
    return D;
}

这是一组数字，不适用。

Base = 593803430
Exponent = 3448538912
Modulus = 8

不，该函数没有检查以确定Modulus是否为2的幂。原因是这是一个内部函数，我已经知道只有2的幂可以传递给它。但是，我已经仔细检查过以确保没有非2的幂。

感谢你们提供的任何帮助！

最佳答案

的确，如果x是n的素数（x和n没有公因数），则x ^ a = x ^（phi（a））（mod n），其中phi是Euler的totient函数。这是因为x属于multiplicative group of (Z/nZ)，其阶为phi（a）。

但是，对于x并非相对于n素数的情况，这不再成立。在您的示例中，基数与模数确实有一个公因数，即2。因此，该技巧在这里无效。但是，如果您愿意，可以编写一些额外的代码来处理这种情况-也许找到x可以被2整除的最大2幂，例如2 ^ k。然后将x除以2 ^ k，运行原始代码，将其输出向左移k * e，其中e是您的指数，并取模M。当然，如果k不为零，通常会得到答案零