《计算数论》复习提纲.ppt

计算数论复习提纲,整数的因子分解(ch1),1.整数的唯一分解定理2.欧几里德算法最大公因子的求法最大公因子的整数线性表示模n的逆元一元线性同余方程的求法Mersenne素数Fermat素数,同余（ch2）,同余，简化了数论中的许多问题.同余的基本性质剩余类环同余方程的求解方法线性同余方程的求解高次同余方程的求解同余方程组的求解方法原根和指数缩系应用,二次剩余（ch3）,二次剩余的概念模为奇素数的平方剩余与平方非剩余勒让德符号雅可比符号重点：二次同余方程有解的判断与求解,连分数(ch5),连分数的定义和性质：连分数、简单连分数的概念、性质每一个简单连分数都是一个实数实数表示为连分数：任一无理数都可表为无限简单连分数，有理数的连分数表示法循环连分数：二次代数数都是循环连分数二次方根的连分数最佳渐近分数,有限域(ch6),有限域GF(pm)的结构、组成、运算,素性检测(ch8),确定性算法试除法利用n-1、n+1的因子分解的素性检验概率算法Miller-Rabin算法Lehmann算法Solovay-Strassen,大整数因子分解算法（ch9）,通用整数因子分解方法：理论基础连分数方法（CFRAC），二次筛法（QS）*数域筛法（NFS）专门用途的因子分解方法“rho”方法“p-1”方法,数论在密码学上的应用(ch10),公钥密码RSA机制Elgamal机制,习题,习题（续）,1.设用户A的公开参数为(NA=55，eA=23)，用户B的公开参数为(NB=33，eB=13)，用户A应用RSA算法向用户B传送的消息m=6时，求A发送的带签名的保密信息。2.设用户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（modq）又（q,2）=1，2q-11（modq）设i是使得2x1（modp）成立最小正整数，即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+1,例4设x为整数，证明形如的整数的所有奇因都有4h+1的形式（其中h为整数）,证明：设2n+1是整数的任一奇素因数，于是有即故-1是模2n+1的平方剩余，即其中2n+1是奇素数。所以故，。所以n是偶数，记n=2h,便有2n+1=4h+1.这样便证明了整数的所有奇素因数必形如4h+1。又由于两个4h+1形式的数的乘积仍为4h+1形式的数，故形式的数的奇因数必为4h+1形式的数。,例5解同余方程,解：d=(12,30)=6,查表ind2=24,6|24，有解且本题有6个解，12indx=ind2(30)即indx4(mod5)indx2,7,12,17,22,27(mod30)查模31指标表，x9,17,8,22,14,23(mod31),例6解同余方程28x21(mod35),解：（28,35）=7|21，原同余方程有解，且有7个解原同余方程等价于4x3(mod5)而且4x3(mod5)解为x2(mod5)原同余方程解为2，7，12，17，22，27，31（mod35）,例7设p=4n+3是素数，试证当q=2p+1也是素数时，梅素数Mp不