chap8-數(shù)論入門(mén)

1、第八章 數(shù)論初步,8.1素?cái)?shù)8.2費(fèi)馬定理和歐拉定理8.3 素?cái)?shù)測(cè)試8.4剩余定理8.5離散對(duì)數(shù),2024/3/23,大連理工大學(xué),8.1 素?cái)?shù),定義 8.1：（整除、倍數(shù)、因數(shù)）設(shè)a，b為整數(shù)，若存在整數(shù)c，使b=ac，則稱(chēng)a可整除b，記作a|b。b叫做a的倍數(shù)，a叫做b的因數(shù)。若不存在這樣的整數(shù)c，則稱(chēng)a不能整除b，記作a | b。* 如果b|g，b|h,對(duì)于

2、任何整數(shù)m和n，則滿(mǎn)足b|(mg+nh).,2024/3/23,大連理工大學(xué),,8.1 素?cái)?shù),定義 8.2：（公約數(shù)、最大公約數(shù)、素?cái)?shù)、互素、兩兩互素）設(shè)a，b，…，l是整數(shù)，若有整數(shù)d滿(mǎn)足d|a，d|b， …，d|l的公約數(shù)。a，b， …，l的公約數(shù)中最大者成為它們的最大公約數(shù)，記作（ a，b， …，l ）。如果（ a，b， …，l ）=1，則說(shuō)a，b， …，l 為互素。如果a，b， …，l 中的每個(gè)數(shù)都與其它數(shù)互素，則

3、稱(chēng)它們兩兩互素。,2024/3/23,大連理工大學(xué),8.1 素?cái)?shù),關(guān)于公約數(shù)有以下性質(zhì)：性質(zhì)1 若a是b的倍數(shù)，則（a，b）=b性質(zhì)2 若a=bq+c，則（a，b）= （b，c）定義8.3（素?cái)?shù)）：只有1和自身為其因數(shù)的，大于1的整數(shù)叫素?cái)?shù)。,2024/3/23,大連理工大學(xué),,to factor a number n>1 is to write it as a product of ot

4、her numbers: n=a x b x c note that factoring a number is relatively hard compared to multiplying the factors together to generate the number the prime factorisation of a number n is when its written as a product of pri

5、mes eg. 91=7x13 ; 3600=24x32x52,Relatively Prime Numbers & GCD,two numbers a, b are relatively prime if have no common divisors apart from 1 eg. 8 & 15 are relatively prime since factors of 8 are 1,2,4,8 and of

6、 15 are 1,3,5,15 and 1 is the only common factor conversely can determine the greatest common divisor by comparing their prime factorizations and using least powerseg. 300=21x31x52 18=21x32 hence GCD(18,300)=21x31x50=6

7、,8.2 費(fèi)馬定理Fermat's Theorem,費(fèi)馬小定理：若 p 是素?cái)?shù)，a 是正整數(shù)且不能被 p 整除， gcd(a,p)=1，則： ap-1 = 1(mod p)?；蛘吡硪环N形式：ap=a(mod p)，這種形式不要求 a 與 p 互素。useful in public key and primality testing,,,定理：(消去律)對(duì)于ab≡ac（mod m）來(lái)說(shuō)，若gcd(a,m)＝1則b≡c(mod m

8、),例如1：附加條件不滿(mǎn)足的情況6×3=18≡2 mod 8 a=6 n=86×7=42≡2 mod 8但3≠7 mod 8例如2：附加條件滿(mǎn)足的情況5×3＝15≡7 mod 8 a=5 n=85×11=55≡7 mod 83≡11 mod 8,,證明：構(gòu)造模p的完全剩余系P = {0，1, 2, … ,p-1}，step1：gcd(a, p) = 1，所以A= {0*a, 1

9、*a, 2*a, … ,(p-1)*a}也是模p的一個(gè)完全剩余系。 假設(shè)ja=ka(modp) ,因?yàn)間cd(a, p) = 1，j=k(modp),顯然j、k 不能相等 A= {0*a, 1*a, 2*a, … ,(p-1)*a}也是模p的一個(gè)完全剩余系。 就是說(shuō)P和A在模p意義下是相等的。因?yàn)? ≡ 0a (mod p)，所以 P-{0} 與 A-{0*a

10、}在模p意義下是相等的。記P'=P-{0},A'=A-{0*a},2024/3/23,大連理工大學(xué),,,step2：令W = πP' = 1 * 2 * 3 * 4 … * (p-1)，Y = πA' = a * 2a *3a * 4a * …(p-1)a = W*a^(p-1) //π表示連乘積有，W ≡ Y (mod p)即，W ≡ W*a^(p-1) (mod p)又因?yàn)椋?W, p)

11、= 1則有，1 ≡ a^(p-1) (mod p),2024/3/23,大連理工大學(xué),歐拉定理,歐拉定理：對(duì)任意互素的 a 和 n，有 aΦ(n) = 1(mod n)。其中，Φ(n)是歐拉函數(shù)，即小于 n 且與 n 互素的正整數(shù)的個(gè)數(shù)。當(dāng)m是素?cái)?shù)時(shí)，小于m且與m互素的正整數(shù)個(gè)數(shù)，用φ(m)表示，稱(chēng)m的Euler函數(shù)m是素?cái)?shù)時(shí)，φ(m)=m-1對(duì)n=pq, p和q 是素?cái)?shù)，φ(n)=φ(p)φ(q)=(p-1)(q-1),202

12、4/3/23,大連理工大學(xué),Euler 函數(shù)舉例,ø(37) = 36 φ(15）= φ（3）* φ(5）=（3-1）*（5-1） =8 這8個(gè)模15的剩余類(lèi)是： {1，2，4，7，8，11，13，14},證明：對(duì)n=pq, p和q 是素?cái)?shù)，φ(n)=φ(p)φ(q)=(p-1)(q-1)考慮模為n的數(shù)集Zn = {0, 1,2,....,pq -1}而不和n互質(zhì)的集合由下面三個(gè)集

13、合的并構(gòu)成：1) 能夠被p整除的集合{p,2p,3p,....,(q-1)p} 共計(jì)q-1個(gè)2) 能夠被q整除的集合{q,2q,3q,....,(p-1)q} 共計(jì)p-1個(gè)3) {0}很顯然，1、2集合中沒(méi)有共同的元素，因此φ(n)中元素個(gè)數(shù) ＝ pq -1 - (p-1）- （ q- 1) = (p-1)(q-1),歐拉定理 （Euler’s Theorem）,若（a, n）=1, 則 a φ(n)= 1 mod n 利

14、用歐拉定理求乘法反元素a-1 若φ(n) 已知，則由歐拉定理可知 a*a φ(n)-1= 1 mod n a-1 = a φ(n)-1 假設(shè)a =3, n=8, 利用歐拉定理，求a-1,a-1=3,,歐拉定理的證明,8.3 Miller Rabin Algorithm,a test based on prime properties that result from Fermat’s Theoremalgorit

15、hm is:TEST (n) is:1. Find integers k, q, k > 0, q odd, so that (n–1)=2kq2. Select a random integer a, 1<a<n–13. if aq mod n = 1 then return (“inconclusive");4. for j = 0 to k – 1 do5. if (a2jq mod n

16、= n-1) then return(“inconclusive")6. return (“composite"),大素?cái)?shù)產(chǎn)生,素?cái)?shù)生成過(guò)程: ?隨機(jī)選擇一個(gè)奇數(shù)n(如通過(guò)偽隨機(jī)數(shù)發(fā)生器) ?隨機(jī)選擇a, 使a<n ?進(jìn)行素性測(cè)試(例如用Miller-Rabin算法),若n沒(méi)有通過(guò)測(cè)試,拋棄n,轉(zhuǎn)到? ?如果通過(guò)了足夠次數(shù)的測(cè)試,認(rèn)為n是素?cái)?shù)。素?cái)?shù)理論: 在N附近，每ln(N)個(gè)整數(shù)

17、中有一個(gè)素?cái)?shù),8.4 中國(guó)剩余定理,中國(guó)剩余定理CRE，說(shuō)明某一個(gè)范圍內(nèi)的整數(shù)可通過(guò)它的一組剩余類(lèi)數(shù)來(lái)重構(gòu)，這組剩余類(lèi)數(shù)是對(duì)該整數(shù)用一組兩兩相素的整數(shù)取模得到的。一個(gè)整數(shù)被正整數(shù)n除后，余數(shù)有n種情形：0，1，2，3，…，n-1，它們彼此對(duì)模n不同余。這表明，每個(gè)整數(shù)恰與這n個(gè)整數(shù)中某一個(gè)對(duì)模n同余。這樣一來(lái)，按模n是否同余對(duì)整數(shù)集進(jìn)行分類(lèi)，可以將整數(shù)集分成n個(gè)兩兩不相交的子集。我們把（所有）對(duì)模n同余的整數(shù)構(gòu)成的一個(gè)集合叫做模n的

18、一個(gè)剩余類(lèi)。,8.4 剩余定理,（同余）：設(shè)n為一自然數(shù)，若a-b為n的倍數(shù)，則稱(chēng)a與b關(guān)于模n同余。記作 a≡b（mod n）；若a與b關(guān)于模n不同余，則記作 a≠b（mod n）；如果a≡b（mod n），則稱(chēng)b為a對(duì)模n的余數(shù)。反之，a也是b對(duì)模n的余數(shù)。性質(zhì)1：若a≡b（mod n）看作a與b的二元關(guān)系，則它是一個(gè)等價(jià)關(guān)系，即滿(mǎn)足：自反性 a ≡a（mod n）；對(duì)等性 如果a mod n=b

19、mod n，則a≡b（mod n）；對(duì)稱(chēng)性 若a≡b（mod n），則b≡a（mod n）；傳遞性 若a≡b（mod n）， b≡c（mod n），則a≡c（mod n）。,2024/3/23,大連理工大學(xué),同余或按模計(jì)算,性質(zhì) 2：若ai≡bi（mod n）（i=1，2，…，k）推論1：若 a≡b（mod n），則 ak≡bk（mod n），推論2：若 a≡b（mod n），則 ka≡kb（mod n），

20、以上兩式中：k 為任意整數(shù)（同余類(lèi)）：全體整數(shù)按照對(duì)模n的余數(shù)關(guān)系可分為n類(lèi)，使得同類(lèi)之?dāng)?shù)關(guān)于模n同余，不同類(lèi)之?dāng)?shù)關(guān)于模n不同余。這樣劃分的類(lèi)叫做模n同余類(lèi)。,2024/3/23,大連理工大學(xué),,定義：完全剩余系在模n的每個(gè)同余類(lèi)中取出一個(gè)數(shù)作為代表構(gòu)成的集合，叫做模n的完全剩余系。集合{0，1，2，…，n-1} 叫做模n的非負(fù)最小剩余系；集合{0，1，-1，2，-2，…} 叫做模n的絕對(duì)最小剩余系；

21、若（k，n）=1，則 0，k，2k，…，（n-1）k 為n的一個(gè)完全剩余系。,2024/3/23,大連理工大學(xué),,定義（縮剩余系）：從模n的n個(gè)同類(lèi)中取出與n互素的同余類(lèi)，從中個(gè)取出一個(gè)代表，構(gòu)成的集合叫做模n的縮剩余系。若{a1， a2，… ，a } 為模n的一個(gè)縮剩余系，又（k，n）=1，則{k a1 ，ka2，…，ka }也為一個(gè)縮剩余系。,2024/3/23,大連理工大學(xué),,定理（Fermat定理）：

22、設(shè)p為素?cái)?shù)，則對(duì)任意整數(shù)a，有ap≡a（mod p）(歐拉定理) 若（a, n）=1, 則 a φ(n)= 1 mod n*Fermat定理和Euler給出了方程ax ≡ 1（mod n）的解為x=amod n，若n為素?cái)?shù)，可進(jìn)一步簡(jiǎn)化上式為x=a（n-1）-1 mod n= an-2 mod n**若將其擴(kuò)展到一般一次同余方程ax ≡ b（mod n），若（a，n）=1 此方程有解，且有唯一的解 ，其解為x=b

23、x0 mod n；其中x0為方程ax ≡ 1（mod n）的解，即x0 =a mod n *,大連理工大學(xué),單變量線性同余（Linear Congruence in One Variable）,定義：已給整數(shù)a, b及n>0, ax=b mod n, 其中x 為變量。問(wèn)題：上式是否有解，如果有解，解是什么？定理：令 a, b, n 為整數(shù)，且a>0, (a, n)=d(1)若 d不能整除b, 則ax=b

24、 mod n 無(wú)解(2)若 d能整除b, 記做d|b, 則ax=b mod n 有d個(gè)解,ax = b mod n的求解過(guò)程：利用歐幾里德算法求出d=(a, n) 若d 不能整除b, 則無(wú)解。(2)若d能整除b, 則令： 因?yàn)?(a’, n’)=1, a’ x’ =b’ mod n’ 有唯一解，假設(shè)此解為x0 利用歐幾里德算法求出a’模n’的乘法逆元(a’)-1, x’= (a’)-1 b’

25、mod n’ x0 = x’ mod n 令x= x0 +(n/d)t mod n, t=1,2, …, d-1, 即可求出剩下的d-1個(gè)解,求解9x=12 mod 15 (1)求出d=(a, n)=(9,15)=3 3 能整除12，因此x有解，且有3個(gè)解 (2),Chinese Remainder Theorem,used to speed up modulo computations

26、 if working modulo a product of numbers eg. mod M = m1m2..mk Chinese Remainder theorem lets us work in each moduli mi separately since computational cost is proportional to size, this is faster than working in the fu

27、ll modulus M,Chinese Remainder Theorem,can implement CRT in several waysto compute A(mod M)first compute all ai = A mod mi separatelydetermine constants ci below, where Mi = M/mithen combine results to get answer u

28、sing:,30,Chinese Remainder Theorem (中國(guó)剩余定理),在中國(guó)古代著名數(shù)學(xué)著作《孫子算經(jīng)》卷下第28題，叫做“物不知數(shù)”，原文如下：今有物不知其數(shù)。三三數(shù)之余二；五五數(shù)之余三；七七數(shù)之余二。問(wèn)物幾何？也就是求正整數(shù)x，一個(gè)整數(shù)除以三余二，除以五余三，除以七余二，求這個(gè)整數(shù)。x ≡ 2 (mod 3)x ≡ 3 (mod 5)x ≡ 2 (mod 7)兩個(gè)問(wèn)題？(1) x

29、是否存在？ (2) 如何求x？,31,回答(1)：上式中 a1=2， a2=3， a3=2 令 n1, n2, …, nt為兩兩互素的正整數(shù)， 令 N= n1n2 …nt 則以下同余系統(tǒng)中，x= a1 mod n1, x= a2 mod n2, …, x= at mod nt, x會(huì)在[0, N-1]中有唯一解證明：由于n1, n2, …, nt為兩兩互素的正整數(shù)，故對(duì)所有 i= 1, 2, …, t,(ni,N/

30、ni)=1。因此，存在yi,使得(N/ni) yi =1 mod ni。若我們令則x 是上述同余系統(tǒng)的解，因?yàn)閷?duì)于所有i, 1≤ i ≤t,,回答(2)： N=3*5*7=105, N/n1=105/3=35, N/n2=105/5=21 N/n3=105/7=15 35y1=1mod3 y1=2 21y2=1mod5 y2=1 15y3=1mod7 y3=1x=35*2*2+21*1*3+13

31、*1*2=23 mod 105,,口訣：三人同行七十稀，五樹(shù)梅花廿一枝， 七子團(tuán)圓月正半，除百零五便得知。,2024/3/23,大連理工大學(xué),,,2024/3/23,大連理工大學(xué),8.5 離散對(duì)數(shù),生成元可證明：在GF(p)中至少存在一個(gè)元素g，使得GF(p)中任意非零元素可以表示成g的某次方冪的形式，g稱(chēng)為GF(p)的生成元,生成元的例子,有限域GF（23），5是GF（23）的生成元,Powers mod 1

32、9,Powers mod 19,Discrete Logarithms,the inverse problem to exponentiation is to find the discrete logarithm of a number modulo p that is to find i such that b = ai (mod p) this is written as i = dloga b (mod p)if a is

33、 a primitive root then it always exists, otherwise it may not, eg.x = log3 4 mod 13 has no answer x = log2 3 mod 13 = 4 by trying successive powers whilst exponentiation is relatively easy, finding discrete logarithms