Goppa code[1][2][3]

Description

Let \( G(z) \) be a polynomial describing a projective plane curve with coefficients from \( GF(q^m) \) for some fixed integer \(m\). Let \( L \) be a finite subset of the extension field \( GF(q^m) \) where \(q\) is prime, meaning \( L = \{\alpha_1, \cdots, \alpha_n\} \) is a subset of nonzero elements of \( GF(q^m) \). A Goppa code \( \Gamma(L,G) \) is an \([n,k,d]\) linear code consisting of all vectors \(a = a_1, \cdots, a_n\) such that \( R_a(z) =0 \) modulo \(G(z)\), where \( R_a(z) = \sum_{i=1}^n \frac{a_i}{z - \alpha_i} \).

Protection

The length \( n = |L| \) , dimension \( k \geq n-mr \) where \( r = \text{deg} G(z) \), and the minimum distance \( d \geq r +1 \).

Rate

There exist Goppa codes defined over larger alphabets that meet the Gilbert-Varshamov, or GV, bound.

Decoding

Algebraic decoding algorithms [4].If \( \text{deg} G(z) = 2t \) , then there exists a \(t\)-correcting algebraic decoding algorithm for \( \Gamma(L,G) \).

Realizations

The binary version \( (q=2) \) is commonly used in post-quantum cryptosystems such as the McElise cryptosystem [5].

Notes

GAP function GoppaCode(G,L) takes in a polynomial \(G\) that satisfies the necessary conditions for a Goppa code and a list \(L\) that contains elements in \(GF(q)\) that are not roots of \(G\). It returns a Goppa code.

Parents

Cousin

Zoo code information

Internal code ID: goppa

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: goppa

Cite as:
“Goppa code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/goppa
BibTeX:
@incollection{eczoo_goppa, title={Goppa code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/goppa} }
Permanent link:
https://errorcorrectionzoo.org/c/goppa

References

[1]
V. D. Goppa, "A new class of linear error-correcting codes", Probl. Peredach. Inform., vol. 6, no. 3, pp. 24-30, Sept. 1970.
[2]
V. D. Goppa, "Rational representation of codes and (Lg) codes", Probl. Peredach. Inform., vol. 7, no. 3, pp. 41-49, Sept. 1971.
[3]
E. Berlekamp, “Goppa codes”, IEEE Transactions on Information Theory 19, 590 (1973). DOI
[4]
N. Patterson, “The algebraic decoding of Goppa codes”, IEEE Transactions on Information Theory 21, 203 (1975). DOI
[5]
H. Janwa and O. Moreno, “McEliece public key cryptosystems using algebraic-geometric codes”, Designs, Codes and Cryptography 8, (1996). DOI

Cite as:

“Goppa code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/goppa

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/q-ary_digits/goppa.yml.