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

《初等数论ppt第四章 同余式、一次同余式、孙子定理课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、gcd(m,n)=1mj(n)≡1modn—欧拉定理mkj(n)≡1modnmkj(n)+1≡mmodngcd(m,n)≠1m是p的倍数或q的倍数，设m=cp，gcd(m,q)=1,mj(q)≡1modq，mkj(q)≡1modq，[mkj(q)]j(p)≡1modqmkj(n)≡1modq，存在一整数r，使mkj(n)≡1＋rq两边同乘m=cp,mkj(n)+1≡m+rcpq=m+rcn,即mkj(n)+1≡mmodn11RSA算法实现如何判定一个给定的大整数是素数？已知d如何计算e，使e*d≡1modΦ(n)？如何计算C≡Memodn或M≡Cdmodn？12第四章基

3、本内容同余式的概念一次同余式概念及求解孙子定理：求解同余方程组高次同余式的解数及解法质数模的同余式§1基本概念及一次同余式§2孙子定理除数余数最小公倍数衍数乘率各总答数最小答数323×5×7=1055×7235×2×2140+63+30=233233-2×105=23537×3121×1×3723×5115×1×2除数余数最小公倍数衍数乘率各总答数m1b1M1m2b2M2︰︰︰︰︰mkbkMk利用中国剩余定理的计算机算数运算作业7：P751，2P791