模幂(模运算中的幂) [英] Modular Exponentiation (Power in Modular Arithmetic)

问题描述

你好！
我陷入了对模幂运算概念的了解.当我需要它以及它如何工作时.
假设我将幂函数调用为: power(2，n-1).
n = 10

Hello!
I am getting stuck in understanding the concept of modular Exponentiation. When i need this and how this works.
Suppose i am calling the power function as : power(2,n-1).
How the loops will be executed for say n=10

#define m 1000000007

unsigned long long int power(unsigned long long int x, unsigned long long int n){

    unsigned long long int res = 1;
    while(n > 0){
        if(n & 1){
            res = res * x;
            res = res % m;
        }
        x = x * x;
        x= x % m;
        n >>= 1;
    }
    return res;

}

推荐答案

从DAle链接的Wikipedia页面上的模定律(关于您的上一个问题)，我们可以获得两个公式:

From the modulo laws on DAle's linked Wikipedia page (on your previous question), we can obtain two formulas:

根据第一个公式，很明显，我们可以根据n / 2的结果迭代地计算n的模数.这是通过线条完成的

From the first formula it is clear that we can iteratively calculate the modulo for n from the result for n / 2. This is done by the lines

x = x * x;
x = x % m;

因此，算法中有log n个步骤，因为每次x的指数加倍.步数计数由n >>= 1和while (n > 0)完成，它们对log n步数进行计数.

There are thus log n steps in the algorithm, because each time the exponent of x doubles. The step counting is done by n >>= 1 and while (n > 0), which counts log n steps.

现在，您可能想知道1)为什么这部分没有设置res的值，以及2)这些行的目的是什么

Now, you may be wondering 1) why doesn't this part set the value of res, and 2) what is the purpose of these lines

if(n & 1){
   res = res * x;
   res = res % m;
}

这是必要的，因为在迭代的某些点，无论是开始还是结束，n的值都可能是奇数.我们不能只是忽略它，而是继续使用公式1，因为这意味着我们将跳过的力量为x！ (整数除法是四舍五入的，例如5 >> 1 = 2，我们将使用x^4而不是x^5).如果n为奇数(即n % 2 = n & 1 = 1)，则此if语句处理情况.它只是使用上面的公式2来将x的单次幂加"到结果中.

This is necessary as at certain points in the iteration, be it the start or the end, the value of n may be odd. We can't just ignore it and keep using formula 1, because that means we would skip a power of x! (Integer division rounds down, so e.g. 5 >> 1 = 2, and we would have x^4 instead of x^5). This if statement handles the case when n is odd, i.e. n % 2 = n & 1 = 1. It simply uses formula 2 above to "add" a single power of x to the result.

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