信息保障与安全05数论入门ppt课件.ppt

数论入门数论入门 2024/8/18华中农业大学信息学院2§0 整数整数n整数：整数：n整数集整数集{… , -3, -2, -1, 0, 1, 2, 3, …} 记为记为Zn整除：整除：n设设a, b为为整整数数若若存存在在某某个个整整数数c, 使使得得b=ac, 则则称称a整整除除b〔〔等等价价地地，，称称a是是b的的一一个个因因子子，，或或者者说说a为为b的的一一个个因因子子））若若a整整数数b，，则则记为记为 a | b n例如：例如：2024/8/18华中农业大学信息学院3§0 整数整数n整除的基本性质：整除的基本性质：n对对所所有有的的整整数数a，，b，，c，，有有以以下下正正确确结结论：论：n a | an假设假设 a | b 且且 b | c ，那么，那么 a | c n假假设设 a | b 且且 a | c，，则则对对于于所所有有的的整整数数x，，y，有，有a |（（bx+cy）n假假设设 a | b 且且 b | a，，那那么么 a = + b 或或 a = -b n例如例如 2024/8/18华中农业大学信息学院4§0 整数整数n整数的整除算法整数的整除算法n若若a，，b均均为为整整数数，，且且b>=1, 则则按按照照a除除以以b的的普普通通长长除除法法可可以以找找到到整整数数q〔〔商商〕〕和和r余余数，使得：数，使得：a=qb+r，其中，其中0<=r

唯一n除除法法所所得得余余数数记记为为a mod b，，商商记记为为a div bn例如例如 2024/8/18华中农业大学信息学院5§0 整数整数n整数模整数模nn设设n为一整数为一整数n若若a，，b为为整整数数，，则则称称a与与b是是模模n同同余余的的，，记记为为a ≡ b〔〔mod n）n同余的性质：对所有的整数同余的性质：对所有的整数a，，a1，，b，，b1，，c有有na ≡ b （（mod n〕〕当当且且仅仅当当a与与b被被n除除时时所所得得的的余余数相同n自反性：自反性： a ≡ a （（mod n））n对对称称性性：：假假设设 a ≡ b （（mod n）），，则则b ≡ a （（mod n））n传传递递性性：：假假设设 a ≡ b （（mod n）），，b ≡ c （（mod n），则），则a ≡ c （（mod n））n假假设设 a ≡ a1〔〔mod n）），，b ≡ b1 （（mod n）），，那那么么 a + b ≡ a1 + b1 （（mod n）），，且且 a b ≡ a1 b1 （（mod n）） 2024/8/18华中农业大学信息学院6§0 整数整数n整数的乘法逆元整数的乘法逆元n设设a为为整整数数，，若若存存在在整整数数x，，使使得得ax ≡1〔〔mod n），则称），则称x为为a的模的模n的乘法逆元。

的乘法逆元n若若x存存在在，，则则它它是是唯唯一一的的，，此此时时称称a为为可可逆的，逆的，a的逆元记为的逆元记为a-1n设设a为为整整数数，，则则a可可逆逆当当且且仅仅当当 gcd〔〔a，，n））= 12024/8/18华中农业大学信息学院72024/8/187乘法逆元乘法逆元n若若ab≡1 mod n，， 则a和和b互互为mod n的乘的乘法逆元n例：例：2*4 ≡1 mod 7，，n则2是是4模模7的乘法逆元的乘法逆元n 或或 4是是2模模7的乘法逆元的乘法逆元n求乘法的逆元用欧几里得求乘法的逆元用欧几里得扩展算法2024/8/18华中农业大学信息学院8欧几里得扩展算法欧几里得扩展算法EUCLID(m, b)1. (A1, A2, A3)←(1, 0, m); (B1, B2, B3)←(0, 1, b)2. if B3 = 0return A3 = gcd(m, b); no inverse3. if B3 = 1 return B3 = gcd(m, b); B2 = b–1 mod m4. Q = 5. (T1, T2, T3) = (A1 – Q B1, A2 – Q B2, A3 – Q B3)6. (A1, A2, A3) = (B1, B2, B3)7. (B1, B2, B3) = (T1, T2, T3)8. goto 2乘法逆元乘法逆元2024/8/18华中农业大学信息学院9乘法逆元乘法逆元gcd(1759, 550)=1QA1A2A3B1B2B3—101759015503015501–310951–3109–516521–5165106–33941106–3394–1113551Abstract AlgebraAlgebraic structure Semigroupclosure封闭性, associative 结合律Groupclosure, associativity, identity单位元, inverse逆元Ring+: associativity, commutativity交换律, identity, inverse 0*: associativity, distributivity分配律Fielda ringmultiplicative inverse 乘法逆元Lattice, Boolean群：群群：群G G有时记为有时记为{G, {G, ··},},是一个二元运算的集合，这是一个二元运算的集合，这个二元运算表示为个二元运算表示为··（操作符（操作符·· 可以指加法，乘法可以指加法，乘法或者其他的数学运算符），或者其他的数学运算符），G G中的每一个序偶中的每一个序偶(a,b)(a,b)通过运算生成通过运算生成G G中的元素中的元素( a( a··b)b)，满足以下公理：，满足以下公理：chap4 有限域(A1)封闭性: 若a和b都属于G， a ·b也属于G(A2)结合律：对G中任意元素a, b, c，都有a ·(b ·c)=(a ·b) ·c成立。

A3)单位元：G中存在一个元素e，对于G中任意元素a，都有a ·e= e·a=a成立A4)逆元：对于G中任意元素a，G中都存在一个元素a’，使得a · a’= a’ ·a=e成立4.1 群环域n群 Groupn集合，元素n二元运算 ·n封闭性、结合律n单位元、逆元n有限群、无限群n交换群〔Abel）n循环群n生成元环 Ringn环Rn二元运算: 加法+、乘法×n(R, +)是交换群n乘法封闭性、乘法结合律n分配律 a(b+c) = ab+acn交换环n乘法交换律n整环〔交换环且）n乘法单位元1n无零因子: ab=0 a=0或b=0域 Fieldn域FnF是整环n存在乘法逆元(0除外)n除法定义: a/b = a(b-1)n有理数域、实数域、复数域n有限域chap4 有限域(A1)加法封闭性(A2)加法结合律(A3)加法单位元(A4)加法逆元(M4)乘法交换律(M1)乘法封闭性(M2)乘法结合律(M3)分配率(M7)乘法逆元(M5)乘法单位元(M6)无零因子(A5)加法交换律群可交换群环可交换环整环域Group >> Ring >> Field域相关概念及定理n域的特征n - 任意元素a的n次累计和为0的最小的n；n域的特征要么是素数，要么是0(没有)；n素域：没有非{0}真子域的域；n有限域的阶是p^n〔其中p是素数）；n有限域的乘法群是循环群；可逆在加/解密中的重要性n加密的操作对象是比特分组，通常被看作整数n加密是对整数的变换。

这种变换必须能恢复(解密时)，即可逆如果加密是乘法，则解密就是除法，而域上正好有除法---乘法逆元n对于8bits字节，希望Z256是域，但它不是；于是转而寻求GF(2^8)，它是域nAES的S盒是基于模2系数的模某8次不可约多项式的剩余类4.2 模运算n模运算即求余数〔C语言中的运算符％）nx mod n＝an其中0≤ab)ngcd(a, b) = gcd(b, a mod b)n求最大公因子n辗转相除法〔欧几里德算法）ngcd(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)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)n{nif ((a==0) || (b==0))nreturn a+b;nelsenreturn gcd(a%b, b%a);n}4.4 有限域GF(p)n域，无限域n有限域，又叫Galoris域n有限域的阶都有pn的形式n阶为p的有限域记为GF(p)n唯一性 (Isomorphism)n在同构意义下，某阶有限域只有一个nGF(p)：(Zp, +, x)nGF(p^m)：n系数在Zp上的模某不可约多项式的多项式域nGF(2^n)：p=2GF(p)：(Zp, +, x)n逆元n由于p是素数，所以除了0外都有逆元nGF(p=2)：(Z2, +, x)nGF(p=7)：(Z7, +, x)n*GF(p=8)：(Z8, +, x)不是域求逆元：扩展Euclid算法n扩展扩展Euclid算法算法n做欧几里德算法的计算序列做欧几里德算法的计算序列nr0＝＝q1r1＋＋r2 (令令r0＝＝n，，r1＝＝a)nr1＝＝q2r2＋＋r3nr2＝＝q3r3＋＋r4n…nrm-2＝＝qm-1rm-1＋＋rm (1)nrm-1＝＝qmrm＋＋ rm+1 (0)n记记t0 ＝＝rm+1，，t1＝＝rm，，…n依依tj＝＝tj-2 －－qi-1 tj-1 mod r0，，…n得得tmn逆逆r1的逆的逆扩展Euclid算法举例n22×□≡ 1 mod 31n31＝＝1×22＋＋9-1×22 ≡ 9 即即 30×22≡ 9 mod 31n22＝＝2×9＋＋422-2×(30×22) ≡ 4 即即 3×22≡ 4 mod 31n 9＝＝2×4＋＋130×22-2×(3×22) ≡1即即24×22≡ 1 mod 31n28×□≡ 1 mod 75n75＝＝2×28＋＋19-2×28≡19 即即 73×28≡19 mod 75n28＝＝1×19＋＋928-1×(73×28)≡9 即即 3×28≡ 9 mod 75n19＝＝2×9＋＋1 (73×28)-2×(3×38)≡1 即即67×28≡ 1 mod75n269×□≡ 1 mod 349n349＝＝1×269＋＋80 -1×269≡80 即即 -1×269n269＝＝3×80＋＋29 269-3×(-1×269)≡29 即即 4×269n 80＝＝2×29＋＋22 (-1×269)-2×(4×269)≡22 即即 -9×269n 29＝＝1×22＋＋7 (4×269)-1×(-9×269)≡7 即即 13×269n 22＝＝3×7＋＋1 (-9×269)-3×(13×269)≡1即即-48×269 得得301函数reverse()nint reverse(int a, int m)n{int 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 (r>1);nif (r==0) return 0;nif (b<0) b += m;nreturn b;n}4.5 多项式运算n多项式 {一元n次整数域}n多项式运算n加，减n乘n例子：f(x) = x3 + x2 + 2，g(x) = x2 - x + 1nf(x) + g(x) = x3 + 2x2 - x + 3nf(x) – g(x) = x3 + x + 1nf(x) x g(x) = x5 + 3x2 - 2x + 2-q除法: f(x)/g(x)=q(x) … r(x)q整除，若r(x)=0q模g(x)同余qf(x) = q(x) g(x) + r(x)q f(x) ≡ r(x) mod g(x)q不可约多项式(素多项式,既约多项式)qg(x)不能表示为另两个多项式的乘积q关于系数∈Zn的多项式多项式环n系数是域F的多项式，构成环n系数是Zn的多项式环n系数是Zp的多项式环n在Z2上的多项式环，n在计算机上操作时有优势n加法，即XORn乘法，即ANDn构造GF(p^n)n从环到域构造GF(p^n)n系数在Zp上的n-1次多项式f(x)集合Sn共有p^n个n(S,＋,×)构成有限域GF(p^n) n需要某n次不可约多项式m(x)n使用模m(x)的多项式加法和乘法n从GF(p^n)到GF(2^n)n到GF(2^8) in AESExample GF(23)-n 4.6 有限域GF(2^n)n系数模2，即只可0或1n若次数最高7次，共2^8=256个多项式(剩余类)n加法nXORn乘法n移位，加法/XORn乘法逆元(除法)n扩展Euclid算法GF(2^3)上的运算〔in AES）nm(x) = x^8 + x^4 + x^3 + x + 1n运算表：8x8n{ AES }Termsnabelian groupassociativecoefficient setncommutativecommutative ringcyclic groupndivisorEuclidean algorithm fieldnfinite groupfinite ringfinite fieldngeneratorgreatest common divisorngroupidentity elementninfinite groupinfinite ringinfinite fieldnintegral domaininverse elementirreducible polynomialnmodular arithmeticmodular polynomial arithmeticnmodulo operator modulusmonic polynomialnorderpolynomialpolynomial arithmeticnpolynomial ringprime numberprime polynomialnrelatively primeresiduering小结n域结构在密码学上有重要应用。

n另外，格结构也越来越表现出重要用途2024/8/18华中农业大学信息学院43§1 素数n数论主要关心的是素数数论主要关心的是素数n整数整数p > 1是素数，当且仅当它只有因子是素数，当且仅当它只有因子±1和和± pn素数不能写作其它数的乘积素数不能写作其它数的乘积 n1是素数，但一般对它没兴趣是素数，但一般对它没兴趣 n例如：例如：2, 3, 5, 7是素数，是素数，4, 6, 8, 9, 10 不是素数不是素数n200以内的素数以内的素数: n2 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 149 151 157 163 167 173 179 181 191 193 197 199 2024/8/18华中农业大学信息学院442024/8/18华中农业大学信息学院45素数的个数2024/8/18华中农业大学信息学院46素因子分解素因子分解n算数基本定理：算数基本定理：n任意整数任意整数 a > 1 都可以唯一地因子分解为都可以唯一地因子分解为a = p1a1p2a2…ptat ，其中，，其中，pi 均是素数，且均是素数，且p10n如如. 91 = 7 x 13 ; 3600 = 24 x 32 x 52 n确定一个大数的素因子分解不是一件容易的事确定一个大数的素因子分解不是一件容易的事2024/8/18华中农业大学信息学院47互素和最大公因子互素和最大公因子n两个数两个数 a, b 互素，如果它们没有除互素，如果它们没有除1以外的公因子以外的公因子 n如如 ( 8, 15 ) = 1 n最大公因子最大公因子n如如: 300 = 22 x 31 x 52 n 18 = 21 x 32 n 因此因此 GCD( 18, 300 ) = 21 x 31 x 50 = 62024/8/18华中农业大学信息学院48§2 Fermat定理和定理和Euler定理定理nap-1 ≡ 1 ( mod p)np是素数，是素数，gcd( a, p ) = 1nFermat小定理小定理nap ≡ a (mod p)np是素数，是素数，a是任意整数是任意整数n在公钥密码中很有用在公钥密码中很有用Fermat 定理定理2024/8/18华中农业大学信息学院49n小于小于n且与且与n互素的正整数的个数互素的正整数的个数 n如如 n = 10, n {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ，，{1, 3, 7, 9} n ø(10) = 4n素数素数 p ø(p) = p-1 n素数素数p, q，有，有 ø(pq) = (p-1) x (q-1) n如：如：nø(37) = 36nø(21) = (3–1) x (7–1) = 2 x 6 = 12n商定：商定： ø(1) = 1Euler函数函数 ø(n)2024/8/18华中农业大学信息学院50n定定 理：理：n设设 n = p1e1 p2e2 … prer，，pi ≠ pj, pi为素数，为素数，ei≥1,那么那么nø(n) = n (1-p1-1) (1-p2-1)…(1-pr-1)例如：例如：12 = 22 * 3 ø(12) = 12 * (1-2-1) * (1-3-1) = 42024/8/18华中农业大学信息学院512024/8/18华中农业大学信息学院52naø(n) ≡ 1 (mod n)n对任意对任意 a, n，，gcd(a, n) = 1n另一种表示：另一种表示：naø(n)+1 ≡ a (mod n)n对任意对任意 a, nn如：如：na = 3; n = 10; ø(10) = 4; n那么那么 34 = 81 ≡ 1 mod 10na = 2; n = 11; ø(11) = 10;n那么那么 210 = 1024 ≡ 1 mod 11nFermat定理是定理是Euler定理的推论，或者说，定理的推论，或者说， Euler定理是定理是Fermat定理的更一般化形式。

定理的更一般化形式Euler 定定 理理2024/8/18华中农业大学信息学院53n与与RSA有关的结果有关的结果n两个素数两个素数 p 和和 q，整数，整数m 和和 n，，n = pq, 0< m 0, q 是奇数，使得是奇数，使得 (n–1) = 2kqn 2. 随机选择整数随机选择整数 a, 1 < a < n–1n 3. if aq mod n = 1 then 前往前往 (“不确定不确定");n 4. for j = 0 to k – 1 don 5. if (a2jq mod n = n-1)n then 前往前往(“ 不确定不确定")n 6. return (“合数合数")2024/8/18华中农业大学信息学院56概率方面的考虑概率方面的考虑n如果如果Miller-Rabin测试返回测试返回 “合数合数”，则该，则该数一定不是素数；前往数一定不是素数；前往“不确定不确定”，则该数，则该数可能是素数，也可能是伪素数可能是素数，也可能是伪素数n遇到伪素数的概率遇到伪素数的概率 < 1/4n用用t个不同的随机选择的数个不同的随机选择的数a，重复做测试，重复做测试t次，次，则则n是素数的概率是是素数的概率是:nPr = 1 - 4-tn例如例如. t = 10，，n是素数的概率是素数的概率 > 0.9999992024/8/18华中农业大学信息学院57素数的分布素数的分布n数论中的素数定理可知：数论中的素数定理可知：n附近的素数分布附近的素数分布情况为，平均每情况为，平均每 ln(n)个整数中有一个素数个整数中有一个素数n偶数和偶数和5的倍数，都不是素数，所以只需要的倍数，都不是素数，所以只需要测试测试 0.4ln(n)次次n如，要找如，要找2200左右的素数，则约需左右的素数，则约需55次测试次测试n这里只是平均意义上的结论这里只是平均意义上的结论n有时素数分布很密，有时很松有时素数分布很密，有时很松2024/8/18华中农业大学信息学院58§4 中国剩余定理中国剩余定理Chinese Remainder Theoremn用于加速模运算用于加速模运算 n某某一一范范围围内内的的整整数数可可通通过过它它对对两两两两互互素素的的整数取模所得的余数来重构整数取模所得的余数来重构 n使使得得非非常常大大的的数数对对M的的模模运运算算转转化化到到更更小小的数上来进行运算的数上来进行运算2024/8/18华中农业大学信息学院59中国剩余定理中国剩余定理n可以多种方式实现可以多种方式实现CRTn计算计算 A(mod M)n首先依次计算所有首先依次计算所有 ai = A mod mi n确定常数确定常数 ci , 其中其中 Mi = M/min用下列式子得到结果用下列式子得到结果:2024/8/18华中农业大学信息学院60中国剩余定理中国剩余定理除除数数mi余余数数ai最小公最小公倍数倍数衍衍数数Mi = M/mi乘率乘率Mi-1ci各总各总ai ci答数答数m1a1M=m1m2…mkM1M1-1m2a2M2M2-1………………mkakMkMk-12024/8/18华中农业大学信息学院61应应 用用 举举 例例n计计 算：算：n120523 = 1651 * 73 = (973 + 678) * 73 ≡ ？？ (mod 1813)n已知已知1813 = 37 * 49 且〔且〔37，，49））= 12024/8/18华中农业大学信息学院62nM = m1 * m2 = 37 * 49 (37, 49) = 1n973可用较小的两个模数可用较小的两个模数37和和49重构，表示为〔重构，表示为〔11，，42））n678可表示为〔可表示为〔12，，41））n则则1651 = 973 + 678就可表示为就可表示为n （（11 + 12 mod 37, 42 + 41 mod 49））= (23, 34)n则则120523 = 1651 * 73就可表示为就可表示为n （（23 * 73 mod 37, 34 * 73 mod 49））= (14, 32)应应 用用 举举 例例2024/8/18华中农业大学信息学院63应用举例应用举例n孙子算经：孙子算经：n今有物不知其数，三三数之剩二，五五数之剩今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？三，七七数之剩二，问物几何？n答曰二十三答曰二十三设所求物数为设所求物数为 X, 那么那么 X ≡ 2〔〔mod 3), X ≡ 3〔〔mod 5), X ≡ 2〔〔mod 7)n术曰：「三三数剩一置几何？术曰：「三三数剩一置几何？n答曰：五乘七乘二得之一百四。

答曰：五乘七乘二得之一百四 n五五数剩一复置几何？五五数剩一复置几何？n答曰，三乘七得之二十一是也答曰，三乘七得之二十一是也 n七七数剩一又置几何？七七数剩一又置几何？n答曰，三乘五得之十五是也答曰，三乘五得之十五是也 n三乘五乘七，又得一百零五三乘五乘七，又得一百零五 n到了明代，数学家程大位用诗歌概括了这一算法到了明代，数学家程大位用诗歌概括了这一算法:n　　三人同行七十稀，五树梅花廿一枝，　　三人同行七十稀，五树梅花廿一枝， n　　七子团圆月正半，除百零五便得知　　七子团圆月正半，除百零五便得知 n　　这首诗的意思是：用　　这首诗的意思是：用3除所得的余数乘上除所得的余数乘上70，，加上用加上用5除所得余数乘以除所得余数乘以21，再加上用，再加上用7除所得的除所得的 余数乘上余数乘上15，结果大于，结果大于105就减去就减去105的倍数，这的倍数，这样就知道所求的数了样就知道所求的数了 2024/8/18华中农业大学信息学院66中国剩余定理中国剩余定理除除数数mi余余数数ai最小公最小公倍数倍数衍衍数数Mi = M/mi乘率乘率Mi-1ci各总各总ai ci答数答数32M=3*5*7=1055*725*7*270*2140+63+30=233≡23 mod 105537*317*3*121*3723*513*5*115*22024/8/18华中农业大学信息学院67§5.1 本原根本原根§5 离散对数离散对数Discrete Logarithms2024/8/18华中农业大学信息学院68§5.1 本原根本原根naø(n)mod n = 1 nam = 1 (mod n), GCD(a, n) = 1n一定存在一定存在 ，因为，因为m = ø(n) ，（，（ ø(n) 是可能的最高指数）是可能的最高指数）nm不一定最小不一定最小n一旦到达一旦到达m, 将会产生循环。

将会产生循环n最小的最小的m，成为，成为a的阶n如果一个数如果一个数a的阶为的阶为ø(n)，则称，则称a为为n的本原根的本原根n若若p是素数是素数, a是是p的本原根，那么的本原根，那么na1, a2, a3, …, ap-1 是模是模p各不相同的各不相同的 ；；n并不是所有整数模并不是所有整数模n都有本原根都有本原根n只有只有n是形为是形为2，，4，，pα和和2 pα的整数才有本原根，其中的整数才有本原根，其中p是奇素是奇素数，数， α是正整数是正整数2024/8/18华中农业大学信息学院692024/8/18华中农业大学信息学院70n求求 x ，以满足，以满足 y = gx (mod p) n可以写作可以写作 x = logg y (mod p)n如果如果g是是p的本原根，则的本原根，则x一定存在；否则，一定存在；否则，不一定存在不一定存在, 例如例如.nx = log3 4 mod 13 无解无解 nx = log2 3 mod 13 = 4 n指数运算相对容易，求离散对数问题是困指数运算相对容易，求离散对数问题是困难的难的§5.2 离散对数离散对数2024/8/18华中农业大学信息学院71n定义：定义：n若若m > 1, (a, m) = 1, 则使得同余式则使得同余式 ai ≡ 1(mod m)n成立的最小正整数成立的最小正整数i，叫做，叫做a对模对模m的离散对数。

的离散对数n指数一定是欧拉函数的因子指数一定是欧拉函数的因子n对任意整数对任意整数b和模数和模数p的本原根的本原根a，有唯一的幂，有唯一的幂i，使得，使得nb ≡ ai mod p, 其中其中0 ≤ i ≤ p-1n该指数该指数i称为以称为以a为底模为底模p的离散对数，记为的离散对数，记为 dloga, p(b)n离散对数不仅与模有关，而且与本原根有关离散对数不仅与模有关，而且与本原根有关n例如：例如：n2对模对模7的指数是的指数是3，对模，对模11的指数是的指数是10，所以，，所以，2是模是模11的的一个本原根，而不是模一个本原根，而不是模7的本原根；的本原根；ndlog2, 9(8) = 32024/8/18华中农业大学信息学院722024/8/18西安电子科技大学 计算机学院73小小 结结q素数素数qFermat和和Euler定理定理q欧拉函数欧拉函数 ø(n) q素性测试〔素性测试〔Miller-Rabin算法）算法）q中国剩余定理中国剩余定理q离散对数离散对数2024/8/18华中农业大学信息学院74谢谢 谢谢 ！！。