文档介绍：分组密码小结
王滨

1
主要内容
欧几里德算法
求最大公约数
求模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<b,并记amodb=r.
引理3 设a、b、r为不全为零的整数,且a=bq+r,则gcd(a,b)=gcd(b,r).
证明:设d= gcd(a,b),由于d| a=bq+r,且d|b,则一定有d|r,则d| 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)
Step1 Aa;Bb
Step2 计算带余除法,求出满足
A=qB+r和0<=r<B的 q和r.
Step3 当r=0时,输出B=gcd(a,b);
当r>0时,执行AB;Br后返回执行
Step2.
5
例1 计算gcd(63,100)
解 63 = 0×100 + 63,
100 = 1×63 + 37,
63 = 1×37 + 26
37 = 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×63
7
输出使得ax+by=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.
Step1 Aa;Bb;s=1;t=0;x=0;y=1;
Step2 计算带余除法,求出满足
A=qB+r和0<=r<B的 q和r.
Step3 当r=0时,输出B=gcd(a,b)和x,y;
当r>0时,执行
AB; Br
wx; xs-qx; sw;
wy; yt-qy; tw;
后返回执行 Step2.
9
欧几里得算法:----计算gcd(a(x),b(x))和使z(x)a(x)+y(x)b(x)=gcd(a(x),b(x))成立的z(x),y(x).
Step1 A(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)<deg(B)的 q(x)和r(x).
Step3 当r(x)=0时,输出B(x)=gcd(a(x),b(x))和z(x),m(x);
当r(x)!=0时,执行
A(x)B(x); B(x)r(x)
w(x)z(x); 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