第讲分组密码小节.ppt

第讲分组密码小节.ppt

ID:50759122

大小:247.50 KB

页数:19页

时间:2020-03-13

第讲分组密码小节.ppt_第1页
第讲分组密码小节.ppt_第2页
第讲分组密码小节.ppt_第3页
第讲分组密码小节.ppt_第4页
第讲分组密码小节.ppt_第5页
资源描述:

《第讲分组密码小节.ppt》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、分组密码小结王滨2005.03.251主要内容欧几里德算法求最大公约数求模n的逆元2欧几里得算法(辗转相除法)引理1记gcd(a,b)是非负整数a和b的最大公因子,则gcd(a,b)=1等价于存在整数x,y,使得ax+by=1其中的x和y可由辗转相除法求出。3辗转相除法引理2(带余除法)设a是整数,b是自然数,则存在整数q和非负整数r,使得a=bq+r,且0<=r

2、a=b

3、q+r,且d

4、b,则一定有d

5、r,则d

6、gcd(b,r).下证d=gcd(b,r).由于gcd(a/d,b/d)=1,一定有gcd(r/d,b/d)=1,故d=gcd(b,r)。证毕。4辗转相除法:----计算gcd(a,b)Step1Aa;BbStep2计算带余除法,求出满足A=qB+r和0<=r0时,执行AB;Br后返回执行Step2.5例1计算gcd(63,100)解63=0×100+63,100=1×63+37,63=1×37+2637=

7、1×26+11,26=2×11+4,11=2×4+3,4=1×3+1,3=3×1+0故gcd(63,100)=1.6系数的计算倒推进行(将余数代入):1=4-1×3=4-1×(11-2×4)=-1×11+(1+2)×4=-1×11+3×4=-1×11+3×(26–2×11)=-7×11+3×26=-7×(37–26)+3×26=-7×37+(7+3)×26=-7×37+10×26=-7×37+10×(63-37)=10×63-17×37=10×63-17×(100-63)=-17×100+27×637输出使得ax+by=

8、gcd(a,b)的gcd(a,b)和x,y的推理过程.记a0=a,a1=b,则求ax+by=gcd(a,b)的过程可写为:即8欧几里得算法:----计算gcd(a,b)和使ax+by=gcd(a,b)成立的x,y.Step1Aa;Bb;s=1;t=0;x=0;y=1;Step2计算带余除法,求出满足A=qB+r和0<=r0时,执行AB;Brwx;xs-qx;sw;wy;yt-qy;tw;后返回执行Step2.9欧几里得算法:-

9、---计算gcd(a(x),b(x))和使z(x)a(x)+y(x)b(x)=gcd(a(x),b(x))成立的z(x),y(x).Step1A(x)a(x);B(x)b(x);s(x)=1;t(x)=0;z(x)=0;y(x)=1;Step2计算带余除法,求出满足A(x)=q(x)B(x)+r(x)和deg(r)

10、);z(x)s(x)-q(x)z(x);s(x)w(x);w(x)y(x);y(x)t(x)-q(x)v(x);t(x)w(x);后返回执行Step2.10辗转相除法的C语言算法intinverse(a)inta;{registerintn1,n2,q,r,b1,b2,t;if(!a)b2=0;else{n1=n;n2=a;b2=1;b1=0;do{r=(n1%n2);q=(n1-r)/n2;if(!r){if(b2<0)b2=n+b2;}else{n1=n2;n2=r;t=b2;b2=b1-q*b2;b1=t

11、;}}while(r);}return(b2);}11例子:求10110110在modb(x)中的逆10110110a(x)=x7+x5+x4+x2+x,b(x)=x8+x4+x3+x+1100011011,求z(x)满足z(x)a(x)+y(x)b(x)=1.解:step1:A(x)=a(x),B(x)=b(x),s(x)=1,z(x)=0,t(x)=0,y(x)=1;step2:A(x)=0*B(x)+r(x),r(x)=a(x);由于r(x)!=0,则A(x)=B(x),B(x)=r(x);w(x)=z(x)=

12、0;z(x)=s(x)-q(x)z(x)=s(x)=1;s(x)=w(x)=0执行step2(100011011)=x*(10110110)+r故q(x)=x;r(x)=(01110111)A(x)=(10110110);B(x)=r(x);w(x)=1,z(x)=x;s(x)=1;执行step2(10110110)

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。