- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
–若gcd(a,b)=1, b在模a下有乘法逆元(设b<a)。 即存在x<a,bx≡1 mod a 思路：求gcd(a,b)，当gcd(a,b)=1时，则返回b的逆元。
整除中的一个论断：
若gcd(a,b)=d，则存在m,n，使得d=ma+nb。
那么当gcd(a,b)=1时，有ma+nb=1， 即m是a模b的逆元，n是b模a的逆元。
Galois 域：
如果 n是素数 p ，则模运算modulo p 形成 Galois
Field modulo p
记为： GF(p)
4.1.2 素数和互素数
因子：
• 对整数 b!=0 及 a , 如果存在整数 m 使得 a=mb,称 b 整除 a, 也称b是a的因子。 • 记作 b|a • 例 1,2,3,4,6,8,12,24 整除 24
4.1.6 欧几里得算法
1. 求两个正整数的最大公因子
2. 两个正整数互素，可以求一个数关于另一个数的乘法逆 元 • 性质: 对任意非负整数a和正整数b, 有 gcd(a,b)=gcd(b,a mod b) • 证明： a=kb+r≡r mod b a mod b=a-kb 设d是a，b的公因子，即d|a , d|b, 所以d|kb.
同余的性质：
• • • • 若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
求余运算a mod n将a映射到集合{0,1,…,n-1},求余运算称 为模运算。 模运算的性质 –[(a mod n)+(b mod n)] mod n=(a+b) mod n –[(a mod n)-(b mod n)] mod n=(a-b) mod n –[(a mod n)×(b mod n)] mod n=(a×b) mod n
定理:设a∈Zn,gcd(a,n)=1,则a在Zn有逆元。 证明思路： 1. 用反证法证明a和Zn中任何两个不同的数相乘结果 都不相同 2. 从1得出a×Zn=Zn,因此存在x∈Zn,使a×x=1 mod n • 设a为素数，Zp中每一个非零元素都与a互素，因此 有乘法逆元，有乘法可约律 (a×b)=(a×c) mod n, b=c mod n
5. (T1 T2 T3)(X1-QY1,X2-QY2,X3-QY3);
6. (X1 X2 X3)(Y1Y2 Y3); 7. (Y1Y2 Y3)(T1 T2 T3); 8.Goto 2
例：求解 11d (mod51) = 1的步骤。 即求11-1mod51=？
循 环 次 数
Q
X 1 1 0 1 -1 2
• 欧拉定理
若a和n互素,则aφ (n)=1 mod n
4.1.5 素性检验
对给定的数检验其是否为素数
• 爱拉托斯散(Eratosthenes)筛法 定理： 设n是正整数，若对所有满足p≤ p | n，那么n一定是素数。 若要找出不大于n的所有素数：
n 的素数p，都有
先将2到n之间的整数列出，从中删除小于等于 n 的所有 素数的倍数，余下的整数即是所要求的素数。 此方法在n很大时，实际上是不可行的。
• 欧拉函数 –设n为一正整数，小于n且与n互素的正整数的个数 称为n的欧拉函数，记为φ(n) 例：Φ(6)=2, Φ(7)=6, Φ(8)=4 显然，若n是素数， Φ(n)=n-1
定理： 若n是两个素数p和q的乘积，则Φ(n)＝ Φ(p) Φ(q)=(p-1)(q-1)
例：21=3×7 ，因此φ(21)= φ(3) × φ(7)=2×6=12
扩展欧几里德算法： Extended Euclid(f,d) (f>d) 求d模f的逆元 1.（X1 X2 X3)(1,0,f);(Y1Y2 Y3)(0,1,d);
2. If Y3=0, then return X3=gcd(f,d);停止，没有逆元;
3. If Y3=1, then return X3=gcd(f,d);Y2=d-1 mod f; 4. Q=X3 div Y3（整数除）;
X 2 0
X 3
Y 1
Y 2 1
Y 3 11
f *X1+ d*X2 =X3 f *Y1+ d*Y2 =Y3 f *T1+ d*T2 =T3
Extended Euclid(f,d) (f>d) 1.（X1 X2 X3)(1,0,f); (Y1Y2 Y3)(0,1,d); 2. If Y3=0, then return X3=gcd(f,d); 停止，没有逆元; 3. If Y3=1, then return X3=gcd(f,d);Y2=d-1 mod f; 4. Q=X3 div Y3（整数除）; 5. (T1 T2 T3) (X1-QY1,X2-QY2,X3QY3); 6. (X1 X2 X3)(Y1Y2 Y3); 7. (Y1Y2 Y3)(T1 T2 T3); -1 11 mod51=14 8.Goto 2
公钥密码
制的基本概念
RSA算法
4.1.1 群、环、域
群<G,*>的定义:
*为乘法时，称为乘法群 逆元（a-1） *为加法时，称为加法群 逆元（-a）
一些数字组成的集合 一个二元运算，运算结果属于此集合（封闭性） 服从结合律。有单位元，逆元 。 如果是可交换的，则成为Abel群
即：{a mod p,2a mod p,…,(n-1)a mod p} ={1,…,p-1}
(a mod p) ×(2a mod p) ×…×(n-1)a mod p=(p-1)!ap-1 mod p
因此：(p-1)! ap-1 mod p =(p-1)!modp
(p-1)!与p互素，所以乘法可约律，ap-1=1 mod p
初 -值 1 2 3 4 4 1 1 1
51 0
1 11 1 -4 7 5 4 -1 2
-4 7 5 -9 4 3 1
-9 3
-3 14
Q=X3 div Y3 = 51/11 = 4 T1=X1-Q*Y1 = 1- 4*0 = 1
Miller-Rabin素性概率检测法
引理： 如果p为大于2的素数，则方程x2≡1 mod p的解只有和 x≡1和x≡-1
证明: x2≡1 mod p x2 -1 ≡0 mod p(x+1)(x-1)≡0 mod p 例： x2=1(mod8) 所以： p|(x+1)或p|(x-1)或p|(x+1)且p|(x-1) 若 且p|(x-1) ，则存在 x+1=kp, 12p|(x+1) =1 mod8 32=1 mod8 k,j，使 52=1 mod8 x-1=jp 72=1 mod8 可得：2=(k-j)p, 这是不可能的。 又5=-3 mod8 ， 7=-1 mod8， 所以： p|(x+1)或p|(x-1) 所以方程的解为：1，-1，3，-3 8不是素数。 设： p|(x+1)，则x+1=kp x=-1modp 设： p|(x-1)，则x-1+1=kp x=1modp
定义Zn为小于n的所有非负整数集合 Zn={0,1,2,…,n-1}
4.1.4 费尔玛定理和欧拉定理
费尔玛定理： 若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1 mod p • 证明： 当gcd(a,p)=1,则a×Zp=Zp 。 又因为a×0≡0modp,所以a×(Zp-{0})=Zp-{0}
素数：
• 素数: 只有因子 1 和自身 • 1 是一个平凡素数 • 例 2,3,5,7 是素数, 4,6,8,9,10 不是
200以内的素数：
• 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
由d|a和d|kb，得d|(a mod b)， 故d是b和a mod b的公因子。 a,b以及b,a mod b公因子集合相同，故最大公因子也相同。 gcd(55,22)=gcd(22,11)=gcd(11,0)=11 gcd(11,10)=gcd(10,1)=1
Euclid算法： Euclid(f,d) f>d 1. Xf;Yd;
素数分解：
• • • 把整数n写成素数的乘积 分解整数要比乘法困难 整数 n的素数分解是把它写素数的乘积 eg. 91 = 7 × 13 ; 3600 = 24 × 32 × 52
互素数：
• 整数 a, b 互素是指 它们没有除1之外的其它因子。 8 与15 互素 8的因子1,2,4,8 15的因子 1,3,5,15 1 是唯一的公因子 • 记为：gcd(8,15)=1
环<R,+,*>的定义:
Abel 群，及一个乘法运算： 满足结合律与加法的分配律 如果加法满足交换律, 则称交换环 例：整数 mod N （for any N ）
域<F,+,*>的定义： <F,+>是Abel加群 环 <F-{0},*>是Abel 乘群 例： 整数 mod P （ P 为素数）
引理的逆命题： 若方程x2≡1 mod p，有唯一解x不为+1或-1，p不是素数。
• Miller-Rabin素性概率检测法 –n为待检测数，a为小于n的整数，将n-1表示为二进 制形式bkbk-1…b0,d赋初值为1，算法核心如下： for i=k downto 0 do n-1≡-1 mod n,所以x ≠1和x ≠n-1指 {xd; x2≡1 mod n 有非±1的根,n不是素数。 d(d×d) mod n; if d=1 and (x≠1)and(x≠n-1) then return False if bi=1 the d(d×a) mod n } For循环结束,有d≡an-1 mod n。 由费尔玛定理,若n为素数,d为1。 if d ≠1 then return False; 所以d≠1，则d不是素数。 return True –若返回False,n不是素数,若返回True,有可能是素数。
