网上购物网站开发报价,青白江网站建设,天津津坤科技发展有限公司,营销型网站免费模板次幂函数取模算法 高次幂函数取模算法 在平常的工作学习中#xff0c;我们经常需要用到求取一个数字或者幂运算的余数#xff0c;尤其在密码学中最为常用的RSA算法就经常要用到这种运算#xff0c;我们称之为高次幂函数的取模运算。 在本篇文章中#xff0c;将会首先介绍运… 次幂函数取模算法 高次幂函数取模算法 在平常的工作学习中我们经常需要用到求取一个数字或者幂运算的余数尤其在密码学中最为常用的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_castint (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_castint (res);//以int类型返回最终结果
} 使用这个算法即便是处理很大的数据都可以快速的求得余数非常好用这里想说学好数学才是真的生产力 Github https://github.com/haoyuanliu 个人博客 http://haoyuanliu.github.io/ 个人站点欢迎访问欢迎评论
