二次剩余课件.ppt

1、第三章第三章 二次剩余二次剩余本章内容一、二次剩余的概念一、二次剩余的概念二、模为奇素数的平方剩余与平方非剩余二、模为奇素数的平方剩余与平方非剩余 三、勒让德符号三、勒让德符号 四、雅可比符号四、雅可比符号五、小结五、小结重点重点：二次同余方程有解的判断与求解二次同余方程有解的判断与求解3.1 二次剩余的概念二次同余式的一般形式是二次同余式的一般形式是)(mod02mcbxax)(mod0ma 其中其中m是正整数，是正整数， 。上式等价于同余式上式等价于同余式2(mod)ydmacbdbaxy4,22)(mod2max1),(ma 定义定义1 设设m是正整数，若同余式是正整数，若同余式有解，则

2、有解，则a叫做模叫做模m的的平方剩余平方剩余(或二次剩余或二次剩余)，记为，记为QR；否则否则a叫做模叫做模m的的平方非剩余平方非剩余(或二次非剩余或二次非剩余)，记为，记为NR 。例例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(

3、mod232xxy解：解： 模模7的二次剩余是：的二次剩余是：1，2，4；二次非剩余是：；二次非剩余是：3，5，6。 对对 ，分别求出，分别求出 对应的的值为对应的的值为 )7(mod6 , 5 , 4 , 3 , 2 , 1 , 0 xy)7(mod0 x)7(mod22y)7(mod4 , 3y)7(mod1x)7(mod42y)7(mod5 , 2y)7(mod3x)7(mod42y)7(mod5 , 2y)7(mod4x)7(mod02y)7(mod0y)7(mod6x)7(mod02y)7(mod0y)7(mod2x)7(mod52y无解无解)7(mod5x)7(mod62y无解无解

4、3.2 模为奇素数的平方剩余与平方非剩余2(mod11)xa 例例如如： 111,2,3, 4,5 .取取模模的的一一个个简简化化系系为为可以验证：可以验证：11 111 12211(mod11); ( 2)1(mod11);11 111 122( 1)1(mod11); 21(mod11); 而而11 111 111 122231(mod11); 41(mod11);51(mod11).11 111 122( 3)1(mod11);( 4)1(mod11); 11 12( 5)1(mod11). 模模11的平方剩余为的平方剩余为1，-2，3，4，5；平方非剩余为平方非剩余为-1，2，-3，-

5、4，-5.2(mod11)xa 例例如如：模模11的平方剩余为的平方剩余为1，-2，3，4，5.22(mod11)3,8(mod11);xx 方方程程的的解解为为：21(mod11)1,10(mod11);xx方方程程的的解解为为：23(mod11)5,6(mod11);xx方方程程的的解解为为：24(mod11)2,9(mod11);xx方方程程的的解解为为：25(mod11)4,7(mod11).xx方方程程的的解解为为：例1 利用定理判断补充 模重复平方计算法补充 模重复平方计算法 符号表示如下：QR QR=QR QR NR=NRNR NR=QR 若用数字代替符号QR与NR，易见：QR如

6、同+1 NR如同-1 定理定理2 设设p是奇素数，则模是奇素数，则模p的简化剩余系中平方剩余与的简化剩余系中平方剩余与平方非剩余的个数各为平方非剩余的个数各为 ，且，且 个平方剩余与序列个平方剩余与序列中的一个数同余，且仅与一个数同余。中的一个数同余，且仅与一个数同余。21p21p222)21( ,2 ,1p 7,1,2,3 .p 例例如如：取取则则其其简简化化系系为为模模7的平方剩余为的平方剩余为1，2，-3；平方非剩余为平方非剩余为 -1，-2，3.22211 (mod7);23 (mod7); 32 (mod7). 且且有有：3.3 勒让德符号勒让德符号利用欧拉判别条件虽然可以判定利用欧

7、拉判别条件虽然可以判定 x2 a (mod p) 的解的存在性，但对较大的素数模，实际运用很困难。的解的存在性，但对较大的素数模，实际运用很困难。通过引入勒让德符号，本节给出了较方便的判别方法。通过引入勒让德符号，本节给出了较方便的判别方法。目的：目的：快速判断整数快速判断整数a是否为素数是否为素数p的平方剩余。的平方剩余。, 0, 1, 1paappapa|若的平方非剩余是模若的平方剩余是模若 定义定义 设设p是素数是素数, 定义勒让德定义勒让德Legendre符号如符号如下：下：123451111 0.55555( )( )( )( )( ) ，如如, 1, 1与与4 4是模是模5 5的平

8、方剩余，的平方剩余，2 2与与3 3是模是模5 5的平方非剩余，的平方非剩余，所所以以有有由此定义，欧拉判别法则可以表示成如下形式：由此定义，欧拉判别法则可以表示成如下形式： 定理定理2 设设p是奇素数，则对任意整数是奇素数，则对任意整数a，有，有 )(mod21papap定理定理1 1 Legendre符号基本性质符号基本性质 11 (1,2,)22 (Gauss ( 1) .)mpaa , ppakk =ppmap 设设 是是奇奇素素数数, , 是是整整数数, ,如如果果整整数数中中模模 的的最最小小正正剩剩余余大大于于的的个个数数是是, ,则则 引引理理( () ), ,2p于于的的最最

9、小小正正剩剩余余 则则121,1,2,2tpa aaaaa 证证 设设是是整整数数关关2pp于于模模 的的小小于于的的最最小小正正剩剩余余, ,12 ,mb bb是是一一切切大大1211!(1)(2)()22pppaaaa 1212 (mod)tma aa b bbp 1212( 1)()()() (mod)mtma aapbpbpbp ()(mod)jjpbbp 0 (mod)jiijpakakakakp或或111.22ijppkkp因因为为 12, mpbpbpbp是是模模 两两两两不不同同余余的的. .1212, tma aapbpbpbp易易知知是是模模 两两两两不不同同余余的的. .

10、12,ta aap事事实实上上, ,是是模模 两两两两不不同同余余的的, ,若若有有 (mod),jipbap ,ijk k则则有有使使( , )1, 0 (mod),ijp akkp因因所所以以这这不不可可能能, ,12121,1,2,2tmpa aapbpbpb 是是的的一一1211!(1)(2)()22pppaaaa 1212(1)()()()mtma aapbpbpb1(1)! (mod)2mpp 于于是是1(, )1, 1,2,2pak pk 因因为为1 2p 所所以以个个整整数数个个排排列列. .12 (1) (mod)pmaapp 因因此此引引理理得得证证. .1,ap 注注意意

11、到到 ( 1) .map 故故 212118 (i) ( 1)(ii) ( ,2)1, ( 1)pkpakpppapap 设设 是是奇奇素素数数定定理理若若3 32 2则则 , ,1,0,1,2,2kkakpakprrp kp 证证 因因11,2,2pk 对对求求和和 有有111222111()pppkkkkakakprp12211118ptmijkijpakapabp 即即 121111()2ptmmijjkijjakpapbbmpp 由引理由引理的证明的证明12211128pmjkjakppmpbp 122111, (1)28pmjkjpakapmpbp 因因此此1122111(1)(1)

12、2ppmjkkjakakmpm pbpp12211 (1) (mod2)8pkpakamp 所所以以2 2的倍数的倍数12,00,akpapp 若若则则21 (mod2)8pm 于于是是212 8pmr 22112222( 1)( 1)( 1)pprmp 由由引引理理121 (mod2)pkakamp 若若 为为奇奇数数, , 则则112211 +2( 1)( 1)( 1)ppkkakaktppmap 由由引引理理121 +2pkakmtp 即即 证明：证明：由由 定理定理3 有有1122, ( 1).pqqppq 显显然然 只只需需证证明明等等式式二次互反律的证明：二次互反律的证明：1122

13、11, ( 1)pqhkqhpkpqqppq 于于是是112211 ( 1), ( 1)pqhkqhpkpqqppq 为为此此 只只需需证证明明, ,11221111 22pqhkqhpkpqpq1111 , 22pqpq令令22pq考考察察长长为为, ,宽宽为为 的的矩矩形形内内的的整整点点个个数数. .:如如下下图图11.OABCp q一一方方面面, ,矩矩形形内内所所含含的的整整数数点点个个数数为为qhSTp另另一一方方面面, ,在在直直线线上上, ,整整点点个个数数为为, ,故故在在三三角角1(,0)A p1(0,)Cq(0,0)O(,)2 2p qBqyxp xy( ,0)S hTA

14、C1(,0)A p1(0,)Cq(0,0)O(,)2 2p qBqyxp xy( ,0)S hTAC11phqhOABp 形形内内的的整整点点个个数数为为. .11.qkpkOBCq 同同理理, ,三三角角形形内内的的整整点点个个数数为为(0, )NkMOABC故故矩矩形形内内的的整整点点1111pqhkqhpkpq 11111111 .22pqhkqhpkpqp qpq从从而而至至此此, ,二二次次互互反反律律得得证证. . ,qyxp 因因为为直直线线上上无无整整点点个个数数为为例例 计算如下勒让德符号的值。计算如下勒让德符号的值。 ,322,171732271372003911(1) (

15、2) (3) nmm是否为素数是否为素数q=0q=1q=-1q=2out:01停止停止否否是，计算是，计算nmodm=q218( 1)m 12( 1)m返回返回1212rkkkrqppp121111()222212( 1)ipppmimmmpppikkk,21riikkk,21为奇数；为奇数；为偶数。为偶数。 1 ,3p求求所所有有奇奇素素数数它它以以 为为其其例例二二次次剩剩余余. .31:p 即即求求满满足足条条件件的的分分析析所所有有奇奇素素数数. .3 1 3.ppp解解 设设 是是奇奇素素数数, ,易易知知满满足足条条件件的的由由二二次次互互反反律律123( 1)3ppp 121,

16、1 (mod4)( 1)1, 1 (mod4)ppp 当当因因 当当11, 1 (mod6)3311, 1 (mod6)3ppp 当当当当1 (mod4)1 (mod4)31 1 (mod6)1 (mod6)ppppp 所所以以或或311 (mod12) 1 (mod12)ppp 即即 或或 3 1 (mod12)pp 故故 是是模模 二二次次剩剩余余的的充充要要条条件件是是2 ,.1,dpdp 设设 是是奇奇素素数数是是整整 例例数数 如如果果则则22 ,ppxdy假假若若 有有表表达达式式( , )1.dp dp 证证 由由题题设设1 1知知, ,22 |, |.p xp xpdy 若若则

17、则( , )1, |.p dp y 因因所所以以2222|,|,pxpy于于是是有有222|,pxdyp从从而而 这这不不可可能能. .|,( , )1.pxp x 故故于于是是( , )1.p y 进进而而2221ddydyxppppp此此时时与与题题设设矛矛盾盾. .22pxdy 一一定定不不能能表表示示为为的的形形式式. .对于奇素数对于奇素数p，利用计算，利用计算Legendre符号可以判定方程符号可以判定方程x2 a (mod p) (1)是否有解。是否有解。对于一般的正整数对于一般的正整数m， 如何判定方程如何判定方程是否有解呢？是否有解呢？x2 a (mod m) (2) 四、雅

18、可比符号对于一般的正整数对于一般的正整数m，如果它的标准分解式是，如果它的标准分解式是1212kkmppp 那么判定方程那么判定方程 x2 a (mod m) (2)是否有解，是否有解，可归结为对形如方程可归结为对形如方程x2 a (mod p) (1) 的可解性判定。的可解性判定。 因此，在理论上，利用因此，在理论上，利用Legendre符号可以判定符号可以判定方程方程(2)是否有解。是否有解。 但是，写出正整数的标准分解式常会遇到实际困难，但是，写出正整数的标准分解式常会遇到实际困难， 所以利用所以利用LegendreLegendre符号判定方程符号判定方程(2)(2)的可解性并不容的可解

19、性并不容易实现。易实现。 例如，取例如，取m = 45 = 3 3 5，则，则251822222( 1)1453355( ) ( )( )( ) ( ) ，3 1 5 12228282828352( 1)145335533( ) ( )( )( ) ( )( ) ( ) . .rpapama1rppm1ipa 定义定义 设设 是奇素数是奇素数 的乘积。对任意整的乘积。对任意整数数 ，定义雅可比，定义雅可比(Jacobi)符号为符号为()iap其其中中右右端端的的（1 i k）是）是Legendre符号。符号。 例如，取例如，取m = 45 = 3 3 5，则，则251822222( 1)145

20、3355( ) ( )( )( ) ( ) ，3 1 5 12228282828352( 1)145335533( ) ( )( )( ) ( )( ) ( ) . .当当m为奇素数时，则上式为勒让德符号。为奇素数时，则上式为勒让德符号。 注意注意：(1) 当当m是奇素数时，是奇素数时，Jacobi符号就是符号就是Legendre符号。符号。 前者是前者是后者的推广。后者的推广。 (2) 雅可比符号为雅可比符号为1时，不能判断时，不能判断a是否为模是否为模m的平方的平方剩余。例如剩余。例如333( 1)( 1)1119717 因为因为 ，而同余式组，而同余式组 的每个同的每个同余式都无解，所以

21、余式都无解，所以3是模是模119的平方非剩余。的平方非剩余。177119)17(mod3)7(mod322xx 如果如果 ，则，则 ； ( ,)1a m 20am设设m是奇数，则雅可比符号有以下性质：是奇数，则雅可比符号有以下性质：1),(ma122mama ，如果，如果 ，则，则 ； mbmamab(3)mamma(2) ；11m(1)21) 1(1mm，81) 1(2mmm(4)(5) 设设m,n都是奇数，则都是奇数，则 。nmmnnm2121) 1(12, 2,rmp ppmN NZ理理 若若，则则得得引引，使使221111112,2.2288rriiiippmmNN121122rmp

22、pp 证证明明：12111(12)(12)(12)12222rppp 1122riipN 2222121188rmp pp 22212111(18)(18)(18)18888rppp 21128riipN 定理定理1 1 设设m = p1p2pk是奇数，其中是奇数，其中p1, p2, pk是素数，是素数，则下面的结论成立：则下面的结论成立：121(1)( 1);()mm 2182(2)( 1).( )mm 12( 1);m 111()()kiimp 证证明明：12111222( 1)kppp 122( 1)mN 122( )( )kiimp 22212111888( 1)kppp 218( 1

23、).m 定理定理2 2 设设m，n是大于是大于1的奇整数，则的奇整数，则1122( 1)( )( )mnnmmn 利用以上定理，我们可以很容易地计算利用以上定理，我们可以很容易地计算Jacobi符符号，特别是号，特别是Legendre符号的数值。但是，必须注意，符号的数值。但是，必须注意，如同在定义的注如同在定义的注2中指出的，在判断方程中指出的，在判断方程(2)的可解的可解性时，性时，Legendre符号和符号和Jacobi的作用是不一样的。的作用是不一样的。 方程方程(2)(2)有解。有解。对于一般的正奇数对于一般的正奇数m来说，来说， = 1并不能保证并不能保证()am)563(mod2

24、862x例例 判断同余式是否有解？判断同余式是否有解？563 563 1143 1 563 1822143 122862143563( 1)( 1)56356356314391( 1)1143143 解：不用考虑解：不用考虑563是否为素数，直接计算雅可比符号是否为素数，直接计算雅可比符号:所以同余式无解。所以同余式无解。 当当n是合数的时候，若（是合数的时候，若（a/n）=1，则，则a不一定是模不一定是模n的二的二次剩余。定义次剩余。定义 |( , )1,nQaa na是模n的二次剩余 |1naJan则有则有 。集合。集合 中的数称为模中的数称为模n的伪二次剩余。的伪二次剩余。nnQJnnn

25、QJQ124581011131617192014164116161416411-11-1-11-111-11-1111-11-11-11-1-1-11-111-1-1-1-111-11例：例：2mod21a 3a 7a 21aa24() ( )ababa 与与例例 设设a与与b是正奇数，求是正奇数，求 的关系。的关系。22444() ()()aaababab 解解：2(4)18( 1)4()a baab 211 418224( 1)( 1)()baa bababa 21111822( 1)( )babba . .结论：猜想二次剩余问题的难度与因子分解难度相当。结论：猜想二次剩余问题的难度与因子

26、分解难度相当。 定理定理3.12 若若n=pq，且，且n的素因子的素因子p和和q已知，则整数已知，则整数a为为模模n的二次剩余，当且仅当的二次剩余，当且仅当 1aapq五、小结)(mod2max 1),(ma1、m是正整数是正整数a是是m的二次剩余。的二次剩余。2、欧拉判别条件、欧拉判别条件p是奇素数是奇素数( , )1a p 121(mod)papap是 的平方剩余121(mod)papap 是 的平方非剩余, 0, 1, 1paappapa|若的平方非剩余是模若的平方剩余是模若3、勒让德符号的定义、勒让德符号的定义 设设p是素数，定义如下：是素数，定义如下：rpapama14、雅可比符号定义、雅可比符号定义 对任意奇数对任意奇数m，定义为：，定义为：,amamm a 不一定是模 的平方剩余若 是模 的平方非剩余若() 11,1,0, 六六 应用应用作业作业 3月25日 P45 3.3 3.5 3.9 4月8 日 P45 3.6 3.7 P 34 2.7(利用二次互反律)