例2 设p.q是两个不同的奇素数,n=pq, a是 与pq互素的整数,如果整数e满足1<e< (n) ,且(e, (n) )=1,那么存在整数d,1≤d< (n) 使得ed≡ 1(mod (n) ),而且,对于整 数a, c ,ae ≡c(mod n), 有cd ≡a(mod n) 证明:因为(e, (n) )=1,故存在整数d,1≤d< (n) 使得 ed≡ 1(mod (n) ), 因此,存在正整数k 使得 ed= 1+k (n)
• 定理2(Fermat) 设p是素数,则对于任意 的整数a,有 • ap a (mod p)。 • 证明 若(a, p) 1,则由定理1得到 • ap 1 1 (mod p) ap a (mod p)。 • 若(a, p) > 1,则pa,所以 • ap 0 a (mod p)。 • 证毕。
2.4 欧拉定理, 费马定理
定理3 (威尔逊定理) p为素数 iff (p-l)!-1(mod p).
充分性: 若(p-1)! = -l (mod p), 则 p为素数. 假设p是合数, 令 p=ab, a≠p. 由题设条件 知, p|((p-1)!+l). 又因 a|p, 则有 a|((p-1)!+1). 但由于 a≤p-1可得 a|(p-1)!, 从而 a|(((p1)!+1)-(p-1)!), 即a|l, 因而p只有因子1和p, 即p为素数
RSA公钥密码算法
• • • • • • (1)选取两个大素数p,q (2)计算n=pq, (n) =(p-1)(q-1) (3)随机选取正整数e,1< e < (n) 且(e,(n) )=1 (4)计算d,满足de≡1(mod (n) ) (p,q为了安全考虑通常被毁掉) d 是保密的,n,e公开 (5)加密:对明文m, 1< m< n ,加密后密文: c≡ me (mod n), • (6)解密:对应密文1< c< n ,解密后明文: m≡ cd (mod n),