1、 數論入門數論入門 2022-5-1華中農業大學信息學院2n整數：整數：q整數集整數集 , -3, -2, -1, 0, 1, 2, 3, 記為記為Z。n整除：整除：q設設a, b為整數。若存在某個整數為整數。若存在某個整數c, 使得使得b=ac, 則則稱稱a整除整除b（等價地，稱（等價地，稱a是是b的一個因子，或者的一個因子，或者說說a為為b的一個因子）。若的一個因子）。若a整數整數b，則記為，則記為 a | b 。n例如：例如：2022-5-1華中農業大學信息學院3n整除的基本性質：整除的基本性質：q對所有的整數對所有的整數a，b，c，有以下正確結論：，有以下正確結論：q a | aq若若

2、 a | b 且且 b | c ，則，則 a | c 。q若若 a | b 且且 a | c，則對于所有的整數，則對于所有的整數x，y，有有a |（bx+cy）。）。q若若 a | b 且且 b | a，則，則 a = + b 或或 a = -b 。n例如例如 2022-5-1華中農業大學信息學院4n整數的整除算法整數的整除算法q若若a，b均為整數，且均為整數，且b=1, 則按照則按照a除以除以b的的普通長除法可以找到整數普通長除法可以找到整數q（商）和（商）和r余數，余數，使得：使得：a=qb+r，其中，其中0=r Ring Field域相關概念及定理n域的特征 - 任意元素a的n次累計和為

3、0的最小的n；域的特征要么是素數，要么是0(沒有)；n素域：沒有非0真子域的域；n有限域的階是pn（其中p是素數）；n有限域的乘法群是循環群；可逆在加/解密中的重要性n加密的操作對象是比特分組，通常被看作整數加密是對整數的變換。這種變換必須能恢復(解密時)，即可逆。如果加密是乘法，則解密就是除法，而域上正好有除法-乘法逆元。n對于8bits字節，希望Z256是域，但它不是；于是轉而尋求GF(28)，它是域。nAES的S盒是基于模2系數的模某8次不可約多項式的剩余類。4.2 模運算n模運算即求余數（C語言中的運算符）x mod na其中0ab)gcd(a, b) = gcd(b, a mod b

4、)n求最大公因子輾轉相除法（歐幾里德算法）gcd(a, b) = gcd(b%a, a%b)GCD(1970,1066)1970 = 1 x 1066 + 904 gcd(1066, 904)1066 = 1 x 904 + 162 gcd(904, 162)904 = 5 x 162 + 94 gcd(162, 94)162 = 1 x 94 + 68 gcd(94, 68)94 = 1 x 68 + 26 gcd(68, 26)68 = 2 x 26 + 16 gcd(26, 16)26 = 1 x 16 + 10 gcd(16, 10)16 = 1 x 10 + 6 gcd(10, 6)

5、10 = 1 x 6 + 4 gcd(6, 4)6 = 1 x 4 + 2 gcd(4, 2)4 = 2 x 2 + 0 gcd(2, 0)函數gcd(a, b)nint gcd(int a, int b)nnif (a=0) | (b=0)nreturn a+b;nelsenreturn gcd(a%b, b%a);n4.4 有限域GF(p)n域，無限域n有限域，又叫Galoris域有限域的階都有pn的形式階為p的有限域記為GF(p)n唯一性 (Isomorphism)q在同構意義下，某階有限域只有一個nGF(p)：(Zp, +, x)GF(pm)：q系數在Zp上的模某不可約多項式的多項式域

6、GF(2n)：p=2GF(p)：(Zp, +, x)n逆元q由于p是素數，所以除了0外都有逆元nGF(p=2)：(Z2, +, x)GF(p=7)：(Z7, +, x)* GF(p=8)：(Z8, +, x)不是域求逆元：擴展Euclid算法n擴展擴展Euclid算法算法做歐幾里德算法的計算序列做歐幾里德算法的計算序列r0q1r1r2 (令令r0n，r1a)r1q2r2r3r2q3r3r4rm-2qm-1rm-1rm (1)rm-1qmrm rm+1 (0)記記 t0 rm+1，t1rm，依依 tjtj-2 qi-1 tj-1 mod r0，得得 tm逆逆 r1的逆的逆擴展Euclid算法舉例

7、n22 1 mod 31311229-122 9 即 3022 9 mod 312229422-2(3022) 4 即 322 4 mod 31 92413022-2(322) 1即2422 1 mod 31n28 1 mod 757522819-22819 即 732819 mod 7528119928-1(7328)9 即 328 9 mod 7519291 (7328)-2(338)1 即6728 1 mod75n269 1 mod 349349126980 -126980 即 -126926938029 269-3(-1269)29 即 4269 8022922 (-1269)-2(4

8、269)22 即 -9269 291227 (4269)-1(-9269)7 即 13269 22371 (-9269)-3(13269)1即-48269 得301函數reverse()nint reverse(int a, int m)nint b, b1=1, b2=0; / 逆元nint r, r1=a, r2=m; /ndo r = r2 % r1; / y-kx = rnb = (b2-(r2/r1)*b1)%m;nr2 = r1;b2 = b1;nr1 = r;b1 = b;n while (r1);nif (r=0) return 0;nif (b 1是素數，當且僅當它只有因子是

9、素數，當且僅當它只有因子1和和 p。q素數不能寫作其它數的乘積素數不能寫作其它數的乘積 q1是素數，但一般對它沒興趣是素數，但一般對它沒興趣 n例如：例如：2, 3, 5, 7是素數，是素數，4, 6, 8, 9, 10 不是素數不是素數n200以內的素數以內的素數: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 2022-5-1華中

10、農業大學信息學院442022-5-1華中農業大學信息學院4520004000600080001000020040060080010001200素數的個數2022-5-1華中農業大學信息學院46素因子分解素因子分解n算數基本定理：算數基本定理：任意整數任意整數 a 1 都可以唯一地因子分解為都可以唯一地因子分解為a = p1a1p2a2ptat ，其中，其中，pi 均是素數，且均是素數，且p1p20q如如. 91 = 7 x 13 ; 3600 = 24 x 32 x 52 2022-5-1華中農業大學信息學院47互素和最大公因子互素和最大公因子n兩個數兩個數 a, b 互素，如果它們沒有除互素

11、，如果它們沒有除1以外的公因子以外的公因子 q如如 ( 8, 15 ) = 1 n最大公因子最大公因子q如如: 300 = 22 x 31 x 52 18 = 21 x 32 因此因此 GCD( 18, 300 ) = 21 x 31 x 50 = 62022-5-1華中農業大學信息學院482 Fermat定理和定理和Euler定理定理nap-1 1 ( mod p)qp是素數，是素數，gcd( a, p ) = 1nFermat小定理小定理qap a (mod p)qp是素數，是素數，a是任意整數是任意整數2022-5-1華中農業大學信息學院49n小于小于n且與且與n互素的正整數的個數互素的

12、正整數的個數 如如 n = 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ，1, 3, 7, 9 (10) = 4n素數素數 p (p) = p-1 n素數素數p, q，有，有 (pq) = (p-1) x (q-1) n如：如：(37) = 36(21) = (31) x (71) = 2 x 6 = 12n約定：約定： (1) = 12022-5-1華中農業大學信息學院50n定定 理：理：設設 n = p1e1 p2e2 prer，pi pj, pi為素數，為素數，ei1,則則(n) = n (1-p1-1) (1-p2-1)(1-pr-1)例如：例如：12 = 2 *

13、 3 2022-5-1華中農業大學信息學院512022-5-1華中農業大學信息學院52na(n) 1 (mod n)對任意對任意 a, n，gcd(a, n) = 1n另一種表示：另一種表示：a(n)+1 a (mod n)對任意對任意 a, nn如：如：a = 3; n = 10; (10) = 4; 則則 34 = 81 1 mod 10a = 2; n = 11; (11) = 10;則則 210 = 1024 1 mod 11nFermat定理是定理是Euler定理的推論，或者說，定理的推論，或者說， Euler定理是定理是Fermat定理的更一般化形式。定理的更一般化形式。2022-

14、5-1華中農業大學信息學院53n與與RSA有關的結果有關的結果q兩個素數兩個素數 p 和和 q，整數，整數m 和和 n，n = pq, 0 m 0, q 是奇數，使得是奇數，使得 (n1) = 2kq 2. 隨機選擇整數隨機選擇整數 a, 1 a n1 3. if aq mod n = 1 then 返回返回 (“不確定不確定); 4. for j = 0 to k 1 do 5. if (a2jq mod n = n-1) then 返回返回(“ 不確定不確定) 6. return (“合數合數)2022-5-1華中農業大學信息學院56概率方面的考慮概率方面的考慮n如果如果Miller-Ra

15、bin測試返回測試返回 “合數合數”，則該數，則該數一定不是素數；返回一定不是素數；返回“不確定不確定”，則該數可，則該數可能是素數，也可能是偽素數能是素數，也可能是偽素數n遇到偽素數的概率遇到偽素數的概率 0.9999992022-5-1華中農業大學信息學院57素數的分布素數的分布n數論中的素數定理可知：數論中的素數定理可知：n附近的素數分布附近的素數分布情況為，平均每情況為，平均每 ln(n)個整數中有一個素數個整數中有一個素數n偶數和偶數和5的倍數，都不是素數，所以只需要的倍數，都不是素數，所以只需要測試測試 0.4ln(n)次次q如，要找如，要找2200左右的素數，則約需左右的素數，則

16、約需55次測試次測試n這里只是平均意義上的結論這里只是平均意義上的結論q有時素數分布很密，有時很松有時素數分布很密，有時很松2022-5-1華中農業大學信息學院584 中國剩余定理中國剩余定理Chinese Remainder Theoremn用于加速模運算用于加速模運算 n某一范圍內的整數可通過它對兩兩互素某一范圍內的整數可通過它對兩兩互素的整數取模所得的余數來重構的整數取模所得的余數來重構 n使得非常大的數對使得非常大的數對M的模運算轉化到更小的模運算轉化到更小的數上來進行運算的數上來進行運算2022-5-1華中農業大學信息學院59中國剩余定理中國剩余定理n可以多種方式實現可以多種方式實現

17、CRTn計算計算 A(mod M)q首先依次計算所有首先依次計算所有 ai = A mod mi q確定常數確定常數 ci , 其中其中 Mi = M/miq用下列式子得到結果用下列式子得到結果:2022-5-1華中農業大學信息學院60中國剩余定理中國剩余定理除除數數mi余余數數ai最小公最小公倍數倍數衍衍數數Mi = M/mi乘率乘率Mi-1ci各總各總ai ci答數答數m1a1M=m1m2mkM1M1-1m2a2M2M2-1mkakMkMk-12022-5-1華中農業大學信息學院61應應 用用 舉舉 例例n計計 算：算：q120523 = 1651 * 73 = (973 + 678) *

18、 73 ？ (mod 1813)q已知已知1813 = 37 * 49 且（且（37，49）= 12022-5-1華中農業大學信息學院62nM = m1 * m2 = 37 * 49 (37, 49) = 1n973可用較小的兩個模數可用較小的兩個模數37和和49重構，表示為重構，表示為（11，42）n678可表示為（可表示為（12，41）n則則1651 = 973 + 678就可表示為就可表示為 （11 + 12 mod 37, 42 + 41 mod 49）= (23, 34)n則則120523 = 1651 * 73就可表示為就可表示為 （23 * 73 mod 37, 34 * 73

19、mod 49）= (14, 32)應應 用用 舉舉 例例2022-5-1華中農業大學信息學院63應用舉例應用舉例n孫子算經：孫子算經：q今有物不知其數，三三數之剩二，五五數之剩三，今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？七七數之剩二，問物幾何？q答曰二十三答曰二十三設所求物數為設所求物數為 X, 則則 X 2（mod 3), X 3（mod 5), X 2（mod 7)n術曰：三三數剩一置幾何？術曰：三三數剩一置幾何？n答曰：五乘七乘二得之一百四。答曰：五乘七乘二得之一百四。 n五五數剩一復置幾何？五五數剩一復置幾何？n答曰，三乘七得之二十一是也。答曰，三乘七得之二

20、十一是也。 n七七數剩一又置幾何？七七數剩一又置幾何？n答曰，三乘五得之十五是也。答曰，三乘五得之十五是也。 n三乘五乘七，又得一百零五。三乘五乘七，又得一百零五。 n到了明代，數學家到了明代，數學家程大位程大位用詩歌概括了這一算法用詩歌概括了這一算法:n三人同行七十稀，五樹梅花廿一枝，三人同行七十稀，五樹梅花廿一枝， n七子團圓月正半，除百零五便得知。七子團圓月正半，除百零五便得知。 n這首詩的意思是：用這首詩的意思是：用3除所得的余數乘上除所得的余數乘上70，加上用加上用5除所得余數乘以除所得余數乘以21，再加上用，再加上用7除所得的除所得的 余數乘上余數乘上15，結果大于，結果大于105

21、就減去就減去105的倍數，這的倍數，這樣就知道所求的數了。樣就知道所求的數了。 2022-5-1華中農業大學信息學院66中國剩余定理中國剩余定理除除數數mi余余數數ai最小公最小公倍數倍數衍衍數數Mi = M/mi乘率乘率Mi-1ci各總各總ai ci答數答數32M=3*5*7=1055*725*7*270*2140+63+30=23323 mod 105537*317*3*121*3723*513*5*115*22022-5-1華中農業大學信息學院675.1 本原根本原根2022-5-1華中農業大學信息學院685.1 本原根本原根na(n)mod n = 1 nam = 1 (mod n),

22、 GCD(a, n) = 1q一定存在一定存在 ，因為，因為m = (n) ，（，（ (n) 是可能的最高指數）是可能的最高指數）qm不一定最小不一定最小q一旦到達一旦到達m, 將會產生循環。將會產生循環。q最小的最小的m，成為，成為a的的階階。n如果一個數如果一個數a的階為的階為(n)，則稱，則稱a為為n的的本原根本原根n若若p是素數是素數, a是是p的本原根，則的本原根，則a1, a2, a3, , ap-1 是模是模p各不相同的各不相同的 ；n并不是所有整數模并不是所有整數模n都有本原根。都有本原根。q只有只有n是形為是形為2，4，p和和2 p的整數才有本原根，其中的整數才有本原根，其中p是奇是奇素數，素數， 是正整數。是正整數。2022-5-1華中農業大學信息學院692022