有限体
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/08/05 22:43 UTC 版)
有限体(ゆうげんたい、英語:finite field)とは、代数学において、有限個の元からなる体、すなわち四則演算が定義され閉じている有限集合のことである。主に計算機関連の分野においては、発見者であるエヴァリスト・ガロアに因んでガロア体あるいはガロア域(ガロアいき、Galois field)などとも呼ぶ[1]。
- ^ a b c d van der Waerden 2003, Section 6.7.
- ^ Lidl & Niederreiter 1997, Theorem 2.21.
- ^ Lidl & Niederreiter 1997, Theorem 2.35.
有限体
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/11/10 05:38 UTC 版)
「離散フーリエ変換 (一般)」の記事における「有限体」の解説
環として有限体 F = G F ( q ) {\displaystyle F=GF(q)} ( q {\displaystyle q} は素数のべき乗)を考えた場合には、 単位元の原始n乗根の存在は自動的に n {\displaystyle n} が q − 1 {\displaystyle q-1} を割り切ることを意味する。 これは、各元の位数は体 F {\displaystyle F} の乗法群のサイズを必ず割り切り、乗法群のサイズは q − 1 {\displaystyle q-1} であることから言える。 これは、特に n = 1 + 1 + ⋯ + 1 ⏟ n t i m e s {\displaystyle n=\underbrace {1+1+\cdots +1} _{n\ {\rm {times}}}} が乗法逆元を持つことを保証し、式(3)における 1 n {\displaystyle {\frac {1}{n}}} はその逆元である。 G F ( q ) {\displaystyle GF(q)} 上での離散フーリエ変換の応用として、符号理論におけるリード・ソロモン符号やBCH符号の復号がある。これは、円分高速フーリエ変換といった効率の良いアルゴリズムによって実行可能である。
※この「有限体」の解説は、「離散フーリエ変換 (一般)」の解説の一部です。
「有限体」を含む「離散フーリエ変換 (一般)」の記事については、「離散フーリエ変換 (一般)」の概要を参照ください。
有限体
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/05/25 08:44 UTC 版)
詳細は「有限体」を参照 任意の有限体 K に対し、その加法群 (K, +) は素数位数の巡回群の冪であり、乗法群 (K*, ⋅) は巡回群である。
※この「有限体」の解説は、「有限アーベル群」の解説の一部です。
「有限体」を含む「有限アーベル群」の記事については、「有限アーベル群」の概要を参照ください。
有限体
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/07/18 03:21 UTC 版)
詳細は「有限体」を参照 素数による商体 ℤ/pℤ の構成は他の構造へ一般化される。情報処理において、数は n ビットでコードされる(つまり、数は 0 と 1 からなる長さ n の数列に対応する)。それは二元体 F2 上の n-次元ベクトル空間のベクトル[要曖昧さ回避]と見なすことができる。この構造はしばしば F2 に係数を持つ次数が m より真に小さい多項式全体の成す空間と見なされる。乗法について閉じているためには、この空間は次数 n の適当な多項式 f で割られなければならない。その多項式 f が既約(素数に対応するもの)であるとき、得られる構造は位数 2n の有限体になる。数 a modulo 2n と多項式 P modulo f はよく似ており、事実 a = ∑ i = 0 n − 1 a i 2 i and P = ∑ i = 0 n − 1 α i X i ( a i , α i ∈ F 2 ) {\displaystyle a=\sum _{i=0}^{n-1}a_{i}2^{i}\quad {\text{ and }}\quad P=\sum _{i=0}^{n-1}\alpha _{i}X^{i}\quad (a_{i},\alpha _{i}\in \mathbf {F} _{2})} のように書ける。 用例の一つは F2 上の疑似乱数生成器である。そのような生成器は例えば携帯電話での音声通信の文脈でストリーム暗号 A5/1 によって使われる。これは線形帰還シフトレジスタ (LFSR) の後ろの成分を持つ。F2 の元の長さ n の二つの有限列として、係数列および初期化列が ( c 1 , … , c n ) and ( u 0 , … , u n − 1 ) {\displaystyle (c_{1},\dots ,c_{n})\quad {\text{ and }}\quad (u_{0},\dots ,u_{n-1})} で与えられるとき、LFSRは疑似乱数列 (uj) を線形回帰数列 u j = ∑ i = 1 n c i u j − i ( j ≥ n ) {\displaystyle u_{j}=\sum _{i=1}^{n}c_{i}u_{j-i}\quad (j\geq n)} によって得る。係数列はしばしば固定される。ゆえに鍵は、整数 a modulo 2n で表される初期化列 a = ∑ i = 0 n − 1 u i 2 i {\displaystyle a=\sum _{i=0}^{n-1}u_{i}2^{i}} を与える。得られた結果は周期的だが、係数列を適切に選べば周期は 2n – 1 と非常に長くなる。この状況は、 R = 1 − ∑ i = 1 n c i X i {\displaystyle R=1-\sum _{i=1}^{n}c_{i}X^{i}} で与えられる「帰還多項式」R が巡回群 (F2n)* の生成元の最小多項式であるときに生じる。
※この「有限体」の解説は、「合同算術」の解説の一部です。
「有限体」を含む「合同算術」の記事については、「合同算術」の概要を参照ください。
有限体
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/04/15 01:15 UTC 版)
有限体 F について、その位数は素数 p の冪 q = pf であるとする。このとき、有限体 F の零元 0 以外の元は単位元 1 の q − 1 乗根として得られる。すなわち F ∖ { 0 } = { x ∈ F p ¯ ∣ x q − 1 − 1 = 0 } {\displaystyle F\smallsetminus \{0\}=\{x\in {\overline {\mathbb {F} _{p}}}\mid x^{q-1}-1=0\}} が成り立つ。ここで F p ¯ {\displaystyle {\overline {\mathbb {F} _{p}}}} は位数 p の有限体 F p {\displaystyle \mathbb {F} _{p}} の代数的閉包である。あるいは F = { x ∈ F p ¯ ∣ x q − x = 0 } {\displaystyle F=\{x\in {\overline {\mathbb {F} _{p}}}\mid x^{q}-x=0\}} と記しても同じことである。
※この「有限体」の解説は、「冪根」の解説の一部です。
「有限体」を含む「冪根」の記事については、「冪根」の概要を参照ください。
- 有限体のページへのリンク