ゴッパ符号

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

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

P₁, P₂, ..., P_n

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

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

関数型符号

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

[math]\mathbb{F}_q[/math] 上の L(G) の固定基底

f₁, f₂, ..., f_k

について、対応する [math]\mathbb{F}_q^n[/math] 内のゴッパ符号は、

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

というベクトルによって [math]\mathbb{F}_q[/math] 上に分布する。等価的に

[math]\alpha : L(G) \longrightarrow \mathbb{F}^n[/math]

の像としても定義され、ここで f は [math]f \longmapsto (f(P_1), \dots ,f(P_n))[/math] で定義される。

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

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

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

[math]k = l(G) - l(G-D)[/math]

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

[math]d \geq n - \deg(G)[/math]

である。

証明

[math]C(D,G) \cong L(G)/\ker(\alpha) [/math]

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

[math]\ker(\alpha)=L(G-D) [/math]

[math]f \in \ker(\alpha)[/math] と仮定する。すると [math]f(P_i)=0, i=1, \dots ,n[/math] なので、[math]\mathrm{div}(f) \gt D [/math] である。従って [math]f \in L(G-D)[/math] である。逆に [math]f \in L(G-D)[/math] と仮定する。すると

[math]P_i \lt G, i=1, \dots ,n[/math]

なので

[math]\mathrm{div}(f)\gt D[/math]

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

[math]f(P_i)=0, i=1, \dots ,n[/math]

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

[math]\mathrm{div}(f)+G-P_{i_1} - \dots - P_{i_{n-d}}\gt 0[/math]

である。

[math]\deg(\mathrm{div}(f))=0[/math]

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

[math]\deg(G)-(n-d) \geq 0[/math]

が得られる。従って

[math]d \geq n - \deg(G)[/math]

である。Q.E.D.

留数型符号

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

応用

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

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

[math] {n^k} \choose {\log_2 n}[/math]

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

外部リンク

• 代数幾何符号の歩み 水野弘文（イオンド大学）、2004年
• An undergraduate thesis on Algebraic Geometric Coding Theory
• 代数幾何符号に関する研究 上原剛（愛媛大学）、2001年