计算数论复习提纲市公开课金奖市赛课一等奖课件

《计算数论》复习提纲第1页第1页整数因子分解(ch1)1.整数唯一分解定理2.欧几里德算法最大公因子求法最大公因子整数线性表示模n逆元一元线性同余方程求法Mersenne素数

Fermat素数第2页第2页同余（ch2）同余，简化了数论中许多问题.同余基本性质剩余类环同余方程求解办法线性同余方程求解高次同余方程求解同余方程组求解办法原根和指数缩系应用第3页第3页二次剩余（ch3）二次剩余概念模为奇素数平方剩余与平方非剩余勒让德符号雅可比符号重点：二次同余方程有解判断与求解第4页第4页连分数(ch5)连分数定义和性质：连分数、简朴连分数概念、性质每一个简朴连分数都是一个实数

实数表示为连分数：任一无理数都可表为无限简朴连分数，有理数连分数表示法

循环连分数：二次代数数都是循环连分数二次方根连分数最佳渐近分数第5页第5页有限域(ch6)有限域GF(pm)结构、构成、运算第6页第6页素性检测(ch8)

拟定性算法试除法利用n-1、n+1因子分解素性检查概率算法Miller-Rabin算法Lehmann算法Solovay-Strassen第7页第7页大整数因子分解算法（ch9）通用整数因子分解办法：理论基础连分数办法（CFRAC），二次筛法（QS）*数域筛法（NFS）专门用途因子分解办法“rho”办法“p-1”办法第8页第8页数论在密码学上应用(ch10)

公钥密码RSA机制Elgamal机制第9页第9页习题第10页第10页习题（续）1.设用户A公开参数为(NA=55，eA=23)，用户B公开参数为(NB=33，eB=13)，用户A应用RSA算法向用户B传送消息m=6时，求A发送带署名保密信息。2.设用户A选取p=11和q=7作为模数为N=pqRSA公钥体制两个素数，选取eA=7作为公开密钥。请给出用户A秘密密钥，并验证3是不是用户A对报文摘要5署名。第11页第11页例2：设素数p>2，则2P-1质因数一定是2pk+1形。

证：设q是2P-1质因数，由于2P-1为奇数，∴q≠2，∴（2，q）=1。由条件q|2P-1,即2P≡1（modq）又∵（q,2）=1，2q-1≡1（modq）设i是使得2x≡1（modp）成立最小正整数，即i是2模p阶。若1<i<p，则有i|p，则与p为素数矛盾，∴i=p,∴p|q-1又∵q-1为偶数，2|q-1,∴2p|q-1,q-1=2pk,即q=2pk+1第12页第12页例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形式数。第13页第13页例5

解同余方程

解：d=(12,30)=6,查表ind2=24,6|24，有解且本题有6个解，

12indx=ind2(30)即indx≡4(mod5)∴indx≡2,7,12,17,22,27(mod30)查模31指标表，∴x≡9,17,8,22,14,23(mod31)第14页第14页例6解同余方程28x≡21(mod35)解：∵（28,35）=7|21，∴原同余方程有解，且有7个解原同余方程等价于4x≡3(mod5)并且4x≡3(mod5)解为x≡2(mod5)∴原同余方程解为2，7，12，17，22，27，31（mod35）第15页第15页例7设p=4n+3是素数，试证当q=2p+1也是素数时，梅素数Mp不是素数证：∵q=8n+7,∴q|Mp，∴Mp