chap8-數(shù)論入門

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

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

3、稱它們兩兩互素。,2024/3/23,大連理工大學,8.1 素數(shù),關于公約數(shù)有以下性質(zhì)：性質(zhì)1 若a是b的倍數(shù)，則（a，b）=b性質(zhì)2 若a=bq+c，則（a，b）= （b，c）定義8.3（素數(shù)）：只有1和自身為其因數(shù)的，大于1的整數(shù)叫素數(shù)。,2024/3/23,大連理工大學,,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 費馬定理Fermat's Theorem,費馬小定理：若 p 是素數(shù)，a 是正整數(shù)且不能被 p 整除， gcd(a,p)=1，則： ap-1 = 1(mod p)。或者另一種形式：ap=a(mod p)，這種形式不要求 a 與 p 互素。useful in public key and primality testing,,,定理：(消去律)對于ab≡ac（mod m）來說，若gcd(a,m)＝1則b≡c(mod m

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

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

10、}在模p意義下是相等的。記P'=P-{0},A'=A-{0*a},2024/3/23,大連理工大學,,,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)又因為，(W, p)

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

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

13、合的并構成：1) 能夠被p整除的集合{p,2p,3p,....,(q-1)p} 共計q-1個2) 能夠被q整除的集合{q,2q,3q,....,(p-1)q} 共計p-1個3) {0}很顯然，1、2集合中沒有共同的元素，因此φ(n)中元素個數(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 假設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"),大素數(shù)產(chǎn)生,素數(shù)生成過程: ?隨機選擇一個奇數(shù)n(如通過偽隨機數(shù)發(fā)生器) ?隨機選擇a, 使a<n ?進行素性測試(例如用Miller-Rabin算法),若n沒有通過測試,拋棄n,轉到? ?如果通過了足夠次數(shù)的測試,認為n是素數(shù)。素數(shù)理論: 在N附近，每ln(N)個整數(shù)

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

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

19、mod n，則a≡b（mod n）；對稱性 若a≡b（mod n），則b≡a（mod n）；傳遞性 若a≡b（mod n）， b≡c（mod n），則a≡c（mod n）。,2024/3/23,大連理工大學,同余或按模計算,性質(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ù)（同余類）：全體整數(shù)按照對模n的余數(shù)關系可分為n類，使得同類之數(shù)關于模n同余，不同類之數(shù)關于模n不同余。這樣劃分的類叫做模n同余類。,2024/3/23,大連理工大學,,定義：完全剩余系在模n的每個同余類中取出一個數(shù)作為代表構成的集合，叫做模n的完全剩余系。集合{0，1，2，…，n-1} 叫做模n的非負最小剩余系；集合{0，1，-1，2，-2，…} 叫做模n的絕對最小剩余系；

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

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

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

24、 mod n 無解(2)若 d能整除b, 記做d|b, 則ax=b mod n 有d個解,ax = b mod n的求解過程：利用歐幾里德算法求出d=(a, n) 若d 不能整除b, 則無解。(2)若d能整除b, 則令： 因為 (a’, n’)=1, a’ x’ =b’ mod n’ 有唯一解，假設此解為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個解,求解9x=12 mod 15 (1)求出d=(a, n)=(9,15)=3 3 能整除12，因此x有解，且有3個解 (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 (中國剩余定理),在中國古代著名數(shù)學著作《孫子算經(jīng)》卷下第28題，叫做“物不知數(shù)”，原文如下：今有物不知其數(shù)。三三數(shù)之余二；五五數(shù)之余三；七七數(shù)之余二。問物幾何？也就是求正整數(shù)x，一個整數(shù)除以三余二，除以五余三，除以七余二，求這個整數(shù)。x ≡ 2 (mod 3)x ≡ 3 (mod 5)x ≡ 2 (mod 7)兩個問題？(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會在[0, N-1]中有唯一解證明：由于n1, n2, …, nt為兩兩互素的正整數(shù)，故對所有 i= 1, 2, …, t,(ni,N/

30、ni)=1。因此，存在yi,使得(N/ni) yi =1 mod ni。若我們令則x 是上述同余系統(tǒng)的解，因為對于所有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,,口訣：三人同行七十稀，五樹梅花廿一枝， 七子團圓月正半，除百零五便得知。,2024/3/23,大連理工大學,,,2024/3/23,大連理工大學,8.5 離散對數(shù),生成元可證明：在GF(p)中至少存在一個元素g，使得GF(p)中任意非零元素可以表示成g的某次方冪的形式，g稱為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