Wolfram言語＆システムドキュメントセンター

FiniteField

FiniteField[p,d]

個の元からなる有限体を与える．

FiniteField[p,f]

がの既約多項式である有限体を与える．

FiniteField[p,…,rep]

"Polynomial"または"Exponential"の体の元表現 rep を使う．

詳細

有限体はガロア(Galois)体としても知られている．
有限体は，代数計算，暗号学，符号化理論，組合せ論，代数幾何学，整数論，有限幾何学にしばしば用いられる．
体は，4つの算術演算+，-，*，÷がすべてある代数系である．有限体は，素数と正の整数について個の元を持つことができる．
番目の元はすべてのについてとなる加法の単位元で，番目の元はすべてのについてとなる乗法の単位元を与える．

FiniteFieldElement[,k]または[k]を使って番目の元が入手できる．これはと表示される．
同じ体にあるFiniteFieldElementオブジェクトは算術操作によって自動的に結合される．
有限体からの係数を持つ多項式には，PolynomialGCD，Factor，Expand，PolynomialQuotientRemainder，Resultantのような多項式操作を使うことができる．有限体からの係数を持つ有理関数には，TogetherおよびCancelを使うことができる．
Det，Inverse，RowReduce，NullSpace，MatrixRank，LinearSolveのような線形代数操作は，有限体からの項を持つ行列に使うことができる．
SolveおよびReduceを使って方程式系を有限体上で解くことができる．
FiniteFieldは"Polynomial"と"Exponential"の異なる2つの表現 rep をサポートする．
"Polynomial"表現は複素数のデカルト表現に似た表現で，加算と減算は簡単だが乗算と除算は少々難しくなる．
表現　次数 d の既約多項式を使って商を持つ体を識別する：
の各元は多項式として表される．基底がのベクトルと考えることもできる．
列挙　元は辞書的順序の逆順に列挙される．
,,…,,…,
操作　かつとすると以下になる．
かつ
は (PolynomialRemainder) を法として簡約されて次数になる．（. ）で乗法の逆元は拡張多項式の最大公約数を使って計算される．は既約なので，．したがって，多項式とについて拡張多項式の最大公約数からが得られる．を法として簡約するとになる．したがってである．
"Exponential"表現は複素数の極表現に似た表現で，乗算と除算は簡単だが加算と減算は少々難しくなる．
表現　"Polynomial"表現におけるように，この表現も次数 d の既約多項式を使うが，は原始的でもなければならない．が原始的なので，のベキはの中の以外のすべての元を表す．
が乗法について巡回群なので，この表現は巡回群表現としても知られている．
列挙　元は指数順に列挙される．
, , , …, , …,
操作　かつとすると以下になる．
$u *v=alpha^(TemplateBox[{{(, {i, +, j}, )}, {(, {q, -, 1}, )}}, Mod])$ かつ
反転するととなる．加法と減法についてはにはとなるような簡単な規則はなく，体のサイズがで線形な参照テーブルに格納されている．これによってデータ格納という費用はかかるが操作が速くなる．これはまた"Exponential"表現は大きい体には適していないことも意味している．
表現間の現実的な違いは次の通りである．
"Polynomial"の作成には時間がかからず，余分なメモリも使わない．大きい体に使えるが操作は若干遅くなる．
"Exponential"の作成には若干時間がかかり，体の大きさに比例して余分なメモリも必要となる．小さい体に使えて操作は若干速い．
Information[FiniteField[…], prop]は有限体の特性 prop を与える．次は指定可能な特性である．

	"Characteristic"	有限体の標数 p
	"ExtensionDegree"	上の有限体の拡大次数 d
	"FieldSize"	体の元の数 q=p^d
	"FieldIrreducible"	体の構築に使われた多項式関数 f
	"ElementRepresentation"	"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

フロベニウス(Frobenius)自己同型はをに写像する：

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)

エラー訂正コードを実装する．ハミングコードはビットのメッセージをビットシーケンスで符号化し，エラーを1つ修正することができる：

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, θ]

受信したメッセージの位置にエラーが1つ含まれていればであり，したがってである：

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]

受信したメッセージのエラーが1つ以下の場合，復号化されたメッセージは正しい：

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

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

任意の素数ベキについて，次数の直交ラテン方陣を構築する．次数のラテン方陣は，各行各列が要素中の各1要素を厳密に1回含む配列である．2つの配列を並置して構成されたペアがすべて異なる場合，そのラテン方陣のペアは直交すると言われる：

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集合である．の個の整数の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]

が長さのSidon集合であることを確認する：

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列は，文字の各の列がの循環列に厳密に1回現れるようなアルファベットの文字の循環列である．文字のアルファベットの次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-Box Step」を実装する．「Nyberg S-Box」と呼ばれる最初の部分はにおける乗法の逆元を使用する：

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

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

2番目の部分には上のアフィン変換が含まれる：

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]

Forward S-Boxは2つの部分からなる：

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

Forward S-Boxの表を16進法で計算する：

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-Box変換を定義する：

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-Box表を16進法で計算する：

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

逆S-BoxがForward S-Boxの逆であることを確認する：

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

Diffie–Hellman公開鍵の暗号システムを2049ビットの素数で実装する：

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

2番目のユーザはを選ぶ：

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

2048ビットのメッセージを送るために，2番目のユーザはとを送る：

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

その他のラーニングリソース

テクニカルサポート

データサイエンス，金融，ビジネス

工学

科学とテクノロジー

教育のためのテクノロジー

教育イニシアチブ

使い始める

Grow Your Skills

Wolframと繋がる

大人用の教育プログラム

若者のための教育プログラム

読む

FiniteField

詳細

例題

例 (2)

スコープ (16)

表現と特性 (4)

算術操作 (3)

自己同型と埋込み (2)

有限体上の多項式 (2)

有限体上の線形代数 (4)

有限体上の方程式 (1)

アプリケーション (8)

特性と関係 (7)

テキスト

CMS

APA

BibTeX

BibLaTeX

FiniteField

詳細

例題

例 (2)

スコープ (16)

表現と特性 (4)

算術操作 (3)

自己同型と埋込み (2)

有限体上の多項式 (2)

有限体上の線形代数 (4)

有限体上の方程式 (1)

アプリケーション (8)

特性と関係 (7)

関連項目

関連するガイド

履歴

テキスト

CMS

APA

BibTeX

BibLaTeX