密码学数学基础第五讲 二次剩余.pdf

第第5讲讲 二次剩余二次剩余 教师教师：：李艳俊李艳俊 本讲内容本讲内容 一一、、二次剩余的概念二次剩余的概念 二二、、模为奇素数的平方剩余与平方非剩余模为奇素数的平方剩余与平方非剩余 三三、、勒让德符号勒让德符号 四四、、雅可比符号雅可比符号 五五、、小结小结 一一、、二次剩余的概念二次剩余的概念 二次同余式的一般形式是二次同余式的一般形式是 )(mod0 2 mcbxax )(mod0m a   其中其中m是正整数是正整数，， 上式等价于同余式上式等价于同余式 2 (mod)ydm acbdbaxy4,2 2  )(mod 2 max1),(ma 定义定义1 设设m是正整数是正整数，，若同余式若同余式 有解有解，，则则a叫做模叫做模m的的平方剩余平方剩余(或二次剩余或二次剩余)；；否则否则a叫做叫做 模模m的的平方非剩余平方非剩余(或二次非剩余或二次非剩余) 例例1 1 分别求出模分别求出模1111，，1212的二次剩余和二次非剩余的二次剩余和二次非剩余 解解：： 模模1111的二次剩余是的二次剩余是：：1 1，，3 3，，4 4，，5 5，，9 9；； 二次非剩余是二次非剩余是：：2 2，，6 6，，7 7，，8 8，，1010。

模模1212的二次剩余是的二次剩余是：：1 1；； 二次非剩余是二次非剩余是：：5，，7，，11 例例2 求满足同余式求满足同余式的所有的点的所有的点)7(mod2 32 xxy 解解：： 模模7的二次剩余是的二次剩余是：：1，，2，，4；；二次非剩余是二次非剩余是：：3，，5，，6 对对，，分别求出分别求出对应的的值为对应的的值为)7(mod6 , 5 , 4 , 3 , 2 , 1 , 0x y )7(mod4 , 3y )7(mod5 , 2y )7(mod5 , 2y )7(mod0y )7(mod0y )7(mod0x )7(mod1x )7(mod3x )7(mod4x )7(mod6x )7(mod2x )7(mod5x )7(mod2 2 y )7(mod4 2 y )7(mod4 2 y )7(mod0 2 y )7(mod0 2 y )7(mod5 2 y )7(mod6 2 y 无解无解 无解无解 二二、、模为奇素数的平方剩余与平方非剩余模为奇素数的平方剩余与平方非剩余 定理定理1(欧拉判别条件欧拉判别条件) 设设p是奇素数是奇素数，，，，则则 (1) a是模是模p的平方剩余的充分必要条件是的平方剩余的充分必要条件是 (2) a是模是模p的平方非剩余的充分必要条件是的平方非剩余的充分必要条件是 当当a是模是模p的平方剩余时的平方剩余时，，同余式同余式恰有两解恰有两解。

1),(pa )(mod1 2 1 pa p   )(mod1 2 1 pa p   )(mod 2 pax  227 1 113 2 137mod227137mod2271   解解: 例例 判断判断137是否为模是否为模227平方剩余平方剩余 定理定理2 设设p是奇素数是奇素数，，则模则模p的简化剩余系中平方剩余与的简化剩余系中平方剩余与 平方非剩余的个数各为平方非剩余的个数各为，，且且个平方剩余与序列个平方剩余与序列 中的一个数同余中的一个数同余，，且仅与一个数同余且仅与一个数同余 2 1p 2 1p 222 ) 2 1 ( ,,2 ,1 p  所以所以137是模是模227平方非剩余平方非剩余 三三、、勒让德符号勒让德符号 由此定义由此定义，，欧拉判别法则可以表示成如下形式欧拉判别法则可以表示成如下形式：：               , 0 , 1 , 1 p a ap pa pa |若 的平方非剩余是模若 的平方剩余是模若 定义定义 设设p是素数是素数，，定义勒让德符号如下定义勒让德符号如下：： 定理定理 设设p是奇素数是奇素数，，则对任意整数则对任意整数a，，有有 )(mod 2 1 pa p a p          设设p是奇素数是奇素数，，则勒让德符号有如下性质则勒让德符号有如下性质：： (2) ，，进一步进一步，，若若，，则则；；                  p a p pa )(mod pba                   p b p a (3) ，，进一步进一步，，若若，，则则，， 若若，，则则；；                          p b p a p ab 1),(pa 1 2          p a 1),(   pa0 2          p a 1 1          p 2 1 ) 1( 1           p p (1) ，，；； qp, 11 22 ( 1) pq qp pq       (5) 若若是互素的奇素数是互素的奇素数，，则则。

8 1 2 ) 1( 2           p p (4) ；； 例例1 计算如下勒让德符号的值计算如下勒让德符号的值 , 3 2      2 , 17          17 3       227 137       2003 911 (1) (2) (3) n m m是否为素数是否为素数 q=0q=1q=-1q=2 out:01 停止停止 否否 是是，，计算计算nmodm=q 2 1 8 ( 1) m   1 2 ( 1) m  返回返回 12 12 r kkk r qppp 12 1111 () 2222 12 ( 1) i pppm i mmm ppp        i kkk,, 21 rii kkk,, 21 为奇数为奇数；； 为偶数为偶数 例例2 判断同余式判断同余式 )305(mod1 2 x 是否有解是否有解？？有解时有解时，，求出其解数求出其解数 例例3 判断同余式判断同余式 )413(mod2 2 x 是否有解是否有解？？有解时有解时，，求出其解数求出其解数。

注意注意：：雅可比符号为雅可比符号为1时时，，不能判断不能判断a是否为模是否为模m的平的平 方剩余方剩余例如例如 四四、、雅可比符号雅可比符号                       r p a p a m a  1 r ppm 1  i p a 定义定义 设设是奇素数是奇素数的乘积的乘积对任意整对任意整 数数，，定义雅可比定义雅可比(Jacobi)符号为符号为 333 ( 1)( 1)1 119717       因为因为，，而同余式组而同余式组的每个同的每个同 余式都无解余式都无解，，所以所以3是模是模119的平方非剩余的平方非剩余 177119      )17(mod3 )7(mod3 2 2 x x m为奇素数时为奇素数时，，则为勒让德符号则为勒让德符号 如果如果，，则则；；( ,)1a m  2 0 a m     设设m是奇数是奇数，，则雅可比符号有以下性质则雅可比符号有以下性质：： 1),(ma 1 2 2                m a m a ，，如果如果，，则则；；                  m b m a m ab (3)             m a m ma (2) ；； 1 1       m (1) 2 1 ) 1( 1         m m ，， 8 1 ) 1( 2         mm m (4) (5) 设设m,n都是奇数都是奇数，，则则。

               n m m n nm 2 1 2 1 ) 1( )563(mod286 2 x 例例 判断同余式是否有解判断同余式是否有解？？ 563 563 1143 1 563 1 822 143 1 2 2862143563 ( 1)( 1) 563563563143 91 ( 1)1 143143               解解 不用考虑不用考虑563是否为素数是否为素数，，直接计算雅可比符号直接计算雅可比符号: 所以同余式无解所以同余式无解 五五、、小结小结 )(mod 2 max 1),(ma1、、m是正整数是正整数 a是是m的二次剩余的二次剩余 2、、欧拉判别条件欧拉判别条件p是奇素数是奇素数 ( , )1a p  1 2 1(mod) p apap  是 的平方剩余 1 2 1(mod) p apap   是 的平方非剩余               , 0 , 1 , 1 p a ap pa pa |若 的平方非剩余是模若 的平方剩余是模若 3、、勒让德符号的定义勒让德符号的定义 设设p是素数是素数，，定义如下定义如下：：                       r p a p a m a  1 4、、雅可比符号定义雅可比符号定义 对任意奇数对任意奇数m，，定义为定义为：： , am am m a  不一定是模 的平方剩余 若 是模 的平方非剩余 若() 1 1, 1, 0,        课后作业课后作业 （（1 1））习题习题1 1、、3 3、、8 8 （（2 2））预习第预习第6 6章章 群群 。