大数取模运算Barrett reduction-程序员宅基地

技术标签: Barrett reduction  大数指数运算  

Barrett reduction算法的证明和使用。

 

作者刚做完了课程设计作业,闲来无事写篇文章。

 

大数中的指数运算,需要对一个数进行取模,因为最大可能二进制下2048位的2048位次方,所以必须边做乘法边取模。

乘法使用快速幂,如果底数位数是x,指数位数是e,底数足够大的话,复杂度取决于模数,模数是m位的话,复杂度是O(m*m*e)。程序里,大数的存储是2的32次方进制的,这里的m*m要除以(32*32)。

取模运算,如果直接调用大数取模,因为除法是很慢的,所以效率很低。用Barrett reduction算法可以将除法转化为乘法和位运算,减法。

因为模数是任意的,所以不用蒙哥马利算法。

作业里只要求完成非负的大数运算,后面证明中默认大数都是非负的。

 

下面介绍Barrett reduction算法

求 x mod m

 m的位数是k

使用条件: x位数不大于2*k。对同一个数反复取模。

使用方法(这里是非负数):

计算常量 mu=b^2k / m

取模时:

q1 = x / b^(k-1)

q2 = q1 * mu

q3 = q2 / b^(k+1)

 

r1 = x % b^(k+1)

r2 = (q3 * m) % b^(k+1)

r = r1 - r2

if ( r > m ) r -= m

return r

 

很多资料把mu=b^2k / m写成了mu=b^k / m,作者被坑了,很生气,决定放假写这么一个文章。另外,百度上基本看不到什么相关的证明。

 

证明:

 []表示取整,b是大数的进制

 

上面w为x/m取整,q3和w非常接近,q3=w或者q3=w-1。

最后的余数ANS  (x mod m)就是 x - m * w,也就是 x-q3*m 就能得到 ANS或者ANS+m,如果是后者,再做一次减法就可以得到余数。

 

 

 

只需要一次除法预处理。

之后的除法和取模都是对进制b的若干次方进行的,所以位运算即可。

乘法时,因为最后结果是要取最后k+1位的,所以在乘的时候,可以直接把k+1位前面的丢弃,减少循环次数。作者是另外写了一个限制位数的乘法函数,效率提升了一些。

 

证明部分截图自word实验报告。

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/YKRY35/article/details/79179285

智能推荐

基于Kepler.gl 和 Google Earth Engine 卫星数据创建拉伸多边形地图-程序员宅基地

文章浏览阅读965次,点赞18次,收藏21次。现在我们有了 2021 年和 2023 年的 NDVI 数据帧,我们需要从 2021 年的值中减去 2023 年的值以捕获 NDVI 的差异。该数据集包括像素级别的植被值,我们将编写一个自定义函数来根据红色和绿色波段的表面反射率计算 NDVI。在我的上一篇文章中,我演示了如何将单个多边形分割/镶嵌为一组大小均匀的六边形。现在我们有了植被损失数据,让我们使用 Kepler.gl 可视化每个六边形的植被损失。将地图保存为 HTML 文件,在浏览器中打开 HTML 以获得更好的视图。现在我们将调用该函数并使用、

Echarts绘制任意数据的正态分布图_echarts正态分布图-程序员宅基地

文章浏览阅读3.3k次,点赞6次,收藏5次。正态分布,又称高斯分布或钟形曲线,是统计学中最为重要和常用的分布之一。_echarts正态分布图

Android中发送短信等普通方法_android bundle.get("pdus");-程序员宅基地

文章浏览阅读217次。首先要在Mainfest.xml中加入所需要的权限:[html] view plain copyprint?uses-permission android:name="android.permission.SEND_SMS"/> uses-permission android:name="android.permission.READ_SMS"/> _android bundle.get("pdus");

2021-07-26 WSL2 的安装和联网_wsl2 联网-程序员宅基地

文章浏览阅读2.6k次。0、说明最近在学习 Data Assimilation Research Testbed (DART) 相关内容,其软件是在 Unix/Linux 操作系统下编译和运行的 ,由于我的电脑是 Windows 10 的,DART 推荐可以使用 Windows Subsystem For Linux (WSL) 来创建一个 Windows 下的 Linux 子系统。以下的内容主要介绍如何安装 WSL2,以及 WSL2 的联网。1、如何在 Windows 10 下安装WSL具体的安装流程可以在 microso_wsl2 联网

DATABASE_LINK 数据库连接_添加 database link重复的数据库链接命-程序员宅基地

文章浏览阅读1k次。DB_LINK 介绍在本机数据库orcl上创建了一个prod_link的publicdblink(使用远程主机的scott用户连接),则用sqlplus连接到本机数据库,执行select * from scott.emp@prod_link即可以将远程数据库上的scott用户下的emp表中的数据获取到。也可以在本地建一个同义词来指向scott.emp@prod_link,这样取值就方便多了..._添加 database link重复的数据库链接命

云-腾讯云-实时音视频:实时音视频(TRTC)-程序员宅基地

文章浏览阅读3.1k次。ylbtech-云-腾讯云-实时音视频:实时音视频(TRTC)支持跨终端、全平台之间互通,从零开始快速搭建实时音视频通信平台1.返回顶部 1、腾讯实时音视频(Tencent Real-Time Communication,TRTC)拥有QQ十几年来在音视频技术上的积累,致力于帮助企业快速搭建低成本、高品质音视频通讯能力的完整解决方案。..._腾讯实时音视频 分享链接

随便推点

用c语言写个日历表_农历库c语言-程序员宅基地

文章浏览阅读534次,点赞10次,收藏8次。编写一个完整的日历表需要处理许多细节,包括公历和农历之间的转换、节气、闰年等。运行程序后,会输出指定年份的日历表。注意,这个程序只是一个简单的示例,还有很多可以改进和扩展的地方,例如添加节气、节日等。_农历库c语言

FL Studio21.1.1.3750中文破解百度网盘下载地址含Crack补丁_fl studio 21 注册机-程序员宅基地

文章浏览阅读1w次,点赞28次,收藏27次。FL Studio21.1.1.3750中文破解版是最优秀、最繁荣的数字音频工作站 (DAW) 之一,日新月异。它是一款录音机和编辑器,可让您不惜一切代价制作精美的音乐作品并保存精彩的活动画廊。为方便用户,FL Studio 21提供三种不同的版本——Fruity 版、Producer 版和签名版。所有这些版本都是独一无二的,同样具有竞争力。用户可以根据自己的需要选择其中任何一种。FL Studio21.1.1.3750中文版可以说是一站式综合音乐制作单位,可以让您录制、作曲、混音和编辑音乐。_fl studio 21 注册机

冯.诺伊曼体系结构的计算机工作原理是,冯 诺依曼型计算机的工作原理是什么...-程序员宅基地

文章浏览阅读1.3k次。冯诺依曼计算机工作原理冯 诺依曼计算机工作原理的核心是 和 程序控制世界上不同型号的计算机,就其工作原理而言,一般都是认为冯 诺依曼提出了什么原理冯 诺依曼原理中,计算机硬件系统由那五大部分组成的 急急急急急急急急急急急急急急急急急急急急急急冯诺依曼结构计算机工作原理的核心冯诺依曼结构和现代计算机结构模型 转载重学计算机组成原理 一 冯 诺依曼体系结构从冯.诺依曼的存储程序工作原理及计算机的组成来..._简述冯诺依曼计算机结构及工作原理

四国军棋引擎开发(2)简单的事件驱动模型下棋-程序员宅基地

文章浏览阅读559次。这次在随机乱下的基础上加上了一些简单的处理,如进营、炸棋、吃子等功能,在和敌方棋子产生碰撞之后会获取敌方棋子大小的一些信息,目前采用的是事件驱动模型,当下完一步棋界面返回结果后会判断是否触发了相关事件,有事件发生则处理相关事件,没有事件发生则仍然是随机下棋。1.事件驱动模型首先定义一个各种事件的枚举变量,目前的事件有工兵吃子,摸暗棋,进营,明确吃子,炸棋。定义如下:enum MoveE..._军棋引擎

STL与泛型编程-第一周笔记-Geekband-程序员宅基地

文章浏览阅读85次。1, 模板观念与函数模板简单模板: template< typename T > T Function( T a, T b) {… }类模板: template struct Object{……….}; 函数模板 template< class T> inline T Function( T a, T b){……} 不可以使用不同型别的..._geekband 讲义

vb.net正则表达式html,VB.Net常用的正则表达式(实例)-程序员宅基地

文章浏览阅读158次。"^\d+$"  //非负整数(正整数 + 0)"^[0-9]*[1-9][0-9]*$"  //正整数"^((-\d+)|(0+))$"  //非正整数(负整数 + 0)"^-[0-9]*[1-9][0-9]*$"  //负整数"^-?\d+$"    //整数"^\d+(\.\d+)?$"  //非负浮点数(正浮点数 + 0)"^(([0-9]+\.[0-9]*[1-9][0-9]*)|([0..._vb.net 正则表达式 取html中的herf