PPTOK :您身边最贴心好用的PPT站!

您当前所在位置:首页?>?PPT课件?>?学校ppt?>?高校大学PPT → 信息安全数学基础ppt素材

信息安全数学基础ppt素材

  • 素材大小:1.06 MB
  • 素材授权:免费下载
  • 更新时间:2017-01-22
  • 素材类别:高校大学PPT
  • 素材格式:.ppt
  • 关键提要:工学
  • 素材版本:PowerPoint2003及以上版本(.ppt)
网友评分:
PPT介绍优秀PPT相关PPT精品PPT

这是一个关于信息安全数学基础ppt素材,主要介绍二次剩余的概念、勒让德符号、高斯二次互反律、雅可比符号、二次同余式的解法和解数。欢迎点击下载哦。

PPT预览

信息安全数学基础ppt素材

PPT内容

第3章 二次剩余
第3章 二次剩余
我们来考虑这样一个问题:什么时候整数a可以表示为某个整数x的平方对素数p取模之后的结果呢?
数学家欧拉、勒让德和高斯对这个问题以及相关工作进行了大量的研究。本章我们就来介绍这些研究成果。
第3章 二次剩余
二次剩余的概念
勒让德符号
高斯二次互反律
雅可比符号
二次同余式的解法和解数
3.1 二次剩余的概念
设p是一个奇素数,整数a与p相对互素。本节我们将主要解决这样一个问题:整数a在什么条件下可以表示为某整数x的平方对素数p取模之后的结果。
3.1 二次剩余的概念
二次剩余的定义
定义3.1.1:设整数a与正整数m互素,
若同余式x2?a (mod m)有解,则称a为模m的二次剩余;
若同余式x2?a (mod m)无解,则称a为模m的二次非剩余。
3.1 二次剩余的概念
二次剩余的定义
例3.1.1:确定哪些整数是模10的二次剩余。
解:首先由于对任意的整数n,由带余数除法,存在唯一的整数k与n1,使得
??????????????????? n=10k+n1,其中0≤n1<10
则?????????????? n2=100k2+20k·n1+n12
于是?????????? n2≡n12 (mod 10),0≤n1<10
因而为了确定哪些整数是模10的二次剩余,只需要关注整数1,2,3,…,9的平方。
3.1 二次剩余的概念
二次剩余的定义
首先为了确定哪些整数是模10的二次剩余,只需要关注整数1,2,3,…,9的平方。而
?????????????????????????? 12≡92≡1 (mod 10)
?????????????????????????? 22≡82≡4 (mod 10)
?????????????????????????? 32≡72≡9 (mod 10)
?????????????????????????? 42≡62≡6 (mod 10)
?????????????????????????? 52≡5 (mod 10)
同时,由于在整数1,4,5,6,9中与10互素的整数只有1和9,因而只有1和9是模10的二次剩余,而整数2,3,7,8中与10互素的整数只有3和7,因而只有3和7是模10的二次非剩余。
3.1 二次剩余的概念
二次剩余的定义
例3.1.2:确定哪些整数是模11的二次剩余。
解:只需要关注整数1,2,3,…,10的平方。而
??????????????????????????? 12≡102≡1 (mod 11)
??????????????????????????? 22≡92≡4 (mod 11)
??????????????????????????? 32≡82≡9 (mod 11)
??????????????????????????? 42≡72≡5 (mod 11)
??????????????????????????? 52≡62≡3 (mod 11)
同时由于整数1,2,3,…,10均与11互素,因而整数1,3,4,5,9是模11的二次剩余,而整数2,6,7,8,10是模11的二次非剩余。
3.1 二次剩余的概念
二次剩余的定义
例3.1.3:确定哪些整数是模13的二次剩余。
解:类似于例3.1.1的讨论,这里我们只需要关注整数1,2,3,…,12的平方。而
??????????????????????????? 12≡122≡1 (mod 13)
??????????????????????????? 22≡112≡4 (mod 13)
??????????????????????????? 32≡102≡9 (mod 13)
??????????????????????????? 42≡92≡3 (mod 13)
??????????????????????????? 52≡82≡12 (mod 13)
??????????????????????????? 62≡72≡10 (mod 13)
同时由于整数1,2,3,…,12均与13互素,因而整数1,3,4,9,10,12是模13的二次剩余,而整数2,5,6,7,8,11是模13的二次非剩余。
3.1 二次剩余的概念
二次剩余的定义
由例3.1.2和例3.1.3我们看到,模奇素数11与13的二次剩余与二次非剩余的个数相同。
一般地,我们有如下定理:
3.1 二次剩余的概念
二次剩余的性质
引理3.1.1:设p是奇素数,a是整数,且p?a,则同余式
x2≡a (mod p)
或者没有解或者恰有两个模p不同余的解。
证明:若同余式
x2≡a (mod p)
有一个解x=x0,则由于
(-x0)2=x02≡a (mod p)
因而可以同时找到同余式的另一个解x=-x0
3.1 二次剩余的概念
二次剩余的性质
用反证法来证明解x=-x0与x=x0不同余,假设
x0≡-x0 (mod p),即2x0≡0 (mod p)
此时由
x02≡a (mod p)
得到
p|(x02-a)
又p?a,因而p?x0;又p是奇数,进而
p?2x0
这与2x0≡0 (mod p)矛盾。
3.1 二次剩余的概念
二次剩余的性质
接下来证明同余式x2≡a (mod p)模p不同余的解不多于两个。假设x=x0与x=x1都是同余式x2≡a (mod p)的解,则
x02≡x12≡a (mod p)
即?????????????????
x02-x12=(x0+x1)(x0-x1)≡0 (mod p)
因为p是素数,因而
??????????????????????????? p|(x0+x1)或者p|(x0-x1)
即?????????????????? x0≡x1 (mod p)或x0≡-x1 (mod p)
综上,若同余式x2≡a (mod p)有解,则恰有两个模p不同余的解。结论得证。
3.1 二次剩余的概念
二次剩余的性质
定理3.1.1:若p是奇素数,则在整数1,2,…,p-1中恰有(p-1)/2个模p的二次剩余,(p-1)/2个模p的二次非剩余。
证明:为在整数1,2,…,p-1中找出p的所有二次剩余,我们计算这些整数平方的模p的最小剩余。
因为要考虑p-1个平方,且同余方程x2≡a (mod p)或者没有解,或者有两个解,所以在1,2,…,p-1中,p的二次剩余恰有(p-1)/2个,剩下的p-1-(p-1)/2=(p-1)/2个小于p-1的整数是模p的二次非剩余。
3.2 勒让德符号
本节我们首先给出一个用于确定给定的整数是否为模奇数p的二次剩余的记号——勒让德(Legendre)符号。随后将描述并证明两个重要的判别法:欧拉判别法与高斯引理,其中欧拉判别法可以用于确定给定的整数a是否为模奇素数p的二次剩余,而高斯引理则可以用于确定-1和2是否为模p的二次剩余。
3.2 勒让德符号
勒让德符号的定义
欧拉判别法
高斯引理
3.2 勒让德符号
勒让德符号的定义
定义3.2.1:设p是奇素数,a是整数,且p?a,则
勒让德(Legendre)符号定义为
3.2 勒让德符号
勒让德符号的定义
例3.2.1:由例3.1.3知道,勒让德符号
的值如下
3.2 勒让德符号
欧拉判别法
接下来我们给出用于判断一个整数是否为模素数p的二次剩余的判别法:欧拉判别法。
3.2 勒让德符号
欧拉判别法
定理3.2.1(欧拉判别法):设p是奇素数,a是整数,且
p?a,则
证明:由于勒让德符号的取值只有±1,因而下面我们可以分两种情形来讨论。
3.2 勒让德符号
欧拉判别法
首先,若
则a是模p的二次剩余,即同余式
x2≡a (mod p)
有解,设其解为x=x0,即
x02≡a (mod p)
由费马小定理,有
3.2 勒让德符号
欧拉判别法
因而若

3.2 勒让德符号
欧拉判别法
其次,若
则a是模p的二次非剩余,即同余式
x2≡a (mod p)
无解。
又对每一个与p互素的整数i,线性同余式
ix≡a (mod p)
都存在一个整数解j,即
ij≡a (mod p)
3.2 勒让德符号
欧拉判别法
而同余式x2≡a (mod p)无解,则线性同余式ij≡a (mod p)中 i≠j,进而可以将1,2,…,p-1中的整数划分成(p-1)/2对,使得每对的乘积为a,将所有这些整数对乘在一起,得到
(p-1)!≡a(p-1)/2 (mod p)
由威尔逊定理,有
-1≡a(p-1)/2 (mod p)
3.2 勒让德符号
欧拉判别法
因而若
同样有
综上,结论成立。
3.2 勒让德符号
欧拉判别法
例3.2.2:设p=13,a=132,由于
132(13-1)/2=1326 (mod 13) ≡ 26≡-1 (mod 13)
由欧拉判别法有
因而132是模13的二次非剩余。
3.2 勒让德符号
欧拉判别法
利用这个判别法可以证明勒让德符号的许多重要性质。
3.2 勒让德符号
欧拉判别法
定理3.2.2:设p是奇素数,a,b是整数,p?a且p?b,则
(i) 若a≡b (mod p),则
(ii)
(iii)
3.2 勒让德符号
欧拉判别法
证明:
(i) 若
a≡b (mod p)
则同余式
x2≡a (mod p)
有解当且仅当同余式
x2≡b (mod p)
有解,因而
3.2 勒让德符号
欧拉判别法
(ii) 由欧拉判别法

因而
由于勒让德符号的值只有±1,因而结论成立。
3.2 勒让德符号
欧拉判别法
(iii) 由于
由(ii)的结果得到
3.2 勒让德符号
欧拉判别法
由定理3.2.2的(ii)知:
一个素数的两个二次剩余或两个二次非剩余的乘积是一个二次剩余,而一个素数的一个二次剩余与一个二次非剩余的乘积是一个二次非剩余。
任意给定正整数n的素分解式????????????????????????? ,由定理3.2.2可知要确定勒让德符号????? 的值,只需确定勒让德符号??????????????????????????? (其中q是一奇素数)的值。
3.2 勒让德符号
欧拉判别法
利用欧拉判别法我们首先可以立即得到如下结论:
3.2 勒让德符号
欧拉判别法
定理3.2.3:设p是奇素数,则
证明:由欧拉判别法,
由于p是奇素数,故对模数4而言,p只能取p=4k+1与p=4k+3,其中k为整数。
3.2 勒让德符号
欧拉判别法
若p=4k+1,即p≡1 (mod 4),则(-1)(p-1)/2=(-1)2k=1,因而此时
若p=4k+3,即p≡3 (mod 4),则(-1)(p-1)/2=(-1)2k+1=-1,因而此时
3.2 勒让德符号
高斯引理
下面我们不加证明地给出用于确定与奇素数p互素的整数n是否为模p的二次剩余的另外一个判别标准:高斯引理。
3.2 勒让德符号
高斯引理
定理3.2.4(高斯引理):令奇素数p不整除整数n,同时设在(p-1)/2个数n, 2n,…, (p-1)n/2对p取模得到的最小正剩余中有m个大于p/2,则
3.2 勒让德符号
高斯引理
例3.2.3:p=13,n=63,则63,126,189,252,315,378对13取模的最小剩余11,9,4,5,3,1中有两个大于13/2,即m=2,进而由高斯引理有
3.2 勒让德符号
高斯引理
例3.2.4:p=17,n=10,则10,20,30,40,50,60,70,80对17取模的最小剩余10,3,13,6,16,9,2,12中有5个大于17/2,即m=5,进而由高斯引理有
3.2 勒让德符号
高斯引理
定理3.2.5:若p是奇素数,则
因而,若???????????????????????
p≡±1 (mod 8)
则2为模p的二次剩余;

p≡±3 (mod 8)
则2为模p的二次非剩余。
3.2 勒让德符号
高斯引理
证明:由于p是奇素数,可令
p=8a+r,r=1,3,5,7
接下来计算(p-1)/2个整数2, 2×2,…, (p-1)×2/2对p取模得到的最小正剩余中大于p/2的个数m,由于这(p-1)/2个整数已经在0和p之间,因而m的值是满足不等式
p/2<2k<>
的k的个数,即
p/4<>


所以
3.2 勒让德符号
高斯引理
m=[p/2]-[p/4]=[(8a+r)/2]-[(8a+r)]/4]=2a+[r/2]-[r/4]
当r分别取1,3,5,7时,m≡0, 1, 1, 0 (mod 2)。
故当p=8a+1或p=8a+7,即
时,2为模p的二次剩余;
而当p=8a+3或p=8a+5,即
时,2为模p的二次非剩余。
3.2 勒让德符号
高斯引理
例3.2.5:由于
???????????????????? 3≡3? (mod 8),? 5≡-3 (mod 8)
???????????????????? 7≡-1 (mod 8),11≡3? (mod 8)
?????????????????? 13≡-3 (mod 8),17≡1? (mod 8)
?????????????????? 19≡3? (mod 8),23≡-1 (mod 8)
?????????????????? 29≡-3 (mod 8),31≡-1 (mod 8)
因而

3.2 勒让德符号
高斯引理
例3.2.6:计算????????? 以及????????? 。
解:由242≡4 (mod 7),得到
由例3.2.5知
由289≡-10 (mod 13),得到
由 13≡1 (mod 4),得到
3.2 勒让德符号
高斯引理
而由13≡-3 (mod 8),因而
又由例3.2.1知?????????????? ,因而
3.3 高斯二次互反律
背景
假设p,q是两个不同的奇素数,且q是p的二次剩余,那么p是否也为q的二次剩余?
欧拉(Euler)在18世纪中叶给出了这个问题的答案,但他也只是给出了这个问题的经验性结论,没有能从理论上加以证明。
1785年勒让德以二次互反律的形式重新陈述了这个问题。由此定律一旦知道同余式x2≡q (mod p)是否有解就可以确定同余式x2≡p (mod q)是否有解,从而在实际上解决了二次剩余的判别问题。
1796年高斯首次给出了这个定律的严格证明。随后他又发现了另外七个不同的证明。高斯把二次互反律誉为算术理论中的宝石,是一个黄金定律。
3.3 高斯二次互反律
高斯二次互反律
定理3.3.1(高斯二次互反律):设p,q是两个不同的奇素数,则
注意:
当p≡1 (mod 4)时,(p-1)/2是偶数;
当p≡3 (mod 4)时,(p-1)/2是奇数。
即若p≡1 (mod 4)或q≡1 (mod 4),则(p-1)/2×(q-1)/2是偶数,
而若p≡q≡3 (mod 4),则(p-1)/2×(q-1)/2是奇数,因而
3.3 高斯二次互反律
高斯二次互反律
由于???????? 与????????? 的可能取值只有1和-1,因而
3.3 高斯二次互反律
高斯二次互反律
这表明若p与q都是奇素数,则若p≡q≡3 (mod 4),
否则,
3.3 高斯二次互反律
高斯二次互反律
例3.3.1:设p=29,q=37,即p≡q≡1 (mod 4),则由二次互反定律有
因而,

3.3 高斯二次互反律
高斯二次互反律
例3.3.2:设p=7,q=23,即p≡q≡3 (mod 4),则由二次互反定律有

由例3.2.5我们知道
因而
3.3 高斯二次互反律
高斯二次互反律
例3.3.3:设p=13,q=19,即
p≡1 (mod 4),q≡3 (mod 4)
则由二次互反定律有
而由例3.2.1
因而
3.4 雅可比符号
雅可比符号的定义
雅可比符号的性质
雅可比符号的计算方法
3.4 雅可比符号
雅可比(Jacobi)符号是勒让德符号的推广,用于勒让德符号的估值以及定义一类伪素数。
定义:令b是一个正整数,若n是一个合数且
bn≡b (mod n)
则n称为以b为基底的伪素数。
3.4 雅可比符号
雅可比符号的定义
定义3.4.1:设奇数n有素分解
又设整数a与n相对互素,则雅可比符号定义为
等式右边的符号都是勒让德符号。
3.4 雅可比符号
雅可比符号的定义
注:
对符号???????? 而言,如果
1)n是奇素数,且a与n相对互素,则其为勒让德符号;
2)n是奇数,且a与n相对互素,则其为雅可比符号。
因为奇素数也是奇数,因此,雅可比符号是勒让德符号的推广。
3.4 雅可比符号
雅可比符号的定义
例3.4.1:由雅可比符号的定义,有

3.4 雅可比符号
雅可比符号的性质
定理3.4.1:设n为合数,若同余式x2≡a (mod n)有解,则
必有
证明:
若p是n的素因子,且x2≡a (mod n)有解,则同余式x2≡a (mod p)也有解,因而
3.4 雅可比符号
雅可比符号的性质
进而若n有素分解

注:
到当同余式x2≡a (mod n)无解时,仍然有可能有
3.4 雅可比符号
雅可比符号的性质
例3.4.2:设a=2,n=65,注意到同余式
??????????????????????????????????? x2≡2 (mod 13)

??????????????????????????????????? x2≡2 (mod 5)
均无解,故同余式
??????????????????????????????????? x2≡2 (mod 65)
也无解,但
3.4 雅可比符号
雅可比符号的性质
定理3.4.2:设奇数n是正整数,且整数a,b均与n互素,则
3.4 雅可比符号
雅可比符号的性质
证明:
(i) 设奇数n的素分解式为
若素数p整除n,则由a≡b (mod n),得到a≡b (mod p),因而
进而
3.4 雅可比符号
雅可比符号的性质
3.4 雅可比符号
雅可比符号的性质
3.4 雅可比符号
雅可比符号的性质
而pi-1是偶数,因而结合
的二项展开式得到

3.4 雅可比符号
雅可比符号的性质

以此为基础,利用数学归纳法即可得到

3.4 雅可比符号
雅可比符号的性质
3.4 雅可比符号
雅可比符号的性质
(iv) 若p是素数,则
因而
3.4 雅可比符号
雅可比符号的性质

3.4 雅可比符号
雅可比符号的性质



以此为基础,利用数学归纳法即可得到
3.4 雅可比符号
雅可比符号的性质
这表明
将上述(n2-1)/8的同余式与??????? 的表达式相结合,得到
3.4 雅可比符号
雅可比符号的性质
定理3.4.3(雅可比符号的二次互反律):设奇数n与m互素,则
证明:
设m与n的素分解式分别为
3.4 雅可比符号
雅可比符号的性质


因而
3.4 雅可比符号
雅可比符号的性质
由高斯二次互反律
因而
3.4 雅可比符号
雅可比符号的性质
由雅可比符号的性质定理3.4.2的证明过程,得到
因而
进而
3.4 雅可比符号
雅可比符号的计算方法
首先设正整数a与b互素且a>b,R0=a,R1=b,利用算术基本定理并将余数中2的最高次幂分解出来,得到
其中s1是非负整数,奇数R2是小于R1的正整数。若连续使用算术基本定理并将余数中2的最高次幂分解出来,将得到下列等式
其中sj是非负整数,奇数Rj<>
3.4 雅可比符号
雅可比符号的计算方法
下面利用所给出的n-1个等式并结合雅可比符号的性质,介绍一个计算雅可比符号的算法。
3.4 雅可比符号
雅可比符号的计算方法
定理3.4.4:设a与b是正整数且a>b,则
其中sj与Rj如上定义。
3.4 雅可比符号
雅可比符号的计算方法
证明:由上述第一个方程以及雅可比符号的性质,得到
由雅可比符号的二次互反定律,得到
因而
3.4 雅可比符号
雅可比符号的计算方法
例3.4.3:计算???????????? 的值。
解:首先
???????????????????????? 327=89?3+22?15
?????????????????????????? 89=15?5+2?7
?????????????????????????? 15=7?2+20?1
由于327>89,因而由定理3.4.4,得到
3.5 二次同余式的解法和解数
二次同余的解法
二次同余的解数
3.5 二次同余式的解法和解数
二次同余的解法
由勒让德符号的性质,当
且p不太大时,可将x=1, 2, …, (p-1)/2直接代入该二次同余式进行求解。
但是当p很大时,求出此二次同余式的解并不容易。
然而若p≡3 (mod 4)或p≡5 (mod 8),有以下结论
3.5 二次同余式的解法和解数
二次同余的解法
定理3.5.1:设勒让德符号????????????? 则
(i) 当p≡3 (mod 4)时
为二次同余式x2≡n (mod p)的解;
(ii) 当p≡5 (mod 8) 时,若

3.5 二次同余式的解法和解数
二次同余的解法
为二次同余式x2≡n (mod p)的解;


为二次同余式x2≡n (mod p)的解。
3.5 二次同余式的解法和解数
二次同余的解法
证明:
欧拉判别法,若

那么
3.5 二次同余式的解法和解数
二次同余的解法
(i) 由
得到
那么当(p+1)/2为偶数,即p≡3 (mod 4)时,
即此时
为二次同余式x2≡n (mod p)的解。
3.5 二次同余式的解法和解数
二次同余的解法
(ii)首先由威尔逊定理
因而

3.5 二次同余式的解法和解数
二次同余的解法
3.5 二次同余式的解法和解数
二次同余的解法
例3.5.1:设p=11,n=20,则

p≡3 (mod 4)
因而±20(11+1)/4=±203是二次同余式
x2≡20 (mod 11)
的解。
3.5 二次同余式的解法和解数
二次同余的解法
例3.5.2 设p=61,n=327,则
又p≡5 (mod8),且
因而±(61-1)/2! ·327(61+3)/8=±30!3278是二次同余式x2≡327 (mod 61)的解。
3.5 二次同余式的解法和解数
二次同余的解法
定理3.5.2:设p≡1 (mod 8),???????????????????????? ,则
二次同余式x2≡n (mod p)有解??????????????? ,其中h满足p=2kh+1,2?h,sk≥0是某个整数。
证明:由p≡1 (mod 8),可设p=2kh+1,2?h,k≥3。由于
因而由欧拉判别法,
3.5 二次同余式的解法和解数
二次同余的解法
因此

故有非负整数s2=hf(f=0或1)使得
于是下面两个同余式有且只有一个成立
3.5 二次同余式的解法和解数
二次同余的解法
故又有非负的s3=s2+2hf1(f1=0或1)使得
k是有限整数,故必有非负的sk使得


3.5 二次同余式的解法和解数
二次同余的解数
引理 3.5.1:设f(x)为整系数多项式
?????????????????? f(x)=anxn+an-1xn-1+…+a1x+a0
则f(x)的一阶导数
????????????????? f(x)’=nanxn-1+(n-1)an-1xn-2+…+2a2x+a1

???????????????????? f(x)≡0 (mod p)与f(x)’≡0 (mod p)
无公解,则f(x)≡0 (mod pl)的解数等于f(x)≡0 (mod p)的解数。
3.5 二次同余式的解法和解数
二次同余的解数
证明:当l=1时,显然成立。
令x1是f(x)≡0 (mod pl-1)的解,则
f(x1+pl-1y)=an(x1+pl-1y)n+an-1(x1+pl-1y)n-1+…+a1(x1+pl-1y)+a0由于
?????????????? (x+pl-1y)i≡xi+ipl-1yxi-1 (mod pl),i=1,2,…,n
因而
f(x1+pl-1y)≡an(x1n+npl-1yx1n-1)
?????????????????? +an-1(x1n-1+(n-1)pl-1yx1n-2)+…+a1(x1+pl-1y)+a0
?????????????? ≡anx1n+an-1x1n-1+…+a1x1+a0
??????????????????????????? +annpl-1yx1n-1+an-1(n-1)pl-1yx1n-2+a1pl-1y
?????????????? ≡f(x1)+pl-1yf(x)’ (mod pl)
3.5 二次同余式的解法和解数
二次同余的解数
但由于f(x)≡0 (mod p)与f(x)’≡0 (mod p)无公解,因而
p?f(x1)’,故存在唯一的y使得
f(x1+pl-1y)≡0 (mod pl)
因而若f(x)≡0 (mod pl-1)有解,则f(x)≡0 (mod pl)存在唯一解,由归纳假设知结论成立。
3.5 二次同余式的解法和解数
二次同余的解数
定理 3.5.3:设p为素数,l>0,且p?n。
若p为奇素数,则二次同余式x2≡n (mod pl),有
个解。
在p=2时,二次同余式x2≡n (mod pl),l>0,的解数有下面三种情形:
a) l=1,有一个解;
b) l=2,当n≡1 (mod 4)时,有二个解;当n≡3 (mod 4)时,无解;
c) l>2,当n≡1 (mod 8)时,有四个解;当n?1 (mod 8)时,无解。
3.5 二次同余式的解法和解数
二次同余的解数
证明:若p为奇素数,则
当l=1时,二次同余式x2≡n (mod p)或者没有解或者恰有两个模p不同余的解,因而结论成立。
当l>1时,令f(x)=x2-n,则f(x)/=2x,则由于f(x)=x2-n≡0 (mod p)与f(x)/=2x≡0 (mod p)无公解,
因而f(x)≡0(mod pl)与f(x)≡0(mod p)有相同的解数,即
x2≡n (mod pl)与x2≡n (mod p),有相同的解数。
因而p为奇素数时,结论成立。
3.5 二次同余式的解法和解数
二次同余的解数
在p=2时,
a) l=1,则由2?n,知n≡1(mod2),故显然此时二次同余式x2≡n (mod 2)只有唯一解x≡1 (mod 2)。
b) l=2,容易验证x2≡1 (mod 4)时,有二个解x≡1 (mod4)和x≡-1 (mod 4);而x2≡3 (mod 4)时,无解。
c) l>2时,由2?n,知n为奇数,故若二次同余式x2≡n (mod 2l)有解,则其解必为奇数(若x为偶数2k,则n=4k 2-r·2l为偶数,矛盾),设解x为2k+1,则
(2k+1)2=4k(k+1)+1=8·(k(k+1)/2)+1≡1 (mod8)
3.5 二次同余式的解法和解数
二次同余的解数
(2k+1)2=4k(k+1)+1=8·(k(k+1)/2)+1≡1 (mod8)
即二次同余式x2≡n(mod2l)若有解,则必定有
n≡1 (mod8)
因而若n?1(mod8),则二次同余式x2≡n (mod pl)无解。
下面讨论n≡1 (mod8)时的情形:
1) 容易验证当l=3时,二次同余式x2≡n (mod 2l)有四个解:1,3,5,7。
2) 我们用数学归纳法来证明当l>3时,二次同余式x2≡n (mod pl)有四个解:
3.5 二次同余式的解法和解数
二次同余的解数
设a满足a2≡n (mod pl-1),则由于2?n,知n为奇数,故2?a,即a为奇数,设为a=2k+1,则
????????? (a+2l-2b)2=a2+ab2l-1+22(l-2)b2
???????????????????????? =a2+(2k+1)·b2l-1+22(l-2)b2
???????????????????????? =a2+k·b2l+b2l-1+22(l-2)b2
???????????????????????? ≡a2+b2l-1(mod 2l)

由上式知道a+2l-2b就满足二次同余式x2≡n (mod 2l),故二次同余式x2≡n (mod 2l)必定有解存在。
3.5 二次同余式的解法和解数
二次同余的解数
现设x1是二次同余式x2≡n (mod 2l)的一个解,x2是二次同余式x2≡n (mod 2l)的任一解,则容易验证x1,-x1,x1+2l-1,-x1+2l-1是二次同余式x2≡n (mod 2l)的四个不同余的解。
下证x2与x1,-x1,x1+2l-1,-x1+2l-1之一模2l同余。
首先由于x1与x2都是二次同余式x2≡n (mod 2l)的解,因而
(x2-x1)(x2+x1)≡0 (mod 2l)
又二次同余式x2≡n (mod 2l)的解必定为奇数,即x1与x2均为奇数,于是x2-x1与x2+x1都是偶数,故上式给出
(x2-x1)/2×(x2+x1)/2≡0 (mod 2l-2)
3.5 二次同余式的解法和解数
二次同余的解数
但(x2-x1)/2与(x2+x1)/2不能同时为奇数或偶数,否则其和x2或其差x1不会为奇数,因而(x2-x1)/2与(x2+x1)/2一奇一偶,进而
(x2-x1)/2≡0(mod2l-2)或(x2+x1)/2≡0(mod2l-2)。

x2=x1+k2l-1或x2= -x1+k2l-1
若k为奇数,即k=2d+1,则
x2=x1+(2d+1)2l-1或x2= -x1+(2d+1)2l-1
即x2与x1+2l-1或-x1+2l-1模2l同余;故x2=x1+k2l-1或x2= -x1+k2l-1。
3.5 二次同余式的解法和解数
二次同余的解数
若k为偶数,即k=2d,则
x2=x1+2d·2l-1或x2= -x1+2d·2l-1
即x2与x1或-x1模2l同余。
即无论哪一种情形,x2与x1,-x1,x1+2l-1,-x1+2l-1之一模2l同余。
这就证明了l≥3时,x2≡n (mod 2l)有四个解。

相关PPT

通信工程防护基本课程之设备环境防护案例ppt课件:这是一个关于通信工程防护基本课程之设备环境防护案例ppt课件,主要介绍通信设备防护的大致分类、了解通信设备运行环境的基本要求、掌握基本的防护原理、掌握常见问题的分析及处理方法。欢迎点击下载哦。
《通信工程概预算》课件ppt:这是一个关于《通信工程概预算》课件ppt,主要介绍通信工程概述 、通信建设工程与定额、通信建设工程费用定额、通信建设工程工程量计算、通信工程概预算的编制。欢迎点击下载哦。
《材料物理化学课件介绍》ppt:这是一个关于《材料物理化学课件介绍》ppt,主要介绍相与相平衡、相图、相变、晶体的成核和生长机理。欢迎点击下载哦。
《信息安全数学基础ppt素材》是由用户BROWN(= 0 =于2017-01-22上传,属于高校大学PPT。

标签:

优秀PPT

缩略图

  • 信息安全数学基础ppt素材

下载地址

  • 信息安全数学基础ppt素材

相关PPT

推荐

颜色分类黑色PPT亚博体育app在线下载橙色PPT亚博体育app在线下载紫色PPT亚博体育app在线下载蓝色PPT亚博体育app在线下载黄色PPT亚博体育app在线下载红色PPT亚博体育app在线下载绿色PPT亚博体育app在线下载彩色PPT亚博体育app在线下载黑白PPT亚博体育app在线下载

行业分类科技PPT亚博体育app在线下载医学PPT亚博体育app在线下载教育PPT亚博体育app在线下载工业PPT亚博体育app在线下载金融PPT亚博体育app在线下载音乐PPT亚博体育app在线下载汽车房地产互联网培训手机

实用必备个人简历自我介绍年终总结职业规划述职报告工作汇报工作总结岗位竞聘公司简介发布会年会论文答辩

PPT推荐语文课件数学课件英语课件美术课件物理课件科学课件化学课件地理课件生物课件主题班会家长会绘本故事

节日PPT新年元旦节农历春节情人节元宵节三八妇女节愚人节清明节五一劳动节母亲节六一儿童节端午节

节日PPT 父亲节七夕情人节教师节中秋节国庆节重阳节万圣节光棍节感恩节平安夜圣诞节纪念日