密码学的数论基础.

1、第第7 7讲讲 数论基础数论基础第第7 7讲讲 数论基础数论基础1.定义：定义： 设整数设整数a和和b,且且a 0，如果存在整数，如果存在整数k使得使得b=ak， 那么就说那么就说a整除整除b（或（或b能被能被a整除）整除），记作，记作a|b，或者说，或者说b是是a的倍数。的倍数。 2.整除的基本性质整除的基本性质( N 整数集整数集) (1) a(a0), a|0,a|a (同理同理 b N,1|b) (2) b|a, cb|ca (3) a|b, b|c a|c.（传递性）（传递性） (4) a|b, a|c a|(xb+yc) (x,y N) (5) b|a 且且a0 |b|a| (6)

2、 cb|ca, b|a1.定义：定义： 一个大于一个大于1的整数的整数p，只能被，只能被1或者是它本身整除或者是它本身整除,而不能而不能被其他整数整除，则称整数为素数被其他整数整除，则称整数为素数(prime number)，否，否则就叫做合数则就叫做合数(composite)。 eg 素数（素数（2，3，5，7，11，13等）等） 合数（合数（4，6，8，9，12等）等） 2.补充定理补充定理(1)：设：设a是任一大于是任一大于1的整数，则的整数，则a的的除除1外的最小正因子外的最小正因子q是素数，并且当是素数，并且当a是合数是合数时：时：素数补充定理qa2.补充定理补充定理(2)：若：若p

3、是一个素数，是一个素数，a是任一整数，是任一整数，则有则有p|a或或(p,a)=1素数补充定理（续）素数补充定理（续）2.补充定理：补充定理： p为素数，且为素数，且p|ab,那么那么p|a或或p|b。 更一般地，如果更一般地，如果abz能够被素数能够被素数p整除，那么整除，那么a,b,z中的某个数必能被中的某个数必能被p整除。整除。3.素数个数定理（素数个数定理（1）：）： 素数的个数是无限的素数的个数是无限的原因：原因：（1）N（N1）的除）的除1外的最小正因数外的最小正因数q是一个素数是一个素数（2）如果）如果q=pi，（，（i1,2,k), 且且q|N，因此，因此q|(N- p1p2,

4、.pk)，所以，所以q|1，与，与q是素数矛盾。是素数矛盾。素数个数定理及证明证明：反证法证明：反证法假设正整数个数是有限的，设为假设正整数个数是有限的，设为p1,p2,.,pk令：令：p1p2pk+1=N (N1)则则N有一个素数有一个素数p，且，且ppi（i=1,2,k).故故p是上述是上述k个素数外的另外一个素数。个素数外的另外一个素数。因此与假设矛盾。因此与假设矛盾。素数定义及素数个数定理3.素数个数定理（素数个数定理（2）：）： 设设 (x)是小于是小于x的素数个数，则的素数个数，则 (x) x / lnx, 即即x时，比值时，比值 (x) /(x / lnx) 1 eg:可以估算可

5、以估算100位素数的个数：位素数的个数： (10100) - (1099) 10100/(ln10100) 1099/(ln1099) 3.9 * 1097.1.整数的唯一分解定理定理（算术基本定理）整数的唯一分解定理定理（算术基本定理）: 设设nZ, 有分解式有分解式, n = p1e1p2e2.pmem,其中其中p1, p2, pmZ+是互不相同的素数是互不相同的素数, e1,e2,emZ+, 并且数对并且数对(p1, e1), (p2, e2),(pm, em)由由n唯一确定（即唯一确定（即如果不考虑顺序，如果不考虑顺序，n的分解是唯一的）的分解是唯一的）.eg: 504=23327,

6、1125 = 3253整数的唯一分解定理就是在所有比就是在所有比1大的整数中大的整数中,除了除了1和它本身以外和它本身以外,不再有别的约数不再有别的约数,这种整数这种整数叫做质数叫做质数,质数又叫做素数。质数又叫做素数。判断方法：小的素数要记住，比如判断方法：小的素数要记住，比如11、13、17、19、23、29、31等，最等，最好把好把100以内的素数都记以内的素数都记住：住：357111317192329313741434753596167717379838997对于大数，首先看能不能被对于大数，首先看能不能被2、3、5、7整除，如果不能，就看能不能被更整除，如果不能，就看能不能被更大的素

7、数整除，这样你记住的相对小素数就有用了，一个一个试，从大的素数整除，这样你记住的相对小素数就有用了，一个一个试，从11开开始，以此试始，以此试13、17、19、23、29、31等。要一直试到比这个数的平方根等。要一直试到比这个数的平方根大的第一个数，如果没有能整除的，则这个数是素数。大的第一个数，如果没有能整除的，则这个数是素数。2. 求最大公约数的两种方法：求最大公约数的两种方法： (1)因数分解：因数分解： eg:1728 = 2632,4536 = 23347, gcd(1728, 4536) = 2332=72.(2)欧几里得欧几里得(Euclid)算法算法 设设a, b N, ab0

8、, 用以下方法可求出用以下方法可求出 gcd(a,b).最大公约数的欧几里得算法. ,)gcd( ,0 , . )gcd( ,0 ,)gcd( ,0 ,)gcd()gcd( ,0 ,1111123223332121122211111nnnnnnnnnnnnrqrr,rrrrrqrr,rrrrrqrr,rrrrrqrbb,ra,bbrrbqa 欧几里得算法抽象欧几里得算法抽象112 1213 2324 342111b.gcd( , )kk kkkkkkaqbrq rrrq rrrq rrrq rrrqra br规律：余数除数被除数忽略最大公约数的欧几里得算法 欧几里得算法实现欧几里得算法实现10

9、11112gcd( , ):;101(,.,):gcd( , )mmmrmrmmm mmmma bra rb mwhilerdoqrrq rmmreturnq qqrcommenta br算法最大公约数的欧几里得算法 模运算典型实例时钟模12的运算证明：证明：必要性必要性:设设ab (mod m), a=mp+r, b=mq+r, 0rm a-b=m(p-q), m|(a-b).充分性充分性:设设m|(a-b), a=mp+r, b=mq+s, 0r, sm a-b=m(p-q)+(r-s) m|(r-s) 0|r-s|1，如果，如果gcd(a, n) = 1,则则:a?(n) 1mod n.

10、 eg: 求求7803的后三位数字的后三位数字 解：解： 7803（mod 1000）的结果）的结果 ?(1000) = 1000(1-1/2)(1-1/5) = 400， 有有7803 (7400)273 343 (mod 1000)推论（推论（ Fermat小定理）小定理）: p素数素数,a是整数且不能被是整数且不能被p整除整除,则则:a p-1 1 mod p. 例如：例如： 求求 253 (mod 11) = ? 由由Fermat小定理小定理: 210 = 1024 1 (mod 11) 253 = (210)523 1523 8 (mod 11) 解：解：（1）由费尔马定理）由费尔马

11、定理2100（mod 1001）1（mod 101）（2）243210 (2100) 432210 210 1024 (mod 101)=14eg: 计算计算243210 （mod 101） 解：因为解：因为41是素数，所以由费马定理有是素数，所以由费马定理有 1777401（mod 41），而），而 1841 = 46 * 40 + 1 所以所以17771841 1777 14 (mod 41)， a=14eg: 17771841 a（mod 41），求），求a在在0到到41的值。的值。 解：解：由欧拉定理得由欧拉定理得1061（mod7），），下面求下面求1010被被6除所得的余数，除所得

12、的余数， 1010(-2)10=4555-2 4(mod6)， 所以所以1010 =6q+4，其中，其中q是一个正整数。于是是一个正整数。于是 (1010)10=106q+4=(106)q10410434=9222=4（mod7），），因此，因此，再过再过(1010)10天是星期五。天是星期五。eg: 如果今天是星期一，问从今天起再过如果今天是星期一，问从今天起再过(1010)10天天是星期几？是星期几？ eg: 1、 21000000mod 77=?1 1 2 21 12(mod 789)2(mod 789)7 7 2 26464367(mod 789)367(mod 789)2 2 2 2

13、2 24(mod 789)4(mod 789)8 8 2 2128128559(mod 789)559(mod 789)3 3 2 24 416(mod 789)16(mod 789)9 9 2 225625637(mod 789)37(mod 789)4 4 2 28 8256(mod 789)256(mod 789)10 10 2 2512512580(mod 789)580(mod 789)5 5 2 2161649(mod 789)49(mod 789)11 11 2 210241024286(mod 789)286(mod 789)6 6 2 2323234(mod 789)34(m

14、od 789)计算计算Xa ( mod n) ,其中其中 x, a, n Z+ Eg:计算计算21234 (mod 789) 一种有效的方法：一种有效的方法： 24 16 28 256 216 2562 49 232 492 34 264 342 367 2128 3672 559 2256 5592 37 2512 372 580 21024 5802 286 1234 = 1024+128+64+16+2 （1234 = (10011010010)2） 21234 = 286 559 367 49 4 481 (mod 789)优势：优势：模的幂运算可快速完成，并且模的幂运算可快速完成，并

15、且不需要太大内存不需要太大内存22/ 2 (2-1) / 2 (yyyyyyy表 示除 以取 整 ， 即 ：是 偶 数（是 奇 数 ）但是，上述计算过程并不适合于计算机程序实但是，上述计算过程并不适合于计算机程序实现。为此，可以采用现。为此，可以采用“重复平方重复平方-乘乘”运算来运算来进行指数模运算。进行指数模运算。2222() () (yyyxyxxxy因 此 ：是 偶 数是 奇 数 ）重复平方重复平方-乘算法乘算法 求模指数运算的重复平方-乘算法 输入：整数 x，y，n：x0，y?0，n1 输出：(mod )yxn 算法描述： 00 mod_exp(x,y, n) 01 if y=0 r

16、eturn(1) 02 if y (mod 2)=0 return(mod_exp(x2(mod n), y2, n)（mod n） 03 return(x mod_exp(x2(mod n), y2, n)(mod n) 由欧拉定理知道：如果由欧拉定理知道：如果(a, m)1，m1，则，则a?(n) 1(mod m)也就是说，如果也就是说，如果(a, m)1，m1，则存在一个整数，则存在一个整数满足满足:a 1(mod m)定义（整数的次数）：定义（整数的次数）： 若若(a, m)1，m1，则使得同余式，则使得同余式 a 1(mod m)成立的成立的最小正整数最小正整数叫做叫做a对模对模m的

17、的次数次数。定理：设定理：设a对模数对模数m的次数为的次数为l，an1（mod m），则），则l|n。证明：证明： 如果结论不成立，则必有两个整数如果结论不成立，则必有两个整数q和和r，使得：，使得： nqlr（0rl） 而而1 an a(qlr) aqlar ar (mod m)，因此与，因此与l的定义相的定义相违背。违背。 推论：设推论：设a对模数对模数m的次数为的次数为l，则，则l|?(m)。整数次数的计算：整数次数的计算： 因为因为l|?(m)，因此可以通过计算以下对模数，因此可以通过计算以下对模数m的值求出。的值求出。例如：例如：m7，a2(m)62322（mod 7）423（mod

18、 7）1因此因此a对模数对模数m的次数为的次数为3。s1212s,.dd .dmdddaaa，（其中，是 （）的诸因子）整数次数的有效计算方法（整数次数的有效计算方法（1）：）：1212.killlklimpppmp如 果是的 标 准 分 解 式 ， 整 数 a对 模 数 m的 次 数等 于 整 数 a对 模 数的 诸 次 数 的 最 小 公 倍 数 。1212a1, 2,.,),.,0|(1, 2,.,),.,iiiliiklddilddiikfpikdfffapamdmdddamapfdikdfff证 明 ： 设表 示对 模 数（1(mod )1(mod )如 果不 是 模 数的 次 数

19、， 则 设 其 次 数 为1(mod )1(mod )与是的 最 小 公 倍 数 矛 盾 。整数次数的有效计算方法（整数次数的有效计算方法（1）：）：amam例如：设 2，45，求 对的次数。解 ：45 5 92对 模 数 5的 次 数 是 42对 模 数 9的 次 数 是 6因 此 2对 模 数 45的 次 数 为 ：4,6=12。整数次数的有效计算方法（整数次数的有效计算方法（2）：）：211212|1 2 jjfijjjjjjpapffffpfpafjifpfji定 理 （ 次 数 的 求 法 之 二 ）设是 一 个 素 数 ，对 模 数的 次 数 是， 则 ：=或=； 又 设， 则 有

20、 ：10102apaf例 如 ： 设 7， 2， 求对 模 数的 次 数。122410410127148,2| 4822128fff解 ：， 所 以 ：定理：设定理：设a对模数对模数m的的次数次数为为l，1,a, a2,，al-1对对模数模数m两两不同余。两两不同余。证明：证明： 如果结论不成立，则有某对如果结论不成立，则有某对j，k（0jkl-1，使得：，使得： aj ak（mod m） 因此：因此： ak-j 1（mod m） 而而1k-j0,(g,m)=1, 如果整数如果整数g对对m的的次数次数为为?(m) ，则，则g叫做叫做m的一个的一个本原根本原根（或（或原根原根）. eg: 3是模

21、是模7的的本原根本原根 因为因为3 ?(7) 36 1(mod 7) w37 mod 7 = 3 38 mod 7 = 2w39 mod 7 = 6 310 mod 7 = 4w311 mod 7 = 5 312 mod 7 = 1例如：例如：m7，a2(m)62322（mod 7）423（mod 7）1因此：因此： a对模数对模数m的次数为的次数为3 (m) 所以：所以： 2不是不是7的本元根。的本元根。定理（原根）定理（原根） 设整数设整数m0,(g,m)=1,则则g是是m的一个原根的充要的一个原根的充要条件是：条件是： g，g2，g?(m)组成模数组成模数m的一组缩系。的一组缩系。定理说

22、明：如果定理说明：如果g是是m的一个原根，则模数的一个原根，则模数m的一的一组缩系可表示为形如定理中的几何级数。组缩系可表示为形如定理中的几何级数。2.定理：定理： 设对素数设对素数p而言，如果而言，如果g是一个是一个本原根本原根 (1)如果如果n是是整数，那么整数，那么gn 1(mod p)当且仅当当且仅当 n0(mod p-1) (2)如果如果j和和k都是整数，那么都是整数，那么gj gk当且仅当当且仅当j k(mod p-1)问题：是否所有的正整数都有原根？问题：是否所有的正整数都有原根？例如：例如：m12(m)623，与，与m互素的正整数包括互素的正整数包括5，7，11。52（mod

23、12）1因此，因此，5对对12的次数是的次数是272（mod 12）1因此因此7对模数对模数m的次数为的次数为2112（mod 12）1因此因此11对模数对模数m的次数为的次数为2因此因此m12没有原根。没有原根。定理（整数存在原根的必要条件）：定理（整数存在原根的必要条件）： 设设m1，若，若m有原根，则有原根，则m必为下列诸数之一：必为下列诸数之一：2，4，pl，2pl（l1，p为奇素数）。为奇素数）。定理（整数存在原根的充分条件）：定理（整数存在原根的充分条件）： 设设m2，4，pl，2pl（l1，p为奇素数）时，则为奇素数）时，则m有原有原根。根。定理（整数原根个数）：定理（整数原根个

24、数）： 设设m有一个原根有一个原根g，则，则m恰有恰有?(?(m)个对模数个对模数m不同余不同余的原根，这些原根由以下集合给出：的原根，这些原根由以下集合给出：|1( ),( , ( ) 1tSgtmtm 17gmmmmm1( ),( , ( ) 13 mod733 mod75mtmtm 例如，已知 3是 7的一个原根，求 的所有元根。解：（ ）62 3（ ）（6）2因此 有两个元根。满足条件的t=1,5即 有两个元根，分别为3和5原根的判断：原根的判断： 一般来说，判断一般来说，判断g是否时一个素数是否时一个素数m的原根时，的原根时，不需要逐一计算不需要逐一计算g1，g2，g?(m)，而仅需

25、要，而仅需要计算计算gt(modm），其中），其中t|?(m)。 23gmm4 mod74 mod7)24 mod7) 14 mod71m16例如，判断 4是否是 7的一个原根解：（ ）62 3满足条件t| (m)的t=1,2,3,6（）4（）因此4不是 的本元根。定理（原根的计算）：定理（原根的计算）： 12( )2.11(mod )(1,2,., )ismqmmqqqgmgmgm is设，（ ）的所有不同的素因子是 ， ， ，（ ， ），则 是 的一个原根的充要条件是： 3121220812412525)20,812mod4140112mod411811241gmmqqmmqqm例如，证明

26、 是 的原根。证明：（ ），（）（）由定理是 的一个原根。 12gm6 2 32,33;2mod7mod763 m 7mqqmm1223例如，判断 3是否是 7的原根。解：（ ）所以（ ）（ ）qq3 （）2 13 （）1因此 是 的原根。 12gmm2,33;2mod7mod7m=7qqmm1223例如，判断 4是否是 7的一个原根解：（ ）62 3所以（ ）（ ）qq4 （）2 14 （）1因此4不是的本元根。定理（原根的计算）：定理（原根的计算）： 1 ,1,2,.,papd dpd设 对模数奇素数 的次数是（），则：a都不是 的原根。 12.1,12.dadpdddpadpd证明：因为

27、 （ ， ， ）对模数 的次数为，而（ ， ）所以 （ ， ， ）都不是 的原根。（ ， ）一个计算原根的算法：一个计算原根的算法： 2112.1221112, 2,., 2(3)1111dppppaapddppdpp （）列出数， ， （）取 ，计算 对 的次数 ，如果 ，2就是 的原根，算法结束；如果，在步骤中列出的数中除去以下各数：在步骤（）列出的数中再取一个，重复步骤（），直到步骤（）缩列出的数仅剩下（ ）个。41例如：求出 的原根。1解 ：（ ） 列 出1， 2， 3， .， 40 （ 1）（2）取2，因为2对模数41的次数为20，因此（1）式中除去以下各数：2，4，8，16，32，

28、23，5，10，20，40，39，37，33，25，9，18，36，31，21，1得到：3，6，7，11，12，13，14，15，17，19，22，24，26，27，28，29，30，34，35，38 41例如：求出 的原根。解(续）：（3）取3，因为3对模数41的次数为8，因此在（1）式中除去以下各数：3，9，27，40，38，32，14，1其中1，9，32，40在第一次已经除去，得到：6，7，11，12，13，15，17，19，22，24，26，28，29，30，34，35这剩下的（40）16个数就是41的原根。如果整数如果整数m0有一个元根有一个元根g，g，g2，g?(m)(或数或数1,

29、g，g，g2，g?(m)-1）组成模数）组成模数m的一组缩系。的一组缩系。例如，例如， 3是模是模7的的本原根，因此本原根，因此： 31 3 32 2 33 6 34 4 35 5 36 1 上述六个数刚好是模数上述六个数刚好是模数m的一组缩系。的一组缩系。定义：任一整数定义：任一整数n，（，（n，m）1，必有唯一的整，必有唯一的整数数k（0k ?（m），满足：），满足： ngk（mod m） 其中其中k叫做叫做n对模数对模数m的指数，记做的指数，记做kindgn（简（简记为记为ind n） (指数也叫做指数也叫做离散对数离散对数)。xg mod m (mod )xngm对于已知元根g和模数m

30、，求任意整数n的离散对数k,可以通过得到：( )(13) 12(1,2,.,12)(0( ) 2 (mod13)iiikimn ikkmn例：g=2是m=13的元根,。求的离散对数：指数的性质：设指数的性质：设g是是m的原根，如果的原根，如果(a,m)(b,m)1：11g11()( )(mod ( )(2)(mod ( )(1)(3)1 0,1( )(4)( 1)(2)2(5)mind a(mod ( )nggind abinda ind bmindanindamnindindgmindmgind a ind gm（）设 也是 的一个原根，则(mod13)()( )(mod ( )(mod13

31、)311(mod12)3(mod12)ind abinda ind bmindindxindindx3x113x11例：求解同余方程3x 11(mod13)解：上述方程与gg同解。因为所以方程gg与同解，其指数为8，因此x=8即是方程解。55(mod12)5939(mod12)39(mod12)8,11,75indindindxindxx33例：求解同余方程x(mod13)解：解上述方程只需要解3indx。因为所以所以indx=3,7,11是的解。因此是方程x(mod13)的解。3(mod ( )(1)23(mod12)nindanindamnxindindx例：求解幂同余方程2(mod13)

32、解：因为所以的解就是原方程的解。ind2=4,ind3=9所以2x=8(mod 12)即x=4就是原方程的解。0-1(mod ),kpykpygppp gy猜想（离散对数困难问题）对于一个奇素数 ，整数 ，存在唯一的满足。选择一个适当大的 ，如果已知和 ，计算离散对数k是十分困难的。基于离散对数困难性假设，基于离散对数困难性假设，EIGamal提出了提出了EIgamal公钥公钥密码体制。密码体制。21()(mod)()()attatatttmyypmb gmb gmb bm12mod113412det234 112424215343131291(mod11)75注意：注意：5 5是是-2-2的

33、的乘法逆元素乘法逆元素注意：括号里的注意：括号里的是是A A的伴随矩阵的伴随矩阵定义定义(二次剩余）二次剩余） 设设n是一个大于是一个大于1的正整数，的正整数， aZ, a 0 (mod n). 如果同余方程如果同余方程 x2a (mod n) 有一个解有一个解1xn-1, 则称则称a是是模数模数n的的二次剩余二次剩余，而，而x称之为称之为a模模n的平方根。的平方根。如果上述方程无解，则如果上述方程无解，则a称之为模数称之为模数n的非二次剩余。的非二次剩余。群的定义 设G为非空集合，在G内定义了一种代数运算为，若满足下述公理：(1)有封闭性。对任意a、bG，恒有abG. (2)结合律成立。对任

34、意a、b、cG，有(ab)c=a(bc)(3)G中有一恒等元e存在，对任意aG, 有eG, 使ae=ea=a(4)对任意aG，存在a的逆元a-1G，使aa-1= a-1a =e则G构成一个群。若群G满足交换律，则称群G为交换群群举例例如，对于非空集合G=0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10，在mod11的情况下做加法运算，构成一个群，且是交换群。下面看看G，+满足公理的情况。(1)封闭性。对任意a、bG，恒有a+b(mod11)G. 例如, 8+9=176(mod11)G, 满足封闭性性质。 (2)结合律成立。对任意a、b、cG，有(a+b) +c=a+ (b+c)。这个容易理解。(3)G中有一恒等元e存在，对任意aG, 有eG, 使a+e=e+a=a. 在给定的集合G中，e=0, 满足上面的性质，故恒等元存在。(4)对任意aG，存在a的逆元a-1G，使a+a-1= a-1+a=e. 例如, 7在集合中的逆元为4，因7+4(mod11) 0显然，加法满足交换律，故该群是交换群群的例子 又如，对于非空集合