Wolfram 语言与系统参考资料中心

FiniteField

FiniteField[p,d]

给出有个元素的有限域.

FiniteField[p,f]

给出有限域，其中是中的不可约多项式.

FiniteField[p,…,rep]

使用域元素表示法 rep，可以是 "Polynomial" 或者 "Exponential".

范例

打开所有单元关闭所有单元

基本范例 (2)

表示质数域：

Wolfram Language code: ℱ = FiniteField[5, 1]

做算术：

Wolfram Language code: {ℱ[3] + ℱ[4], ℱ[2] ℱ[4]}

做多项式代数：

Wolfram Language code: Factor[2x ^ 2 + 3x + 1, Extension -> ℱ]

表示具有特征和扩张度的有限域：

Wolfram Language code: ℱ = FiniteField[17, 3]

使用多项式系数或索引指定域的元素：

Wolfram Language code: {a, b} = {ℱ[{1, 2, 3}], ℱ[123]}

做算术：

Wolfram Language code: (a ^ 2 + 2b) / (5a b - 7)

做多项式代数：

Wolfram Language code: PolynomialRemainder[x ^ 5 - 1, a x ^ 3 + b x + a b, x]

范围 (16)

表示和属性 (4)

表示一个特征为、扩张度为的有限域：

Wolfram Language code: ℱ = FiniteField[1009, 3]

找出用于构造域的不可约多项式：

Wolfram Language code: Information[ℱ, "FieldIrreducible"]

默认情况下，使用域元素的多项式表示：

Wolfram Language code: Information[ℱ, "ElementRepresentation"]

求域的其它性质：

Wolfram Language code: Information[ℱ, {"Characteristic", "ExtensionDegree", "FieldSize"}]

域加法和乘法单位元的索引为和：

Wolfram Language code: ℱ[123] - ℱ[123]

Wolfram Language code: ℱ[345] / ℱ[345]

使用自定义不可约多项式构建有限域：

Wolfram Language code: f = 2# ^ 4 + 57# ^ 3 + 43 # ^ 2 + 17# - 500&;

验证多项式是不可约的：

Wolfram Language code: IrreduciblePolynomialQ[f[x], Modulus -> 509]

表示域：

Wolfram Language code: ℱ = FiniteField[509, f, "Polynomial"]

不可约域等于指定的多项式模约化域特征：

Wolfram Language code: PolynomialMod[Information[ℱ, "FieldIrreducible"][x] - f[x], 509]

构造一个使用元素指数表示的有限域：

Wolfram Language code: ℱ = FiniteField[7, 3, "Exponential"]

用于表示域的多项式是本原多项式：

Wolfram Language code: PrimitivePolynomialQ[Information[ℱ, "FieldIrreducible"][x], 7]

域加法和乘法单位元的索引为和：

Wolfram Language code: ℱ[21] - ℱ[21]

Wolfram Language code: ℱ[32] / ℱ[32]

该域的所有非零元素都是索引为的元素的幂：

Wolfram Language code: q = Information[ℱ, "FieldSize"]

Wolfram Language code: θ = ℱ[2]

Wolfram Language code: And@@Table[ℱ[ind] == θ ^ (ind - 1), {ind, q - 1}]

代表质域：

Wolfram Language code: FiniteField[11]

Wolfram Language code: % === FiniteField[11, 1]

表示一个有 49 个元素的有限域：

Wolfram Language code: FiniteField[49]

Wolfram Language code: % === FiniteField[7, 2]

算术 (3)

在有限域中执行算术运算：

Wolfram Language code:

ℱ = FiniteField[3, 6];
{a, b} = {ℱ[123], ℱ[432]}

Wolfram Language code: {a + b, a - b, a b, a / b, a ^ 321}

有理数幂仅适用于指数分母和：

Wolfram Language code: {a ^ (1 / 3), Sqrt[a]}

对于某些域元素，平方根可能不存在：

Wolfram Language code: Sqrt[b]

算术运算将整数视为域的元素：

Wolfram Language code:

ℱ = FiniteField[19, 3];
a = ℱ[123]

Wolfram Language code: {a + 5, 7a}

有理数需要在域特征模下有效：

Wolfram Language code: a + 7 / 8

Wolfram Language code: a + 2 / 19

用 Element 决定哪些有理数可以用域元素标识：

Wolfram Language code: {Element[7 / 8, ℱ], Element[2 / 19, ℱ]}

为了比较的目的，有理数用域元素标识：

Wolfram Language code: ℱ[0] == 0

Wolfram Language code: ℱ[1] == 1

不同有限域的元素不能合并：

Wolfram Language code:

ℱ = FiniteField[389, 2];
𝒢 = FiniteField[389, 4];

Wolfram Language code: ℱ[123] - 𝒢[123]

具有相同特征和不可约域但不同元素表示的域是允许的：

Wolfram Language code: ℋ = FiniteField[389, Information[ℱ, "FieldIrreducible"], "Exponential"];

Wolfram Language code: ℱ[123] - ℋ[123]

自同构和嵌入 (2)

计算有限域元素的所有共轭：

Wolfram Language code:

ℱ = FiniteField[7, 5];
a = ℱ[123]

Wolfram Language code: conj = Table[FrobeniusAutomorphism[a, i], {i, 0, 4}]

共轭是 a 的最小多项式的根：

Wolfram Language code: f = MinimalPolynomial[a]

Wolfram Language code: f /@ conj

弗罗贝尼乌斯自同构将映射到：

Wolfram Language code: FrobeniusAutomorphism[a] == a ^ 7

计算一个有限域在另一个有限域中的嵌入：

Wolfram Language code:

𝒦 = FiniteField[29, 3];
ℱ = FiniteField[29, 6];
emb = FiniteFieldEmbedding[𝒦, ℱ]

通过嵌入映射有限域元素：

Wolfram Language code: emb[𝒦[123]]

嵌入保留算术运算：

Wolfram Language code: {a, b} = {𝒦[345], 𝒦[678]};

Wolfram Language code: emb[a + b] == emb[a] + emb[b]

Wolfram Language code: emb[a b] == emb[a]emb[b]

有限域上的多项式 (2)

在有限域上计算多项式：

Wolfram Language code:

ℱ = FiniteField[11, 3];
f = ℱ[1]x ^ 2 + ℱ[2]x + ℱ[3];
g = ℱ[12]x ^ 5 + ℱ[21]x + ℱ[33];
h = ℱ[321]x ^ 3 + ℱ[27]x ^ 2 + ℱ[53]x + ℱ[19];

展开乘积：

Wolfram Language code: fg = Expand[f g]

Wolfram Language code: gh = Expand[g h]

计算最大公因式：

Wolfram Language code: gcd = PolynomialGCD[fg, gh]

约去一个分数：

Wolfram Language code: Cancel[gcd / g]

计算商和余数：

Wolfram Language code: {q, r} = PolynomialQuotientRemainder[g, h, x]

Wolfram Language code: Expand[g - q h - r]

分解一个多项式：

Wolfram Language code: Factor[h]

计算结果：

Wolfram Language code: Resultant[f, g, x]

计算多元多项式：

Wolfram Language code: Expand[(f y + g z)(h z + 1)]

Wolfram Language code: Factor[%]

Wolfram Language code: Discriminant[f y ^ 2 + g y + h, y]

在有限域的扩张上对多项式进行因式分解：

Wolfram Language code:

ℱ = FiniteField[29, 3];
f = ℱ[12]x ^ 2 + ℱ[34]x + ℱ[56];

多项式在上是不可约的：

Wolfram Language code: Factor[f]

将嵌入更大的域中，然后对进行因式分解：

Wolfram Language code:

𝒢 = FiniteField[29, 6];
ℰ = FiniteFieldEmbedding[ℱ, 𝒢];

Wolfram Language code: Factor[f, Extension -> ℰ]

有限域上的线性代数 (4)

有限域上矩阵的积：

Wolfram Language code:

a = (⁠|                                                                                          |                                                                                          |                                                                                         |
| ---------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------- | --------------------------------------------------------------------------------------- |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {12}]    | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {23}]    | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {5, 1}] |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {16, 1}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {27, 1}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {9, 2}] |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {20, 2}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {2, 3}]  | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {3, 3}] |⁠);b = (⁠|                                                                                           |                                                                                           |
| ----------------------------------------------------------------------------------------- | ----------------------------------------------------------------------------------------- |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {7, 4}]   | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {2, 8}]   |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {26, 11}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {21, 15}] |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {16, 19}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {11, 23}] |⁠);
a.b//MatrixForm

矩阵的幂：

Wolfram Language code: MatrixPower[a, 123456789]//MatrixForm

矩阵的基本属性，包括行列式：

Wolfram Language code:

a = (⁠|                                                                                          |                                                                                          |                                                                                         |
| ---------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------- | --------------------------------------------------------------------------------------- |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {12}]    | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {23}]    | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {5, 1}] |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {16, 1}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {27, 1}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {9, 2}] |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {20, 2}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {2, 3}]  | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {3, 3}] |⁠);
Det[a]

计算逆矩阵：

Wolfram Language code: Inverse[a]//MatrixForm

验证结果：

Wolfram Language code: %.a//MatrixForm

矩阵的特征多项式：

Wolfram Language code: CharacteristicPolynomial[a, x]

验证该多项式满足凯莱-哈密顿定理：

Wolfram Language code: CoefficientList[%, x].(MatrixPower[a, #]& /@ Range[0, 3])//MatrixForm

计算矩阵的秩和零空间：

Wolfram Language code:

c = (⁠|                                                                                              |                                                                                              |                                                                                             |                                                                                               |
| -------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------- | --------------------------------------------------------------------------------------------- |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {16, 13, 1}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {25, 22, 2}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {5, 3, 4}]  | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {14, 12, 5}]  |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {23, 21, 6}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {3, 2, 8}]   | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {2, 11, 9}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {27, 16, 10}] |⁠);

Wolfram Language code: MatrixRank[c]

Wolfram Language code: NullSpace[c]//MatrixForm

Wolfram Language code: c.Transpose[%]//MatrixForm

矩阵的行约化：

Wolfram Language code: RowReduce[c]//MatrixForm

求解线性方程：

Wolfram Language code:

a = (⁠|                                                                                          |                                                                                          |                                                                                         |
| ---------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------- | --------------------------------------------------------------------------------------- |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {12}]    | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {23}]    | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {5, 1}] |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {16, 1}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {27, 1}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {9, 2}] |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {20, 2}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {2, 3}]  | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {3, 3}] |⁠);b = (⁠|                                                                                           |                                                                                           |
| ----------------------------------------------------------------------------------------- | ----------------------------------------------------------------------------------------- |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {7, 4}]   | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {2, 8}]   |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {26, 11}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {21, 15}] |
| FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {16, 19}] | FiniteFieldElement[FiniteField[29, 2 + 15*#1 + 2*#1^2 + #1^4 & , "Polynomial"], {11, 23}] |⁠);
(x = LinearSolve[a, b])//MatrixForm

验证结果：

Wolfram Language code: a.x === b

计算 a 的 LU 分解：

Wolfram Language code: {l, u, p, cn} = LUDecomposition[a]

验证分解的结果：

Wolfram Language code: l.u === p.a

利用三角矩阵的前向和后向代换重建解 x：

Wolfram Language code: x == LinearSolve[u, LinearSolve[l, p.b]]

有限域上的方程 (1)

求解有限域上的方程：

Wolfram Language code: ℱ = FiniteField[7, 5];

单变量方程：

Wolfram Language code: Solve[x ^ 5 + ℱ[123]x == ℱ[127], x]

Wolfram Language code: Reduce[x ^ 9 + 5 x + 3 == 0, x, ℱ]

线性方程组：

Wolfram Language code: Solve[ℱ[123]x + ℱ[234]y == ℱ[345] && ℱ[321]x + ℱ[432]y == ℱ[543], {x, y}]

Wolfram Language code: Reduce[ℱ[1234]x + ℱ[2345]y + ℱ[3456]z == ℱ[4567] && ℱ[1]x + ℱ[2]y + ℱ[3]z == ℱ[4], {x, y, z}]

多项式方程组：

Wolfram Language code: Solve[x ^ 2 + y ^ 2 == 3 && x ^ 5 + y ^ 5 == 5, {x, y}, ℱ]

Wolfram Language code:

Reduce[ℱ[123]x ^ 2 + ℱ[234]y ^ 3 + ℱ[345]z ^ 4 == ℱ[456] && ℱ[21]x + ℱ[32]y ^ 2 + ℱ[43]z ^ 3 == ℱ[54] && x y z == ℱ[1], {x, y, z}]

求解的实例：

Wolfram Language code: FindInstance[x ^ 2 + y ^ 2 + z ^ 2 == 21, {x, y, z}, ℱ]

Wolfram Language code: FindInstance[ℱ[321]x ^ 3 + ℱ[432]y ^ 3 + ℱ[543]z ^ 3 == ℱ[654] && x ^ 2 == ℱ[333]y z + ℱ[111], {x, y, z}, 3]

消除量词：

Wolfram Language code: Resolve[Exists[z, ℱ[111]x + ℱ[222]y + ℱ[333]z == ℱ[444] && ℱ[555]x + ℱ[666]y + ℱ[777]z == ℱ[888]]]

Wolfram Language code: 𝒦 = FiniteField[2, 5];

Wolfram Language code:

Resolve[Exists[{y, z}, 𝒦[1]x ^ 2 + 𝒦[2]y ^ 3 + 𝒦[3]z ^ 4 == 𝒦[4] && 𝒦[5]x ^ 4 + 𝒦[6]y ^ 3 + 𝒦[7]z ^ 2 == 𝒦[8] && x y z != 𝒦[0]]]

应用 (8)

执行纠错码. 汉明码将位消息编码为位序列，并且最多可以纠正一个错误：

Wolfram Language code:

m = 5;
n = 2 ^ m - 1;
k = n - m;

令为使用指数元素表示法的具有个元素的有限域，令是用于构造的不可约多项式，令为的生成器：

Wolfram Language code:

ℱ = FiniteField[2, m, "Exponential"];
f = Information[ℱ, "FieldIrreducible"][x];
θ = ℱ[{0, 1}]

编码后的消息是的系数列表，其中的系数列表是原始消息：

Wolfram Language code: encode[kbits_] := PadRight[Mod[CoefficientList[f(kbits.x ^ Range[0, k - 1]), x], 2], n]

Wolfram Language code: msg = Table[RandomInteger[], {k}]

Wolfram Language code: enc = encode[msg]

令为多项式，该多项式的系数列表是接收到的消息：

Wolfram Language code: t[nbits_, x_] := nbits.x ^ Range[0, n - 1]

如果接收到的消息没有错误，则，因此：

Wolfram Language code: t[enc, θ]

如果接收到的消息在位置包含一个错误，则，因此：

Wolfram Language code: err = ReplaceAt[enc, e_ :> 1 - e, RandomInteger[{1, n}]]

Wolfram Language code: t[err, θ]

检查并更正收到的消息：

Wolfram Language code:

correct[nbits_] := 
	With[{ep = t[nbits, θ]}, 
	If[ep == 0, 
	nbits, 
	ReplaceAt[nbits, e_ :> 1 - e, ep["Index"]]]]

Wolfram Language code: correct[err] === enc

要对消息进行解码，需要计算的系数列表：

Wolfram Language code: decode[nbits_] := PadRight[CoefficientList[PolynomialQuotient[nbits.x ^ Range[0, n - 1], f, x, Modulus -> 2], x], k]

当接收到的消息没有错误或有一个错误时，解码后的消息是正确的：

Wolfram Language code: decode[correct[enc]] === msg

Wolfram Language code: decode[correct[err]] === msg

为任意质数幂构造个正交的阶拉丁方阵. 阶拉丁方阵是一个数组，其中每一行和每一列都包含恰好个元素中的每个元素一次. 如果通过并置两个数组形成的个数对都不同，则称这对拉丁方阵是正交的：

Wolfram Language code:

q = 9;
ℱ = FiniteField[3, 2];
squares = Table[Table[(ℱ[k]ℱ[i - 1] + ℱ[j - 1])["Index"] + 1, {i, q}, {j, q}], {k, q - 1}];
MatrixForm /@ squares

验证所有数组都是拉丁方阵：

Wolfram Language code: latinQ[a_] := Union[Sort /@ Join[a, Transpose[a]]] === {Range[q]}

Wolfram Language code: latinQ /@ squares

验证所有数组对都是正交的：

Wolfram Language code: orthogonalQ[a_, b_] := Length[Union[Transpose[{Flatten[a], Flatten[b]}]]] == q ^ 2

Wolfram Language code: orthogonalQ@@@Subsets[squares, {2}]

如果时，和都是不同的，那么一个有限的整数集合是一个西顿（Sidon）集合. 对于质幂，在中构造一个个整数的西顿集合：

Wolfram Language code:

sidon[q_] := 
	Module[{ff, g}, 
	ff = FiniteField[q ^ 2, "Exponential"];
	g = ff[2];Prepend[Select[Range[q ^ 2 - 1], Mod[(g ^ # - g)["Index"] - 1, q + 1] == 0&], 1]]

Wolfram Language code:

q = 27;
a = sidon[q]

验证是长度为的西顿集合：

Wolfram Language code: Length[a] == q

Wolfram Language code: sums = Join@@Table[a[[i]] + a[[j]], {j, q}, {i, j}];

Wolfram Language code: Length[sums] == Length[Union[sums]] == q(q + 1) / 2

对于有个字母的字母表，阶的 de Bruijn 序列是字母表中个字母的循环序列，使得个字母的每个序列作为的子序列恰好出现一次. 为一个有个字母的字母表构造一个阶数为的 de Bruijn 序列，取质幂：

Wolfram Language code:

deBruijn[q_, n_] := 
	Module[{f1, f2, emb, s, p}, 
	f1 = FiniteField[q, "Exponential"];
	f2 = FiniteField[q ^ n, "Exponential"];
	emb = FiniteFieldEmbedding[f1, f2];
	s = FiniteFieldIndex[emb["Projection"][FromFiniteFieldIndex[Range[q ^ n - 1], f2]]];
	p = SequencePosition[s, Table[0, {n - 1}]][[1, 1]];
	Insert[s, 0, p]]

Wolfram Language code:

q = 8;n = 3;
s = deBruijn[q, n]

验证对于一个有个字母的字母表，是阶数为的 de Bruijn 序列：

Wolfram Language code: Sort[Partition[s, n, 1, 1]] === Tuples[Range[0, q - 1], n]

如果的所有项为或且 $H.TemplateBox[{H}, Transpose]=n I_n$ ，则矩阵是哈达玛（Hadamard）矩阵. 为任意素幂构建一个阶数为的哈达玛矩阵，其中：

Wolfram Language code:

ξ[e_] := If[Head[Sqrt[e]] === FiniteFieldElement, 1, -1]
h[0, _, _] := 1
h[_, 0, _] := 1
h[i_, j_, ff_] := If[i == j, -1, ξ[ff[j - 1] - ff[i - 1]]]

Wolfram Language code:

q = 7 ^ 3;
ℱ = FiniteField[7, 3];
(H = Table[h[i, j, ℱ], {i, 0, q}, {j, 0, q}])//MatrixPlot

Wolfram Language code: Union[Flatten[H]]

Wolfram Language code: H.Transpose[H] === (q + 1)IdentityMatrix[q + 1]

实现高级加密标准（AES）算法中使用的 Rijndael S 盒步骤. 第一部分称为 Nyberg S 盒，使用中的乘法逆：

Wolfram Language code: F256 = FiniteField[2, # ^ 8 + # ^ 4 + # ^ 3 + # + 1&]

Wolfram Language code: NybergSbox[byte_] := Piecewise[{{(F256[byte] ^ (-1))["Index"], byte != 0}}, 0]

第二部分涉及上的仿射变换：

Wolfram Language code:

F2 = FiniteField[2];
a = Map[F2, {{1, 0, 0, 0, 1, 1, 1, 1}, {1, 1, 0, 0, 0, 1, 1, 1}, {1, 1, 1, 0, 0, 0, 1, 1}, {1, 1, 1, 1, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 0, 0, 0}, {0, 1, 1, 1, 1, 1, 0, 0}, {0, 0, 1, 1, 1, 1, 1, 0}, {0, 0, 0, 1, 1, 1, 1, 1}}, {2}];
b = F2 /@ {1, 1, 0, 0, 0, 1, 1, 0};
affine[byte_] := FromDigits[Reverse[FiniteFieldIndex[a.Reverse[IntegerDigits[byte, 2, 8]] + b]], 2]

前向 S 盒由这两部分组成：

Wolfram Language code: ForwardSbox[byte_] := affine[NybergSbox[byte]]

用十六进制符号计算前向 S 盒表：

Wolfram Language code: tohex[byte_] := StringJoin@@(FromCharacterCode[If[# <= 9, # + 48, # + 87]]& /@ IntegerDigits[byte, 16, 2])

Wolfram Language code: Table[tohex[ForwardSbox[16i + j]], {i, 0, 15}, {j, 0, 15}]//MatrixForm

定义逆 S 盒变换：

Wolfram Language code:

ainv = Inverse[a];
affineinv[byte_] := FromDigits[Reverse[FiniteFieldIndex[ainv.(Reverse[IntegerDigits[byte, 2, 8]] - b)]], 2]

Wolfram Language code: InverseSbox[byte_] := NybergSbox[affineinv[byte]]

用十六进制符号计算逆 S 盒表：

Wolfram Language code: Table[tohex[InverseSbox[16i + j]], {i, 0, 15}, {j, 0, 15}]//MatrixForm

验证逆 S 盒是正 S 盒的逆：

Wolfram Language code: (InverseSbox /@ ForwardSbox /@ Range[0, 255]) === Range[0, 255]

使用 2049 位素数实现 Diffie–Hellman 公钥密码系统：

Wolfram Language code:

p = 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596248443;
ℱ = FiniteField[p];

查找域的基元元素：

Wolfram Language code: g = ℱ[PrimitiveRoot[p]]

第一个用户选择一个私钥：

Wolfram Language code: SeedRandom[1234];a = RandomInteger[{2, p - 2}]

公钥由、和组成：

Wolfram Language code: g1 = g ^ a

第二个用户选择：

Wolfram Language code: b = RandomInteger[{2, p - 2}]

要发送 2048 位信息，第二个用户发送和：

Wolfram Language code: m = RandomInteger[{1, 2 ^ 2048}]

Wolfram Language code: e = m g1 ^ b

Wolfram Language code: g2 = g ^ b

第一个用户可以通过计算恢复：

Wolfram Language code: d = e / g2 ^ a

Wolfram Language code: d["Index"] == m

实现数字签名方案. 固定一个质数，并找到的基元：

Wolfram Language code:

p = 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224143009;
Zp = FiniteField[p];
g = Zp[PrimitiveRoot[p]]

选取一个秘密整数，并公布、和：

Wolfram Language code:

SeedRandom[1234];
h = RandomInteger[{2, p - 1}];
c = g ^ h

信息的签名是一对小于并使得的正整数. 计算签名需要知道秘密整数：

Wolfram Language code:

signature[m_] := 
	Module[{k, a, b, d, r, s}, 
	k = 2;
	While[GCD[k, p - 1] != 1, k++];
	{d, {a, b}} = ExtendedGCD[k, p - 1];
	r = (g ^ k)["Index"];
	s = Mod[a(m - h r), p - 1];
	{r, s}]

签名可通过公开信息进行验证：

Wolfram Language code: verify[{r_, s_}, m_] := g ^ m == c ^ r Zp[r] ^ s

为随机生成的信息计算签名：

Wolfram Language code:

m = RandomInteger[{1, p - 1}];
{r, s} = signature[m]

验证签名：

Wolfram Language code: verify[{r, s}, m]

属性和关系 (7)

具有特征和扩张度的有限域具有个元素：

Wolfram Language code: ℱ = FiniteField[7, 10]

Wolfram Language code: Information[ℱ, "FieldSize"] == 7 ^ 10

具有特征的有限域的元素满足：

Wolfram Language code:

ℱ = FiniteField[11, 3];
{a, b} = {ℱ[123], ℱ[456]}

Wolfram Language code: {(a + b) ^ 11, a ^ 11 + b ^ 11}

因此映射是一个域自同构，称为 FrobeniusAutomorphism：

Wolfram Language code: FrobeniusAutomorphism[a] == a ^ 11

域生成器是不可约域的根：

Wolfram Language code:

ℱ = FiniteField[109, 5];
θ = ℱ[{0, 1}]

Wolfram Language code: f = Information[ℱ, "FieldIrreducible"]

Wolfram Language code: f[θ]

使用 FrobeniusAutomorphism 求的剩余根：

Wolfram Language code: Table[FrobeniusAutomorphism[θ, k], {k, 4}]

Wolfram Language code: f /@ %

具有个元素的有限域的所有元素都是的根：

Wolfram Language code:

ℱ = FiniteField[3, 5];
q = Information[ℱ, "FieldSize"]

Wolfram Language code: Union[x ^ q - x /. Table[{x -> ℱ[i]}, {i, 0, q - 1}]]

实际上，：

Wolfram Language code: Expand[Product[x - ℱ[i], {i, 0, q - 1}]]

Wolfram Language code: Coefficient[%, x, 1] == -1

在上的任何次不可约多项式都在个元素的域上具有个根：

Wolfram Language code:

ℱ = FiniteField[73, 6];
f = 9x ^ 6 + 54x ^ 2 + 42x + 11

使用 IrreduciblePolynomialQ 与 Modulusp 验证在上的不可约性：

Wolfram Language code: IrreduciblePolynomialQ[f, Modulus -> 73]

使用 Factor 与 Extensionℱ 验证 f 是线性因子在 ℱ 上的乘积：

Wolfram Language code: Factor[f, Extension -> ℱ]

使用 FiniteField[p,1] 在质数域上计算：

Wolfram Language code: ℱ = FiniteField[19, 1];

Wolfram Language code: ℱ[12] ℱ[7] + ℱ[3]

与使用 Mod 获得的结果进行比较：

Wolfram Language code: Mod[12 7 + 3, 19]

在上进行多项式计算：

Wolfram Language code: Discriminant[ℱ[4]x ^ 3 + ℱ[5]a x + ℱ[11], x]

与使用 Modulus 选项获得的结果进行比较：

Wolfram Language code: Discriminant[4x ^ 3 + 5a x + 11, x, Modulus -> 19]

使用 ToFiniteField 将整数系数转换为有限域质子域中的元素：

Wolfram Language code:

ℱ = FiniteField[29, 3];
ToFiniteField[123 + 456x + 789x ^ 2 + x ^ 3, ℱ]

FromFiniteField 将系数转换回整数：

Wolfram Language code: FromFiniteField[%, ℱ]

将系数转换为有限场元，用 t 表示场发生器：

Wolfram Language code: ToFiniteField[(t ^ 2 + 3t + 11)x + (21t + 12)y + 3t ^ 2 - 11, ℱ, t]

将有限域系数转换为 t 的多项式，其中 t 代表域发生器：

Wolfram Language code: FromFiniteField[%, ℱ, t]

Top

更多学习资源

技术支持

数据科学、金融与商业

工程

科学与技术

教育科技

教育举措

开始

提高你的技能

与我们合作

成人教育计划

青少年教育计划

欢迎阅读

FiniteField

更多信息

范例

基本范例 (2)

范围 (16)

表示和属性 (4)

算术 (3)

自同构和嵌入 (2)

有限域上的多项式 (2)

有限域上的线性代数 (4)

有限域上的方程 (1)

应用 (8)

属性和关系 (7)

文本

CMS

APA

BibTeX

BibLaTeX

	"Characteristic"	有限域的特征 p
	"ExtensionDegree"	有限域在上的扩张度 d
	"FieldSize"	域的元素个数 q=p^d
	"FieldIrreducible"	用于构造域的多项式函数 f
	"ElementRepresentation"	"Polynomial" 或 "Exponential"

FiniteField

更多信息

范例

基本范例 (2)

范围 (16)

表示和属性 (4)

算术 (3)

自同构和嵌入 (2)

有限域上的多项式 (2)

有限域上的线性代数 (4)

有限域上的方程 (1)

应用 (8)

属性和关系 (7)

参见

相关指南

历史

文本

CMS

APA

BibTeX

BibLaTeX