电子科技大学：《现代密码理论 Modern Cryptographic Theory》课程教学资源（课件讲稿）第6章 公钥密码（一）6.1-6.4

例 9 6.1一次同余式与中国剩余定理

6.1 一次同余式与中国剩余定理

一次同余式与中国剩余定理 好 一 次同余式 中国剩余定理

中国剩余定理 一次同余式与中国剩余定理 一次同余式

一次同余式 。定义 ■给定整数a,b和正整数n,当mod n≠0，则称x=b mod n为模 n的一次同余式，其中x为变量。 。一次同余式有解的定理 ■一次同余式ax三b mod ni有解，当且仅当gcd(a,n)b。如果这个 同余式有解，则共有gcd(a,)个不同的解。 ■如果x是满足c三b mod n的一个整数，那么满足x三xo mod n 的所有整数也能满足≡b mod n。也就是说，x的同余类都 满足心三b mod n。我们称x的同余类为同余式的一个解

定义  给定整数a, b和正整数n，当a mod n≠0，则称ax ≡ b mod n为模 n的一次同余式，其中x为变量。 一次同余式有解的定理  一次同余式ax ≡ b mod n有解，当且仅当gcd(a, n)|b。如果这个 同余式有解，则共有gcd(a, n)个不同的解。  如果x0是满足ax ≡ b mod n的一个整数，那么满足x ≡ x0 mod n 的所有整数也能满足ax ≡ b mod n 。也就是说，x0的同余类都 满足ax ≡ b mod n 。我们称x0的同余类为同余式的一个解。 一次同余式

一小 次同余式组 。在密码学中，有时候需要求解一次同余式组： x=b modn x≡b2modn2 x=b mod ng ■其中，当时，gcd(nn)-l。 ■我国古代的《孙子算经》中就提到了这种形式的问题：“今有物 不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物 几何”。 x=2mod3 等价于求解同余式组： x≡3mod5 x=2mod 7

在密码学中，有时候需要求解一次同余式组：  其中，当i≠j时，gcd(ni , nj )=1。  我国古代的《孙子算经》中就提到了这种形式的问题：“今有物 不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物 几何”。 一次同余式组 等价于求解同余式组： 1 1 2 2 mod mod mod k k x b n x b n x b n           2mod 3 3mod5 2mod 7 x x x        

中国剩余定理 。定理 ■设n1,n2,,nw是两两互素的正整数，b1,b2,,b是任意k个整 数，则同余式组 x≡b mod n x≡b2modn2 x≡b,mod ng ■在模N=n12nk下有唯一解x三∑b,N,y,modN i=1 ■其中，N=NWny=N1 mod n,i=l,2,,ko

定理  设n1 , n2 , …, nk是两两互素的正整数，b1 , b2 , …, bk是任意k个整 数，则同余式组  在模N=n1n2…nk下有唯一解  其中，Ni =N/ni , yi≡Ni -1 mod ni , i=1, 2, …, k。 中国剩余定理 1 1 2 2 mod mod mod k k x b n x b n x b n           1 mod k i i i i x b N y N  

中国剩余定理 。利用中国剩余定理求解同余式方程组 x≡2mod3 x=3mod5 x=2mod 7 解：由前面定理可知n1=3,n2=5,n3=7,b1=2,b2=3,b3=2 由计算得N=3×5×7=105,N=105/3=35,N2=105/5=21,N3=105/7=15, y1351m0d3=2m0d3,y2=211m0d5=1mod5,y3=151mod7=1mod7 则x=2×35×2+3×21×1+2×15×1m0d105=23m0d105

利用中国剩余定理求解同余式方程组 解：由前面定理可知n1=3, n2=5, n3=7, b1=2, b2=3, b3=2 由计算得N=3×5×7=105, N1=105/3=35, N2=105/5=21, N3=105/7=15， y1≡35-1mod 3=2 mod 3，y2≡21-1mod 5=1 mod 5，y3≡15-1mod 7=1 mod 7 则x≡2×35×2+3×21×1+2×15×1 mod 105=23 mod 105. 中国剩余定理 2mod 3 3mod5 2mod 7 x x x        

例 9 6.2二次剩余

6.2 二次剩余

二次剩余 ·二次剩余定义 ■令n为正整数，若一整数a满足gcd(a,n)=1且x2≡a mod ni有 解，则称a为模n的二次剩余(quadratic residue);否则称a为 模n的二次非剩余(quadratic non-residue)。 ·欧拉判别法则 ■设p为奇素数，如果a是模p的二次剩余，则： p-] a2≡1modp 如果a是模p的二次非剩余，则： p-l a2≡-1modp

二次剩余定义  令n为正整数，若一整数a满足gcd(a, n)=1且𝒙 𝟐 ≡ a mod n有 解，则称a为模n的二次剩余(quadratic residue)；否则称a为 模n的二次非剩余(quadratic non-residue)。 欧拉判别法则  设p为奇素数，如果a是模p的二次剩余，则： 如果a是模p的二次非剩余，则： 二次剩余 1 2 1mod p a p   1 2 1mod p a p   

二次剩余举例 ■设n=7,因为 12≡1m0d7,22≡4m0d7 32≡2m0d7,42≡2m0d7 52=4m0d7,62≡1mod7 1、2、4是模7的二次剩余，而3、5、6是模7的二次非剩余。 ■如p是素数，则模p的二次剩余的个数为(p-1)/2,模p的二次非剩余 的个数也为(p-1)/2

二次剩余举例  设n=7，因为 1 2  1 mod 7，2 2  4 mod 7 3 2  2 mod 7，4 2  2 mod 7 5 2  4 mod 7，6 2  1 mod 7 1、2、4是模7的二次剩余，而3、5、6是模7的二次非剩余。  如p是素数，则模p的二次剩余的个数为(p-1)/2，模p的二次非剩余 的个数也为(p-1)/2

例 9 6.3指数与原根

6.3 指数与原根