ゴッパ符号(ゴッパふごう、英: Goppa code)または代数幾何符号(だいすうきかふごう、英: algebraic geometric code)は、有限体
上の代数曲線 X を使って構築される線型符号である。V. D. Goppa が考案した。場合によっては、興味深い極値特性(extremal property)を示すことがある。
ゴッパ符号は、
上で定義された非特異の代数多様体 X のいくつかの有理点
- P1, P2, ..., Pn
を使って構築でき、X 上の因子 G は
とは互いに素な有理点からのみ得られる。リーマン=ロッホの定理によれば、因子 G に対応して、一意な有限次元のベクトル空間
が存在する。このベクトル空間は
の関数空間の部分空間である。
このような情報を使って構築されるゴッパ符号には、2種類のものが存在する。
関数型符号[編集]
曲線 X、因子 G、有理点群
から構築される関数型符号は以下の通りである。
上の L(G) の固定基底
- f1, f2, ..., fk
について、対応する
内のゴッパ符号は、
- (fi(P1), fi(P2), ..., fi(Pn))
というベクトルによって
上に分布する。等価的に
![{\displaystyle \alpha :L(G)\longrightarrow \mathbb {F} ^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bfbadc0aa002caf524d11c4daedc4f571e9ac53b)
の像としても定義され、ここで f は
で定義される。
上記で定義された
を使って因子を
とする。通常ゴッパ符号は C(D,G) と記述される。
次に、C 上の因子 D と符号のパラメータの関係を示す。l(D) という記法は L(D) の次元を意味する。
命題 ゴッパ符号 C(D,G) の次元は
![{\displaystyle k=l(G)-l(G-D)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/107786b47f40fe3b5db084db73dc6eedb6d28e4b)
であり、2つの符号語間の最小ハミング距離は
![{\displaystyle d\geq n-\deg(G)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8cf78b1a48a85b1b14e41b0b031ced9fdef500b6)
である。
証明
![{\displaystyle C(D,G)\cong L(G)/\ker(\alpha )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b385f26eea2cb32264ffba30003fd3b3498b5cae)
なので、次が成り立つことを示さなければならない。
![{\displaystyle \ker(\alpha )=L(G-D)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fae11550b5e66f0463c8228f8c562c48025b7cff)
と仮定する。すると
なので、
である。従って
である。逆に
と仮定する。すると
![{\displaystyle P_{i}<G,i=1,\dots ,n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35b34105bef7e4d8db2db22ee78b5ce690859d86)
なので
![{\displaystyle \mathrm {div} (f)>D}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c8635ff7f1bb59b6d24dddd58dbc0bba93427e17)
である(G は
で問題を解かないので、代わりに f でそれをする必要がある)。従って
![{\displaystyle f(P_{i})=0,i=1,\dots ,n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/939e3459bcd929920921d7f0513df82a01ce83e1)
となる。
を示すため、
のハミング重みを d とする。これはつまり、
個の
(例えば
)について
であることを意味する。従って
であり、
![{\displaystyle \mathrm {div} (f)+G-P_{i_{1}}-\dots -P_{i_{n-d}}>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7be9290dbb68318ff35d3a35cd16a72af5a7c994)
である。
![{\displaystyle \deg(\mathrm {div} (f))=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e9125958bc3d02b8b4bd04a5f7e4cda0241fb05)
であることに着目して両辺の次数をとると
![{\displaystyle \deg(G)-(n-d)\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1f5c534994ca963fd2c89871ce947011d5c68d0)
が得られる。従って
![{\displaystyle d\geq n-\deg(G)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8cf78b1a48a85b1b14e41b0b031ced9fdef500b6)
である。Q.E.D.
留数型符号[編集]
留数型符号は関数型符号の双対として定義されるか、
における何らかの関数の留数として定義される。
暗号理論において、ゴッパ符号はマックエリス暗号で使われている。
一般にゴッパ符号は性質の良い線型符号と見なされ、
![{\displaystyle {n^{k}} \choose {\log _{2}n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f31c5caf3ca7ac3fb7b3ffd118ca8c0cdf831a5e)
の誤りを訂正可能である。また復号も簡単で、ユークリッドの互除法とベールカンプ=マッシー法を使えばよい。
外部リンク[編集]