1、 数论入门数论入门 2022-1-20华中农业大学信息学院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-1-20华中农业大学信息学院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-1-20华中农业大学信息学院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 mo
4、d b)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,
5、 6)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)-
8、2(4269)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-1-
10、20华中农业大学信息学院442022-1-20华中农业大学信息学院4520004000600080001000020040060080010001200素数的个数2022-1-20华中农业大学信息学院46素因子分解素因子分解n算数基本定理：算数基本定理：任意整数任意整数 a 1 都可以唯一地因子分解为都可以唯一地因子分解为a = p1a1p2a2ptat ，其中，其中，pi 均是素数，且均是素数，且p1p20q如如. 91 = 7 x 13 ; 3600 = 24 x 32 x 52 2022-1-20华中农业大学信息学院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-1-20华中农业大学信息学院482 Fermat定理和定理和Euler定理定理nap-1 1 ( mod p)qp是素数，是素数，gcd( a, p ) = 1nFermat小定理小定理qap a (mod p)qp是素数，是素数，a是任意整数是任意整数2022-1-20华中农业大学信息学院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-1-20华中农业大学信息学院50n定定 理：理：设设 n = p1e1 p2e2 prer，pi pj, pi为素数，为素数，ei1,则则(n) = n (1-p1-1) (1-p2-1)(1-pr-1)例如：例
13、如：12 = 2 * 3 2022-1-20华中农业大学信息学院512022-1-20华中农业大学信息学院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定理的更一般化形式。定理的
14、更一般化形式。2022-1-20华中农业大学信息学院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-1-20华中农业大学信息学院56概率方面的考虑概率方面的考虑
15、n如果如果Miller-Rabin测试返回测试返回 “合数合数”，则该数，则该数一定不是素数；返回一定不是素数；返回“不确定不确定”，则该数可，则该数可能是素数，也可能是伪素数能是素数，也可能是伪素数n遇到伪素数的概率遇到伪素数的概率 0.9999992022-1-20华中农业大学信息学院57素数的分布素数的分布n数论中的素数定理可知：数论中的素数定理可知：n附近的素数分布附近的素数分布情况为，平均每情况为，平均每 ln(n)个整数中有一个素数个整数中有一个素数n偶数和偶数和5的倍数，都不是素数，所以只需要的倍数，都不是素数，所以只需要测试测试 0.4ln(n)次次q如，要找如，要找2200左
16、右的素数，则约需左右的素数，则约需55次测试次测试n这里只是平均意义上的结论这里只是平均意义上的结论q有时素数分布很密，有时很松有时素数分布很密，有时很松2022-1-20华中农业大学信息学院584 中国剩余定理中国剩余定理Chinese Remainder Theoremn用于加速模运算用于加速模运算 n某一范围内的整数可通过它对两两互素某一范围内的整数可通过它对两两互素的整数取模所得的余数来重构的整数取模所得的余数来重构 n使得非常大的数对使得非常大的数对M的模运算转化到更小的模运算转化到更小的数上来进行运算的数上来进行运算2022-1-20华中农业大学信息学院59中国剩余定理中国剩余定理
17、n可以多种方式实现可以多种方式实现CRTn计算计算 A(mod M)q首先依次计算所有首先依次计算所有 ai = A mod mi q确定常数确定常数 ci , 其中其中 Mi = M/miq用下列式子得到结果用下列式子得到结果:2022-1-20华中农业大学信息学院60中国剩余定理中国剩余定理除除数数mi余余数数ai最小公最小公倍数倍数衍衍数数Mi = M/mi乘率乘率Mi-1ci各总各总ai ci答数答数m1a1M=m1m2mkM1M1-1m2a2M2M2-1mkakMkMk-12022-1-20华中农业大学信息学院61应应 用用 举举 例例n计计 算：算：q120523 = 1651 *
18、 73 = (973 + 678) * 73 ？ (mod 1813)q已知已知1813 = 37 * 49 且（且（37，49）= 12022-1-20华中农业大学信息学院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 *
19、 73 mod 37, 34 * 73 mod 49）= (14, 32)应应 用用 举举 例例2022-1-20华中农业大学信息学院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除所得的除所得的 余数
21、乘上余数乘上15，结果大于，结果大于105就减去就减去105的倍数，这的倍数，这样就知道所求的数了。样就知道所求的数了。 2022-1-20华中农业大学信息学院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-1-20华中农业大学信息学院675.1 本原根本原根2022-1-20华中农业大学信息学院685.1 本原根本原根na(n)mo
22、d n = 1 nam = 1 (mod n), 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
23、 p的整数才有本原根，其中的整数才有本原根，其中p是奇是奇素数，素数， 是正整数。是正整数。2022-1-20华中农业大学信息学院692022-1-20华中农业大学信息学院70n求求 x ，以满足，以满足 y = gx (mod p) n可以写作可以写作 x = logg y (mod p)n如果如果g是是p的本原根，则的本原根，则x一定存在；否则，一定存在；否则，不一定存在不一定存在, 例如例如.x = log3 4 mod 13 无解无解 x = log2 3 mod 13 = 4 2022-1-20华中农业大学信息学院71n定义：定义：若若m 1, (a, m) = 1, 则使得同余式则
24、使得同余式 ai 1(mod m)成立的最小正整数成立的最小正整数i，叫做，叫做a对模对模m的离散对数。的离散对数。n指数一定是欧拉函数的因子指数一定是欧拉函数的因子n对任意整数对任意整数b和模数和模数p的本原根的本原根a，有唯一的幂，有唯一的幂i，使得，使得b ai mod p, 其中其中0 i p-1该指数该指数i称为以称为以a为底模为底模p的离散对数，记为的离散对数，记为 dloga, p(b)n离散对数不仅与模有关，而且与本原根有关。离散对数不仅与模有关，而且与本原根有关。n例如：例如：q2对模对模7的指数是的指数是3，对模，对模11的指数是的指数是10，所以，所以，2是模是模11的一个本原根，而不是模的一个本原根，而不是模7的本原根；的本原根；qdlog2, 9(8) = 32022-1-20华中农业大学信息学院722022-1-20西安电子科技大学 计算机学院73小小 结结q素数素数qFermat和和Euler定理定理q欧拉函数欧拉函数 (n) q素性测试（素性测试（Miller-Rabin算法）算法）q中国剩余定理中国剩余定理q离散对数离散对数2022-1-20华中农业大学信息学院74谢谢 谢谢 ！
