证：设q是2P-1的质因数，由于2P-1为奇数，
∴ q≠2， ∴ （2，q）=1。 由条件q| 2P-1, 即2P≡1（mod q）
又∵ （q,2）=1，2q-1≡1（mod q） 设i是使得2x≡1（mod p）成立最小正整数，即i是
2模p的阶。
若1<i<p，则有i|p，则与p为素数矛盾，∴ i=p,
17
THANKS
FOR WATCHING
演讲人: XXX
PPT文档·教学课件
谢谢大家！本文档为精心编制而成，您可以在下载后自由修改和打印，希望下载对您有帮助！
2020/10/16
14
例6 解同余方程28x≡21(mod 35)
解：∵ （28,35）=7|21， ∴ 原同余方程有解，且有7个解 原同余方程等价于4x≡3(mod 5) 而且4x≡3(mod 5)解为x≡2(mod 5) ∴ 原同余方程解为2，7，12，17，22，27，
31（mod 35）
2020/10/16
15
例7 设p=4n+3是素数，试证当q=2p+1也是素数时， 梅素数Mp不是素数
证：∵ q=8n+7,
24n32q2 1q 21(mqo ) d
∴ q |Mp，∴ Mp不是素数。
2020/10/16
16
例9 若p和q=4p+1均为奇素数，则2是模q的一个原根。
2020/10/16
4
连分数(ch5)
连分数的定义和性质：
连分数、简单连分数的概念、性质 每一个简单连分数都是一个实数
实数表示为连分数：
任一无理数都可表为无限简单连分数， 有理数的连分数表示法
循环连分数：
二次代数数都是循环连分数 二次方根的连分数
最佳渐近分数
2020/10/16
5
有限域(ch6)
故-1是模2n+1的平方剩余，即 1 1. 2n 1
其中2n+1是奇素数。所以 2n11(mo 4)d
故 2n0(mo4，)d n0(m 。 o2d )
所以n是偶数，记n=2h,便有2n+1=4h+1.这样便证明了整数 的所有奇素因数必形如4h+1。又由于两个4h+1形式的数的乘积仍
2020/10/16
有限域 GF(pm)的结构、组成、运算
2020/10/16
6
素性检测(ch8)
确定性算法
试除法 利用n-1、n+1的因子分解的素性检验
概率算法
Miller-Rabin算法 Lehmann算法 Solovay-Strassen
2020/10/16
7
大整数因子分解算法（ch9）
通用整数因子分解方法：理论基础
为4h+1 形式的数，故 x2 1形式的数的奇因数必为
4h+1形式的数。
13
例5 解同余方程
解：d=(12,30)=6, 查表ind2=24, 6|24，有解且本题有6个解，
12indx=ind2(30) 即indx≡4(mod 5) ∴ indx≡2,7,12,17,22,27(mod 30) 查模31指标表， ∴ x≡9,17,8,22,14,23(mod 31)
送的消息m=6时，求A发送的带签名的保密信息。 2.设用户A选取p=11和q=7作为模数为N=pq的RSA公钥体
制的两个素数，选取eA=7作为公开密钥。请给出用户A的 秘密密钥，并验证3是不是用户A对报文摘要5的签名。
2020/10/16
11
q 1
例2：设素数p>2，则2P-1的质因数一定是 2pk+1形。
剩余类环
同余方程的求解方法
线性同余方程的求解 高次同余方程的求解
同余方程组的求解方法 原根和指数 缩系 应用
2020/10/16
3
二次剩余（ch3）
二次剩余的概念 模为奇素数的平方剩余与平方非剩余 勒让德符号 雅可比符号 重点：二次同余方程有解的判断与求解
2020/10/16
连分数方法（CFRAC）， 二次筛法（QS） *数域筛法（NFS）
专门用途的因子分解方法
“rho”方法 “p-1”方法
2020/10/16பைடு நூலகம்
8
数论在密码学上的应用(ch10)
公钥密码
RSA机制 Elgamal机制
2020/10/16
9
习题
2020/10/16
10
习题（续）
1.设用户A的公开参数为(NA=55，eA=23)，用户B的公开 参数为(NB=33，eB=13)，用户A应用RSA算法向用户B传
《》复习提纲
2020/10/16
1
整数的因子分解(ch1)
1.整数的唯一分解定理 2.欧几里德算法
最大公因子的求法 最大公因子的整数线性表示 模n的逆元 一元线性同余方程的求法
Mersenne素数 Fermat素数
2020/10/16
2
同余 （ch2）
同余，简化了数论中的许多问题. 同余的基本性质
∴ p|q-1 又∵ q-1为偶数，2|q-1, ∴ 2p|q-1,q-1=2pk,即q=2pk+1
2020/10/16
12
例4 设x为整数，证明形如x2 1的整数的所有奇因都 有4h+1的形式（其中h为整数）
证明：设2n+1是整数x2 1的任一奇素因数，于是有
x210(m2o n d 1),即 x21(m2o n d1).
