《计算数论复习提纲》由会员分享，可在线阅读，更多相关《计算数论复习提纲（18页珍藏版）》请在装配图网上搜索。
1、计算数论计算数论复习提纲复习提纲 整数的因子分解整数的因子分解(ch1)n1.整数的唯一分解定理n2.欧几里德算法 最大公因子的求法最大公因子的整数线性表示模n的逆元一元线性同余方程的求法nMersenne素数n Fermat素数同余同余（ch2）n同余，简化了数论中的许多问题.n同余的基本性质剩余类环n同余方程的求解方法线性同余方程的求解高次同余方程的求解n同余方程组的求解方法n原根和指数n缩系n应用二次剩余（二次剩余（ch3）n二次剩余的概念二次剩余的概念n模为奇素数的平方剩余与平方非剩余模为奇素数的平方剩余与平方非剩余 n勒让德符号勒让德符号 n雅可比符号雅可比符号重点重点：二次同余方程
2、有解的判断与求解二次同余方程有解的判断与求解连分数连分数(ch5)n连分数的定义和性质连分数的定义和性质：连分数、简单连分数的概念、性质连分数、简单连分数的概念、性质每一个简单连分数都是一个实数每一个简单连分数都是一个实数n 实数表示为连分数实数表示为连分数：任一无理数都可表为无限简单连分数，任一无理数都可表为无限简单连分数，有理数的连分数表示法有理数的连分数表示法n 循环连分数循环连分数：二次代数数都是循环连分数二次代数数都是循环连分数二次方根的连分数二次方根的连分数n 最佳渐近分数最佳渐近分数有限域有限域(ch6)n有限域有限域GF(pm)的结构、组成、运算的结构、组成、运算素性检测素性检
3、测(ch8)n确定性算法确定性算法 试除法试除法利用利用n-1、n+1的因子分解的素性检验的因子分解的素性检验n概率算法概率算法pMiller-Rabin算法算法pLehmann算法算法pSolovay-Strassen大整数因子分解算法（大整数因子分解算法（ch9）n通用整数因子分解方法：理论基础连分数方法（连分数方法（CFRAC），），二次筛法（二次筛法（QS）*数域筛法（数域筛法（NFS）n专门用途的因子分解方法专门用途的因子分解方法“rho”方法方法“p-1”方法方法数论在密码学上的应用数论在密码学上的应用(ch10)n公钥密码公钥密码 RSA机制机制Elgamal机制机制习题习题（续
4、）n1.设用户A的公开参数为(NA=55，eA=23)，用户B的公开参数为(NB=33，eB=13)，用户A应用RSA算法向用户B传送的消息m=6时，求A发送的带签名的保密信息。n2.设用户A选取p=11和q=7作为模数为N=pq的RSA公钥体制的两个素数，选取eA=7作为公开密钥。请给出用户A的秘密密钥，并验证3是不是用户A对报文摘要5的签名。例例2：设素数：设素数p2，则，则2P-1的质因数一定是的质因数一定是2pk+1形。形。证：证：设q是2P-1的质因数，由于2P-1为奇数，q2，（2，q）=1。由条件q|2P-1,即2P1（mod q）又（q,2）=1，2q-11（mod q）设i是
5、使得2x1（mod p）成立最小正整数，即i是2模p的阶。若1ip，则有i|p，则与p为素数矛盾，i=p,p|q-1又 q-1为偶数，2|q-1,2p|q-1,q-1=2pk,即q=2pk+11q1q例例4 设设x为整数，证明形如为整数，证明形如 的整数的所有奇因都的整数的所有奇因都有有4h+1的形式（其中的形式（其中h为整数）为整数）证明：设2n+1是整数 的任一奇素因数，于是有 即 故-1是模2n+1的平方剩余，即 其中2n+1是奇素数。所以 故 ，。所以n是偶数，记n=2h,便有2n+1=4h+1.这样便证明了整数 的所有奇素因数必形如4h+1。又由于两个4h+1形式的数的乘积仍 为4h
6、+1 形式的数，故 形式的数的奇因数必为 4h+1形式的数。12x),(mod12012nx).(mod1212nx.1121n)(mod 4112n)4(mod02 n)(mod 20n12x12x例例5 5 解同余方程解同余方程解：d=(12,30)=6,查表ind2=24,6|24，有解且本题有6个解，12indx=ind2(30)即indx4(mod 5)indx2,7,12,17,22,27(mod 30)查模31指标表，x9,17,8,22,14,23(mod 31)例例6 解同余方程解同余方程28x21(mod 35)n解：（28,35）=7|21，原同余方程有解，且有7个解原同
7、余方程等价于4x3(mod 5)而且4x3(mod 5)解为x2(mod 5)原同余方程解为2，7，12，17，22，27，31（mod 35）例例7 设设p=4n+3是素数，试证当是素数，试证当q=2p+1也是素数时，也是素数时，梅素数梅素数Mp不是素数不是素数证：q=8n+7,q|Mp，Mp不是素数。)(mod12222134qqqn例例9 若若p和和q=4p+1均为奇素数，则均为奇素数，则2是模是模q的一个原根。的一个原根。例例 解同余式解同余式 257(mod64)x 571(mod8)解：因为解：因为 ，所以方程有，所以方程有4 4解。解。2357(mod8)(14)xxt 把把的的解解记记为为，257(mod16)x 代代入入，得得31(mod2)t 34412(58)ttxt 记记，257(mod32)x 再再代代入入，得得40(mod2)t 4552(516)ttxt 记记，257(mod64)x 代代入入，得得51(mod2)t 5612tt6(2132)xt 21,53(mod64).x 即即
计算数论复习提纲
