北交大 密码学课件 第4章_数论初步和有限域

模运算
设 n 是一正整数，a 是整数，如果用 n 除 a，得商为 q， 余数为 r，则 a=qn+r, 0≤r<n,
q a n
其中 x 为小于或等于 x 的最大整数。
a n a mod n a 用 a mod n 表示余数 r，则 n 。
算法中的变量有以下关系：
fT1+dT2=T3; fX1+dX2=X3; fY1+dY2=Y3
在算法Euclid (f, d)中，X等于前一轮循环中的Y， Y等于前一轮循环中的X mod Y。而在算法 Extended Euclid(f, d)中，X3等于前一轮循环中的 Y3，Y3等于前一轮循环中的X3-QY3，由于Q是Y3 除X3的商，因此Y3是前一轮循环中的Y3除X3的余 数，即X3 mod Y3，可见Extended Euclid(f, d)中 的X3、Y3与Euclid(f, d)中的X、Y作用相同，因此 可正确产生gcd(f, d)。
推广的Euclid算法先求出gcd(a, b)，当gcd(a,
b)=1时，则返回b的逆元。
Extended Euclid(f, d) （设 f >d） 1. (X1, X2, X3)←(1, 0, f); 2. if Y3=0 then return 3. if Y3=1 then return 4. Q X 3 / Y3 ； 5. (T1, T2, T3)←(X1-QY1, X2-QY2, X3-QY3); 6. (X1, X2, X3)←(Y1, Y2, Y3); 7. (Y1, Y2, Y3)←(T1, T2, T3); 8. goto 2。 (Y1, Y2, Y3)←(0, 1, d); X3=gcd(f, d)；no inverse; Y3=gcd(f, d)；Y2=d-1 mod f;
定理：设 a∈Zn，gcd(a, n)=1，则 a 在 Zn 中有乘法逆元。
证明：首先证明 a 与 Zn 中任意两个不相同的数 b、c（不妨设 c<b） 相乘，其结果必然不同。 否则设 a × b ≡ a × c mod n ，则 存在两 个整数 k1,k2 ，使 得 ab=k1n+r，ac=k2n+r，可得 a(b-c)=(k1-k2)n，所以 a 是(k1-k2)n 的一个 因子。又由 gcd(a，n)=1，得 a 是 k1-k2 的一个因子，设 k1-k2=k3a， 所以 a(b-c)=k3an，即 b-c=k3n，与 0<c<b<n 矛盾。 所以|a×Zn|=|Zn|。又知 a×Zn Zn，所以 a×Zn=Zn。 因此对 a∈Zn，存在 x∈Zn，使得 a×x≡1 mod n，即 x 是 a 的 乘法逆元。记为 x a 。 （证毕）
在求两个数的最大公因子时，可重复使用以上结论。 例如：gcd(55, 22) = gcd(22, 55 mod 22) = gcd(22,11) = gcd(11, 0) = 11。 gcd(18,12) = gcd(12,6) = gcd(6,0) = 6, gcd(11,10) = gcd(10,1) = gcd(1,0) = 1。
如果gcd (f, d)=1，则在最后一轮循环中Y3=0，
X3=1，因此在前一轮循环中Y3=1.
因为 fY1+dY2=Y3 成立，
即 即 fY1+dY2=1， Y2≡d-1 mod f。 所以 dY2=1+(-Y1)×f，dY2≡1 mod f，
求gcd(7, 5)
Q 1 2
X1 1 0 1
如果(a mod n)=(b mod n)， 则称两整数 a 和 b 模 n 同余， 记为 a≡b mod n。称与 a 模 n 同余的数的全体为 a 的 同余类，记为[a]，称 a 为这个同余类的表示元素。 注意： 如果 a≡0(mod n)，则 n|a。
同余有以下性质： ① 若 n|(a-b)，则 a≡b mod n。 ② (a mod n)≡(b mod n)，则 a≡b mod n。 ③ a≡b mod n,则 b≡a mod n。 ④ a≡b mod n, b≡c mod n, 则 a≡c mod n。 从以上性质易知，同余类中的每一元素都可作为这个同余 类的表示元素。
加法：对每一 x，都有一 y，使得 x+y≡0 mod 8。如对 2，有 6，使得 2+6≡0 mod 8，称 y 为 x 的负数，也称为加法逆元。 乘法： 对 x， 若有 y， 使得 x×y≡1 mod 8， 如 3×3≡1 mod 8， 则称 y 为 x 的倒数，也称为乘法逆元。 并非每一 x 都有乘法逆元。
数论初步
整数分解的唯一性：设 P 是所有素数集合，则任意整数 a (a>1)都能惟一地写成以下形式：
a p
pP ap
其中 a p 0 , 等号右边的乘积项取所有的素数，然而大多指 数项 a p 为 0。 相应地，任一正整数也可由非 0 指数列表表示。例如： 11011 可表示为{a7=1, a11=2, a13=1}。 两数相乘等价于对应的指数相加，即由 k=mn 可得：对每 一素数 p, kp=mp+np。而由 a|b 可得：对每一素数 p, ap≤bp。
Euclid算法
欧几里得算法
求两个正整数的最大公因子 推广的Euclid算法不仅可求两个正整数的最大公 因子，而且当两个正整数互素时，还可求出其中 一个数关于另一个数的乘法逆元。
最大公因子
定理：对任意非负整数 a 和正整数 b，有 gcd(a, b)=gcd(b, a mod b)。 证明： b 是正整数， 因此可将 a 表示为 a=kb+r≡r mod b， a mod b=r, 其中 k 为一整数，所以 a mod b =a-kb。 设 d 是 a，b 的公因子，即 d|a，d|b，所以 d|kb。由 d|a 和 d|kb 得 d|(a mod b)， 因此 d 是 b 和 a mod b 的公因子。 所以得出 a，b 的公因子集合与 b，a mod b 的公因子集 合相等，两个集合的最大值也相等。 （证毕）
Euclid 算法描述： 因 gcd(a, b)=gcd(|a|, |b|)，因此可假定算法的输入是两个正整 数，设为 d，f，并设 f >d。 Euclid（f, d） 1. X←f; Y←d； 2. if Y=0 then return X=gcd(f, d)； 3. R=X mod Y； 4. X=Y； 5. Y=R； 6. goto 2。
此外还有以下性质： 如果(a+b)≡(a+c) mod n，则 b≡c mod n，称为加法的可约律。 该性质可由上式两边同加上 a 的加法逆元得到。 类似性质对乘法不一定成立。例如 6 × 3 ≡ 6 × 7 ≡ 2 mod 8 ，但
3 7 mod 8。
原因：6 乘以 0 到 7 得到的 8 个数仅为 Z8 的一部分。即如果将对 Z8 作 6 的乘法 6×Z8（即用 6 乘 Z8 中每一数）看作 Z8 到 Z8 的映射的 话，Z8 中至少有两个数映射到同一数，因此该映射为多到一的。 所以对 6 来说， 没有惟一的乘法逆元。 但对 5 来说， 5×5≡1 mod 8， 因此 5 有乘法逆元 5。仔细观察可见，与 8 互素的几个数 1，3，5， 7 都有乘法逆元。 这一结论可推广到任，考虑 Z8 上的模加法和模乘法。
+ 0 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 0 2 2 3 4 5 6 7 0 1 3 3 4 5 6 7 0 1 2 4 4 5 6 7 0 1 2 3 5 5 6 7 0 1 2 3 4 6 6 7 0 1 2 3 4 5 7 7 0 1 2 3 4 5 6
1
设 p 为一素数，则 Zp 中每一非 0 元素都与 p 互素，因此有乘法逆 元。 类似于加法可约律，可有以下乘法可约律： 如果(a×b)≡(a×c) mod n 且 a 有乘法逆元，那么对(a×b)≡(a× c) mod n 两边同乘以 a-1，即得 b≡c mod n
欧几里得算法
×
0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7
2 0 2 4 6 0 2 4 6
3 0 3 6 1 4 7 2 5
4 0 4 0 4 0 4 0 4
5 0 5 2 7 4 1 6 3
6 0 6 4 2 0 6 4 2
7 0 7 6 5 4 3 2 1
0 1 2 3 4 5 6 7
一般地， 定义 Zn 为小于 n 的所有非负整数集合， 即 Zn={0,1, …,n-1}， 称 Zn 为模 n 的同余类集合。其上的模运算有以下性质： ① 交换律 ② 结合律 ③ 分配律 ④ 单位元 ⑤ 加法逆元 (w+x) mod n=(x+w) mod n (w×x) mod n=(x×w) mod n [(w+x)+y] mod n=[w+(x+y)] mod n [(w×x)×y] mod n=[w×(x×y)] mod n [w×(x+y)] mod n=[w×x+w×y] mod n (0+w) mod n=w mod n (1×w) mod n=w mod n 对 w∈Zn，存在 z∈Zn，使得 w+z≡0 mod n， 记 z=-w。
k j p p 这是因为 只能被 ( j k ) 整除。
最大公约数定义和性质
最大公约数
如果将a，b都表示为素数的乘积，则gcd(a, b)极
易确定。
例如：
300=22×31×52
18=21×32
gcd(18,300)=21×31×50=6
求解gcd(a,b)
两种方法求解gcd(a, b)