ゴッパ符号

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

P1, P2, ..., Pn

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

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

関数型符号[編集]

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

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

f1, f2, ..., fk

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

(fi(P1), fi(P2), ..., fi(Pn))

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

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

の像としても定義され、ここで ff \longmapsto (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 \geq n - \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{div}(f) > D である。従って f \in L(G-D) である。逆に f \in L(G-D) と仮定する。すると

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

なので

\mathrm{div}(f)> D

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

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

となる。d \geq n - \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{div}(f)+G-P_{i_1} - \dots - P_{i_{n-d}}> 0

である。

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

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

\deg(G)-(n-d) \geq 0

が得られる。従って

d \geq n - \deg(G)

である。Q.E.D.

留数型符号[編集]

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

応用[編集]

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

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

 {n^k} \choose {\log_2 n}

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

外部リンク[編集]