信安数学基础

写在前边，本文是作者应对期末考试写的复习文, 感觉应该有点用, 就顺带着传上来, 其中有些直接标注了ppt页数, 是作者得到的课件, 读者不必太在意.

另外, 本文大量使用了Mathjax语法, 希望不会引起很多渲染错误吧…

Chap.1 整除，带余除法

1.1 基础概念阐述

全体整数的集合Z，全体自然数的集合N

整除的记法： a|b ，称为 b被a整除 ，意味着 b是a的倍数，a是b的因子 。

1.2 整除的性质

1.3 素数

素数即 其正因子只有1和它自己 的整数。反之，则称为 合数 。

对于素数和合数，有几个定理：

• 合数的最小真因子一定是素数（Chap1 P14）
• 素数有无穷多个（Chap1 P15）

素数分布： $ \pi(x) $ 表示 不超过x的素数的个数 。

比较好的估计方法——素数定理： $ \pi(x) \approx \frac{x}{lnx}, x\to\infty $

具体去看Chap1 P19

1.4 带余除法

$$ b = qa + r $$

显然，r = 0 是 a|b 的充要条件

这里有两个取法：

• 最小正剩余：r取值范围为 (0, a-1);
• 最小绝对剩余：r取值范围围绕0左右；

一般都取最小正剩余。

根据这种带余除法，可以根据除数对于整个整数集Z分类。即

$$ S_{a, j} = a*k+j $$

这其中：

• $ j = 0, 1, …, a-1 $
• $ k = 0, \pm 1, \pm2, … $

相当于将Z分成了a类，每类中的数字除以a所得的余数就是j。

关于 进制转换，见 Chap1 P34 ，这里不再赘述。

Chap.2 最大公因子，欧几里得算法

2.1 公因子 & 最大公因子

公因子： d|a 且 d|b ，则d是a、b的公因子。

最大公因子就是其中最大的那个。

记法： $ gcd(a_1, a_2, …, a_n) $

性质：

更严谨一点的说法：

关于这些性质的证明, 见Chap.2 P9

这其中第二条用的尤其多, 意味着最大公因子前后是可以互相加减的.

2.2 互素

如果 $ gcd(a_1, a_2) = 1 $ , 则称a1, a2是互素的.

$ gcd(a_1, a_2, a_3, …, a_n) = 1 $ , 称他们整体互素.

如果他们之间任意两个都互素, 则称 a1, a2, …, ak 两两互素 .

显然, 根据上面的性质5, $ 两两互素\implies整体互素 $ , 反之不然 .

费马数:

$$ F_n = 2^{2^n}+1 , n为非负整数$$

任意两个不同的费马数互素. 关于这个定理的证明, 见Chap2 P13

明确一点: 两个合数也有可能互素, 即便它们是合数 , 如8和15, 或者费马数F5(这是个合数).

有关互素的最大公因子性质:

最后这一条比较重要, 欧几里得算法成立的基础就是这玩意.

更多最大公因子的性质, 见Chap.2 P18 以及 Chap.2 P21

2.3 最小公倍数

公倍数: a|d 且 b|d, 称d为a, b的公倍数.

最小公倍数, 即其中最小的那个, 记作 $ [a, b] $ .

有一个需要摁记住的, $ [a_1, a_2](a_1, a_2) = |a_1a_2| $

2.4 最大公因子的求解-欧几里得算法

基本思路:

$$ (a, b) = (qb+r, b) = (r, b) $$

将大的数字换成小的数字的带余除法形式, 而后依据最大公因子性质2, 直接将乘积去掉.

这个方法也叫做 辗转相除法 .

直到没有余数为止, 此时的数字被就是二者的最大公因子.

扩展欧几里得算法, 可以将 gcd(a, b) 表示成 a, b的线性组合的形式.

具体过程就是从下向上推, 每一次将余数换掉就可以了.

关于这个,可以扩展出一个性质:

a, b的整系数线性组合恰好构成了 gcd(a, b)的所有整数倍.

而如果a, b互素, 即gcd(a, b) = 1, 则任何整数都可以被表示成a, b的整系数线性组合了.

这里还要给一个方法, 用于给出一个整数x 如何用a, b线性组合表示出来.

首先, 如果x可以用a, b的线性组合表示, 则 gcd(a, b)|x 必定成立.

那么, 我们先用欧几里得算法以及扩展欧几里得算法算出gcd(a, b), 以及gcd(a, b)如何用a, b线性表示.

而后在式子前面乘上x与gcd(a, b)的倍数即可.

关于其它的性质, 见Chap.2 P48

2.5 一次不定方程的求解

一次不定方程:

$$ a_1x_1+a_2x_2+…+a_nx_n = c $$

其有解的充要条件是, $ gcd(a_1, a_2, …, a_n)|c $

主要看二元一次不定方程: $ ax+by = c $

如果该方程已经有一组解: $ (x_0, y_0) $ , 则我们可以给出其全部解:

$$
\begin{cases}{c}
x = x_0+\frac{b}{(a, b)}t \\
y = y_0+\frac{a}{(a, b)}t \
\end{cases}
$$

由此, 我们明确了二元一次不定方程的求解:

• 验证是否有解: 即 $ gcd(a, b)|c $ 是否成立
• 如果有解, 利用扩展欧几里得算法求出一组特解(相当于通过扩展欧几里得算法将c表达成a, b的线性组合的形式), 而后根据上面的公式给出通解.

2.6 算术基本定理

通俗的讲, 就是 任何大于1的整数都能化为有限个素数的乘积 .

利用公式表达:

$$ a>1 \implies a = p_1p_2…p_s $$

这其中, p1, p2, …都是素数

推论: 标准素因数分解式

$$ a = p_1^{\alpha_1}p_2^{\alpha_2}…p_n^{\alpha_n} $$

通过这个式子,我们可以给出求最大公因式以及最小公倍数的比较简单的方法:

• 最大公因数: 把每个素因子取最小值,相乘即可.
• 最小公倍数: 把每个素因子取最大值,相乘即可.

这个玩意也能用于证明一些东西, 具体见Chap.2 P79.

素因式的更多推论, 见Chap.2 P82

Chap.3 同余

3.1 同余_概述

若m, a, b 满足 $ m|a-b $ , 则我们称a, b同余, 记作:

$$ a \equiv b\space (mod\space m) $$

跟前面带余除法其实挺像的, 也分非负最小剩余和绝对最小剩余, 这里一般用非负最小剩余来写.

同余的性质:

显然, 既然叫同余了, 自然能得到如下定理, 即 a, b被m除后所得余数相同 .

对于同余式左右而言, 加法 \ 减法 \ 乘法均成立, 但除法比较特殊.

$$ ca \equiv cb\space(mod\space m) \iff
a \equiv b \space (mod \space \frac{m}{(c, m)}) $$

显然, 当且仅当c, m互素, 即(c, m) = 1时, 消去律(除法)才能成立.

3.2 乘法逆元(重要概念)

若 $ m>1 $ , 且 $ (a, m) = 1 $ , 如果存在 c 使:

$$ ca \equiv 1 \space(mod \space m) $$

我们就可以把c称为a对m的逆元, 记为 $ a^{-1}(mod \space m) $

乘法逆元的求法?

利用欧几里得算法.

因为 (a, m) = 1 , 则有 $ sa + tm = 1 $ , 即1可以通过 a 和 m 的线性组合表示, 只需要取 c = s 即满足要求.

至于怎么求解线性组合, 这是第二章的事情, 忘了往回看.

乘法逆元的性质:

给两类典型题目:

1.分数的最小剩余:

求 $ \frac{53}{46} \space (mod \space 25) $

相当于: $ 3 * (46)^{-1} \space (mod \space 25) $

就需要算一个46关于25的乘法逆, 也就是21关于25的乘法逆.

给出过程供参考:

• $ (21, 25) = 1 $
• $ 1 = 6*21 + (-5)*25 $
• 21关于25的乘法逆就是6

因此 $ \frac{53}{46} \space (mod \space 25) = 3*6 = 18 $

2.大数带余除法

求 $ 3^{1001} mod\space 13 $

利用同余式子的可乘性质(最好找一个除以模数模1的, 这样能直接消掉):

$ 3^3 \equiv 1\space(mod\space 13) $

则:

$ 3^{3*333} = 3^{999} \equiv 1\space(mod\space 13) $

因此:

$ 3^{1001}\space(mod\space 13) = 3^2\space(mod\space 13) = 9 $

关于换模的条件:

如果 $ d>1 且 d|m $ , 并且同余式 $ a\equiv b \space (mod\space m) $ 成立;

则能推出 $ a\equiv b\space(mod\space d) $

由上面这个式子, 可以得到推论:

3.3 剩余类和剩余系

3.3.1 剩余类

根据除以模数 m 所得的余数对于整数集合Z进行分类.

总共m个剩余类, 每个剩余类的代表元是: 0, 1, 2, …, m-1

如果该剩余类的 代表元与模数m互素 , 称这个剩余类为m的 既约剩余类 , 既约剩余类的总个数即欧拉函数(Eular函数), 记作 $ \varphi(m) $

两个记法:

所有m的剩余类组成的集合:

$$ Z_m $$

所有m的既约剩余类组成的集合:

$$ Z_m^* $$

有时候为了简写, 会通过一个代表元来表示一整个集合:

$$ Z_{12} = \lbrace 0, 1, 2, 3, …, 11\rbrace $$

$$ Z_{12}^* = \lbrace 1, 5, 7, 11 \rbrace $$

剩余类是一堆同余的整数组成的集合

3.3.2 剩余系

从 每个剩余类中取出一个元素 (即共取出m个元素), 组成一个集合, 叫做m的一个完全剩余系.

相应的, 从 每个既约剩余系中取出一个元素 (即共取出 $ \varphi(m) $ 个元素), 组成一个集合, 叫做m的一个既约剩余系.

完全剩余系最简单的取法就是取 {0, 1, …, m-1}

既约剩余系最简单的取法就是取 小于m的,与m互素的元素 .

3.4 欧拉函数 & 欧拉定理(Euler定理)

前面提到, $ \varphi(m) $ 是m的既约剩余类的个数.

三条性质:

这三条能够解决全部整数欧拉函数的求法

两条推论:

除了 $ \varphi(1) = \varphi(2) = 1 $ , 对于其余的欧拉函数, 都有:

$$ 2|\varphi(m) $$

对于任意n:

$$ \sum_{d|n} \varphi(d) = n $$

即 n的所有因子 (包括n自己) 的欧拉函数相加等于n

欧拉定理:

如果 (a, m) = 1(a与m互素), 则:

$$ a^{\varphi(m)} \equiv 1 \space(mod\space m) $$

费马小定理:

p为素数, 则:

$$ \varphi(p) = p-1 $$

这定理挺好理解的, 就是素数有p-1个既约剩余系(把代表元为0的既约剩余系抛了就行)

结合欧拉定理, 有:

$$ a^{\varphi(p)} = a^{p-1} \equiv 1\space(mod\space p) $$

欧拉定理给出了另一种求a对于m乘法逆元的方式:

$$ a^{-1} \equiv a^{\varphi(m)-1}\space(mod\space m) $$

有了欧拉带余除法, 我们再看这类题:

2.大数带余除法

求 $ 3^{1001} mod\space 13 $

利用同余式子的可乘性质(最好找一个除以模数模1的, 这样能直接消掉):

要找一个除以模数余1的就很简单: 因为 $ 3^{\varphi(13)} = 3^{12} \equiv 1\space(mod\space 13) $

此后消去 $ 3^{12} $ 的元即可, 即:

$$ 3^{1001} = 3^{12*83}*3^{5} $$

即计算:

$$ 3^5 \space(mod\space 13) $$

结果相同.

Chap.4 同余方程

4.1 一元高次同余方程的概念

同余方程：

$$ f(x) = a_nx^n + … + a_1x+a_0 $$

形如:

$$ f(x) \equiv 0\space(mod\space m) $$

的同余式叫做模m的同余方程.

我们将满足上面的式子的x=c称作该方程的一个解.

显然, 如果c是上面方程的一个特解, 那么c对于m的同余类中的所有数都应当是上面这个方程的解(有关m的因子可以直接消掉)

同余方程的次数就是多项式的次数

从本质上, 同余方程就是系数取自 $ Z_m $ 的方程

接下来是两个问题:

• 有没有解?
• 有多少解?
• 如何求解?

关于有没有解这个问题:

同余方程 $ f(x) \equiv 0\space(mod\space m) $ 有解的必要条件是, 对于m的每个因子d (即d|m) , $ f(x) \equiv 0\space(mod\space d) $ 均有解.

这个定理使得可以 通过简单的枚举来判断一个同余方程是不是无解.

如: $ f(x) \equiv 0\space(mod\space 15) $

可以先枚举 $ f(1), f(2), f(3) $ , 判断 $ f(x) \equiv 0\space(mod\space 3) $ 有没有解, 如果模3都无解, 则模15必定无解.

关于有多少解这个问题:

考虑模数是素数的情况:

$$ f(x) \equiv 0\space(mod\space p) $$

的解数不会超过 f(x) 的次数 n.

关于如何求解这个问题:

穷举法:

首先, 也是最简单的方法, 直接从1到p-1穷举.

多项式化简:

其次, 通过多项式的性质来化简系数和次数.

1.化简系数:

如将 $ 15x^2 + 20x + 12(mod\space 11) $ 化简为 $ 4x^2+9x+1(mod\space 11) $ .

2.化简次数:

如果 $ f(x) = q(x)h(x) + r(x) $ , 并且 $ h(x) \equiv 0(mod\space m) $ 是恒等同余式, 则可以将原方程化简为 $ r(x) \equiv 0(mod\space m) $

关键在于找这个h(x)

如果m是素数, 那这个式子可以用欧拉-费马小定理直接给出:

$$ x^{\varphi(p)} \equiv 1(mod\space p) $$

即(把1挪到左边, 两侧同乘x):

$$ x^{p} - x \equiv 0(mod\space p) $$

上面这两个方法其实本质目的在于 把f(x)变得更简单 , 从而更轻松的进行枚举.

4.2 一次同余方程

一次同余方程是最简单的情况:

$$ ax \equiv b(mod\space m) $$

1.a,m同余的情况:

根据同余式的除法性质, 当(a, m) = 1时(即a, m互素), 可以直接将a除到右边.

此时就一个解: $ x \equiv a^{-1}b(mod\space m) $

2.一般情况:

此时有解的充要条件是:

$$ (a, m)|b $$

同时, 解数也正好是 (a, m);

其通解正好是: $ x \equiv x_0 + \frac{m}{(a,m)}t(mod\space m) $

这里: t = 0, 1, …, (a, m)-1;

可以类比一次不定方程的解法, 事实上, 这俩几乎一模一样

因为可以直接将上面这个同余方程等价于:

$$ ax + my = b $$

因此 ,我们继续类比一次不定方程的解题过程:

• 判断有没有解: 即(a,m)|b是否成立
• 如果有解, 通过扩展Euclid算法计算一个特解
• 利用公式给出通解

4.3 一次同余方程组

一次同余方程组的通用形式:

$$ f_i(x) \equiv 0(mod\space m_i) $$

i可以取多个值.

通过 孙子定理 可以对一次同余方程组进行刻画与求解

孙子定理:

设 $ m_1, m_2, …, m_k $ 两两互素 , 则对于任意整数 $ a_1, a_2, …, a_k $ , 一次同余方程组:

$$ x \equiv a_i(mod\space m_i) , \space 1\leq i\leq k$$

一定有解, 并且解在模m的意义下唯一.

这个唯一解是:

$$ x \equiv a_1t_1M_1 + … + a_kt_kM_k(mod\space m) $$

其中:

• $ a_i $ : 就是每个方程后面的整数
• $ m = m_1 * m_2 * … * m_k = m_i * M_i $
• $ t_iM_i \equiv 1(mod\space m_i) $ , 即ti是Mi在模mi意义下的乘法逆元 (Mi的定义上面已经给出)

给个例子:

$$
\begin{cases}{c}
x \equiv 2(mod\space 3) \\
x \equiv 3(mod\space 5) \\
x \equiv 2(mod\space 7) \
\end{cases}
$$

如果 模数两两不互诉?

$$
\begin{cases}{c}
4x \equiv 14(mod\space 15) \\
9x \equiv 11(mod\space 20) \
\end{cases}
$$

先要将其拆开, 如下:

$$
\begin{cases}{c}
4x \equiv 14(mod\space 3) \\
4x \equiv 14(mod\space 5) \\
9x \equiv 11(mod\space 4) \\
9x \equiv 11(mod\space 5) \
\end{cases}
$$

对上面的方程式一一化简即可

$$
\begin{cases}{c}
x \equiv 2(mod\space 3) \\
x \equiv 1(mod\space 5) \\
x \equiv 3(mod\space 4) \\
x \equiv -1(mod\space 5) \
\end{cases}
$$

而后, 有矛盾则无解, 无矛盾则依照正常解法求解即可

Chap.5 二次剩余

5.1 二次剩余概述

二次同余方程:

$$ ax^2 + bx + c = 0(mod\space p) $$

解法如下:

这玩意看一眼就行, 主要为了引出二次剩余.

二次剩余:

素数 p>2 , (p, d) = 1.

如果 $ x^2 \equiv d(mod\space p) $ 有解, 称d是模p的二次剩余.

如果无解,则称d是模p的二次非剩余.

记法:

二次剩余全体组成的集合:

$$ QR_p = \lbrace a|a\in Z^*_p, 存在x\in Z^*_p使得x^2 \equiv a(mod\space p)\rbrace $$

二次非剩余组成的集合:

$$ QR_p = \lbrace a|a\in Z^*_p, 任意x\in Z^*_p均有x^2 \ne a(mod\space p)\rbrace $$

这里直接表明了a属于p的既约非剩余系, 是因为前面提到了(p, d) = 1

给个例子:

$$ QR_7 = \lbrace 1, 2, 4 \rbrace $$

$$ NQR_7 = \lbrace 3, 5, 6 \rbrace $$

关于既约剩余系中二次剩余与二次非剩余的个数:

二次剩余与二次非剩余各占一半, 即: $ |QR_p| = |NQR_p| = \frac{p-1}{2} $

如何判别 d 是否是 模p 的二次剩余?

欧拉判别法:

d 是 模p 的二次剩余的充要条件:

$$ d^{\frac{p-1}{2}} \equiv 1(mod\space p) $$

d 是 模p 的二次非剩余的充要条件:

$$ d^{\frac{p-1}{2}} \equiv -1(mod\space p) $$

推论: Chap.5 P16 P17

这个d的次方可能很大,具体该怎么算,参见前面的大数带余除法问题(3.4 & 3.2)

5.2 Legendre符号

Legendre符号定义:

设素数p > 2, 令:

$$ (\frac{d}{p}) =
\begin{cases}{c}
0, 当p|d时 \\
1, 当d是p的二次剩余时 \\
-1, 当d是p的二次非剩余时 \
\end{cases}
$$

我们称 $ (\frac{d}{p}) $ 为 模p的Legendre符号

Legendre符号性质:

由第一条, Legendre符号就是欧拉判别式的另一种写法.

Legendre符号的有效计算: Gauss二次互反律

设p, q都是奇素数, 那么:

$$ (\frac{q}{p})(\frac{p}{q}) = (-1)^{(\frac{p-1}{2})(\frac{q-1}{2})} $$

如果p, q不是奇素数, 请利用Legendre符号的性质3, 将其转化为奇素数.
划出来的2, 可以用性质5求解

更复杂的例子, 见Chap.5 P28.

Chap.6 原根与指数

6.1 阶 / 原根

讨论：

$$ a^x \equiv b(mod\space m) $$

这方程目前不会涉及, 但一种最简单的情况需要考虑: 即

$$ a^x \equiv 1(mod\space m) $$

使得这个式子成立的 最小的正整数 x 被称为 a模m的阶 , 记作 $ ord_m(a) $ .

特别的, 如果 $ ord_m(a) = \varphi(m) $ 时, 称a是 模m的原根 .

阶的性质:

• 与代表元无关:

如果a和b在关于模m的同一个 既约剩余类 中, 即:

$$ b \equiv a(mod\space m) , \space (a, m) = 1$$

则我们一定能推出:

$$ ord_m(a) = ord_m(b) $$

• 阶的周期性:

即如果有:

$$ a^d \equiv 1(mod\space m) $$

则必定能推出:

$$ ord_m(a)|d $$

相当于阶这个概念自己划定了一个周期, 每经过一个周期, 都会再次回到1.

• 阶与欧拉函数:

对任何正整数m, 均有:

$$ ord_m(a)|\varphi(m) $$

说明任何元素模m的阶, 都必定是m欧拉函数的因子.

• 性质4见Chap.6 P15(a的乘方同余, 则乘方之间有关系)
• 乘法逆元的阶:

有:

$$ ord_m(a) \equiv ord_m(a^{-1}) $$

• a的k次幂的阶与a有关(Chap.6 P17)

有:

$$ ord_m(a^k) = \frac{ord_m(a)}{(ord_m(a), k)} $$

• 原根个数:

如果m有原根(这是大前提) , 则m的原根个数必然是:

$$ \varphi(\varphi(m)) $$

并且所有原根的集合:

$$ \lbrace g^i|(i, \varphi(m)) = 1, 1\leq i<\varphi(m) \rbrace $$

这其中:

• g是m的其中一个原根;
• i是乘方数, 必须满足与m的欧拉函数互素;

举例而言:(还是上面那个17的原根的例子)

17的原根个数:

$$ \varphi(\varphi(17)) = \varphi(16) = \varphi(2^4) = 2^3*(2-1) = 8 $$

最后这步是欧拉函数的性质1. (详见3.4)

• 性质7, 8见Chap.6 P20, 21

• 一个数有原根的充要条件:

当:

$$ m = 2, 4, p^\alpha, 2p^\alpha $$

时, m一定有原根.

这其中:

• p 是奇素数;
• $ \alpha $ 是任意正整数;

这条性质, 和上面那条原根个数的性质, 能够轻松的判断出 一个正整数是否有原根, 有多少原根.

原根的有效求解:

在m有原根的前提下, 对于 $ \varphi(m) $ 所有的素因子 $ q_1, q_2, …, q_s $ , g是模m的原根的充要条件是:

$$ g^{\frac{\varphi(m)}{q_j}} \neq 1(mod\space m), \space j = 1, 2, …, s $$

上面这个式子其实不是一个直接计算的式子, 只能算一个检验式.

关于原根生成的剩余系:

任意原根g都可以生成模m的既约剩余系, 即

$$ \lbrace g^0, g^1, …, g^{\varphi(m)-1} \rbrace $$

这时, 我们称呼g为模m既约剩余系的一个生成元.

请务必明确, 每个原根都能生成一个既约剩余系, 但这 不代表每个既约剩余类的代表元都是原根.

6.2 指数

指数的概念由原根引出.

g为m的原根, 给定与m互素的元素a, 则必定存在一个指数 $ \gamma $ , 使得:

$$ a \equiv g^{\gamma}(mod\space m) $$

我们称这个 $ \gamma $ 为 a对模m的以g为底的指数.

这个概念建议结合上面原根能够生成既约剩余系的性质来理解. 因为原根必定能够生成一个剩余系, 所以这个指数必定存在(这里的a就相当于一个既约剩余类的代表元).

引入指数, 主要是为了这个性质:

g是模m的原根, a与m互素(即(a, m) = 1), 则:

$$ ord_m(a) = \frac{\varphi(m)}{(ind_{m, g}(a), \varphi(m))} $$

这性质的推论很重要.

推论即: 当模m有原根时, 对于每个正除数d| $ \varphi(m) $ , 在模的一个既约剩余系中, 恰好有 $ \varphi(d) $ 个元素的阶等于d.

这个结论后来证明对一般循环群也是对的.

Chap.7 多项式

从这一章开始, 会将讨论范围扩大到多项式, 而不仅仅限制在整数域内

7.1 多项式的概念

$$ K[x] = \lbrace a_nx^n + a_{n-1}x^{n-1} + … + a_1x+a_0|\space a_i \in K \rbrace $$

这里的K可以指代整数Z, 有理数Q, 实数R, 复数C中的任意一个.

多项式的运算此处不再赘述, 仅定义一个多项式的次数:

$$ deg\space f $$

表示多项式f(x)中最高次项的次数.

7.2 多项式上的整除 \ 不可约 \ 唯一分解

类似于整数域, 多项式域内也可以定义整除的概念:

$$ f(x) = g(x)h(x) $$

记作: $ g(x)|f(x) $

相似的, 如果找不到这么个 h(x) , 那么记作: $ g(x) \nmid f(x) $ .

多项式整除的性质:

多项式的不可约性:

$ deg\space p \geq 1$ , 并且在K[x]这个域中仅有平凡分解(就是因子只有1和它自己), 则称p(x)是K[x]内的不可约多项式.

虽然多项式的不可约性随着K所指向的域的变化而变化, 但至少有两个域中, 可以划等号:

$$ f(x)在Z[x]中不可约 \iff f(x) 在Q[x]中不可约 $$

多项式在K[x]上的唯一分解:

因为有不可约多项式的存在(可以理解为 多项式域上的素数 ), 因此每个多项式也必然能够通过一系列不可约多项式表示出来.

$$ f(x) = c * p_1(x)^{e1} * p_2(x)^{e2} * … * p_t(x)^{e_t} $$

7.3 不可约多项式的判别方法

又称爱森斯坦判别法(Eisenstein判别法)

$$ f(x) = a_nx^n + …+ a_0 $$

f(x)是整系数多项式, 如果存在一个素数p, 使得 $ p\nmid a_n $ , $ p^2 \nmid a_0 $ , 但对于剩余的 $ i<n $, 都存在 $ p|a_i $, 则f(x)在Z(Q)上均不可约.

7.4 模p约化

将多项式f(x)的所有系数化为它们的模p剩余类的代表元(就相当于模p)的过程.

为什么要引入这个概念, 因为以下这个定理是一个非常重要的判别不可约多项式的定理:

如果f(x)的模p约化的多项式 $ \overline{f} $ 在 $ Z_p[x] $ 中不可约, 那么f(x) 在 Z[x] 中一定不可约.

Chap.8 域上的一元多项式

8.1 环和域

就是离散中的概念, 这里不会很详细的说明.

(R, +)构成交换群, (R, *)构成半群, 则(R, +, *)称为环, 特别的, 如果 * 运算 也满足交换律, 则称为交换环 .

显然, 对于多项式环, 就是一个很典型的交换环.

域:

交换环的基础上, R中的所有元素都 乘法可逆 , 则称为域.

• $ Z_p $ 是域, 这里p是素数
• $ Z_m $ , 如果m是合数, 那就不是域, 因为并非所有的元素都有乘法逆元(乘法逆元存在的前提是必须互素, 而合数并不是跟其中所有元素都互素, 比如2在 $ Z_4 $ 中就没有乘法逆元).

8.2 域上的一元多项式

我们上面介绍的多项式的整除 \ 可约 \ 不可约 均可以类似的搬下来. 不过要注意, 这里的域可能会由于带余除法的存在导致一些此前不成立的性质.

显然, K[x] 上有无穷多个首项系数为 1 的不可约多项式.

同时还有定理:

设p(x)不可约, 如果 $ p(x) | f(x)g(x)…h(x) $ , 那么p(x)至少整除它们其中之一(即p(x)至少是它们其中之一的因子).

上面这个定理, 类比整数上由很多素数乘积组成的合数.

8.3 域上多项式的不可约性判定

上面提到了, 只要多项式在 $ Z_m $ 域上不可约, 则多项式在Z上就是不可约的.

如何判断多项式在 $ Z_m $ 上不可约?

1.当m较小时, 可以用筛法:

如 $ Z_2 $上全部小于等于三次的不可约多项式:

• 1次多项式均不可约
• 2次多项式可约当且仅当它有1次多项式因子 -> 将全部因子两两相乘枚举出来所有可约的, 剩下的就是不可约的.
• 3次多项式同理.

2.当m较大时, 二次多项式是否可约可以通过二次剩余解决:

由于二次多项式的形式: $ f(x) = ax^2+bx+c $

其可约代表着: $ f(x) \equiv 0(mod\space m) $ 有解.

即令 $ X = b^2 + 4 * a * c $ ;

如果X是模m的二次剩余, 则方程有解, f(x)可约;

如果X是模m的二次非剩余, 则方程无解, f(x)不可约;

至于X是不是模m的二次剩余, 则利用Legendre符号 $ (\frac{X}{m}) $ 来进行判断.

Legendre符号的计算见5.2

8.4 最大公因式 & 欧几里得算法

同理, 域上的多项式也有其最大公因式, 同样可以利用欧几里得算法进行求解, 只不过要把整数带余除法变更为多项式带余除法.

比如: $ (x^2-1, x^2+x-2) $ 的求解过程:

• $ x^2+x-2 = 1*(x^2-1) + (x-1) $ , 转变为求 $ (x^2-1, x-1) $
• $ x^2-1 = (x+1)*(x-1) $
• 最大公因式: x-1;

相应的, 这个过程也可以逆推回去, 跟整数的欧几里得扩展算法一个道理, 这里不再详述.

提一下, 每次求出结果之后别忘了根据域的范围化简, 比如在 $ Z_2 $ 中, 所有的带2的项都可以直接消掉

很显然, 当两个多项式的最大公因式为1时(类比整数互素), 两个多项式可以通过扩展欧几里得算法求得一个关于另一个的乘法逆元.

具体步骤与整数那里完全相同:

• 利用欧几里得算法求出 $ (f(x), g(x)) = 1 $ ;
• 利用扩展欧几里得算法将1表示成两个多项式的线性组合 $ 1 = f(x)*h(x) + g(x)*\varphi(x) $
• h(x)就是该域上f(x)关于g(x)的乘法逆元, 可以表达为: $ f(x)*h(x) \equiv 1(mod\space g(x)) $

Chap.9 多项式同余

9.1 多项式同余 \ 剩余类环

我们还是要类比整数域上的同余计算, 即

$$ f(x) \equiv g(x)(mod\space m(x)) $$

只不过这里全换成了多项式.

显然, 对于m(x), 肯定也存在很多个剩余类, 但这里的剩余类的个数与域有关:
比如, 在 $ Z_2[x] $ 中, $ x^2+1 $ 的所有剩余类代表元:

$$ 0, 1, x, x+1, x^2 $$

由m(x)在域K[x]上的所有剩余类构成的环, 叫做模m(x)的剩余类环, 记作:

$$ K[x] / (m(x)) $$

9.2 多项式剩余类域

当m(x)不可约时(类比到整数域中m是素数), 此时除了0所在剩余类, 其他的剩余类均可逆.

此时这个剩余类环构成了一个域.

关于多项式的乘法逆怎么求: 类比整数域, 通过多项式域中的扩展欧几里得算法进行计算.(见8.4)

9.3 多项式版本中国剩余定理

当遇到多项式同余方程组时, 可以用多项式版本的中国剩余定理来求解, 具体形式与整数域完全相同.

• 先将后面的模数改为两两互素的形式
• 套公式, 求逆
• 得到通解即可

至此, 信安数学基础这门课的主要内容就结束了.

这篇博文就到这里.