信息安全数学基础

2023-12-17 12:07:24

目录

第一章 整除

整除的概念

欧几里得算法?

扩展欧几里得除法

算数基本定理

第二章 同余

同余

?剩余系

求逆元

?欧拉函数

?欧拉定理

费马定理?

Wilson定理?

第三章? 同余式

一次同余式

?一次同余式求解

?中国剩余定理(CRT)

?模重复平方算法

?第四章 二次同余式与平方剩余

二次同余式与平方剩余

?欧拉判定法则(奇素数)

?Legebdre符号(素数)


第一章 整除

整除的概念

定义1.1? 设a,b是任意两个整数,其中b!=0。如果存在一个整数q,使得等式

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?a=qb

成立,则称为b整除a或者a被b整除,记作b|a。? b叫做a的因数,a叫做b的倍数。

定理1.1 整除的传递性:设a!=0,b!=0,c是三个整数。若a|b,b|c,则a|c。

定理1.2 设a,b,c!=0是三个整数。若c|a,c|b,则c|a+b 或者 c|a-b。

定理1.3?设a,b,c!=0是三个整数。若c|a,c|b,则对于任意的整数s,t,有c|sa+tb。

定义1.2 设整数n!=0,\pm1,如果除了平凡因数\pm1,\pmn外,n没有其他因数,那么n叫做素数(或质数,不可约数);否则n叫合数。

?定理1.4 (每个合数必有素因子)设n是一个正合数,p是一个n的大于1的最小正因数,则p一定是素数,且p<=\sqrt{n}

厄拉托塞师筛法:寻找素数的确定性方法

步骤:1.找出<=\sqrt{n}的所有素数;?

? ? ? ? ? ?2.依次删除这些素数的倍数

? ? ? ? ? ?3.余下的数就是素数

定理1.5 素数有无穷多个?

欧几里得算法?

定理1.7 (Euclid除法,也称为带余除数) 设a,b是两个整数,其中b>0,则存在唯一的整数q,r,使得

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? a=qb+r? ? 0 <= r < b

定义1.4? a=qb+r? ? 0 <= r < b? 其中q叫做a被b除所得的不完全商,r叫做a被b除所得的余数。

定义1.5 (公因子)设 a1,.......,an是n(n>=2)个整数。若整数d是他们中每一个数的因数,那么d叫做a1,.......,an的一个公约数(也叫公因数)。

d是a1,.......,an的一个公约数的数学表达式为? ? d|a1,......,d|an

如果整数a1,.......,an不全为0,那么a1,.......,an的所有公约数中最大的一个公约数叫做最大公约数,记作gcd(a1,......an)或a1,......an)。

特别的,当(a1,......an)=1,称(a1,......an)互素或者互质。

定理1.8 a,b是不全为0的整数,a,b的最大公约数d=(a,b)是集合?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? {sa+tb|s,t\epsilonZ}

中的最小整数。

定理1.10 设a1,......an是n个不全为0的整数,则

(1)a1,......,an与|a1|,......,|an|绝对值是相同的

(2)a1,......,an?=(|a1|,......,|an|)

定理1.11 设b是任意正整数,则(0,b)?

因为 任何非零整数都是0的因数。

定理1.12 设a,b,r是三个不全为0的整数。如果

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?a=qb+r?

其中q是整数,(a,b)=(b,r)。

注:这条性质用于欧几里得除法求最大公因数。当c=0时,b为最大公因数。

可以求两个较大数的公因数转化为求两个较小数的公因数。

?例:

因为 1573=5*286+143,所以(1573,286)=(186,143)=143

扩展欧几里得除法

例题

计算 gcd(169,121)=1的分解步骤

169=1*121+48

121=2*48+25

48=1*25+23

25=1*23+2

23=11*2+1

2=2*1+0

?定理1.12 设a,b是任意两个正整数,则存在整数s,t,使得s*a+t*b=(a,b)。

(这个式子是最大公因式反过来求s,t)

将上述的例子反过来写

1=23-11*2

? =23-11*(25-1*23)

? =-11*25+12*23

? =-11*25+12*(48-1*25)

? =12*48-23*25

? =12*48-23*(121-2*48)

? =-23*121+58*48

? =-23*121+58*(169-1*121)

? =58*169-81*121

根据s*a+t*b=1,所以 s=58,t=-81.

算数基本定理

定理1.14? 设a,b是任意两个不全为零的整数:

(1)若m是任意正整数,则(am,bm)=(a,b)m

(2)若非零正整数d满足d|a,d|b,则(d/a,d/b)=(a,b )/d。特别的,有

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(a/(a,b)),(b/(a,b))=1

定理1.15? 设a1,.......,an是n个整数,且a1\neq0。令

? ? ? ? ? ? ? ? ?(a1,a2)=d2,(d2,a3)=d3,......,(dn-1,an)=dn。

则(a1,......an)=dn。

(多个整数的最大公因数)

?定理1.16? 设a,b,c是三个整数,b,c\neq0,如果(a,c)=1,则

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (ab,c)=(b,c)

?定理1.17? 设p是素数,p|ab,则 p|a 或者 p|b。

定理1.18?? 设a1,.......,an是n个整数。若(ai,c)=1,1\leqslant?i?\leqslantn,则

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(a1.......an,c)=1

定义1.6? (最小公倍数)设a1,.......,an是n个整数。若m是这n个数的倍数,则m叫做这个数的公倍数 。a1,.......,an的所有的公倍数中的最小的正整数叫作最小公倍数,记作[a1,.......,an]。

m=[a1,.......,an]的数学描述:

(1)a1|m,.........,an|m。

(2)若a1|m',........,an|m',则m|m'。

定理1.19? 设a,b是两个互素的整数,则

(1)若a|m,b|m,则ab|m。

(2)[a,b]=ab

定理1.20? ?设a,b是两个正整数,则

(1)a|m,b|m,则[a,b]|m

(2)[a,b]=ab/(a,b)

定理1.21? 设?a1,.......,an是n个整数,且a1\neq0.令

? ? ? ? ? ? ?[a1,a2]=m2,[m2,a3]=m3,........,[mn-1,an]=mn

则? ? ? ? ? ? ? ? ? ? ? ? [a1,.........,an]=mn

算数基本定理:

定理1.22? 任何一个正数n>1都可以表示成素数的乘积,且在不考虑乘积顺序的情况下,该表达式是唯一的,即

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?n=p1.......ps,? ? ? ? ? ? p1\leqslant....\leqslantps

其中pi是素数,且若

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?n=q1........qt,? ? ? ? ? ? q1\leqslant....\leqslantqt

其中qj是素数,则s=t? ,pi=qi

?例如:45=3*3*5? ?35=5*7等

?例题:

求解(45,100)和[45,100]

解答;? ? ?45=2^{0}*3^{2}*5^{1}

? ? ? ? ? ?100=2^{2}*3^{0}*5^{2}

所以? (45,100)=2^{0}*3^{0}*5^{1}=5

? ? ? ? ? ? ?[45,100]? =2^{2}*3^{2}*5^{2}=900

第二章 同余

同余

定义2.1 给定一个正整数m,如果两个整数a,b有m|a-b,则a,b模m同余。

记作a\equivb(mod m);否则,a,b模m不同余,记作a\not\equivb(mod m)。

定理2.1 设m是一个正整数,a,b是两个整数,则a\equivb(mod m)的充要条件是,存在一个整数k,使得a=b+km。

定理L1? 设m是一个正整数,则整数a,b模m同余的充分必要条件是a,b被m除的余数相同?。

定理2.2? (1)自反性 对任意一个整数a,a\equiva(mod m)?

? ? ? ? ? ? ? (2)对称性 若a\equivb(mod m) ,则b\equiva(mod m)

? ? ? ? ? ? ? (3)传递性 若a\equivb(mod m),b\equivc(mod m),则?a\equivc(mod m)

定理2.3 设m是给定的一个正整数,a1,a2,b1,b2是四个整数,如果

?????????????????????????????????????????????????????????a1\equivb1(mod m)

?????????????????????????????????????????????????????????a2\equivb2(mod m)

则有

??????????????????????????????????????????????????????????a1\pma2\equivb1\pmb2?(mod m)

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??a1*a2\equivb1*b2(mod m)

(1)前提是:若果是两个不同的多项式,则对应系数模m同余

(2)如果是未知数模m同余,则两个多项式模m同余

(3)如果对一个多项式 f(x),对满足 x=y(mod m)的任意x,y,有:f(x)=f(y) (mod m)

例题

?

?

?定理L3? 若ac=bc (mod m),(c,m)=d,则??a\equivb(mod m/d)

?

?定理2.4?设m是一个正整数,ad\equivbd(mod m),如果(d,m)=1,则

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????a\equivb(mod m)

(该定理说明了同余关系的“消去”原则是消去值与模的互素)

?定理L4? 设??a\equivb(mod m),则(a,m)=(b,m)。

?剩余系

?例题

?定理2.7? 设m是正整数,则m个整数a1,a2,......,am为模m的一个完全剩余系的充要条件是他们模m两两不同余。

?定理2.8? 设m是正整数,整数a满足(a,m)=1,b是任意整数。若x遍历模m的一个完全剩余系,则ax+b也遍历模m的一个完全剩余系。

求逆元

?简化剩余系

注意是与m互质,而不是本身是素数。

?欧拉函数

注意:1与任何数都互素?

?欧拉定理

例题

费马定理?

Wilson定理?

第三章? 同余式

一次同余式

如果,整数a使得? ? f(a)\equiv0(mod m)? ?成立,则a叫做同余式的解。

注:是a叫做,不是f(a)叫做。

满足x\equiva(mod m)的所有整数都使得同余式成立。所以,以一个剩余类作为一个解。

在模m的完全剩余系中,使得同余式成立的剩余类的个数叫做同余式的解数。

只要找到一个整数a满足? f(a)\equiv0(mod m) ,那么凡是与a模m同余的整数都满足,但所有这些与a模m同余的整数职能算该同余式的一个解。

通常是遍历模m的最小非负完全剩余系。

通过这些例子可以知道,给定同余式的方程,方程解的情况可能是一个,或者多个。但多个解是有限的,最多只能有模m个。

?

?一次同余式求解

?

?注意:这一题因为(a,m)=1,所以存在唯一解。

?中国剩余定理(CRT)

?

?

?模重复平方算法

?第四章 二次同余式与平方剩余

二次同余式与平方剩余

注意:“a是否为模m的平方剩余”是通过“同余式x^{2}\equiva(mod m)是否有解”来定义的。

在定义中需要注意以下三点:

(1)(a,m)=1,表示s是模m完全剩余系中的一个数。

(2)如果存在整数x满足x^{2}\equiva(mod m),且(a,m)=1,则(x,m)=1。

(3)“平方剩余”是指a,并不是同余式的解。

?

?

?欧拉判定法则(奇素数)

?Legebdre符号(素数)

?

?

?

文章来源:https://blog.csdn.net/weixin_57472404/article/details/124479710
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。