《信息安全数学基础》求生指南

感受

先说感受,还就是那个崭新出厂,所以考试前三天才开始学非常痛苦,因为这书真的看不下去

数论部分概念比较简单,但是涉及的计算很多,学到原根解方程那块才知道很多难的点考试是不会考的

抽代部分看书已经看不懂了,建议配合哈工大的网课食用基础概念,考试会考多项式环那块的简单证明和简单计算,其他就是证明了

那那么多证明我哪知道考哪些?会有透题的,或许是自己老师,或许是别的老师,总之保持消息畅通

最后综测80,3.0,算是很满意的成绩了,虽然考试期间有两道计算题我铸币了,算错了好几次最后还是放弃了。

第一章 整数的可除性

欧几里得除法

最大公因数

所有公因数中最大的那个整数,记作 ( a1,…,an )

最小公倍数

所有公倍数中最小的那个正整数,记作 [ a1,…,an ]

整除的进一步性质

① 若 c | ab、(a,c) = 1,则 c | b
② 若 p 是素数,p | ab,则 p | a 或 p | b
③ 若 a₁,a₂,…,an 是 D 的公倍数,则 D | [ a1,…,an ]

真因数

不包括这个数本身的所有因数,例如 6 的真因数是 1、2、3

整数分解定理

若 n | a² – b²,n 不整除 a+b、a-b

则 (n,a+b)、(n,a-b) 是 n 的真因数

π (x)

表示不超过 x 的素数个数,例如 π (2) = 1,π (10) = 4

素数定理

lim(x->∞) π(x) / x / lnx = 1

第二章 同余

同余

剩余类

Ca = { c | c∈Z,c ≡ a (mod m) }

Ca 叫做模 m 的剩余类,c 叫做该类的剩余

完全剩余系

r0,r1,… ,rm-1 是模 m 的完全剩余系充要条件:r 的模 m 两两不同余

两个模的完全剩余系

(m1, m2) = 1,若 k1、k2 遍历模 m1、m2 的完全剩余系

则 k1·m2 + k2·m1 也遍历模 m1、m2 的完全剩余系

多个模的完全剩余系

(m1, … , mx) = 1,若 ki 遍历模 mi 的完全剩余系

则 k1(m2m3…mx) + k2(m1m3…mx) + … + kx(m1m2…mx-1) 也遍历模 mi 的完全剩余系

欧拉函数

整数 1, 2, … , m-1 中与 m 互素的个数叫做欧拉函数,记作:φ(m)

例如:m = 10,则 1, 3, 7, 9 与 10 互素,φ(m) = 4

欧拉函数性质

φ(mn) = φ(m) φ(n)

若 p、q 是素数,则 φ(pq) = pq – p – q + 1

若 m = p1^α1 … pk^αk

也就是

简化剩余系

和剩余系概念差不多,但是得和m互素,也就是 φ (x)的具体值

两个模的简化剩余系

(m1, m2) = 1,若 k1、k2 遍历模 m1、m2 的简化剩余系

则 k1·m2 + k2·m1 也遍历模 m1、m2 的简化剩余系

欧拉定理,费马小定理,Wilson 定理

欧拉定理

费马小定理

也就是说 a^(p-1)≡1(mod p)

Wilson 定理

模模重复平方计算法

先拆解指数,a=1

b不停的平方运算,a根据01进行相乘

第三章 同余式

一次同余式求解

例题

解的个数k

中国剩余定理

通式

对方程组

求M

根据MM‘ ≡1(mod m) 求M’

例题

中国剩余定理的应用

高次同余式的解数和解法

至于解法,特几把烦人,我也没上过课所以不知道课上有没有讲,但好像考纲不考

高次同余式的提升属于是学了就会会了又忘,逆天😭😭😭

素数模的同余式

素数模同余式的简化

先化简

然后直接验算就行

例题

同余式的解数不超过他的次数

需要将多项式变成首1

第四章 二次同余式,平方剩余

一般二次同余式

x ² ≡ a (mod m) ,(a , m) = 1

若同余式有解,则 a 叫做模 m 的平方剩余,否则 a 叫做模 m 的平方非剩余

模为奇素数

x ² ≡ a (mod p) ,(a , p) = 1 ,p 是奇素数

判别条件

并且

(a1 , p) = 1 ,(a2 , p) = 1 ,p 是奇素数
① 若 a1 是模 p 的平方剩余、a2 是模 p 的平方剩余,则 a1 · a2 是模 p 的平方剩余
② 若 a1 是模 p 的平方剩余、a2 是模 p 的平方非剩余,则 a1 · a2 是模 p 的平方非剩余
③ 若 a1 是模 p 的平方非剩余、a2 是模 p 的平方非剩余,则 a1 · a2 是模 p 的平方剩余

勒让德符号

p为奇素数时

对于a==2

对于a!=2,可以用二次互反律和周期性

例题

雅可比符号

当m为合数时

引理

模平方根

剩下的白兰咯~

第五章 原根,指标

定义

若 (a,m) = 1,e 是满足 a^e ≡ 1 (mod m) 的最小正整数
则 e 叫 a 对模 m 的指数,记作 ordm (a)
若 ordm (a) = φ(m),则 a 叫模 m 的原根

指数性质

指数构造

原根

指标

例题

第八章 群

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇