[tju]數(shù)論課件

1、1,數(shù)論,天津大學(xué),2,初等數(shù)論的概念,整除性和約數(shù)：假設(shè)d和a是整數(shù)，d|a（讀作d整除a），意味著存在某個整數(shù)k，有a=kd。如果d|a，并且d≥0，則稱d是a的約數(shù)。每個整數(shù)a都可以被其平凡約數(shù)1和a整除，a的非平凡約數(shù)也成為a的因子。,3,初等數(shù)論的概念,素數(shù)和和數(shù)對于某個整數(shù)a>1，如果它僅有平凡約束1和a則稱p是素數(shù)。否則p是合數(shù)?？梢宰C明素數(shù)有無限多個。篩法求素數(shù)。,4,初等數(shù)論概念,除法定理，余數(shù)和同模

2、除法定理：對任意整數(shù)a和任意正整數(shù)n，存在唯一的整數(shù)q和r，使得a=qn+r，其中0≤r<n。值q成為除法的商，值r=a(mod n)稱為除法的余數(shù)。根據(jù)整數(shù)模n所得的余數(shù)，可以把整數(shù)分成n個等價類。包含整數(shù)的模n等價類為：[a]n={a+kn| k∈Z},5,初等數(shù)論的概念,公約數(shù)與最大公約數(shù)d是a的約數(shù)并且也是b的約數(shù)，則d是b的公約數(shù)。兩個不同時為0的整數(shù)a和b的最大公約數(shù)表示為gcd(a, b)。,6,初等數(shù)論的

3、概念,gcd(a, b) 的性質(zhì)：定理：如果a，b是不全為0的任意整數(shù)，則gcd(a, b)是a與b的線性組合{ax+by:x,y∈Z}中的最小正元素。推論1：對于任意整數(shù)a，b，如果d|a并且d|b，則d|gcd(a, b)。推論2：對于所有整數(shù)a和b以及任意非負整數(shù)n，gcd(an, bn)=n*gcd(a,b)。推論3：對所有正整數(shù)n，a和b，如果n|ab并且gcd(a, n)=1，則n|b。,7,初等數(shù)論的概念,互質(zhì)數(shù)：

4、如果兩個整數(shù)a與b只有公因數(shù)1，即如果gcd(a, b)=1，則a與b稱為互質(zhì)數(shù)。定理：對任意整數(shù)a，b和p，如果gcd(a, p)=1且gcd(b, p)=1，則gcd(ab, p) = 1。,8,初等數(shù)論概念,唯一因子分解唯一質(zhì)因子分解定理：合數(shù)a僅能以一種方式，寫成如下的乘積形式：a=p1e1p2e2…prer其中pi為素數(shù)，p1<p2<…<pr，且ei為正整數(shù)。,9,初等數(shù)論基本概念,例1：求一個正整

5、數(shù)n的所有約數(shù)和。把正整數(shù)n分解質(zhì)因子的乘積，假設(shè)結(jié)果為n=p1e1p2e2…prer，那么正整數(shù)n的所有因子之和為：Sum=(1+p1+p12+…+p1e1)*(1+p2+p22+…+p2e2) *…*(1+pr+pr2+…+prer),10,最大公約數(shù),GCD遞歸定理：對任意非負整數(shù)a和任意正整數(shù)b，gcd(a, b) = gcd(b, a mod b)。,11,最大公約數(shù),歐幾里德算法：EUCLID(a, b) if

6、 b = 0 than return a else return EUCLID(b, a % b),12,最大公約數(shù),歐幾里德算法的運行時間引理：如果a>b≥1并且EUCLID(a, b)執(zhí)行了k≥1次遞歸調(diào)用，則a≥Fk+2，b≥Fk+1 。定理：對任意整數(shù)k≥1，如果a>b≥1且b< Fk+1 ，那么EUCLID(a, b)的遞歸調(diào)用次數(shù)少于k次。,13,最大公約數(shù),二進制最大公約數(shù)算法

7、：如果a和b都是都是偶數(shù)，那么gcd(a, b) = 2gcd(a/2, b/2)。如果a是奇數(shù)，b是偶數(shù)，那么gcd(a, b) = gcd(a, b/2)。如果a和b都是奇數(shù)，那么gcd(a, b) = ((a–b)/2, b)。,14,最大公約數(shù),擴展歐幾里德算法：EXTENDED-EUCLID(a, b) if b = 0 then return (a, 1, 0) (d’,x’,y’)

8、← EXTENDED-EUCLID(b, a%b) (d, x, y) ← (d’, y’, x’ – (a/b) * y’) return (d, x, y),15,模運算,有限群：群(S, +)是一個集合S和定義在S上的二元運算+，它滿足如下性質(zhì)：封閉性：如果a, b∈S，那么a+b ∈S。單位元：存在一個元素e，使得對于所有的a∈S都滿足e+a=a+e=a。結(jié)合律：對于任意的a, b, c都滿足(a+b)+

9、c=a+(b+c)。逆元：對每個a∈S都存在唯一的元素b∈S使得a+b=b+a=e。把b稱作a的逆元。,16,模運算,根據(jù)模加法和模乘法定義的群：定義在集合Zn上集合上的加法和乘法運算定義為：[a]n +n [b]n = [a+b]n[a]n *n [b]n = [a*b]n,17,求解模線性方程,定理：方程ax=b(mod n)對于未知量x有解，當且僅當gcd(a, n)|b定理：方程ax=b(mod n)或者對模n有d個

10、不同的解，其中d=gcd(a, n)或者無解。,18,求解模線性方程,定理：設(shè)d=gcd(a, n)，假定對整數(shù)x’和y’，有d=ax’+ny’。如果d|b，則方程ax=b(modn)有一個解的值為x0，滿足x0=x’(b/d)mod n。,19,求解模線性方程,定理：假設(shè)方程ax=b(mod n)有解（即有d|b，其中d=gcd(a, n)），x0是該方程的任意一個解，則該方程對模n恰有d個不同的解，分別為：xi=x0+i(n/d)(

11、i = 1, 2, …, d-1)。,20,求解模線性方程,MODULAR-LINEAR_EQUATION_SOLVER(a, b, n) (d,x’,y’) ← EXTENDED-EUCLID(a, n) if (d | b) then x0 ← x’(b/d)mod n for i ← 0 to d-1 do print(x0 + i(n / d)) mod n

12、 else print “no solution”,21,模線性方程,定理：對任意n>1，如果gcd(a, n)=1，則方程ax=b(mod n)對模n有唯一解。定理：對任意n>1，如果gcd(a, n)=1，則方程ax=1(mod n)對模n有唯一解，否則無解。,22,中國剩余定理,設(shè)n=n1n2…nk，其中因子ni兩兩互質(zhì)。考慮下列對應(yīng)關(guān)系：a ←→ （a1, a2, …, ak） (1)其中a

13、∈Zn，ai∈Zni，而且對i=1, 2, …kai = a mod ni則映射(1)是一個在Zn與笛卡爾積Zn1× Zn2×…× Znk之間的一一映射。對Zn中的元素所執(zhí)行的操作可以等價地作用于對應(yīng)的k元組，即當在適當?shù)南到y(tǒng)中可以獨立地對每個坐標位置執(zhí)行所需運算。,23,中國剩余定理,推論：如果n1, n2, …, nk兩兩互質(zhì)， n=n1n2…nk，則對任意正整數(shù)a1, a2, …, ak）方程組x

14、=ai(mod ni)關(guān)于未知量x有模n的唯一解。,24,元素的冪,3k mod 7為：i 0 1 2 3 4 5 6 7 8 9 10 113k mod 7 1 3 2 6 4 5 1 3 2 6 4 52k mod 7為：i 0 1 2 3 4 5 6 7 8 9 10 112k mod 7 1 2 4 1 2 4 1 2 4 1 2 4,25,元素的冪,歐拉

15、定理：對于任意整數(shù)n>1，aphi(n)=1(mod n)對所有的a∈Zn*成立。費馬定理：如果p是素數(shù)，則ap-1=1(mod n)對所有的a∈Pn*成立。,26,元素的冪,定理：對所有的素數(shù)p>2和所有正整數(shù)e，滿足Zn*為循環(huán)群的n(n>1)值為2, 4, pe和2pe。,27,元素的冪,定理：如果p是一個奇素數(shù)且e≥1，則方程x2=1(mod pe)僅有兩個解：x=1和x=-1。定理：如果對模n存在1的非平

16、凡平方根，則n是和數(shù)。,28,元素的冪,計算x2=1(mod n)在區(qū)間[1, n-1]上的解的個數(shù)。,29,元素的冪,當n=pk時（p是素數(shù)，并且k>0），由x2=1(mod pk)可以改寫為(x-1)(x+1)=0(mod pk)。所以pk|(x-1)(x+1)。如果p>2，那么p不可能同時整除(x-1)和(x+1)，所以pk|(x-1)或pk|(x+1)。于是可以得到當x=1(mod pk)或x=-1(mod pk)

17、時，x2=1(mod pk)如果p=2，因為2k|(x-1)(x+1)，所以x是奇數(shù)。那么(x-1)和(x+1)是相鄰的偶數(shù)，所以必然有一個能被2整除，卻不能被4整除；而能被4整除的那個必須能被2k-1整除。所以當k>2時，那么x=±1(mod 2k)和x=2k-1 ± 1(mod 2k)都是x2=1(mod 2k)的解。（k=2時這兩組解是一樣的）,30,元素的冪,對于一般情況，首先把n分解成素數(shù)因子乘積的

18、形式：n=p1e1p2e2…prer，（e1, e2…er > 0）。那么x2=1(mod n)成立當且僅當對所有的i都滿足x2=1(mod piei)。對不等于2的pi來說，x mod p1e1有兩種可能（±1），對于等于2的pi，需要看指數(shù)，如果指數(shù)是1，只有一種可能，如果指數(shù)是2，有兩種可能，如果指數(shù)大于2，有四種可能。根據(jù)中國剩余定理，所有素因子的每一組可能值都對應(yīng)了方程的一個解， 由乘法原理，可以得出方程的解的

19、數(shù)目為：2(r+[8|m]+[4|m]-[2|m]),31,離散對數(shù),定義：離散對數(shù)問題（DLP）是這樣的一個問題：給定一個素數(shù)p，p在Zp*上的一個原根a，以及一個整數(shù)b∈ Zp*。求一個整數(shù)x（0<x<p-1)，使得ax=b(mod p)。記作：x=logab,32,離散對數(shù),性質(zhì)1：令a是素數(shù)p的原根，b，r是正整數(shù)，并且a，b，r∈Zp*。那么loga(b*r)=(logab+logar)mod (p-1)；

20、并且對于任意整數(shù)s，有l(wèi)oga(bs)=s*loga(b) mod (p-1)。,33,離散對數(shù),例：令p=11，它的一個原根是2，因為26=9(mod n)，所以log29=6。另外還有26=216=226=9(mod n),34,離散對數(shù),一般離散對數(shù)問題（GDLP）：給定一個n階的有限循環(huán)群G和它的一個原根，以及元素b，求一個整數(shù)x（0≤x≤n-1），使得ax=b,35,離散對數(shù),計算離散對數(shù)窮舉搜索Baby-step Gia

21、nt-step算法,36,離散對數(shù),Baby-step Giant-step算法：Baby-step Giant-step是一個用空間換時間的對窮舉算法的一個改進，令m=(p-1)1/2，如果b=ax，那么可以把x重寫為x=i*m+j，其中0 ≤ i, j < m，于是b=ai*m * aj，兩邊同除得b(a-m)i=aj，然后可以通過下面的算法來計算x。,37,離散對數(shù),38,離散對數(shù),Baby-step Giant-step

22、算法：復(fù)雜度分析：需要保存(p-1)1/2個二元組，生成這些二元組需要的時間為O((p-1)1/2)，對二元組進行排序需要的時間為O(log((p-1)1/2)*(p-1)1/2) 第（5）步的循環(huán)最多執(zhí)行(p-1)1/2次，每次如果采用二分查找來尋找指定元素那么總的時間復(fù)雜度為O((p-1)1/2 log((p-1)1/2),39,離散對數(shù),例：令p=113，a=3，b=57執(zhí)行算法：m=11計算出的二元組排好序為：j

23、 0 1 8 2 5 9 3 7 6 10 43j(mod 113) 1 3 7 9 17 21 27 40 51 63 81計算a-1=3-1(mod 113) = 38，然后計算a-m=3811(mod 113) = 58執(zhí)行循環(huán)過程中r=b*a-mi，查找過程中的(i, r)為：i 0 1 2 3 4 5 6 7 8 9r 57 29 10

24、0 37 112 55 26 39 2 3最終返回：i * m + j = 9 * 11 + 1 = 100,40,離散對數(shù),判斷a是否是Zn*的原根：定理：設(shè)n>1，phi(n)的所有不同素因數(shù)是p1, p2, …, pk。gcd(a, n) = 1，則a是Zn*的原根的充要條件是：對于所有的i(1≤i≤k)，aphi(n)/pi(mod n) != 1,41,二次剩余,定義：設(shè)p是一個奇素數(shù)。如果關(guān)于未知量x的方程x2

25、=a(modp)有解，則數(shù)a∈Zp*就是一個二次余數(shù)。,42,二次余數(shù),定理：對模p，恰有(p-1)/2個二次剩余。證明：對于任意的k∈Zp*，x2=(p-k)2(mod p)。并且對于任意的r∈Zp*，如果r != k并且r != p – k，那么r2和k2對p不是同余的，否則p|(k+r)(k-r)，根據(jù)假設(shè)，p既不能整除(k+r)和也不能整除(k-r)。,43,二次剩余,44,素數(shù)測試,45,素數(shù)測試,46,素數(shù)測試,47,素數(shù)

26、測試,要判斷一個整數(shù)n是不是素數(shù)，應(yīng)用費馬定理：如果n是素數(shù)，那么對于任意的a都滿足an-1=1(mod n)。所以可以通過隨機選取若干個a，來檢驗n是否是素數(shù)。,48,素數(shù)測試,如果n是和數(shù)，并且滿足an-1=1(mod n)那么就說n是一個基為a的偽素數(shù)。,49,素數(shù)測試,然而，并不能通過增加隨機次數(shù)來增加這種測試的正確性，因為存在一些和數(shù)，也滿足對于任意的a，an-1=1(mod n)通常把這樣的和數(shù)成為Carmichael數(shù)。前

27、三個Carmichael數(shù)是561，1105和1729。Carmichael數(shù)是非常少的，在小于100000000的數(shù)中，只有255個Carmichael數(shù)。,50,梅森素數(shù),把形如(2p-1)形式的素數(shù)稱為梅森素數(shù)，p是素數(shù)。[1, 231-1]之間的梅森素數(shù)有：22-1, 23-1, 25-1, 27-1, 213-1, 217-1, 219-1, 231-2梅森素數(shù)的一個性質(zhì)：一個正整數(shù)n的所有約數(shù)和是2的冪當且僅當n能夠被