應(yīng)用密碼學(xué)_第06章_數(shù)論基礎(chǔ)

1、v素?cái)?shù)與互素素?cái)?shù)與互素v費(fèi)馬定理和歐拉定理費(fèi)馬定理和歐拉定理v中國(guó)剩余定理中國(guó)剩余定理v素性檢測(cè)素性檢測(cè)v整數(shù)中的基本概念：素?cái)?shù)、最大公因數(shù)（整數(shù)中的基本概念：素?cái)?shù)、最大公因數(shù)（gcd）、）、最小公倍數(shù)（最小公倍數(shù)（lcm）、互素）、互素v算術(shù)基本定理：任一大于算術(shù)基本定理：任一大于1的整數(shù)的整數(shù)a均能唯一地表均能唯一地表示為素?cái)?shù)冪的乘積，即示為素?cái)?shù)冪的乘積，即 其中其中pi是素?cái)?shù)，是素?cái)?shù)，ttpppa21210iv業(yè)余數(shù)學(xué)家之王業(yè)余數(shù)學(xué)家之王費(fèi)馬費(fèi)馬v費(fèi)馬大定理：當(dāng)費(fèi)馬大定理：當(dāng)n2時(shí)，方程時(shí)，方程xn + yn = zn不存在整不存在整數(shù)解。數(shù)解。vn=2時(shí)，勾股定理、商高定理、畢達(dá)哥拉斯

2、定理時(shí)，勾股定理、商高定理、畢達(dá)哥拉斯定理“不可能將一個(gè)立方數(shù)寫(xiě)成兩個(gè)立方數(shù)之和；或者將不可能將一個(gè)立方數(shù)寫(xiě)成兩個(gè)立方數(shù)之和；或者將一個(gè)一個(gè)4 4次冪寫(xiě)成兩個(gè)次冪寫(xiě)成兩個(gè)4 4次冪之和；或者，總的來(lái)說(shuō)，次冪之和；或者，總的來(lái)說(shuō)，不可能將一個(gè)高于不可能將一個(gè)高于2 2次的冪寫(xiě)成兩個(gè)同樣次冪的和。次的冪寫(xiě)成兩個(gè)同樣次冪的和?！薄拔矣幸粋€(gè)對(duì)這個(gè)命題的十分美妙的證明，這里空白我有一個(gè)對(duì)這個(gè)命題的十分美妙的證明，這里空白太小，寫(xiě)不下。太小，寫(xiě)不下?！?16371637，費(fèi)馬，費(fèi)馬v費(fèi)馬自己證明了費(fèi)馬自己證明了n=4的情況的情況v1753年，歐拉證明了年，歐拉證明了n=3的情況的情況v1853-1856年

3、，法國(guó)科學(xué)院設(shè)立年，法國(guó)科學(xué)院設(shè)立3000法朗獎(jiǎng)金法朗獎(jiǎng)金1847年，柯西與拉梅之爭(zhēng)，化解者：德國(guó)數(shù)學(xué)家年，柯西與拉梅之爭(zhēng)，化解者：德國(guó)數(shù)學(xué)家恩斯特恩斯特 庫(kù)默爾庫(kù)默爾1857年，獎(jiǎng)金給了庫(kù)默爾年，獎(jiǎng)金給了庫(kù)默爾庫(kù)默爾指出：算術(shù)基本定理在復(fù)數(shù)中不成立庫(kù)默爾指出：算術(shù)基本定理在復(fù)數(shù)中不成立 121111112828iiiiv德國(guó)實(shí)業(yè)家保羅德國(guó)實(shí)業(yè)家保羅沃爾夫斯凱爾的工作沃爾夫斯凱爾的工作v1908年立下遺囑：財(cái)產(chǎn)中的一大部分獎(jiǎng)給任何能年立下遺囑：財(cái)產(chǎn)中的一大部分獎(jiǎng)給任何能證明費(fèi)馬大定理的人，獎(jiǎng)金為證明費(fèi)馬大定理的人，獎(jiǎng)金為10萬(wàn)馬克，萬(wàn)馬克， v截止日期：截止日期：2007年年9月月13日。日。

4、 v1997年年6月月27日，安德魯日，安德魯懷爾斯收到了價(jià)值懷爾斯收到了價(jià)值5萬(wàn)美萬(wàn)美元的沃爾夫斯凱爾獎(jiǎng)金。元的沃爾夫斯凱爾獎(jiǎng)金。 v推薦閱讀：推薦閱讀：v費(fèi)馬大定理費(fèi)馬大定理一個(gè)困惑了世間智者一個(gè)困惑了世間智者358年的年的謎謎，（英）西蒙，（英）西蒙辛格（辛格（SimonSingh）著，薛密）著，薛密譯上海譯文出版社譯上海譯文出版社v費(fèi)馬小定理：若費(fèi)馬小定理：若p是素?cái)?shù)，是素?cái)?shù)，p不整除不整除a，則，則a p-11 mod pv等價(jià)形式：等價(jià)形式：a pa mod pv例：設(shè)例：設(shè)p=23， a=2，則由，則由Fermat定理直接可得定理直接可得 222 1 mod 23證證 明明v首先

5、證明，首先證明，1ip-1時(shí)，時(shí)，p整除二項(xiàng)式系數(shù)整除二項(xiàng)式系數(shù) 顯然顯然p整除分子。由于整除分子。由于0ip，所以素?cái)?shù)，所以素?cái)?shù)p不整除所有在分不整除所有在分母中階乘的因子。根據(jù)素?cái)?shù)因子分解的唯一性，母中階乘的因子。根據(jù)素?cái)?shù)因子分解的唯一性，p不能整不能整除分母。除分母。 根據(jù)二項(xiàng)式定理根據(jù)二項(xiàng)式定理 ，由于所有二項(xiàng)式，由于所有二項(xiàng)式系數(shù)都是整數(shù)，系數(shù)都是整數(shù)， 0ip時(shí)，二項(xiàng)式系數(shù)是整數(shù)并且其分式時(shí)，二項(xiàng)式系數(shù)是整數(shù)并且其分式形式中的分子可以被形式中的分子可以被p整除，而分母不能被整除，而分母不能被p整除，所以，整除，所以，在分式化簡(jiǎn)完成后，分子中肯定存在因子在分式化簡(jiǎn)完成后，分子中肯定存

6、在因子p。!ppiipi0pip ii ppxyx yi 對(duì)對(duì) x 歸納：首先，顯然歸納：首先，顯然 1p1 mod p，假設(shè)對(duì)某，假設(shè)對(duì)某個(gè)特定的整數(shù)個(gè)特定的整數(shù) x，有，有 x p x mod p，則，則00111pip ipii pi pppxxxxii 等式右邊的中間部分的所有系數(shù)整除等式右邊的中間部分的所有系數(shù)整除p，因此，因此 這就證明了費(fèi)馬定理。這就證明了費(fèi)馬定理。10 11modppxxxp v歐拉函數(shù)：對(duì)于正整數(shù)歐拉函數(shù)：對(duì)于正整數(shù)n，歐拉函數(shù)，歐拉函數(shù)(n)定義為小于定義為小于n且且與與n互素的正整數(shù)個(gè)數(shù)?；ニ氐恼麛?shù)個(gè)數(shù)。v性質(zhì)：性質(zhì)：（1） (1)=1（2）n為素?cái)?shù)時(shí)，

7、為素?cái)?shù)時(shí)， (n)=n-1；（3）(2k)= 2k-1 ；（4）若）若n=pq 且且gcd (p, q)=1，則，則(n)= (p) (q)（5）若，則）若，則tataapppn2121 111211121121tataappppppntv定理：對(duì)任意整數(shù)定理：對(duì)任意整數(shù)a, n，當(dāng)，當(dāng)gcd(a, n)=1時(shí)，有時(shí)，有 a(n)1 mod nv等價(jià)形式：等價(jià)形式：a(n)1a mod nv推論：給定兩個(gè)素?cái)?shù)推論：給定兩個(gè)素?cái)?shù)p, q，整數(shù)，整數(shù)n=pq和和m，其中，其中 0mn，則有則有m(n)+1m(p-1)(q-1)+1m mod nv丟番圖（丟番圖（Diophantine，古希臘數(shù)學(xué)家

8、，約公元前，古希臘數(shù)學(xué)家，約公元前250年）年）（Chinese Remainder TheoremChinese Remainder Theorem）上帝恩賜他生命的上帝恩賜他生命的1/61/6為童年，再過(guò)生命的為童年，再過(guò)生命的1/121/12，他雙頰長(zhǎng)出了胡子，再過(guò)他雙頰長(zhǎng)出了胡子，再過(guò)1/71/7后他舉行了婚禮，后他舉行了婚禮，婚后婚后5 5年他有了一個(gè)兒子。唉，可憐的孩子，年他有了一個(gè)兒子。唉，可憐的孩子，只活了他父親整個(gè)生命的一半年紀(jì)，便被冷酷只活了他父親整個(gè)生命的一半年紀(jì)，便被冷酷的死神帶走。他以研究數(shù)論寄托他的哀思，的死神帶走。他以研究數(shù)論寄托他的哀思，4 4年后離開(kāi)了人世。年

9、后離開(kāi)了人世。 x-x/6+x/12+x/7+5+x/2+4=0 x-x/6+x/12+x/7+5+x/2+4=0v丟番圖方程，整系數(shù)多項(xiàng)式方程：變量為整丟番圖方程，整系數(shù)多項(xiàng)式方程：變量為整數(shù)的多項(xiàng)式等式。數(shù)的多項(xiàng)式等式。v一般形式：一般形式：cxaxaxanbnnbb212211公元公元3-53-5世紀(jì)，世紀(jì)，孫子算經(jīng)孫子算經(jīng)： “今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何？七七數(shù)之剩二，問(wèn)物幾何？” 術(shù)曰：三三數(shù)之剩二，置一百四十；五五數(shù)之剩三，置術(shù)曰：三三數(shù)之剩二，置一百四十；五五數(shù)之剩三，置六十三；七七數(shù)之剩二，置三

10、十；并之得二百三十三；以六十三；七七數(shù)之剩二，置三十；并之得二百三十三；以二百一十減之即得。凡三三數(shù)之剩一，則置七十；五五數(shù)二百一十減之即得。凡三三數(shù)之剩一，則置七十；五五數(shù)之剩一，則置二十一；七七數(shù)之剩一，則置十五；一百六之剩一，則置二十一；七七數(shù)之剩一，則置十五；一百六以上，以一百五減之即得。以上，以一百五減之即得。 程大位，算法統(tǒng)宗（程大位，算法統(tǒng)宗（15031503） 三人同行七十稀，三人同行七十稀， 五樹(shù)梅花廿一枝，五樹(shù)梅花廿一枝， 七子團(tuán)圓正月半，七子團(tuán)圓正月半， 除百零五便得知。除百零五便得知。n = 70*2+21*3+15*2 mod 105 =23v設(shè)設(shè)a, b, c 的最

11、大公約數(shù)為的最大公約數(shù)為d，則存在整數(shù)，則存在整數(shù)x, y, z，使得使得ax+by+cz=dv在方程組中，模數(shù)在方程組中，模數(shù)3、5、7互素，而互素，而3*5=15、5*7=35和和3*7=21也是互素的，故存在整數(shù)也是互素的，故存在整數(shù)x, y, z，使得使得35x+21y+15z=1v令令e1=35x, e2=21y, e3=15z，則顯然有，則顯然有1111mod 30mod 50mod 7eee2220mod 31mod 50mod 7eee3330mod 30mod 51mod 7eeen = e1*2+e2*3+e3*2 mod 105v由于（由于（3, 35）=1，故存在整數(shù)，

12、故存在整數(shù)a, b，使得，使得3a+35b=1v而而v故可令故可令e1=35b，而其中的，而其中的b為為35模模3的逆元。的逆元。351mod 3350mod 5350mod 7bbbv一次同余方程組的一般形式：一次同余方程組的一般形式：v如果如果m1, m2, , mk兩兩互素，則可利用中國(guó)剩余兩兩互素，則可利用中國(guó)剩余定理求解。定理求解。1122modmodmodkkxamxamxam第一步，計(jì)算第一步，計(jì)算M=m 1m 2m k，以及，以及Mi=M/mi；第二步，求出各第二步，求出各Mi 模模mi 的逆，即計(jì)算的逆，即計(jì)算Mi-1，使得，使得M iM i-11 mod mi；第三步，計(jì)算

13、第三步，計(jì)算x=M i Mi-1 a1+M kM k -1ak mod M則則 x 即即為方程組的一個(gè)解。為方程組的一個(gè)解。 除數(shù)除數(shù)mi余余數(shù)數(shù)ai最小公倍最小公倍數(shù)數(shù)衍衍數(shù)數(shù)Mi = M/mi乘率乘率Mi-1ci各總各總ai ci答數(shù)答數(shù)m1a1M=m1 m2 mkM1M1-1m2a2M2M2-1mkakMkMk-1v解解“物不知其數(shù)物不知其數(shù)”的方程組的方程組(1) 計(jì)算：計(jì)算：M357105， M135，M221，M315 再求出再求出 M112， M211， M311 最后求得最后求得x23 mod 105除數(shù)除數(shù)mi余數(shù)余數(shù)ai最小公倍最小公倍數(shù)數(shù)衍數(shù)衍數(shù)Mi = M/mi乘率乘率

14、Mi-1ci各總各總ai ci答數(shù)答數(shù)32M=3*5*7=1055*725*7*270*2140+63+30=23323 mod 105537*317*3*121*3723*513*5*115*2v練習(xí)：解同余方程組練習(xí)：解同余方程組1mod 72mod 83mod 9xxx1mod 42mod 53mod 7xxxx = 498x = 498x = 17x = 17v練習(xí)：求相鄰的四個(gè)整數(shù)，依次可被練習(xí)：求相鄰的四個(gè)整數(shù)，依次可被22、32、52、72整除整除 vM=mM=m1 1* *m m2 2=37=37* *49=1813,(37,49)=149=1813,(37,49)=19739

15、73可用較小的兩個(gè)模數(shù)可用較小的兩個(gè)模數(shù)3737和和4949重構(gòu)，表示為重構(gòu)，表示為(11(11，42) 42) （1111* *4949* *34+4234+42* *3737* *4=1 mod 18134=1 mod 1813）678678可表示為可表示為(12(12，41)41)則則1651=973+6781651=973+678就可表示為就可表示為 (11+12)mod37,(42+41)mod49)=(23,34)(11+12)mod37,(42+41)mod49)=(23,34)則則120523=1651120523=1651* *7373就可表示為就可表示為 (23(23* *

16、36mod37,3436mod37,34* *24mod49)=(14,32)24mod49)=(14,32)v vWilson階乘判別法階乘判別法vwilson定理：定理：P是素?cái)?shù)是素?cái)?shù) v證明：證明：（ 1，所以不可，所以不可能得到能得到(p 1)! 1 (mod p)。)(mod1)!1(ppv證明：證明：（ = ）vp=2，命題顯然成立；，命題顯然成立；vp=3，命題顯然成立；，命題顯然成立；v對(duì)于對(duì)于p5，令，令aA=2, 3, 4. p-2，則，則B=a, 2a, 3a, ., (p-1)a中不會(huì)有模中不會(huì)有模p同余的兩個(gè)數(shù)。因此，同余的兩個(gè)數(shù)。因此，B中元素被中元素被p除得的余數(shù)

17、形成集合除得的余數(shù)形成集合1, 2, 3,., p-1.v假設(shè)假設(shè)B中元素被中元素被p除余除余1的數(shù)是的數(shù)是a：若若=1，則則a=a，它被，它被p除余除余a，所以，所以=1不成立；不成立；若若=p-1，則，則a=(p-1)a，它被，它被p除余除余p-a,所以所以=p-1不成不成立；立；若若=a，則，則a=a*a，由于，由于a*a1(mod p)，故應(yīng)有，故應(yīng)有a*a-1=(a+1)(a-1)0(mod p)，這只能是，這只能是a=1或或a=p-1，與，與aA矛盾，故不成立；矛盾，故不成立；因此，因此，a且且a, A。若若a1a2, a1, a2A，且，且1a12a21(mod p），因?yàn)椋?/p>

18、為1a1，2a2B，而，而B(niǎo)中的元素關(guān)于中的元素關(guān)于mod p不同余，可見(jiàn)不同余，可見(jiàn)a1a2,則則12。即即A中的每一個(gè)中的每一個(gè)a均可找到與其配對(duì)的均可找到與其配對(duì)的 ，A使使a 1(mod p)。 a不同時(shí)，不同時(shí)，也相異；也相異；因此，因此，A中的偶數(shù)個(gè)（中的偶數(shù)個(gè)（p-3個(gè)）元素可以分成個(gè)）元素可以分成(p-3)/2個(gè)個(gè)二元組（二元組（a, ），每個(gè)二元組都滿足），每個(gè)二元組都滿足a 1(mod p)；234.(p-2)1(mod p)，p-1-1(mod p) (p-1)!-1(mod p)v更快的素性檢測(cè)：僅僅能夠得知更快的素性檢測(cè)：僅僅能夠得知n是否為合數(shù)，而不能是否為合數(shù)，而

19、不能求出其因子。求出其因子。v實(shí)際中使用的方法：先生成大的隨機(jī)整數(shù)，再利用某實(shí)際中使用的方法：先生成大的隨機(jī)整數(shù)，再利用某些算法來(lái)檢測(cè)其素性。些算法來(lái)檢測(cè)其素性。v定理：素?cái)?shù)有無(wú)窮多個(gè)定理：素?cái)?shù)有無(wú)窮多個(gè) 證明：用反證法證明：用反證法 假設(shè)素?cái)?shù)個(gè)數(shù)有限，設(shè)全部的素?cái)?shù)為假設(shè)素?cái)?shù)個(gè)數(shù)有限，設(shè)全部的素?cái)?shù)為p1, p2, , pn，令，令N=p1p2pn+1, 由算術(shù)基本定理，由算術(shù)基本定理，N可以分解為素?cái)?shù)的乘可以分解為素?cái)?shù)的乘積，故一定存在素?cái)?shù)積，故一定存在素?cái)?shù)p能整除能整除N。因而對(duì)某個(gè)。因而對(duì)某個(gè)pi，1in，p=pi ，從而，從而p能整除能整除N-p1p2pn=1，顯然這是不可能的。，顯然這

20、是不可能的。 17世紀(jì)，人們發(fā)現(xiàn)：世紀(jì)，人們發(fā)現(xiàn)：31, 331, 3331, 33 331, 333 331, 3 333 331, 33 333 331都是素?cái)?shù)，然而都是素?cái)?shù)，然而33 333 331=17*19 607 843v0-100之間有之間有25個(gè)素?cái)?shù)個(gè)素?cái)?shù)v1000 0000與與1000 0100之間只有之間只有2個(gè)素?cái)?shù)個(gè)素?cái)?shù)20004000600080001000020040060080010001200v素?cái)?shù)定理是數(shù)論中一個(gè)著名的結(jié)論，它是素?cái)?shù)定理是數(shù)論中一個(gè)著名的結(jié)論，它是18961896年年由由HadamardHadamard和和la Valle-Poussinla V

21、alle-Poussin分別獨(dú)立證明分別獨(dú)立證明的。根據(jù)該定理，如果在的。根據(jù)該定理，如果在0 0到到x x之間隨機(jī)選取一個(gè)之間隨機(jī)選取一個(gè)整數(shù)，其為素?cái)?shù)的概率約為整數(shù)，其為素?cái)?shù)的概率約為1/lnx 1/lnx ，因此，生成，因此，生成“可能為素?cái)?shù)可能為素?cái)?shù)”的大整數(shù)是可行的。的大整數(shù)是可行的。 xxxxlnlim定理（素?cái)?shù)定理）令定理（素?cái)?shù)定理）令(x)(x)表示比表示比x x小的素?cái)?shù)的個(gè)數(shù)，則小的素?cái)?shù)的個(gè)數(shù)，則 v方法一：費(fèi)馬定理方法一：費(fèi)馬定理根據(jù)費(fèi)馬定理，當(dāng)根據(jù)費(fèi)馬定理，當(dāng)p為素?cái)?shù)時(shí)，對(duì)任意整數(shù)為素?cái)?shù)時(shí)，對(duì)任意整數(shù)a，且且p不整除不整除a，有，有a p-11 mod p .(1)逆否命

22、題：若存在逆否命題：若存在a，使得，使得(1)式不成立，則式不成立，則p必必為合數(shù)為合數(shù)合數(shù)判別的充分條件合數(shù)判別的充分條件如果如果p不是素?cái)?shù)，而不是素?cái)?shù)，而(1)仍然成立，則稱仍然成立，則稱p為關(guān)于為關(guān)于基底基底a的的偽素?cái)?shù)。偽素?cái)?shù)。v341，91和和217是關(guān)于基底是關(guān)于基底2，3和和5的最小偽素?cái)?shù)的最小偽素?cái)?shù)v費(fèi)馬定理只是素?cái)?shù)判定的一個(gè)必要條件。費(fèi)馬定理只是素?cái)?shù)判定的一個(gè)必要條件。v對(duì)某個(gè)對(duì)某個(gè)a，如果數(shù)，如果數(shù)p使使(1)成立，則稱其通過(guò)了基數(shù)成立，則稱其通過(guò)了基數(shù)為為a的偽素?cái)?shù)測(cè)試。通過(guò)若干次偽素?cái)?shù)測(cè)試的數(shù)在的偽素?cái)?shù)測(cè)試。通過(guò)若干次偽素?cái)?shù)測(cè)試的數(shù)在概率上是一個(gè)素?cái)?shù)。概率上是一個(gè)素?cái)?shù)。

23、v如果對(duì)所有如果對(duì)所有ap，gcd(a, p)=1，p均能通過(guò)基數(shù)為均能通過(guò)基數(shù)為a的偽素?cái)?shù)測(cè)試，卻仍為合數(shù)，則稱的偽素?cái)?shù)測(cè)試，卻仍為合數(shù)，則稱p為為Carmichael數(shù)數(shù)。最小的三個(gè)最小的三個(gè)Carmichael數(shù)：數(shù)：561，294409，56052361Carmichael數(shù)非常稀少，在數(shù)非常稀少，在1100,000,000范圍內(nèi)的整范圍內(nèi)的整數(shù)中，只有數(shù)中，只有255個(gè)個(gè)Carmichael數(shù)。數(shù)。1992年，年，Alford，Granville和和Pomerance證明了存在無(wú)證明了存在無(wú)限多個(gè)限多個(gè)Carmichael數(shù)。數(shù)。v為了提高素?cái)?shù)測(cè)試的準(zhǔn)確性，可以多次隨機(jī)選取為了提高素

24、數(shù)測(cè)試的準(zhǔn)確性，可以多次隨機(jī)選取小于小于n的正整數(shù)的正整數(shù)a，重復(fù)計(jì)算，重復(fù)計(jì)算an-1 mod n來(lái)判定來(lái)判定n是是否是素?cái)?shù)。否是素?cái)?shù)。v例如，對(duì)于例如，對(duì)于341，取，取a=3，則，則3340 mod 34156，從，從而判定而判定341不是素?cái)?shù)。不是素?cái)?shù)。int ExpMod(int n) /int ExpMod(int n) /計(jì)算計(jì)算a an n-1-1 mod mod n n a=Random(2, n-1); / a=Random(2, n-1); /產(chǎn)生產(chǎn)生2, n-12, n-1之間的隨機(jī)整數(shù)之間的隨機(jī)整數(shù) b=1;b=1; for (i=1; i=n-1; i+) for

25、(i=1; i2，如果對(duì)，如果對(duì)n-1的每個(gè)素因子的每個(gè)素因子p，存在一個(gè)整數(shù)存在一個(gè)整數(shù)a(a1)，使得，使得且且則則n是素?cái)?shù)是素?cái)?shù)nanmod11napnmod11 v證明思路：證明思路：只要證明此時(shí)只要證明此時(shí) ，也就是，也就是 | |p-1,p-p-1,p-1| ,1| ,先證先證p-1p-1| | ，反證：設(shè)反證：設(shè) | |p-1,p-1,且且 | | ，設(shè)，設(shè)ordordp p( (a ai i)=k)=ki i則則k ki i| |p-1, kp-1, ki i|(p-1/p|(p-1/pi i) )所以所以 p pi i| |k ki i，否則否則k ki i|(p-1/p|(

26、p-1/pi i) )所以所以 | |k ki i，否則設(shè)否則設(shè) | |k ki i(0(0jr),(p-1/pjr-1r-jr-1，所以，所以j1j1，所以，所以j=0j=0因?yàn)橐驗(yàn)閗 ki i| | ，所以，所以 | | 矛盾，所以矛盾，所以p-1p-1| |再因?yàn)樵僖驗(yàn)?= 1時(shí)，時(shí)，0pa當(dāng)（當(dāng)（a, p）1時(shí)，時(shí)，1pa2121papappa(4)當(dāng)（當(dāng)（a, p）=1時(shí)，時(shí)，122papavJacobi符號(hào)的計(jì)算符號(hào)的計(jì)算v定理（定理（Gauss二次互反律）設(shè)二次互反律）設(shè)p、q為互素的奇數(shù)，為互素的奇數(shù)，則則補(bǔ)充知識(shí)：補(bǔ)充知識(shí)：JacobiJacobi符號(hào)符號(hào)21211qpqppqv引理引理1 如果如果n是奇素?cái)?shù)，則對(duì)所有是奇素?cái)?shù)，則對(duì)所有a，1an-1，有有v引理引理2 如果如果n是奇合數(shù)，則至多有一半滿足是奇合數(shù)，則至多有一半滿足1an-1 和和 gcd(a, n)=1的整數(shù)的整數(shù)a滿足上式滿足上式 。 12modnaann補(bǔ)充知識(shí)：補(bǔ)充知識(shí)：JacobiJacobi符號(hào)符號(hào)v開(kāi)發(fā)者：開(kāi)發(fā)者：Robert Solovay和和Volker Strassenv算法步驟算法步驟I 隨機(jī)選取整數(shù)隨機(jī)選取整數(shù)a，使得，使得 1an-1；II 如果如果a與與n