2的幂的模幂 [英] Modular Exponentiation over a Power of 2

问题描述

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

So I've been doing some work recently with the modpow function. One of the forms I needed was Modular Exponentiation when the Modulus is a Power of 2. So I got the code up and running. Great, no problems. Then I read that one trick you can make to get it faster is, instead of using the regular exponent, takes it's modulus over the totient of the modulus.

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

Now when the modulus is a power of two, the answer is simply the power of 2 less than the current one. Well, that's simple enough. So I coded it, and it worked..... sometimes.

由于某些原因，有些值不起作用，我只是弄不清楚它是什么.

For some reason there are some values that aren't working, and I just can't figure out what it is.

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;
}

这是一组不适用于的数字.

And this is one set of numbers that it doesn't work for.

Base = 593803430
Exponent = 3448538912
Modulus = 8

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

And no, there is no check in this function to determine if the Modulus is a power of 2. The reason is that this is an internal function and I already know that only Powers of 2 will be passed to it. However, I have already double checked to make sure that no non-powers of 2 are getting though.

感谢大家的帮助！

推荐答案

的确是，如果x 相对质数为n(x和n没有公因数)，则x ^ a = x ^(phi(a))(mod n)，其中phi是欧拉的上位函数.这是因为x属于(Z/nZ)乘法组，其阶为phi( a).

It's true that if x is relatively prime to n (x and n have no common factors), then x^a = x^(phi(a)) (mod n), where phi is Euler's totient function. That's because then x belongs to the multiplicative group of (Z/nZ), which has order phi(a).

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

But, for x not relatively prime to n, this is no longer true. In your example, the base does have a common factor with your modulus, namely 2. So the trick will not work here. If you wanted to, though, you could write some extra code to deal with this case -- maybe find the largest power of 2 that x is divisible by, say 2^k. Then divide x by 2^k, run your original code, shift its output left by k*e, where e is your exponent, and reduce modulo M. Of course, if k isn't zero, this would usually result in an answer of zero.

这篇关于2的幂的模幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！