初等数论第四章-同余式、一次同余式、孙子定理.ppt

第 四章 同余式 -基本概念、一次同余式、孙子定理复习4 欧拉定理 .费马定理及应用 公钥密码体制9算法描述密钥产生 独立地选取两大素数 p和 q(各 100 200位十进制数字 ) 计算 n=p q，其欧拉函数值 (n)=(p 1)(q 1) 随机选一整数 e， 1e(n)， gcd(n), e)=1 在模 (n)下，计算 e的有逆元 d=e -1 mod (n) 以 n， e为公钥。秘密钥为 d。 (p, q不再需要，可以销毁。 ) 加密将明文分组，各组对应的十进制数小于 n c=me mod n 解密 m=cd mod n10