第3章 基础数论

返回总目录,第3章基础数论,教学目的,了解模运算及辗转相除法了解中国余式子定律了解Lagrange定理与费马小定理了解原根、二次剩余、Galois域等概念了解质数理论和连分数了解密码安全伪随机数字生成器,模运算与辗转相除法,本章内容,中国余式子定律,Lagrange定理与费马小定理,原根,二次剩余,Galois域,连分数,质数理论,密码安全伪随机数字生成器,模运算与辗转相除法,3.1模运算与辗转相除法,假设今天是星期五，请问10000天后是星期几？,（即5+10000除以7的余数）,即：10000天后是星期二,同余,定义（同余，Congruence）：令。令为两整数，称a同余b模n，记为，当n整除b-a。而所有与a同余的整数所组成的集合，即称为a的同余类。所有同余类所形成的集合,同余类,同余类满足的性质：,（1）（反身性，Reflexivity）,（3）（迁移性，Transitivity）,若则,例：,令则,模运算,加法：,（1）封闭性：若同余类则,（2）交换律：若同余类则,（4）存在加法单位素：存在，使得,（5）存在加法反元素：对任一存在使得,减法：,乘法：,交换群,定义（交换群）考虑，其中G为集合，而*为运算。令公理：,（1）封闭性：则；（2）交换律：则；（3）结合律：则；（4）存在单位素：，使得（5）存在反元素：，使得,若公理1、3、4、5成立，称为群(Group)；若以上公理15都成立，称为交换群。,交换环,辗转相除法,例：,求7812及6084的最大公因子,被除数=商除数+余数，gcd（被除数，除数）=gcd（除数，余数）辗转相除法就是利用此性质，反复以（除数/余数）取代（被除数/除数）,其中：,所以gcd(7812,6084)=36,辗转相除法,定理3.1整数线性方程有整数解,证明：,若则：,为一整数解,若,有整数解,因：且,所以,借助广义辗转相除法，存在整数，使得,对模乘法,证明：,根据交换群封闭性,则,因，故存在乘法反元素、使得且，而故为的乘法反元素。,模运算与辗转相除法,3.2中国余式子定理（ChineseRemainderTheorem）,定理：,令为两两互质的正整数，令则同余联立方程组在集合有惟一解，其解为其中，而,余式定理应用,其中，为n的质因数，,性质1：,存在群同构（GroupIsomorphism）,定义：,当为正整数时，定义Euler-Phi函数为,性质2：,Lagrange定理与费马小定理,3.3Lagrange定理与费马小定理,令为群，若为子集，且在相同的运算*形成群则称（或H）为G的子群（Subgroup）。,子群(Subgroup),Lagrange定理,定理（Lagrange定理）若G为有限群，H为G中之子群，则,证明：,H为G的子群，为方便起见，假设为乘法群。可定等价关系如下：若如此定义出的等价关系可将分割成若干个等价类，即,每个等价类都有#H个元素（考虑为11对应）。因此#H整除#G,费马小定理,定理（费马小定理）,令为p质数、a为与p互质的整数，则,证明：,考虑乘法群，为其子群，根据Lagrange定理,所以,其中,因此：,原根,考虑2的次方（mod11）：,3.4原根,此时称2为乘法群的原根（PrimitiveRoot）,当时，则10必整除x；此时称10为2在（mod11）（或在乘法群）的秩（Order）,秩,定义：,令G为乘法群，而gG为其中一元素，则元素g的秩（Order）定义为,也可能不存在xN使得，此时定义。若G为有限群，则为G的子群，有，根据Lagrange定理，子群的元素个数必整除母群G的元素个数，故,原根定理,定理：,令g为质数p上的原根，则,（1）若x为整数，则（2）若i、j为整数，则,证明：,子群与循环群,令G为任一乘法群，为任一元素，则为G中的子群（封闭性与反元素的存在性自然成立）。此子群称为由元素g所生成的子群。,定义：子群,定义：循环群（CyclicGroup）,若存在使得，则称G为循环群（CyclicGroup），而g为原根或生成元（Generator）。,二次剩余,3.5二次剩余QuadraticResidue,定义：,同余式,a与n为互质整数,若有整数解，称a为（modn）的二次剩余（QuadraticResidue）若无解则称a为（modn）的非二次剩余（QuadraticNonresidue）。,二次剩余的性质,性质,令p为奇质数，可定义函数,Legendre符号,定义：,令p为质数，定义Legendre符号如下：,定理（Euler判别）,令p为质数，a与p互质。则：,Legendre符号,性质,令p为奇质数，a、b为与p互质的整数，则,（2）,（3）,（4）,（5）,定理QuadraticReciprocity,令p、q为奇质数，则,Jacobi符号,定义：,令a为整数，n0为奇整数，其质因数分解为,定义Jacobi符号：,性质：,当n0为奇整数，Jacobi符号才可能有意义,（5）,（3）,（4）,（2）,（6）,注：a、b为整数，m、n为奇整数,Galois域,3.6Galois域,定义,域（Field）：令K为一集合，并含有两个运算“”及“*”，则（K，*）为域,公理：,（K，*）为交换群，即,（1）（-封闭性）（2）（-单位素）（3）（-反元素）（4）（-结合律）（5）（-交换性）,x=,x,x,y,Galois域,公理：,（1）（*-封闭性）（2）（*-单位素）（3）（*-反元素）（4）（*-结合律）（5）（*-交换性）,公理：,*对有分配律,质数理论,3.7质数理论,定义,令p为不为1的正整数，p为质数（Prime）若某正整数d整除p（记为），则d=1或d=p。,Eratosthenes筛法,质数定理,质数定理,Riemann猜想,Hardy-Littlewood猜想,连分数,3.8连分数,定义,任何以下形式的数均称为连分数,其中，q1、q2、为整数,连分数,性质,令为一实数，其连分数表达式为,其中，,而其各项连分数的收敛值为：,当中满足递推关系及初始条件,连分数,定理：,令（且）为实数x的某项连分数的收敛值,密码安全伪随机数生成器,3.9密码安全伪随机数生成器,BlumBlumShub()dop=RandomPrime();while(p%4!=3);doq=RandomPrime();while(p%4!=3);/p,q为随机质数且=3mod4n=p*q;dos=RandomInteger(1,n);while(gcd(s,n)!=1);/gcd(s,n)=1且s为随机数种子x0=s;for(i=1;i=k;i+)xi=xi-1*xi-1%n;bi=xi,算法,Blum-Blum-Shub伪随机数字生成器,密码安全伪随机数生成器,算法,RSA伪随机数字生成器,RSA_PseudomBitGen()p=RandomPrime();q=RandomPrime();n=p*q;phi=(p-1)*(q