第四章公钥密码:4.1公钥密码常用知识和算法 4.1公钥密码常用知识和算法 ●一、基本数学知识 ●群、环、域、素数 ≥欧几里得算法、扩展欧几里 ●模运算 德算法 ●费尔马定理 求最大公约数和乘法的逆元 pl=1modp,p是素数 ●中国剩余定理 欧拉函数 求一次同余方程组的解 p(n):小于m的且与n互素的正整 数个数 ●离散对数,本原根 ap(n=1 mod n 平方剩余 ●素性检验 ●计算复杂性 1爱拉托斯散筛法( Eratosthenes 依次删去小于m素数的倍数 2. Miller- Rabin概率检测法 3.AKS 历忠毛孑技*字4.1 公钥密码常用知识和算法  一、基本数学知识  群、环、域、素数  模运算  费尔马定理 ⚫ a p-1=1 mod p ，p是素数  欧拉函数 ⚫ (n)：小于n的且与n互素的正整 数个数 ⚫ a (n)=1 mod n  素性检验 ⚫ 1.爱拉托斯散筛法(Eratosthenes) ⚫ 依次删去小于 素数的倍数 ⚫ 2. Miller-Rabin概率检测法 ⚫ 3.AKS 3/ 第四章 公钥密码：4.1 公钥密码常用知识和算法  欧几里得算法、扩展欧几里 德算法 ⚫ 求最大公约数和乘法的逆元  中国剩余定理 ⚫ 求一次同余方程组的解  离散对数，本原根  平方剩余  计算复杂性 n