次幂函数取模算法

2019-04-13 16:06发布生成海报

站内文章 / 模拟电子

16720 0

次幂函数取模算法

高次幂函数取模算法

在平常的工作学习中，我们经常需要用到求取一个数字或者幂运算的余数，尤其在密码学中最为常用的RSA算法就经常要用到这种运算，我们称之为高次幂函数的取模运算。在本篇文章中，将会首先介绍运用程序求解高次幂函数取模的暴力求解方法，然后针对暴力方法算法效率低下的缺点，给出一种快速的取模算法。

暴力取模算法

由于我们的高次幂函数往往拥有很高的幂，而我们在计算机中只有int、float、double、

long
 long

这几种变量类型，远远不能满足我们对于大数字运算的要求，从而导致数据溢出无法完成运算。
所以这里我们需要在每次迭代取模的过程中进行取模运算，从而保证数据不会溢出。代码如下：

int get_mod(int a, int b, int c)
{
    long long result = 1;//声明为long long类型防止溢出
    while(b--)
    {
        result = result * a % c;//这个算法的核心就是在迭代运算过程中进行取模运算
    }
    return static_cast<int> (result);
}

这种算法的正确性毋庸置疑，但是如果幂指数太大的话，需要耗费的时间就更非常多，直接导致运算效率低下，所以只适用于指数不大的情况下使用，下面我们要讲解的蒙哥马利算法就很好地解决了这个问题，而且该算法非常简单，效率极高，完全可以手动演算。

蒙哥马利算法

蒙哥马利算法是一种快速的大数（通常达到几百个二进制）的模乘算法，由彼得·蒙哥马利在1985年提出。
下面直接放代码：

int get_mod(int a, int b, int c)
{
    long long res = 1;//声明为long long类型防止数据溢出
    int temp = a;
    while(b > 0)
    {
        if( b & 1)//取幂指数二进制最后一位
        {
            res = (res * temp) % c;
        }
        temp = (temp * temp) % c;
        b >>= 1;//幂指数二进制向右移动一位
    }
    return static_cast<int> (res);//以int类型返回最终结果
}

使用这个算法，即便是处理很大的数据都可以快速的求得余数，非常好用，这里想说，学好数学才是真的生产力！

Github ： https://github.com/haoyuanliu
个人博客： http://haoyuanliu.github.io/ 个人站点，欢迎访问，欢迎评论！