第九章課件 二次剩余

1、二次剩余二次剩余本講內(nèi)容本講內(nèi)容二次剩余的概念二次剩余的概念模為奇素?cái)?shù)的二次剩余與二次非剩余模為奇素?cái)?shù)的二次剩余與二次非剩余 勒讓德符號(hào)勒讓德符號(hào) RabinRabin公鑰密碼算法公鑰密碼算法二次剩余的概念二次剩余的概念二次同余式的一般形式是二次同余式的一般形式是)(mod02mcbxax)(mod0ma 其中其中m是正整數(shù)，是正整數(shù)， 。上式等價(jià)于同余式上式等價(jià)于同余式2(mod)ydm22,4yaxb dbac)(mod2max1),(ma設(shè)設(shè)m是大于是大于1的整數(shù)，若同余式的整數(shù)，若同余式有解，則有解，則a叫做模叫做模m的二次剩余；否則的二次剩余；否則a叫做模叫做模m的二次非的二次非剩余

2、。剩余。例：求滿足同余式例：求滿足同余式 的所有的點(diǎn)。的所有的點(diǎn)。 )7(mod232xxy模模7的二次剩余是：的二次剩余是：1，2，4；二次非剩余是：；二次非剩余是：3，5，6。 對(duì)對(duì) ，分別求出，分別求出 對(duì)應(yīng)的的值為對(duì)應(yīng)的的值為 )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

3、(mod52y無解無解)7(mod5x)7(mod62y無解無解二次剩余的分布二次剩余的分布 設(shè)設(shè)p是奇素?cái)?shù)，則模是奇素?cái)?shù)，則模p的簡(jiǎn)化剩余系中二次剩的簡(jiǎn)化剩余系中二次剩余與二次非剩余的個(gè)數(shù)各為余與二次非剩余的個(gè)數(shù)各為 ，且，且 個(gè)二次剩余與個(gè)二次剩余與序列序列中的一個(gè)數(shù)同余，且僅與一個(gè)數(shù)同余。中的一個(gè)數(shù)同余，且僅與一個(gè)數(shù)同余。21p21p222)21( ,2 ,1p二次剩余的分布規(guī)律二次剩余的分布規(guī)律二次剩余的分布規(guī)律的證明二次剩余的分布規(guī)律的證明n取模p的絕對(duì)值最小縮系來討論 -(p-1)/2, -(p-1)/2+1, , -1, 1, , (p-1)/2-1, (p-1)/2na是模p的

4、二次剩余當(dāng)且僅當(dāng)a -(p-1)/22, -(p-1)/2+12, , (-1)2, 12, , (p-1)/2-12, (p-1)/22(mod p)n而(-i)2=i2(mod p)，所以a是模p的二次剩余當(dāng)且僅當(dāng) a 12, , (p-1)/2-12, (p-1)/22(mod p) n又因?yàn)?ij (p-1)/2時(shí)， i2 ! j2(mod p)n所以模p的全部二次剩余即 12, , (p-1)/2-12, (p-1)/22(mod p) 共有(p-1)/2個(gè)，所以模p的二次非剩余共有(p-1)- (p-1)/2= (p-1)/2個(gè)歐拉判別條件歐拉判別條件歐拉判別條件歐拉判別條件 設(shè)設(shè)

5、p是奇素?cái)?shù)，是奇素?cái)?shù)，(a, p) = 1，則，則 (1) a是模是模p的平方剩余的充分必要條件是的平方剩余的充分必要條件是 (2) a是模是模p的平方非剩余的充分必要條件是的平方非剩余的充分必要條件是當(dāng)當(dāng)a是模是模p的平方剩余時(shí)，同余式的平方剩余時(shí)，同余式 恰有兩解。恰有兩解。)(mod121pap)(mod121pap)(mod2pax 歐拉判別條件的證明歐拉判別條件的證明n先來證明結(jié)論(1)的必要性，a是模p的二次剩余，則必有x0，使得 x02 a(mod p)成立，因而 x0 (p-1) a(p-1)/2(mod p)因?yàn)?a, p) = 1，所以(x0 , p) = 1，所以 x0

6、(p-1) 1(mod p)所以 a (p-1)/2 1(mod p)歐拉判別條件的證明歐拉判別條件的證明n再來證明結(jié)論(1)的充分性，用反證法，假設(shè)滿足 a (p-1)/2 1 (mod p)的a不是模p的二次剩余n考慮線性同余方程sx a(mod p)，當(dāng)s從模p的絕對(duì)值最小縮系 -(p-1)/2, -(p-1)/2+1, , -1, 1, , (p-1)/2-1, (p-1)/2 中取值時(shí)，方程sx a(mod p) 必有唯一解n亦即s取模p的絕對(duì)值最小縮系中的每個(gè)元素i，必有唯一的x=xi屬于模p的絕對(duì)值最小縮系，使得sx a(mod p) 成立，若a不是模p的二次剩余，則ixi，這樣

7、模p的絕對(duì)值最小縮系中的p-1個(gè)數(shù)可以按兩兩配對(duì)相乘，得到 (p-1)! a (p-1)/2(mod p)n由威爾遜定理(p-1)! -1(mod p)，所以有a (p-1)/2 -1 (mod p)，這與條件a (p-1)/2 1 (mod p)矛盾n所以必定存在一個(gè)i，使得i=xi ，即a是模p的二次剩余歐拉判別條件的證明歐拉判別條件的證明n最后來證明(2)成立，只需證明 a(p-1)/2 1(mod p)和a(p-1)/2 -1(mod p)有且僅有一個(gè)成立即可n由歐拉定理 a(p-1) 1(mod p) 所以 (a(p-1)/2-1) (a(p-1)/2+1) 0(mod p)而p2，

8、且有 (a(p-1)/2-1, a(p-1)/2+1)|2于是 a(p-1)/2 1 (mod p)和a(p-1)/2 -1(mod p)有且僅有一個(gè)成立歐拉判別條件例題歐拉判別條件例題歐拉判別條件的推論歐拉判別條件的推論勒讓德符號(hào)勒讓德符號(hào)由此定義，歐拉判別法則可以表示成如下形式：由此定義，歐拉判別法則可以表示成如下形式： , 0, 1, 1paappapa|若的平方非剩余是模若的平方剩余是模若 定義定義 設(shè)設(shè)p是素?cái)?shù)，定義勒讓德符號(hào)如下：是素?cái)?shù)，定義勒讓德符號(hào)如下：設(shè)設(shè)p是奇素?cái)?shù)，則對(duì)任意整數(shù)是奇素?cái)?shù)，則對(duì)任意整數(shù)a，有，有 )(mod21papap設(shè)設(shè)p是奇素?cái)?shù)，則勒讓德符號(hào)有如下性質(zhì)：

9、是奇素?cái)?shù)，則勒讓德符號(hào)有如下性質(zhì)： (2) ，進(jìn)一步，若，進(jìn)一步，若 ，則，則 ；pappa)(mod pba pbpa(3) ，進(jìn)一步，若，進(jìn)一步，若 ，則，則 ， 若若 ，則，則 ；pbpapab1),(pa12pa1),( pa02pa11p21) 1(1 pp(1) ， ；勒讓德符號(hào)勒讓德符號(hào)勒讓德符號(hào)勒讓德符號(hào)高斯引理高斯引理高斯引理高斯引理二次互反律二次互反律二次互反律二次互反律華羅庚對(duì)高斯二次互反律的評(píng)價(jià) 設(shè)設(shè)p是奇素?cái)?shù)，則勒讓德符號(hào)有如下性質(zhì)：是奇素?cái)?shù)，則勒讓德符號(hào)有如下性質(zhì)： (2) ，進(jìn)一步，若，進(jìn)一步，若 ，則，則 ；pappa)(mod pba pbpa(3) ，進(jìn)一步

10、，若，進(jìn)一步，若 ，則，則 ， 若若 ，則，則 ；pbpapab1),(pa12pa1),( pa02pa11p21) 1(1 pp(1) ， ；qp,1122( 1)pqqppq (5) 若若 是互素的奇素?cái)?shù)，則是互素的奇素?cái)?shù)，則 。 812) 1(2pp(4) ；勒讓德符號(hào)勒讓德符號(hào)若p, q為奇素?cái)?shù)nx2 -1(mod p)有解p 1(mod 4)nx2 2(mod p)有解p 1(mod 8)n若p 1(mod 4)或q 1(mod 4)則 x2 q(mod p)有解 x2 p(mod q)有解n若p 3(mod 4)且q 3(mod 4)則 x2 q(mod p)有解 x2 p(mo

11、d q)無解 x2 p(mod q)有解 x2 q(mod p)無解例例 計(jì)算如下勒讓德符號(hào)的值。計(jì)算如下勒讓德符號(hào)的值。 ,322,171732271372003911(1) (2) (3) 勒讓德符號(hào)勒讓德符號(hào)nmm是否為素?cái)?shù)是否為素?cái)?shù)q=1q=-1q=0q=2out:01停止停止否否是，計(jì)算是，計(jì)算n (mod m)=q218( 1)m 12( 1)m返回返回1212rkkkrqppp121111()222212( 1)ipppmimmmpppikkk,21riikkk,21為奇數(shù)為奇數(shù)為偶數(shù)為偶數(shù)勒讓德符號(hào)勒讓德符號(hào)二次剩余根的實(shí)際求法二次剩余根的實(shí)際求法n華羅庚的觀點(diǎn)p=3(mod

12、4)時(shí)二次剩余根的實(shí)際求法時(shí)二次剩余根的實(shí)際求法n若p=3(mod 4)，且x2=a(mod p)有解，求其解可考慮 a(p-1)/21(mod p)兩邊同乘a，得 a(p+1)/2a (mod p)即 (a(p+1)/4 ) 21(mod p)n所以a(p+1)/4(mod p)即x2=a(mod p)的兩個(gè)解1 判斷同余方程判斷同余方程21(mod307)x 是否有解？有解時(shí)，求出其解數(shù)。是否有解？有解時(shí)，求出其解數(shù)。2 判斷同余方程判斷同余方程230(mod419)x 是否有解？有解時(shí)，求出其解數(shù)。是否有解？有解時(shí)，求出其解數(shù)。 勒讓德符號(hào)（作業(yè)）勒讓德符號(hào)（作業(yè)）3 求解同余方程求解同

13、余方程22(mod23)x Rabin密碼體制密碼體制n對(duì)RSA密碼體制，n被分解成功，該體制便被破譯，即破譯RSA的難度不超過大整數(shù)的分解n但還不能證明破譯RSA和分解大整數(shù)是等價(jià)的，雖然這一結(jié)論已得到普遍共識(shí)nRabin密碼體制已被證明對(duì)該體制的破譯與分解大整數(shù)一樣困難Rabin密碼體制密碼體制1.密鑰生成隨機(jī)選擇兩個(gè)大素?cái)?shù)p、q，滿足 pq3 (mod 4)計(jì)算n=pq。以n作為公開鑰，p、q作為秘密鑰2.加密 cm2 (mod n) 其中m是明文，c是對(duì)應(yīng)的密文Rabin密碼體制密碼體制3.解密即解方程x2c (mod n)，該方程等價(jià)于解方程組由于pq3 (mod 4)，設(shè)t=c(p

14、+1)/4 ，這兩個(gè)方程各自有兩個(gè)解，即 xt (mod p), x-t (mod p) xt (mod q), x-t (mod q)經(jīng)過組合可得4個(gè)同余方程組由中國剩余定理可解出每一方程組的解，共有4個(gè)，即每一密文對(duì)應(yīng)的明文不惟一。為了有效地確定明文，可在m中加入某些信息，如發(fā)送者的身份號(hào)、接收者的身份號(hào)、日期、時(shí)間等22modmodxcpxcqmod ,mod ,mod ,modmod ,mod ,mod ,modxtpxtpxtpxtpxtqxtqxtqxtq Rabin密碼體制的例子密碼體制的例子n設(shè)明文m按以下式加密：cm2 (mod 77)，如果密文c為23，求明文先求23對(duì)模7和模11的平方根，因?yàn)?7113 mod 4所以，23(7+1)/4 2324(mod 7) 23(11+1)/4 2331(mod 11)用中國剩余定理計(jì)算明文的可能取值為 10，32，45，67 小結(jié)小結(jié))(mod2max 1),(ma1、m是正整數(shù)是正整數(shù)方程有解稱方程有解稱a是是m的二次剩余。的二次剩余。2、歐拉判別條件、歐拉判別條件p是奇素?cái)?shù)是奇素?cái)?shù)( , )1a p 121(mo