Barrett算法是利用移位代替除法。
举个例子:已知X M,求Z(三者均为正整数,Z<M)
Z=X mod M
一个很简单的方法就是用X=X-M,一直减下去,直到最后结果<M。
我们令X=kM+Z ,我们只需求出k,然后用X减kM即可。利用高斯取整函数k=[X/M],但是其中用了除了法。我们要避免除法这种长时间运算的计算,所以出现了一个叫做Barrett算法,就是利用移位来代替除法来求得一个k’,(这里的移位是任意进制下的)。经Barrett计算得到的k’要么等于k,要么等于k-1
python3:
import random
def Barrett(x,n,mod):
r=10#按论文,这里应取2的次幂,但python里不好进行二进制处理,就只好取10了(\悲哀)
z=0
u=int(r**(2*n+1)/mod)
k1=int(x/(r**(n-2)))
k2=int( k1*(u/r**(n+3)))
if(k2!=int(x/mod)):
print(k2,int(x/mod))
z=x-k2*mod
while z>=mod:
z=z-mod
return z
if __name__=="__main__":
mod=16891
for i in range(1000):
x=random.randint(30000,99999)
right=x%mod
z=Barrett(x,5,mod)
if(right!=z):
print("fuck")
verilog:
`include "param.v"
module MOD_X(
input wire[`SIZE:0] x,
output wire [`SIZE-1:0] mod_x
);
wire [`SIZE-1:0] z1;
wire [`SIZE-1:0] z2;
wire [`SIZE-1:0] z3;
wire [`SIZE-1:0] k1;
wire [`SIZE-1:0] k2;
assign k1=x >>(`SIZE);
assign k2= k1*(`BARRETT_U>>(`SIZE));
assign z1=x-k2*`P;
assign z2=z1-`P;
assign z3=z2-`P;
assign mod_x=(z1>=`P)? (z2>=`P? ((z3>=`P)?z3-`P:z3):z2 ) :z1;endmodule
param.v:
`define BARRETT_R 2'b10
`define BARRETT_U 8736
有中间变量z1 z2 z3是因为参数的选择,代码中参数的选择,根据式子,到少要判断三次,当然可以选择其他参数达到只判断一次的效果。但是乘法位数将会更大,所以自己折中吧。
需要注意的是,最后一张图片的式子有误,第5行应为:
Z<——Z-k'M
没有链接,只好选择原创了,侵删,论文:NTT处理器的研究与实现_宋鹏飞
以a*b mod q为例
计算 T 0 = a b ⋅ q − 1 m o d R T_0=ab\cdot q^{-1}\mod R T0=ab⋅q−1modR
计算 T 1 = T 0 ⋅ q T_1=T_0\cdot q T1=T0⋅q
计算 T 2 = a b − T 1 T_2=ab-T_1 T2=ab−T1
计算 T 3 = T 2 R T_3=\frac{T_2}{R} T3=RT2
注意:第1步必须mod R !
上述四步得到结果为 a b ⋅ R − 1 m o d q ab\cdot R^{-1}\mod q ab⋅R−1modq,下面将 R 2 R^2 R2乘上后再进行计算计算 T 4 = T 3 ⋅ ( R 2 m o d q ) ⋅ q − 1 m o d R T_4=T_3\cdot (R^2\mod q)\cdot q^{-1}\mod R T4=T3⋅(R2modq)⋅q−1modR
计算 T 5 = T 4 ⋅ q T_5=T_4\cdot q T5=T4⋅q
计算 T 6 = T 3 ⋅ ( R 2 m o d q ) − T 5 T_6=T_3\cdot (R^2\mod q)-T_5 T6=T3⋅(R2modq)−T5
计算 T 7 = T 6 R T_7=\frac{T_6}{R} T7=RT6
注意:第5步必须mod R !
下面举个实例:a = 123, b = 456, q = 677, q − 1 = 613 q^{-1}=613 q−1=613, R=1000, R 2 m o d q = 71 R^2\mod q=71 R2modq=71(注:因为这里的数是十进制表示,所以取R是一千,而不是 2 s o m e t h i n g 2^{something} 2something,原理一样)
- 计算 T 0 = 123 ∗ 456 ⋅ 613 m o d 1000 = 944 T_0=123*456\cdot 613\mod 1000=944 T0=123∗456⋅613mod1000=944
- 计算 T 1 = 944 ⋅ 677 = 639088 T_1=944\cdot 677=639088 T1=944⋅677=639088
- 计算 T 2 = 123 ∗ 456 − 639088 = − 583000 T_2=123*456-639088=-583000 T2=123∗456−639088=−583000
- 计算 T 3 = − 583000 1000 = − 583 T_3=\frac{-583000}{1000}=-583 T3=1000−583000=−583
- 计算 T 4 = − 583 ∗ 71 ⋅ 613 m o d 1000 = − 909 T_4=-583*71\cdot 613\mod 1000=-909 T4=−583∗71⋅613mod1000=−909
- 计算 T 5 = − 909 ⋅ 677 = − 615393 T_5=-909\cdot 677=-615393 T5=−909⋅677=−615393
- 计算 T 6 = − 583 ∗ 71 − ( − 615393 ) = 574000 T_6=-583*71-(-615393)=574000 T6=−583∗71−(−615393)=574000
- 计算 T 7 = 574000 1000 = 574 T_7=\frac{574000}{1000}=574 T7=1000574000=574
print(123*456%677)
结果与python直接计算一致
摘自:Verbauwhede, Ingrid MR, ed. Secure integrated circuits and systems. Berlin: Springer, 2010.
蒙哥马利模乘算法是最常用的一种模乘算法。计算在蒙哥马利域中进行,蒙哥马利域定义为:对于元素 a ∈ F a\in F a∈F和 R ( p < 2 R ) R(p<2^R) R(p<2R),有映射 a → a ⋅ 2 R m o d p a\rightarrow a\cdot 2^R\mod p a→a⋅2Rmodp。蒙哥马利域允许仅用乘法进行有效约简。但在计算之前,所有的输入值必须转换为蒙哥马利域(并在计算出结果后再次转换回去),增加了计算前后的额外复杂度。该方法的优点是可以减少成本高昂的约简运算,将其替换为除以2(位移)操作。假定X、Y为蒙哥马来利坐标中的两个因子,即 X ^ = X ⋅ 2 R m o d p \hat{X}=X\cdot 2^R\mod p X^=X⋅2Rmodp和 Y ^ = Y ⋅ 2 R m o d p \hat{Y}=Y\cdot 2^R\mod p Y^=Y⋅2Rmodp,可使用标准乘法计算 Z ^ = X ^ ⋅ Y ^ = X Y ⋅ 2 2 R \hat{Z}=\hat{X}\cdot\hat{Y}=XY\cdot 2^{2R} Z^=X^⋅Y^=XY⋅22R。需要注意的是,该计算结果既不是蒙哥马利域,也不是标准域需要进行修正。在使用特殊蒙哥马利模乘算法,用 X ⋅ Y ⋅ 2 − R m o d p X\cdot Y\cdot 2^{-R}\mod p X⋅Y⋅2−Rmodp替代 X ⋅ Y m o d p X\cdot Y\mod p X⋅Ymodp体时需要考虑到该情况。
需要指出的是,当涉及多个重复的模乘运算时,可以忽略蒙哥马利计算的额外转换步骤,如进行模幂运算的情况。这些局部乘法运算结果会按照最低有效位到最高有效位的顺序连续相加。在每次迭代时判定中间结果是奇数还是偶数。因此,可以检查中间结果中的最低有效位,如果此位等于"1",则模数会加到中间和上,这就确保了和总是偶数。在每次迭代结束时,中间结果会除以2,这样就可以避免增加中间结果规模的复杂度。
该算法要求每次循环进行两次相加。通过引入冗余表示,改进算法,构建包含CSA加法器的蒙哥马利模乘的高效架构
文章浏览阅读553次。一、IOC是 什么? IOC的英文名字是Inversion of Control,IOC即“控制反转”,不是什么技术,而是一种设计思想。在Java 开发 中,Ioc意味着将你设计好的对象交给容器控制,而不是传统的在你的对象内部直接控制。 ①所谓控制,指的是管理对象的权利; ②所谓反转,指的是由Spring管理而不是开发者管理二、IOC的作用 IoC的其中一个目的是为了解耦合,当将一个对象交给第三方容器管理后,那么对象之间的耦合相较于传统 ne_ioc和di
文章浏览阅读2.1k次。说明Unity 有自己的 接口 Handheld.Vibrate() 来实现手机的震动,这里来介绍下Unity调用ios原生震动。原生ios实现脚本下面有2个脚本都是震动的实现,用来自己测试。iOSHapticInterface.m与MultiHaptic.mm脚本。建议使用iOSHapticInterface.m脚本。iOSHapticInterface.m// This iOS haptic interface is a pretty straightforward impleme_unity nice vibrations
文章浏览阅读888次,点赞32次,收藏9次。continue:跳过本次continue循环后面的代码,重新去判断部分(也就是重新进入while循环),看是否能够进行下一次循环。这串代码与上一次相比,我们把while中的条件改为了i_includeint main(){while(putchar(getchar())!='?'); return 0;}
文章浏览阅读3.3k次。74hc164是高速硅门 CMOS 器件,与低功耗肖特基型 TTL (LSTTL) 器件的引脚兼容。74hc164是 8 位边沿触发式移位寄存器,串行输入数据,然后并行输出。数据通过两个输入端(DSA 或 DSB)之一串行输入;任一输入端可以用作高电平使能端,控制另一输入端的数据输入。两个输入端或者连接在一起,或者把不用的输入端接高电平,一定不要悬空。时钟 (CP) 每次由低变高时,数据右移一位,..._74hc164数码管
文章浏览阅读178次。报错2:error while loading shared libraries: libpython3.7m.so.1.0: cannot open shared object file: No such。报错1:OSError: Python library not found: libpython3.7mu.so.1.0, libpython3.7.so, l。添加库的配置信息,将python/lib的绝对路径(一般为:’/usr/python/lib’),添加至conf文件中。_centos pyinstall
文章浏览阅读674次。1、查看图中两个时间段内,且有“统计存储图片数据”的字段的日志 sed -n '/2021-06-03 11::25:34/,/2021-06-03 11:26:02/p' start.log |grep "统计存储图片数据" 注释: -n参数:只有经过sed特殊处理的那一行(或者动作)才会被显示 p参数:表示在终端打印出来 start.log:日志文件 grep: 对前面查询的结果进行过滤 "统计存储图片数据": 查询的关键字 时间段:格式和日志保持一致,且时间值是真实存在的2、将时._linux命令统计某个时间区间出现的关键字
文章浏览阅读4k次,点赞3次,收藏40次。实现查询和增删改一、Ajax最基本语法二、增删查改1.查询(Get请求)2.增删改(Post请求)三、后台(MVC/WebForm)1.MVC(Post请求)2.WebForm(Post请求)本人小白一个。其中所说可能有些不足,因为这些是我自己在写项目的过程中所使用的Ajax如有不对的地方,欢迎评论提出建议。一、Ajax最基本语法话不多说,直接上代码$.ajax({ url: "/User/GetUser",(这里写请求路径) type: "g_ajax增删改查
文章浏览阅读894次,点赞8次,收藏6次。无论您使用的是Windows、Mac还是Linux系统,主流播放器如VLC、Windows Media Player、QuickTime等都能轻松打开MP4文件,确保用户能够在各种平台上畅快观影。如果需要将M4S转换成MP4,野葱视频转换器为我们提供了便捷的解决方案,不仅具有稳定性,极少发生文件损坏,而且转换速度快,大大节约了时间。随着网络视频的普及,M4S通过分片存储音频和视频数据,提高了网络传输的效率,使得用户在观看视频时能够更加流畅地体验。处理完成后,你将在指定的输出路径中找到生成的MP4文件。_m4s格式转换mp4
文章浏览阅读596次。网络管理报文(CAN 4开头,CAN FD 5开头),应用报文,诊断报文(7开头,物理寻址:一对一 比如对单体安全访问,在线编程,功能寻址:服务需要一对多,保证ECU的状态相同,比如多个 ECU需要知道车速的信息,温度的信息)CAN_H的电平为3.5V,CAN_L线的电平为1.5V,CAN_H和CAN_L的电压差为2V左右,CAN_H和CAN_L线上的电压均为2.5v, CAN_H和CAN_L之间的电压差为0V。1、位错误:当总线赢得发送权后,会对总线电平进行侦听,当发送的电平和侦听的电平不一致;_为什么can诊断都是7开头
文章浏览阅读2.7k次,点赞2次,收藏9次。在本人之前的一篇博文中描写了如何使用OPC自定义接口开发OPCClient,并使用SignalR实现数据的远程实时传输。融合SignalR的OPCClient实现环境参数实时监测但是在使用过程中发现仍有不足之处,本文就是对之前OPCClient的功能改进进行说明。1.问题描述原有的OPCClient在测试环境下可以正常运行,但是在实际生产环境下长时间运行后问题就逐渐暴露出来。主要的问..._titaniumas.opc.client
文章浏览阅读75次。宏工科技十五周年,“归零心态”竞逐全球
文章浏览阅读1.6k次。c++中的extern "C"_c++ extern c