信息安全数学基础第一阶段知识总结.doc

信息安全数学基础第一阶段知识总结
第一章　整数得可除性
一 整除得概念与欧几里得除法
1 整除得概念
定义1 设a、b就是两个整数，其中b≠0如果存在一个整数 q 使得等式 a=bｑ 成立，就称b整除a或者ａ被ｂ整除，记作b|a ,并把b叫作a得因数,把a叫作b得倍数、这时，q也就是a得因数,我们常常将ｑ写成a/b或
否则,就称b不能整除a或者a不能被b整除,记作a b、
2整除得基本性质
(1)当b遍历整数a得所有因数时,－b也遍历整数a得所有因数、
（2)当ｂ遍历整数a得所有因数时,a/b也遍历整数a得所有因数、
（3)设b，c都就是非零整数，
　　　(i）若b|a,则|b|｜|ａ|、
　 (ｉｉ)若ｂ｜a,则ｂｃ|aｃ、
(iii)若b|a,则1〈|b｜≤|ａ|、
3整除得相关定理
（1) 设a,ｂ≠0,c≠０就是三个整数、若c｜b,b|a,则ｃ|a、
(２)　设a，b，c≠０就是三个整数,若ｃ|ａ,ｃ|b,则ｃ｜a±b
(3） 设a，b,c就是三个整数、若c｜a，ｃ|b则对任意整数s，t,有c|ｓa+tb、
(４） 若整数a１ , …,aｎ都就是整数c≠0得倍数，则对任意n个整数s１,…,ｓｎ，整数 　　 　 　 就是c得倍数
（5） 设a，b都就是非零整数、若a|b,ｂ|a,则a=±b
(6)　设a,　ｂ ，　c就是三个整数,且b≠0,c ≠0,如果(a , c）=1,则　
(ab , ｃ)＝（ｂ ，　c）
(7) 设ａ ， b , c就是三个整数,且ｃ≠0，如果c｜ａb　，　（a , ｃ） ＝ 1, 则c　｜ b、
（8） 设ｐ 就是素数，若ｐ |ab ,　则p |a或p|b
（9） 设a1 ， …,an就是n个整数，p就是素数,若ｐ｜　a1 　…an ，则p一定整除某一个ａk
二 整数得表示
主要掌握二进制、十进制、十六进制等得相互转化、
三 最大公因数与最小公倍数
（一)最大公因数
1．最大公因数得概念
定义:设就是个整数,若使得 ,则称为得一个因数。公因数中最大得一个称为得最大公因数。记作、
若　，则称　互素。
若,则称两两互素。ﻫ思考:１.由两两互素，能否导出
2。由 能否导出两两互素？
２。最大公因数得存在性
（1)若 不全为零,则最大公因数存在并且
(2)若全为零,则任何整数都就是它得公因数。这时,它们没有最大公因数．
3.求两个正整数得最大公因数。
定理1：设任意三个不全为零得整数，且　则
辗转相除法
由带余除法 得

　 （1）
　……

　 因为每进行一次带余除法，余数至少减少1，且就是有限整数,故经过有限次带余除法后,总可以得到一个余数就是零得情况，即
　 由(1)知，

定理2：任意两个正整数,则就是(１）中最后一个不等于零得余数.
定理３:任意两个正整数得任意公因数都就是得因数。
4.性质
定理4:任意两个正整数,则存在整数，使得成立
ﻫ定理5:设就是不全为零得整数。
　　　（ｉ)若则
　　 (ii)若则
(ｉii)若就是任意整数，则　
从上面定理我们很容易得到下面几个常用结论:
　　①　
　② 且ﻫ　 　
　　③
④
5.求两个以上正整数得最大公因数

　设
则有下面得定理:

定理6:若　就是个正整数,则
只需证①就是得一个公因数．②　就是得公因数中最大一个
例 求
解:

6．求两个正整数得最大公因数得线性组合（重点掌握)　
方法一 运用辗转相除法求最大公因数得逆过程;
方法二 补充得方法
方法三 运用列表法求解
（二） 最小公倍数
１.最小公倍数得定义
ﻫ定义： 就是 个整数，如果对于整数,有 ,那么叫做得一个公倍数.在 得一切公倍数中最小一个正整数，叫做最小公倍ﻫ数.记作 。

2.最小公倍数得性质。
ﻫ定理1:设就是任给得两个正整数，则
　 　（ｉ)得所有公倍数都就是得倍数.
　　 (ii)
定理２：设正整数就是得一个公倍数，则
3。求两个以上整数得最小公倍数
定理３:设就是个正整数,　若
　 则
只需证:①就是 得一个公倍数，即,
　 ②设就是得任一公倍数，则　
例1 求

解:
又 ﻫ 　

　 ﻫ
ﻫ四 素数 算术基本定理
1．素数、合数得概念
ﻫ定义:一个大于1得整数，如果它得正因数只有１与它得本身,我们就称它为素数，否则就称为合数。
2.性质
ﻫ定理1:设就是大于1得整数,则至少有一个素因数，并且当就是合数时，若就是它大于1得最小正因数,则
定理2　设n就是一个正整数，如果对所有地素数,都有
p n，则n一定就是素数、　
求素数得基本方法：爱拉托斯散筛法。
定理3:设就是素数,就是任意整数，则
　 　(i)　或　 　　(ii) 若　则或
3．素数得个数
ﻫ定理4：素数得个数就是无穷得.
4。 算术基本定理
定理 5　任一整数ｎ〉1都可以表示成素数得乘积，且在不考虑乘积顺序得情况下，该表达式就是唯一得、即
n= ｐ1 … pｓ ， p1≤ … ≤ps , 　 (1)
其中pi 就是素数,并且若ｎ　= q1 　…qｔ　, 　q1 ≤　… ≤ qt ， 其中qj 就是素数,则　ｓ= t , pi = ｑj, １ ≤i ≤ｓ、　
推论1:设就是任一大于1得整数,且 　
　 为素数，且　　 则就是得正因数得充分必要条件就是　　

推论２：且
　　 为素数.
　　 则

第二章 同余
一　同余概念与基本性质
〈一>、同余得定义.
ﻫ定义: 如果用去除两个整数所得得余数相同,则 称整数关于模同余，记作 如果余数不同，则称关于模不同余，记作、
定理１：整数关于模同余充分必要条件就是
〈二〉、性质。
ﻫ定理2：同余关系就是一种等价关系,即满足
　　(１)自反性:
(2）对称性:若
　 (3)传递性：若

定理3:若
　 则:

定理４:若 且　则
定理５:若 且　则
定理６：若,则
ﻫ定理7:若 且 则

定理8:若 则
定理9　设整数n有十进制表示式：
n = ａk １0k　+ ａk—1 １0k—1 +　… + a1 １0 +　a0 ， 0≤ａi <10则 3 |　n得充分必要条件就是 3　| ak + …　+ a0 ;
而９　｜n　得充分必要条件就是 9 | ak + … + a0 、
定理10　设整数n有１000进制表示式:
　ｎ ＝ ａk １０００ｋ ＋ …+ a1 10０0 + ａ0 ,　0≤ai 〈10０0
则7(或 11，或1３）|n得充分必要条件就是７(或11，或1３)能整除整数
(　a0 ＋ a2 + …） – ( a1 +　a3　+ …）
例１:求７除得余数.

解:

　 除得余数为4。

例2:求得个位数.

解:

得个位数为。

二 完全剩余系与互素剩余系
<一>、剩余类.
ﻫ1。定义１：设就是一个给定得正整数.　
则叫做模得剩余类。
ﻫ定理１：设就是模得剩余类，
则有（1）中每一个整数必属于这个类中得一个,且仅属于一个.
　　　(2）中任意两个整数属于同一类得充要条件就是ﻫ　 　　
<二>、完全剩余系
ﻫ1.定义2：在模得剩余类中各取一个数 则个整数称为模得一组完全剩余系。
任意个连续得整数一定构成模得一组完全剩余系.
2.形成完全剩余系得充要条件．
ﻫ定理2:个整数形成模得完全剩余系得充要条件就是：

ﻫ3．完全剩余系得性质．

定理３：若 则当遍历模得完全剩余系时,则ﻫ 　　　也遍历模得完全剩余系。
定理4 设ｍ就是一个正整数,a就是满足(a,m）=1得整数,则存在整数a’
1 ≤a’〈ｍ，使得aa’≡１(mod　 ｍ）
定理5：　若　当分别遍历模得完全剩余系时,则也遍历模得完全剩余系.
例1:问就是否构成模得完全剩余系?

解：

　 就是得一个排列。
能构成模得一组完全剩余系．

〈三〉 简化剩余系
ﻫ1、简化剩余类 、简化剩余系概念.
ﻫ定义３:若模得某一剩余类里得数与互素,则把它称为模得一ﻫ 个互素剩余类。在与模互素得全部剩余类中，各取出一整
　　 数组成得系,叫做模得一组简化剩余系。
在完全剩余系中所有与模互素得整数构成模得简化剩余系.
2.简化剩余系得个数.
ﻫ定义4:欧拉函数就是定义在正整数集上得函数,得值等于ﻫ　 　 序列与互素得个数。
为素数
定理６:个整数构成模得简化剩余系得充要条件就是

定理7：若遍历模得简化剩余系,则也遍历模得
　　简化剩余系
定理8设 m1 ,m2 就是互素得两个正整数,如果x１ , ｘ２　分别遍历模 m1 与　m2　得简化剩余系,则m2x１ +　m1x2　遍历模m1 ｍ2 得简化剩余系、
定理9：若　，则

〈三＞欧拉定理 费马小定理 威尔逊定理
1． 欧拉定理　设m就是大于1得整数，如果a就是满足(ａ　， m)=1得整数，则
2.费马定理　 设p就是一个素数，则对任意整数a ,我们有
　　 ａp 　≡ａ　(mod p）
3．(wilsoｎ）设p就是一个素数、则
<四〉模重复平方计算法
主要掌握运用该方法解题过程
第三章 同余式
1.同余式得定义
定义1 设m就是一个正整数,设ｆ(x）为多项式

其中ａi 就是整数,则 ｆ（x)　≡0（ moｄ m　） （1)叫作模ｍ同余式 、 若
0 （mｏd　m), 则ｎ叫做f（x)得次数,记作deｇf 、此时，（1）式又叫做模ｍ得ｎ次同余式、
2.同余式得解、解数及通解表达式
定理 1　设m就是一个正整数,ａ就是满足a　　m得整数则一次同余式
ａｘ≡ｂ (ｍod　ｍ）有解得充分必要条件就是（a ， ｍ)|b ，而且， 当同余式有解时,其解数为d =（ ａ ，　m)、
定理2设ｍ就是一个正整数，a就是满足(ａ，m)=1得整数，则一次同余式　aｘ ≡　１（mod m)有唯一解ｘ≡a’(mｏd m)、
定理3 设m就是一个正整数,a就是满足（a，ｍ）|ｂ得整数,则一次同余式　ax ≡ b（mod ｍ) 得全部解为

3.中国剩余定理
定理1 （中国剩余定理)设就是k个两两互素得正整数，则对任意得整数,同余式组

一定有解，且解就是唯一得
例1 计算
解一　利用　２、4定理 1（Eulｅｒ定理 ）及模重复平方计算法直接计算、
　因为77=7·11,所以由２、4
定理１（Ｅｕler定理),,又
1000000=166６６·60+40,所以
,设ｍ=77，b=2,令a=1、
将40写成二进制,40＝2３ +　２5 ,运用模重复平方法,我们依次计算如下:
（1）　　
（2)　 n1 = 0， 计算
（3） n2 =　0， 计算
(4）　　n3 = 1, 计算
(5) n4 ＝ 0 , 计算　
（6)　 ｎ６ = 1 ，　计算
最后，计算出
解二 令,因为７7=7·11，所以计算x(moｄ 77)
等价于求解同余式组 因为Eulｅr定理给出
,以及１000000＝16６666·6+4，所以
、
令 ，
分别求解同余式　,得到
故x≡2·11·2+8·7·1≡1００≡２3(mｏd 77）
因此,2 ≡23(ｍoｄ 　７7）
例2:解同余式组

ﻫ解: 　　　　原同余式组有解且同解于

　　两两互素
　 　同余式组有惟一解。

　 　原同余式组得解为
第四章 二次同余式与平方剩余
1。二次同余式得定义
定义１ 设m就是正整数,若同余式
有解，则ａ叫做模ｍ得平方剩余（二次剩余）;否则，a叫做模m得平方非剩余（或二次非剩余)、
2. 模为奇素数得平方剩余与平方非剩余
讨论模为素数ｐ得二次同余式　　　
定理１（欧拉判别条件)设p就是奇素数，（ａ, p)=1,　则
( ｉ ）　a就是模p得平方剩余得充分必要条件就是
(ｉｉ） a就是模p得平方非剩余得充分必要条件就是
并且当ａ就是模p得平方剩余时,同
余式（１)恰有二解、
定理２ 设ｐ就是奇素数,则模ｐ得简化剩余系中平方剩余与平方非剩余得个数各为（p—１)／2,且(p—1)/2个平方剩余与序列：中得一个数同余、且仅与一个数同余、
例1 利用定理判断

3、勒让德符号
定义1 设p就是素数,定义勒让德符号如下:

欧拉判别法则 设ｐ就是奇素数，则对任意整数a,
常用定理及结论
设ｐ就是奇素数,则
(1)　 　
(2)
（3）
（4) 　　　　
　（５)　
(６) 设（a， ｐ)　=1， 则
(7） 设p就是奇素数，如果整数ａ， ｂ满足
a ≡　b(mod p)，则
(8）
(９）互倒定律 若p,ｑ就是互素奇素数,则
例1 ,而

所以
第五章 指数与原根
一 指数
1．指数得定义
定义1 设m〉1就是整数 ，a就是与m互素得正整数,则使得成立得最小正整数e叫做a对模ｍ得指数,记作、
2.指数得性质
定理1 设m>1就是整数,a就是与m互素得整数，则整数d使得得充分必要条件就是、
定理1之推论 设m〉1就是整数，ａ就是与ｍ互素得整数，则
性质1设m>1就是整数,a就是与m互素得整数
(i) 若b≡ａ(mｏd m)，则
(ｉi)设使得则 、
性质2 设m＞1就是整数，a就是与m互素得整数,则 得充分必要条件就是
性质3 设m〉1就是整数，a就是与m互素得整数设ｄ≥0，为整数,则
二　原根
1． 原根得定义
定义　若（a,m)=1, 如果a对模m得指数就是,即则ａ叫做模ｍ得原根
2.原根得相关定理及性质
定理1　设m〉１就是整数 ,a就是与ｍ互素得整数、则 模m两两不同余,特别地，当a就是模m得原根，即时,这个数组成模m得简化剩余系
定理2 设m＞1就是整数,ｇ就是模m得原根，设d≥0为整数，则
就是模m得原根当且仅当
3． 原根存在得条件
定理1 设ｐ就是奇素数,则模p得原根存在、
定理2 设g就是模p得一个原根,则g或者p＋ｇ就是模p2 得原根、
定理3设p就是一个奇素数，则对任意正整数ａ，模ｐa 得原根存在、更确切地说,如果g就是模 ｐ2得一个原根,则对任意正整数a，g就是模ｐa 得原根、
定理４设a≥　１，ｇ就是模pa 得一个原根,则g与ｇ＋ pa 中得奇数就是模2pa得一个原根
定理5　模m得原根存在得充分必要条件就是，其中p就是奇素数、
定理6设m〉1, 　　　 　得所有不同素因数就是q1　，　…，qｋ ,　则g就是模ｍ得一个原根得充分必要条件就是 　 1(ｍod　 m)，i=1,…，k