最新的学习笔记

《信息安全数学基础》最新学习笔记

这里是关于《信息安全数学基础》书的个人笔记和总结，包括将一些概念（整除、同余、群、环、域、多项式等代数学基础）重点记录下来，这样容易快速记忆一些重点，建立信息安全需要掌握的数学基础。然而，这里没有相应的证明，需要详细的证明可以翻书查阅。若有错误的地方，欢迎指正，本人也同步在学习，将不断完善。(本人耗时一整天码字不易，希望对你有所帮助，仅供参考)

参考书籍《信息安全数学基础教程》(第2版)，许春香 周俊辉等人编著。

附：也可直接下载PDF学习，可能里面对应的标注和内容更直观、清晰和完整。

定义1.1：假设 a 、 b a、b a、b 是任意两个整数，其中 b b b 非零，若存在一个整数 q q q，使得 a = q b a=qb a=qb 则称为 b b b能整除 a a a，或称 a a a能被 b b b整除，记为 b ∣ a b|a b∣a，且 b b b是 a a a的因子， a a a是 b b b的倍数。

元素 a 、 b a、b a、b互素的充要条件是，存在 u 、 v u、v u、v使 u a + v b = 1 ua+vb=1 ua+vb=1，则由 ( a , b ) ∣ ( u a + v b ) (a, b)|(ua+vb) (a,b)∣(ua+vb)，得 ( a , b ) ∣ 1 (a, b)|1 (a,b)∣1，所以 ( a , b ) = 1 (a, b)=1 (a,b)=1。

如： a − 1 ( m o d n ) ⇒ a^{-1} \pmod n\Rightarrow a−1(modn)⇒存在整数 b b b 使得 a b ( m o d n ) = 1 ab \pmod n=1 ab(modn)=1。

定义1.2：设 x ∈ R x \in R x∈R， ≤ x \leq x ≤x的最大整数称为 x x x的整数部分，记为 ⌊ x ⌋ \lfloor x\rfloor ⌊x⌋。其中 ⌊ x ⌋ ≤ x ≤ ⌊ x ⌋ + 1 \lfloor x\rfloor\leq x\leq \lfloor x\rfloor+1 ⌊x⌋≤x≤⌊x⌋+1。

定义1.3：给定称为模的正整数 m m m，若 m m m除整数 a 、 b a、b a、b得相同的余数，即存在整数 q 1 q_{1} q1​和 q 2 q_{2} q2​使得 a = q 1 m + r ， b = q 2 m + r a=q_{1}m+r，b=q_{2}m+r a=q1​m+r，b=q2​m+r 则称 a a a和 b b b关于模 m m m同余，记为 a ≡ b ( m o d m ) a\equiv b\pmod m a≡b(modm) a a a和 b b b关于模 m m m同余的充分必要条件为： m ∣ ( a − b ) m|(a-b) m∣(a−b)，即 a = b + m t a=b+mt a=b+mt， t t t是整数。

定义2.1：设 S S S是一个非空集合，如果在 S S S上定义了一个代数运算，称为乘法 ·，记为 a ⋅ b a·b a⋅b。对于乘法，根据习惯可省略乘号写成 a b ab ab ，且满足下列条件，则称 ( S , ⋅ ) (S, ·) (S,⋅) 为一个半群。

则用”乘法“定义的群称为乘法半群；用”加法“定义的群称为加法半群。

定义2.2：一个群 G G G的一个子集 H H H如果对于 G G G的乘法构成一个群，则称为 G G G的子群。

对于任意 a ， b ∈ A a，b\in A a，b∈A ，如果 a ≠ b a\neq b a=b ，有 f ( a ) ≠ f ( b ) f(a)\neq f(b) f(a)=f(b)，则称为 f f f为单射。对于任意 b ∈ B b\in B b∈B ，总有 a ∈ A a\in A a∈A，使 f ( a ) = b f(a)=b f(a)=b，则称 f f f为满射。既是满射又是单射的映射称为一一映射。单射的含义是 A A A中的不同的元素在B中有不同的像。满射是 B B B中的每个元素都成为 A A A中元素的一个像。

定义3.1：如果一个群 G G G里的元素都是某一个元素 g g g的幂，则 G G G称为循环群， g g g称为 G G G的一个生成元。由 g g g生成的循环群记为 ( g ) (g) (g)或 ⟨ g ⟩ \langle g\rangle ⟨g⟩。

循环群的几个性质：

特殊的循环群——剩余类群。

由同余概念，将全体整数 Z Z Z进行分类，设 m m m是正整数，把模 m m m同余的整数归为一类，即可表示为 a = q m + r ， 0 ⩽ r < m ， q = 0 , ± 1 , ± 2 , . . . a=qm+r，0\leqslant r 1 , 1 ± 8 , 1 ± 2 × 8 , 1 ± 3 × 8 , . . . 1,1\pm8, 1\pm2\times 8, 1\pm3\times8,... 1,1±8,1±2×8,1±3×8,... } 2 ‾ = \overline{2}= 2={ 2 , 2 ± 8 , 2 ± 2 × 8 , 2 ± 3 × 8 , . . . 2,2\pm8, 2\pm2\times 8, 2\pm3\times8,... 2,2±8,2±2×8,2±3×8,... } … 7 ‾ = \overline{7}= 7={ 7 , 7 ± 8 , 7 ± 2 × 8 , 7 ± 3 × 8 , . . . 7,7\pm8, 7\pm2\times 8, 7\pm3\times8,... 7,7±8,7±2×8,7±3×8,... }

定理3.1：模 m m m的全体剩余类集合对于剩余类加法构成 m m m阶循环群。注意对于加法，元素的“幂”就是元素的连加。

定义4.1：设 R R R是一非空集合，在 R R R上定义了加法和乘法两种代数运算，分别记为“ + + +”和“ ⋅ · ⋅ ”，如果R具有如下性质：

则称 ( R , + , ⋅ ) (R, +, ·) (R,+,⋅)为一个环。环对于加法构成交换群，对于乘法满足封闭性和结合律，又对加法和乘法满足分配律。如果环 R R R关于乘法还满足交换律，即对于任意，总有，则称 R R R为交换环。

全体整数集合 Z Z Z构成的环是交换环。

由于环里存在两种运算，因此把加法群的单位元称为零元，记为 0 0 0，元素的加法逆元称为负元，记为 − a -a −a。而继续把乘法单位元和乘法逆元分别称为单位元和逆元，用 1 1 1和 a − 1 a^{-1} a−1表示。

定义4.2：如果在一个环 R R R里 a ≠ 0 a\neq 0 a=0， b ≠ 0 b\neq 0 b=0，但 a b = 0 ab=0 ab=0

则称 a a a是这个环的一个左零因子， b b b是这个环的一个右零因子。显然交换环里每个左零因子同时是右零因子。若左右零因子同时存在，则称为零因子。

定义4.3：如果一个环 R R R满足下列条件：

则 R R R称为整环。整数环、全体有理数、全体实数和全体复数都是整环。 条件(2)中 1 ≠ 0 1\neq 0 1=0意味着环中不止一个元素，或存在非零元。

定义4.4：若一个环 R R R存在非零元，而且全体非零元构成一个乘法群，则 R R R称为除环。全体有理数 Q Q Q、全体实数 R R R和全体复数 C C C对于普通的加法和乘法都是除环。

定义4.5：一个交换除环称为一个域 。如果一个环 F F F存在非零元，而且全体非零元构成一个乘法交换群，则 F F F称为一个域。全体有理数 Q Q Q、全体实数 R R R和全体复数 C C C对于普通的加法和乘法都是域。

当 p p p 是素数时，模 p p p剩余类集合对于剩余类加法和乘法构成一个域，记为 G F ( p ) GF(p) GF(p)。

从群的角度出发，则一个集合 F F F是一个域应该满足以下3个条件：

从域、除环、无零因子环和环的定义，可以知道域一定是除环，除环一定是无零因子环。

定义4.6： ( R , + , ⋅ ) (R, +, ·) (R,+,⋅)和 ( R ′ , ⊕ , ⊗ ) (R^{'},\oplus, \otimes) (R′,⊕,⊗)是两个环，如果存在 R R R到 R ′ R^{'} R′的一个映射 f f f，加法和乘法都在 f f f 下得到保持，即对任意 f ( a b ) = f ( a ) f ( b ) f(ab)=f(a)f(b) f(ab)=f(a)f(b) f ( a + b ) = f ( a ) + f ( b ) f(a+b)=f(a)+f(b) f(a+b)=f(a)+f(b)

则称 f f f是 R R R到 R ′ R^{'} R′同态映射，或简称同态。如果 f f f 是单射，则称为 f f f是单同态。如果 f f f 是满射，则称为 f f f是满同态。如果 f f f 是一一映射，则称 f f f 是同构(映射)，此时称 ( R , + , ⋅ ) (R, +, ·) (R,+,⋅)和 ( R ′ , ⊕ , ⊗ ) (R^{'},\oplus, \otimes) (R′,⊕,⊗)是同构，并用 R ≅ R ′ R\cong R^{'} R≅R′表示。

定义5.1：设 F F F是一个域，设 a ≠ 0 a\neq 0 a=0。则称 f ( x ) = a n x n + a n − 1 x n − 1 + . . . + a 1 x + a 0 （ a i ∈ F , n 是非负整数 ) f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x+a_{0}（a_{i}\in F, n是非负整数) f(x)=an​xn+an−1​xn−1+...+a1​x+a0​（ai​∈F,n是非负整数)

域 G F ( 2 ) GF(2) GF(2)上的两个多项式 ( G F ( 2 ) (GF(2) (GF(2)的两个元素表示为 0 0 0和 1 1 1)

定理5.1： F [ x ] F[x] F[x]是具有单位元的整环。

定义5.2：对于 f ( x ) 、 g ( x ) ∈ F [ x ] f(x)、g(x)\in F[x] f(x)、g(x)∈F[x]， f ( x ) ≠ 0 f(x)\neq 0 f(x)=0。如果存在 q ( x ) ∈ F [ X ] q(x)\in F[X] q(x)∈F[X]，使得 g ( x ) = q ( x ) f ( x ) g(x)=q(x)f(x) g(x)=q(x)f(x)，则称 f ( x ) f(x) f(x)整除 g ( x ) g(x) g(x)，记为 f ( x ) ∣ g ( x ) f(x)|g(x) f(x)∣g(x)， f ( x ) f(x) f(x)称为 g ( x ) g(x) g(x)的因式。如果 ( f ( x ) ) k ∣ g ( x ) (f(x))^{k}|g(x) (f(x))k∣g(x)，但 ( f ( x ) ) k + 1 ∣ g ( x ) (f(x))^{k+1}|g(x) (f(x))k+1∣g(x)不能整除g(x)，则称 f ( x ) f(x) f(x)是 g ( x ) g(x) g(x)的 k k k重因式。

定理5.2：欧几里得算法。对于多项式 f ( x ) 、 g ( x ) f(x)、g(x) f(x)、g(x)，其中 d e g ( f ( x ) ) ⩽ d e g ( g ( x ) ) deg(f(x))\leqslant deg(g(x)) deg(f(x))⩽deg(g(x))。反复进行欧几里得算法，得到下列方程式： g ( x ) = q 1 ( x ) f ( x ) + r 1 ( x ) , d e g ( r 1 ( x ) ) < d e g ( f ( x ) ) g(x)=q_{1}(x)f(x)+r_{1}(x), deg(r_{1}(x))