generator - 寻找有限域的生成元

Question

如何找到具有 f(x) 的有限域 Fp[x]/f(x) 的生成元是 Fp 上的不可约多项式。

输入：p（素数），n（正数），f（不可约多项式）
输出：g（生成器）

我有p = 2，n =3，f = x^3 + x + 1
我是新手，所以我不知道从哪里开始。
你有什么解决办法吗？请逐步帮助我

score 0 · Accepted Answer

要找到域 GF(p^n) 的生成器（原始元素）α(x)，从 α(x) = x + 0 开始，然后尝试更高的值，直到找到原始元素 α(x)。

对于较小的场，可以进行蛮力测试以验证 α(x) 的幂将生成场的每个非零数。

cnt = 0
m = 1
do
    cnt = cnt + 1
    m = (m*α)%f(x)
while (m != 1)
if cnt == (p^n-1) then α(x) is a generator for GF(p^n).

对于具有更大域的更快方法，找到 p^n-1 的所有素因子。让 q = 任何这些主要因素。如果 α(x) 是 GF(p^n) 的生成器，那么在 GF(p^n) 中运行时：

α(x)^(p^n-1) % f(x)     == 1
α(x)^((p^n-1)/q) % f(x) != 1, for all q that are prime factors of p^n-1

在这种情况下，GF(2^3) 是一个 3 位字段，因为 2^3-1 = 7，这是素数，所以它只是两个测试，以十六进制显示：x^3 + x + 1 = b (hex)

α(x)^7 % b == 1
α(x)^1 % b != 1
α(x) can be any of {2,3,4,5,6,7} = {x,x+1,x^2,...,x^2+x+1}

作为另一个例子，考虑 GF(2^4)，f(x) = x^4 + x^3 + x^2 + x + 1 (hex 1f)。2^4-1 = 15的质因数是3和5，15/3 = 5和15/5 = 3。所以三个检验是：

α(x)^f % 1f == 1
α(x)^5 % 1f != 1
α(x)^3 % 1f != 1
α(x) can be any of {3,5,6,7,9,a,b,e}

对于更大的领域，找到 p^n-1 的所有素因数需要特殊的算法和大数数学。Wolfram alpha 最多可以处理 2^128-1：

该网页可以分解大量数字，并包含解释和源代码：

要测试 α(x)^(large number) = 1 或 != 1，请在 GF(p^n) 中执行数学运算时通过重复平方使用取幂。

对于 p^n 大于 2^32（40 亿）的大字段，使用上述测试搜索 α(x) = x 的原始多项式。

1 回答 1