ゴッパ符号

出典: フリー百科事典『ウィキペディア(Wikipedia)』

ゴッパ符号(ゴッパふごう、英: Goppa code)または代数幾何符号(だいすうきかふごう、英: algebraic geometric code)は、有限体 ${\displaystyle \mathbb {F} _{q}}${\displaystyle \mathbb {F} _{q}} 上の代数曲線 X を使って構築される線型符号である。V. D. Goppa が考案した。場合によっては、興味深い極値特性(extremal property)を示すことがある。

ゴッパ符号は、${\displaystyle \mathbb {F} _{q}}${\displaystyle \mathbb {F} _{q}} 上で定義された非特異の代数多様体 X のいくつかの有理点

P₁, P₂, ..., P_n

を使って構築でき、X 上の因子 G は ${\displaystyle P_{i}}${\displaystyle P_{i}} とは互いに素な有理点からのみ得られる。リーマン=ロッホの定理によれば、因子 G に対応して、一意な有限次元のベクトル空間 ${\displaystyle L(G)}${\displaystyle L(G)} が存在する。このベクトル空間は ${\displaystyle X}${\displaystyle X} の関数空間の部分空間である。

このような情報を使って構築されるゴッパ符号には、2種類のものが存在する。

曲線 X、因子 G、有理点群 ${\displaystyle P_{i}}${\displaystyle P_{i}} から構築される関数型符号は以下の通りである。

${\displaystyle \mathbb {F} _{q}}${\displaystyle \mathbb {F} _{q}} 上の L(G) の固定基底

f₁, f₂, ..., f_k

について、対応する ${\displaystyle \mathbb {F} _{q}^{n}}${\displaystyle \mathbb {F} _{q}^{n}} 内のゴッパ符号は、

(f_i(P₁), f_i(P₂), ..., f_i(P_n))

というベクトルによって ${\displaystyle \mathbb {F} _{q}}${\displaystyle \mathbb {F} _{q}} 上に分布する。等価的に

${\displaystyle \alpha :L(G)\longrightarrow \mathbb {F} ^{n}}${\displaystyle \alpha :L(G)\longrightarrow \mathbb {F} ^{n}}

の像としても定義され、ここで f は ${\displaystyle f\longmapsto (f(P_{1}),\dots ,f(P_{n}))}${\displaystyle f\longmapsto (f(P_{1}),\dots ,f(P_{n}))} で定義される。

上記で定義された ${\displaystyle P_{i}}${\displaystyle P_{i}} を使って因子を ${\displaystyle D=P_{1}+P_{2}+\cdots +P_{n}}${\displaystyle D=P_{1}+P_{2}+\cdots +P_{n}} とする。通常ゴッパ符号は C(D,G) と記述される。

次に、C 上の因子 D と符号のパラメータの関係を示す。l(D) という記法は L(D) の次元を意味する。

命題 ゴッパ符号 C(D,G) の次元は

${\displaystyle k=l(G)-l(G-D)}${\displaystyle k=l(G)-l(G-D)}

であり、2つの符号語間の最小ハミング距離は

${\displaystyle d\geq n-\deg(G)}${\displaystyle d\geq n-\deg(G)}

である。

証明

${\displaystyle C(D,G)\cong L(G)/\ker(\alpha )}${\displaystyle C(D,G)\cong L(G)/\ker(\alpha )}

なので、次が成り立つことを示さなければならない。

${\displaystyle \ker(\alpha )=L(G-D)}${\displaystyle \ker(\alpha )=L(G-D)}

${\displaystyle f\in \ker(\alpha )}${\displaystyle f\in \ker(\alpha )} と仮定する。すると ${\displaystyle f(P_{i})=0,i=1,\dots ,n}${\displaystyle f(P_{i})=0,i=1,\dots ,n} なので、${\displaystyle \mathrm {div} (f)>D}${\displaystyle \mathrm {div} (f)>D} である。従って ${\displaystyle f\in L(G-D)}${\displaystyle f\in L(G-D)} である。逆に ${\displaystyle f\in L(G-D)}${\displaystyle f\in L(G-D)} と仮定する。すると

${\displaystyle P_{i}<G,i=1,\dots ,n}${\displaystyle P_{i}<G,i=1,\dots ,n}

なので

${\displaystyle \mathrm {div} (f)>D}${\displaystyle \mathrm {div} (f)>D}

である(G は ${\displaystyle -D}${\displaystyle -D} で問題を解かないので、代わりに f でそれをする必要がある)。従って

${\displaystyle f(P_{i})=0,i=1,\dots ,n}${\displaystyle f(P_{i})=0,i=1,\dots ,n}

となる。${\displaystyle d\geq n-\deg(G)}${\displaystyle d\geq n-\deg(G)} を示すため、${\displaystyle \alpha (f)}${\displaystyle \alpha (f)} のハミング重みを d とする。これはつまり、${\displaystyle n-d}${\displaystyle n-d} 個の ${\displaystyle P_{i}}${\displaystyle P_{i}} (例えば ${\displaystyle P_{i_{1}},\dots ,P_{i_{n-d}}}${\displaystyle P_{i_{1}},\dots ,P_{i_{n-d}}})について ${\displaystyle f(P_{i})=0}${\displaystyle f(P_{i})=0} であることを意味する。従って ${\displaystyle f\in L(G-P_{i_{1}}-\dots -P_{i_{n-d}})}${\displaystyle f\in L(G-P_{i_{1}}-\dots -P_{i_{n-d}})} であり、

${\displaystyle \mathrm {div} (f)+G-P_{i_{1}}-\dots -P_{i_{n-d}}>0}${\displaystyle \mathrm {div} (f)+G-P_{i_{1}}-\dots -P_{i_{n-d}}>0}

である。

${\displaystyle \deg(\mathrm {div} (f))=0}${\displaystyle \deg(\mathrm {div} (f))=0}

であることに着目して両辺の次数をとると

${\displaystyle \deg(G)-(n-d)\geq 0}${\displaystyle \deg(G)-(n-d)\geq 0}

が得られる。従って

${\displaystyle d\geq n-\deg(G)}${\displaystyle d\geq n-\deg(G)}

である。Q.E.D.

留数型符号は関数型符号の双対として定義されるか、${\displaystyle P_{i}}${\displaystyle P_{i}} における何らかの関数の留数として定義される。

暗号理論において、ゴッパ符号はマックエリス暗号で使われている。

一般にゴッパ符号は性質の良い線型符号と見なされ、

${\displaystyle {n^{k}} \choose {\log _{2}n}}${\displaystyle {n^{k}} \choose {\log _{2}n}}

の誤りを訂正可能である。また復号も簡単で、ユークリッドの互除法とベールカンプ=マッシー法を使えばよい。

• Henning Stichtenoth、新妻弘(訳):「代数関数体と符号理論」、共立出版、ISBN 978-4-320-11045-8 (2013年8月25日).

• 水野弘文「代数幾何符号の歩み (符号と暗号の代数的数理)」『数理解析研究所講究録』第1361巻、京都大学数理解析研究所、2004年4月、143-151頁、CRID 1050282677085218432、hdl:2433/25267 、ISSN 1880-2818。 
• An undergraduate thesis on Algebraic Geometric Coding Theory
• 上原剛「代数幾何符号に関する研究」(PDF)『数式処理』第9巻第2号、日本数式処理学会、2002年、32-41頁、CRID 1520572358731480448、ISSN 09191410。 

「https://ja.wikipedia.org/w/index.php?title=ゴッパ符号&oldid=103162457」から取得

カテゴリ:

• 誤り検出訂正
• 数学に関する記事
• 代数曲線
• 符号理論
• 有限体

隠しカテゴリ:

• ISBNマジックリンクを使用しているページ