计算数论复习提纲.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（mod q） 又 （q,2）=1，2q-11（mod q） 设i是使得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+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(mod 5) indx2,7,12,17,22,27(mod 30) 查模31指标表， x9,17,8,22,14,23(mod 31),例6 解同余方程28x21(mod 35),解： （28,35）=7|21， 原同余方程有解，且有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不是