ゴッパ符号

ゴッパ符号（ゴッパふごう、テンプレート:Lang-en-short）または代数幾何符号（だいすうきかふごう、テンプレート:Lang-en-short）は、有限体 ${𝔽}_q$ 上の代数曲線 X を使って構築される線型符号である。V. D. Goppa が考案した。場合によっては、興味深い極値特性（extremal property）を示すことがある。

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

P₁, P₂, ..., P_n

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

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

関数型符号

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

${𝔽}_q$ 上の L(G) の固定基底

f₁, f₂, ..., f_k

について、対応する ${𝔽}_q^n$ 内のゴッパ符号は、

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

というベクトルによって ${𝔽}_q$ 上に分布する。等価的に

$\alpha :L(G)⟶{𝔽}^n$

の像としても定義され、ここで f は $f⟼(f(P_1),\dots ,f(P_n))$ で定義される。

上記で定義された $P_i$ を使って因子を $D=P_1+P_2+\cdots +P_n$ とする。通常ゴッパ符号は C(D,G) と記述される。

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

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

$k=l(G)-l(G-D)$

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

$d\ge n-\mathrm{deg}(G)$

である。

証明

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

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

$\ker (\alpha )=L(G-D)$

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

$P_i<G,i=1,\dots ,n$

なので

$\mathrm{d}\mathrm{i}\mathrm{v}(f)>D$

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

$f(P_i)=0,i=1,\dots ,n$

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

$\mathrm{d}\mathrm{i}\mathrm{v}(f)+G-P_{i_1}-\dots -P_{i_{n-d}}>0$

である。

$\mathrm{deg}(\mathrm{d}\mathrm{i}\mathrm{v}(f))=0$

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

$\mathrm{deg}(G)-(n-d)\ge 0$

が得られる。従って

$d\ge n-\mathrm{deg}(G)$

である。Q.E.D.

留数型符号

留数型符号は関数型符号の双対として定義されるか、$P_i$ における何らかの関数の留数として定義される。

応用

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

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

$(\genfrac{}{}{0ex}{}{n^k}{{\log }_{2}n})$

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

関連図書

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

外部リンク

• テンプレート:Cite journal
• An undergraduate thesis on Algebraic Geometric Coding Theory
• テンプレート:Cite journal