第2讲 同余式new.ppt

第2章 同余式 漳州师范学院计算机科学与工程系 § 2.0 同余及其基本性质 中国剩余定理（孙子定理） 在《孙子算经》中，有“物不知其数”一问 今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何 在程大位著的《算法统要》(1593年)中给出解法： 三人同行七十稀，五树梅花廿一枝， 七子团圆正月半，除百零五便得知。 用同余式表示“物不知其数”问题，就是求一个（最小的）正整数x，使 这是一个解同余方程组的问题 某月的1号是星期一，问该月的23号是星期几？ 解：23≡2（mod 7)，2号是星期二，故23号是星期二 § 2.1 中国剩余定理 简单同余方程组 简单同余方程组 简单同余方程组 分析 中国剩余定理 分析 分析 分析 解：利用中国剩余定理，m=3×5×7=105, M1=35, M2=21, M3=15, 所以其解为x=35×2×2+21×3+15×2(mod 105)=23(mod105) 中国剩余定理 中国剩余定理 中国剩余定理 中国剩余定理 § 2.2 剩余类环 剩余类和剩余系 剩余类和剩余系 剩余类和剩余系 剩余类和剩余系 剩余类和剩余系 剩余类和剩余系 剩余类环 剩余类环 剩余类环 Euler定理和Fermat小定理 Euler定理和Fermat小定理 Euler定理和Fermat小定理 Euler定理和Fermat小定理 Euler定理和Fermat小定理 Euler定理和Fermat小定理 Euler定理和Fermat小定理 计算?(m) 计算?(m) 计算?(m) 计算?(m) 计算?(m) 计算?(m) 计算?(m) 计算?(m) 计算?(m) § 2.3 同余方程 线性同余方程 线性同余方程 线性同余方程 线性同余方程 线性同余方程 线性同余方程 线性同余方程 线性同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 高次同余方程 Wilson 定理 Wilson 定理 Wilson 定理 降低方程次数 Wilson 定理 一次同余方程的密码学应用 单表密码 首先建立英文字母和模数26的剩余之间的对应关系 移位密码:将每个字母对应的数字后移若干位作为密文字母对应的数字.如恺撒(Caesar)密码,将每个字母后移3位 Thiscryptosystemisnotsecure wklvfubswrvbvwhplvgrwvhfxuh E≡P+3 mod 26 P ≡E-3 mod 26 仿射密码:将每个字母对应的数字乘以k后再加b作为密文字母对应的数字.如k=7,b=6 Thiscryptosystemisnotsecure jdkcuvshjacscjimkctajciuqvi E≡7P+6 mod 26 P ≡15E+14 mod 26(7×15≡1(mod 26)) § 2.4 原根 模m的阶 模m的阶 模m的阶 模m的阶 模m的阶 模m的阶 模m的阶 k次剩余 k次剩余 k次剩余 k次剩余 k次剩余 k次剩余 k次剩余 k次剩余 k次剩余 原根 原根 原根 原根 原根 原根 求模p的原根 原根 原根 原根 原根 原根 原根 原根 例子 求素数p=47的一个原根 解:对p=47，有标准素因子分解47-1=46=2×23 取整数a=2，223≡1(mod 47)，失败 取整数a=3，323≡1(mod 47)，失败 取整数a=5，523≡-1(mod 47)， 52≡25(mod 47)，因此a=5是p=47的一个原根 原根的一个密码学应用 ElGamal公钥密码体制： 选取大素数p和p的一个原根a，(a,p)=1，1ap 随机选取整数d，2≤d≤p-2，计算?=ad(mod p) p,a,?是公开的加密密钥，d是必威体育官网网址的解密密钥 明文空间为Zp*，密文空间为Zp* ×Zp* 加密变换：对任意明文m∈ Zp*，秘密随机选取一个整数k，2≤k≤p-2 ，密文为c=(c1,c2)，其中，c1=ak(mod p)， c2=m?k(mod p) 解密变换：对任意密文c=(c1,c2) ∈Zp* ×Zp* ，明文为m=c2(c1d)-1(mod p) 证明：因为c1=ak(mod p)， c2=m?k(mod p) ， ?=ad(mod p) ，所以c2(c1d)-1≡m?k(akd)-1≡ madk(akd)-1≡m(mod p) ，即解密变换能正确地从密文恢复出相应的明文，证毕 由上例知p=47有一个原