密码人速戳！一篇文章带你明白根与多项式

三叶草小组Syclover

2024

CRYPTO

目录

一

代数基本定理

二

对称多项式基本定理

三

基本多项式定理

四

⽜顿恒等式

五

⾼联科⽬⼀

六

科⽬⼆

七

⼀元三次⽅程求根公式

八

四次⽅程的根式求解

九

Crypto实践

代数基本定理

任何⼀个⼀元复系数多项式⽅程都⾄少有⼀个复数根。也就是说，复数域是代数封闭的复数域代数封闭。

不得不感慨,还是需要捡起⼀些遗忘的科⽬:)，回忆下笔者和Galois理论的缘起。

对称多项式基本定理

对称多项式： 对于域F上的n元多项式f(x₁, x₂, x_3,…, x_n) ∈ F[x₁, x₂,…, x_n],如果对于任意两个变量对换，原多项式保持不变，则这个多项式称为对称多项式。

等价定义：

基本对称多项式

特别地，对于n次式 x₁x₂ …x_n 本身就是⼀个n次⻬次对称多项式σ_n。

根据代数基本定理，在⼀个代数封闭域F上的n次⾸⼀多项式

都有n个零点，可分解为

展开后得到：

⾸⼀多项式的⻙达定理

与系数关系：

⼀般多项式的⻙达定理

由此完成上述概念阐发的⻙达定理内容。

基本多项式定理

对于变量个数n进⾏归纳：n = 1时，结论成⽴。假设n − 1个变量时，结论成⽴，对于n个变量，结论也成⽴

σ_k为n元基本对称多项式。

τ_k为n − 1元基本多项式。

对于

所以对于是任意n元多项式f ∈ F(x₁,…, x_n),可以写成

• 注意到f为n元对称多项式，可得f在x₁, x₂,…, x_n−1的任意置换下不变。由此可得，g_k是n − 1元对称多项式。

由归纳假设可得，g_k可由τ₁, τ₂ …τ_n−1表出，即有：

⼜τ_k可⽤σ₁, σ₂,…, σ_n−1表出，代⼊：

其中 f_k = f_k(σ₁, σ₂,⋯, σ_n) 是 n 元对称多项式。为了证明 f 可以⽤ σ₁, σ₂,⋯, σ_n 多项式表示，只需要证明 f_k = 0, 1 ≤ k ≤ n − 1 ，由此得到f = f₀

把 x_i 和 x_n 对换得到

矩阵形式可表示为范德蒙矩阵系数形式：

注意到解的唯⼀性，以及特解f₁ = f₂ = ⋯ = f_n−1 = 0, f₀ = f为特解，可得f = f₀

对于三次情况：

⽜顿恒等式

⾼联科⽬⼀

任何⼀个⼀元复系数多项式⽅程都⾄少有⼀个复数根。也就是说，复数域是代数封闭的复数域代数封闭。

写出f(x + 5)并化简，然后得到系数，代⼊恒等式即可。

不过可以有更多⼩Trick :)

p_i的计算过程:

科⽬⼆

根据上⾯得学习：

即

注意到定义多项式系数a_i定义在Z⁺上，故还原其中⼀个多项式为：

⼀元三次⽅程求根公式

对于 ⼀般的⼀元三次⽅程

由代数基本定理，在复数域上有三个根。

简化为⼀元三次⾸⼀多项式：

配⽅法代换：

整理得：

不妨取：

特殊化

不难开三次⽅，在得到z = u + v就是⼀元三次⽅程的⼀个根。

即为判别式。

考虑特殊情况：

x³ = 1的三个根。

注意到：

不难得到

恰好构成⼀个三阶循环群，可以在复平⾯内表示这三个根。

回到⽅程z³ + pz + q = 0：

u = u₀, v = v₀是⽅程组(5)的⼀个解,

那么,由⼯具ω可得⽅程组(5)的三组不同解：

⾄此，我们的求解已经完成.

代回的形式可表示为：

判别式：

• Δ > 0，⽅程有1个解

• Δ = 0，⽅程有2个解

• Δ < 0，⽅程有3个解

判别式的⼀般定义：

对于多项式P(x) = a_nx_n + a_n−1x_n−1 + ⋯ + a₁x + a₀，在复数域上存在n个根 x₁, x₂,…, x_n其判别式为

显然Δ为⼀个对称多项式

例：

⼆次情况。

这更直接的告诉我们：根之间的关系，是否相等，这才是判别式的本质，解⼀元多次⽅程的关键，这触及了群论的本质——对称。

四次⽅程的根式求解

对于⼀般的⾸⼀多项式：

考虑换元消元

笛卡尔-⽅法

显然这是⼀种多项式将次⽅法。

分别⽐较多项式两边

可得

应⽤消元的思想得到

⼜lm = r

可以得到

显然是⼀个关于k²的⼀元三次⽅程，k可解。（根于提到的判别式法）

可推知道x² + kx + l = 0, x² − kx + m = 0

⽽对于⼀元五次⽅程的情况，则需要深⼊学习Galois理论。

Crypto实践