本原多项式 特征多项式

hbghlyj

GF(3)是整数 mod 3。
GF(9)是GF(3) 上的多项式除以 GF(3) 中 2 次不可约多项式$f(x)$的余数。
GF(3) 中 2 次不可约多项式有:$x^2+1$和$x^2-x-1$.
当$f(x)=x^2+1$，GF(9) 的元素是：$0, 1, 2, x, x+1, x+2, 2x, 2x+1, 2x+2$
下面是一些加法的例子：
    1+2=0
    (x) + (2x+1) = 1
    (2x+2) + (2x+2) = 2(2x+2) = x+1
下面是乘法的一些例子：
    2 * 2 = 1
    x * 2 = 2x
    x * x = x^2 = x^2 + 2(x^2+1) = 3x^2 + 2 = 2
    (x+1) * (2x) = 2x^2 + 2x = 2 * 2 + 2x = 2x + 4 = 2x + 1
当$f(x)=x^2-x-1$，GF(9) 的元素是：$0, 1, 2, x, x+1, x+2, 2x, 2x+1, 2x+2$
加法和上面相同.
下面是乘法的一些例子：
    2 * 2 = 1
    x * 2 = 2x
    x * x = x^2 = x^2 + 2(x^2-x-1) = 3x^2 - 2x -2 = x+1
    (x+1) * (2x) = 2x^2 + 2x = 2 * (x+1) + 2x = x + 2

---

用WolframAlpha查GF(9)得:
Primitive polynomials
$x^2 + x + 2$
$x^2 + 2 x + 2$
Characteristic polynomials
$x^2 + 1$
$x^2 + x + 2$
$x^2 + 2 x + 2$
这里的Primitive polynomials应该是生成元.
这里的Characteristic polynomials是什么?

Czhang271828

hbghlyj 发表于 2023-4-19 04:38
这里的Primitive polynomials应该是生成元.
这里的Characteristic polynomials是什么?

$\mathrm{GF}(9)$ 的写法过于印刷化, 一般将有限域写作 $\mathbb F_{3^2}$ 或者 $\mathbb F_9$.

$\mathbb F_{p^n}$ 的特征多项式使得 $\mathbb F_p$ 分裂域为 $\mathbb F_{p^n}$ 的 $\mathbb F_p[X]$ 上多项式. 其中本原多项式是一类特殊的特征多项式, 其在分裂域上的所有根是乘法群 $\mathbb F_{p^n}\setminus\{0\} $ 的生成元.

例如 $\mathbb F_9$ 上非本原的特征多项式有 $x^2+1$. 其任意根 $x_0$ 满足 $x_0^4=(x_0^2)^2=(-1)^2=1$.

hbghlyj

hbghlyj 发表于 2023-4-18 20:38
这里的Characteristic polynomials是什么?

看了几个例子，我知道它们的意思了：

$p^m$ 阶域 $F$ 的“特征多项式”是域 $\hbox{GF}(p)$ 上的那些分裂域同构于 $F$ 的多项式.
相比之下，WolframAlpha列出的“本原多项式”是那些根是本原元素的多项式。 所有本原多项式都是特征多项式，但反之则不总是如此：例如，$X^2 + 1$ 在 GF(3) 上不可约，因此其分裂域为 GF(9)，但其在该域中的根是 4 阶元素，而不是 8 阶元素。参见@Czhang271828的回答。

hbghlyj

WolframAlpha 的输出是
x^8 + x^4 + x^3 + x^2 + 1
x^8 + x^5 + x^3 + x + 1
x^8 + x^5 + x^3 + x^2 + 1
x^8 + x^6 + x^3 + x^2 + 1
x^8 + x^6 + x^4 + x^3 + x^2 + x + 1
x^8 + x^6 + x^5 + x + 1
x^8 + x^6 + x^5 + x^2 + 1
x^8 + x^6 + x^5 + x^3 + 1
x^8 + x^6 + x^5 + x^4 + 1
x^8 + x^7 + x^2 + x + 1
x^8 + x^7 + x^3 + x^2 + 1
x^8 + x^7 + x^5 + x^3 + 1
x^8 + x^7 + x^6 + x + 1
x^8 + x^7 + x^6 + x^3 + x^2 + x + 1
x^8 + x^7 + x^6 + x^5 + x^2 + x + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1

hbghlyj

WolframAlpha 的输出是
x^8 + x^4 + x^3 + x + 1
x^8 + x^4 + x^3 + x^2 + 1
x^8 + x^5 + x^3 + x + 1
x^8 + x^5 + x^3 + x^2 + 1
x^8 + x^5 + x^4 + x^3 + 1
x^8 + x^5 + x^4 + x^3 + x^2 + x + 1
x^8 + x^6 + x^3 + x^2 + 1
x^8 + x^6 + x^4 + x^3 + x^2 + x + 1
x^8 + x^6 + x^5 + x + 1
x^8 + x^6 + x^5 + x^2 + 1
x^8 + x^6 + x^5 + x^3 + 1
x^8 + x^6 + x^5 + x^4 + 1
x^8 + x^6 + x^5 + x^4 + x^2 + x + 1
x^8 + x^6 + x^5 + x^4 + x^3 + x + 1
x^8 + x^7 + x^2 + x + 1
x^8 + x^7 + x^3 + x + 1
x^8 + x^7 + x^3 + x^2 + 1
x^8 + x^7 + x^4 + x^3 + x^2 + x + 1
x^8 + x^7 + x^5 + x + 1
x^8 + x^7 + x^5 + x^3 + 1
x^8 + x^7 + x^5 + x^4 + 1
x^8 + x^7 + x^5 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^6 + x + 1
x^8 + x^7 + x^6 + x^3 + x^2 + x + 1
x^8 + x^7 + x^6 + x^4 + x^2 + x + 1
x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^6 + x^5 + x^2 + x + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1

hbghlyj

WolframAlpha 的输出是

hbghlyj

Czhang271828 发表于 2023-6-5 06:01
$\mathbb F_{p^n}$ 的特征多项式使得 $\mathbb F_p$ 分裂域为 $\mathbb F_{p^n}$ 的 $\mathbb F_p[X]$ 上多项式.

有限域上特征多项式的数量有公式吗？

hbghlyj

Czhang271828 发表于 2023-6-5 06:01
$\mathrm{GF}(9)$ 的写法过于印刷化

是的，但这是 WolframAlpha 输入采用的符号。
我也不喜欢这种符号，因为它与"生成函数"有歧义，例如将 GF(2^n) 输入 WolframAlpha，它将被解释为序列 2^n 的生成函数并输出 1/(1-2z)。

hbghlyj

Czhang271828 发表于 2023-6-5 06:01
$\mathbb F_{p^n}$ 的特征多项式使得 $\mathbb F_p$ 分裂域为 $\mathbb F_{p^n}$ 的 $\mathbb F_p[X]$ 上多项式.

请问这是否与“$\mathbb F_p$ 上的 n 次不可约多项式”相同