Barrett Reduction is a method of reducing a number modulo another number. Barrett reduction, when used to reduce a single number, is slower than a normal divide algorithm. However, by precomputing some values, one can easily far exceed the speed of normal modular reductions.
Because Barrett reduction's benefits are most visible when it is used to reduce various numbers modulo a single number many times, for example, when doing modular exponentiation. Barrett reduction is not particularly useful when used with small numbers (32 or 64 bits); it's benefits occur when using numbers that are implemented by multiple precision arithmetic libraries, such as when implementing the RSA cryptosystem, which uses modular exponentiation with large (> 512 bit) numbers, to encrypt and decrypt.
So, how do you do it? First, keep in mind the following restriction: Barrett Reduction can only reduce numbers that are, at most, twice as long (in words) as the modulus. Thats computer words; usually these are 32 bits long (for example on x86 and PowerPC machines), and sometimes 64 bits (like on the Alpha, UltraSPARC, and MIPS R10000).
So you have some modulus, called m, which is k words long (numbered k-1...0, with 0 being the least significant word). First, pre-calculate the value:
mu = floor(b^k / m)
where b is the "base" of the integers used. For example, if you represented the numbers as a sequence of 32-bit values, b is 2^32, or 0x100000000. You will keep this value mu across function calls (probably stored in a structure somewhere), so you can reuse it.
Now, given a number x, which is an arbitrary integer of size (at most) 2k words (2k-1...0), this procedure (in pseudocode) will return the value of x mod m:
q1 = floor(x / b^(k-1))
q2 = q1 * mu
q3 = floor(q2 / b^(k+1))
r1 = x mod b^(k+1)
r2 = (q3 * m) mod b^(k+1)
r = r1 - r2
if(r < 0)
r = r + b^(k+1)
while(r >= m)
r = r - m
return r
Note that the divisions and modular reductions in this procedure can be replaced by right shifts and AND operations (respectively) if (and only if) b is a power of 2 (which, by far, will be the most common choice). This results in the remaining operations being addition and multiplication, both of which are much cheaper than division for multiple precision integers.
This algorithm is also specified in the Handbook of Applied Cryptography (good book!), and is implemented by some crypto libraries. Another method of doing fast modular reductions is Montgomery Reduction.
分享到:
相关推荐
该文设计出进位保留Barrett模乘法器,乘法部分利用进位保留乘法器,求模运算部分利用Barrett约减运算,用硬件描述语言进行FPGA设计与实现,避免了除法运算。对于192位的操作数,完成Barrett模乘需要约186个时钟周期...
通过安装ros kinetic,pcan驱动及barrett hand ros包控制两个barrett机器手运动。内有全部安装资源及教程。
js rsa非对称加密 前台js 需要的3个Barrett.js
RSA加密需要的前端js Barrett.js
javascript RSA 加密用到的文件(RSA.js BigInt.js, Barrett.js) 附带了rsa1.js,这个版本集成了以上3个文件,加密内容固定,自行斟酌使用
Barrett食管及其相关肿瘤内镜微创治疗进展,刘冰熔,刘敬杨,Barrett食管 (Barrett's esophagus, BE)是食管腺癌的癌前病变,治疗BE对早期食管腺癌及部分贲门癌的预防和治疗很有意义。传统的抑酸治疗效果�
RSA所需js文件 Barrett.js、BigInt.js、RSA.js。需要的请下载
rsa Barrett.js BigInt.js RSA.js前端源码,实现前端加密后端解密RSA, a suite of routines for performing RSA public-key computations in // JavaScript.
barrett_wam_gazebo_sim 克隆 由于此barrett_model包含一个子模块barrett_model ,因此您必须使用以下命令进行克隆(如中所述) git clone --recurse-submodules https://github.com/saszaz/barrett_wam_gazebo_sim ...
制造行业日报:埃斯顿+Barrett:打造科学化的康复机器人.pdf
RSA加密脚本 JavaScript 参考:Blackberry10 使用js+...1,加密非常的简单代码机会上没怎么修改,另外js加密可能出现的问题在BB10 AES加密中已经说过,js RSA加密需要导入3个js文件 分别是Barrett.js,BigInt.js,RSA.js
RSA.js、BigInt.js、Barrett.js与 bcprov-jdk15on-160.jar
前台加密必备js,Barrett.js,BigInt.js,RSA.js
RSA前台加密后台解密案例,包括相关jar包和js文件.
RSA前台加密用到的js文件(RSA.js BigInt.js, Barrett.js)
此 Matlab GUI 演示了如何使用光流算法自动跟踪使用 B 型超声成像的人体内侧腓肠肌 (MG) 肌肉束,该算法利用仿射变换跟踪在初始帧中确定的肌肉束的端点. 请在任何使用此算法的学术著作中引用以下手稿 - 1. Cronin,...
三菱巴雷特 一个 ROS 堆栈,将模型描述以及三菱 arm Barrett 手的硬件和控制接口链接在一起
Barrett's食管相关腺癌NOX5-S表达调控的研究,周永新,冯靖,目的 研究Barrett's食管相关食管腺癌NOX5-S的表达调控,了解食管腺癌的发病机制,为食管腺癌的预防和治疗提供科学的理论依据。 方法 1
除法:Granlund--Montgomery除以不变整数(给出恒定时间模减少量), 使用ct-verif比较固定时间验证的 模块化加法扩展的GCD和模逆, 巴雷特的减少, 蒙哥马利的减少, 蒙哥马利乘法, 模幂(基于蒙哥
5.2 BARRETT缩减 31 5.3 MONTGOMERY缩减 33 6大整数除法实现 37 6.1使用减法替换除法运算 37 6.2模拟笔算除法 38 7大整数幂运算实现 43 7.1单数位幂乘 43 7.2 K—RAY幂乘 45 7.3滑动窗口幂乘 45 结论 47 参考文献 48...