# List decoding for binary Goppa codes

D.J. Bernstein

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

13 Citations (Scopus)

### Abstract

This paper presents a Patterson-style list-decoding algorithm for classical irreducible binary Goppa codes. The algorithm corrects, in polynomial time, approximately $n - \sqrt{n(n-2t-2)}$ errors in a length-n classical irreducible degree-t binary Goppa code. Compared to the best previous polynomial-time list-decoding algorithms for the same codes, the new algorithm corrects approximately $t^2/2n$ extra errors.
Original language English Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings) Y.M. Chee Berlin Springer 62-80 978-3-642-20900-0 https://doi.org/10.1007/978-3-642-20901-7_4 Published - 2011

### Publication series

Name Lecture Notes in Computer Science 6639 0302-9743

Binary codes
Decoding
Polynomials

### Cite this

Bernstein, D. J. (2011). List decoding for binary Goppa codes. In Y. M. Chee (Ed.), Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings) (pp. 62-80). (Lecture Notes in Computer Science; Vol. 6639). Berlin: Springer. https://doi.org/10.1007/978-3-642-20901-7_4
Bernstein, D.J. / List decoding for binary Goppa codes. Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings). editor / Y.M. Chee. Berlin : Springer, 2011. pp. 62-80 (Lecture Notes in Computer Science).
title = "List decoding for binary Goppa codes",
abstract = "This paper presents a Patterson-style list-decoding algorithm for classical irreducible binary Goppa codes. The algorithm corrects, in polynomial time, approximately $n - \sqrt{n(n-2t-2)}$ errors in a length-n classical irreducible degree-t binary Goppa code. Compared to the best previous polynomial-time list-decoding algorithms for the same codes, the new algorithm corrects approximately $t^2/2n$ extra errors.",
author = "D.J. Bernstein",
year = "2011",
doi = "10.1007/978-3-642-20901-7_4",
language = "English",
isbn = "978-3-642-20900-0",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "62--80",
editor = "Y.M. Chee",
booktitle = "Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings)",

}

Bernstein, DJ 2011, List decoding for binary Goppa codes. in YM Chee (ed.), Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings). Lecture Notes in Computer Science, vol. 6639, Springer, Berlin, pp. 62-80. https://doi.org/10.1007/978-3-642-20901-7_4

List decoding for binary Goppa codes. / Bernstein, D.J.

Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings). ed. / Y.M. Chee. Berlin : Springer, 2011. p. 62-80 (Lecture Notes in Computer Science; Vol. 6639).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - List decoding for binary Goppa codes

AU - Bernstein, D.J.

PY - 2011

Y1 - 2011

N2 - This paper presents a Patterson-style list-decoding algorithm for classical irreducible binary Goppa codes. The algorithm corrects, in polynomial time, approximately $n - \sqrt{n(n-2t-2)}$ errors in a length-n classical irreducible degree-t binary Goppa code. Compared to the best previous polynomial-time list-decoding algorithms for the same codes, the new algorithm corrects approximately $t^2/2n$ extra errors.

AB - This paper presents a Patterson-style list-decoding algorithm for classical irreducible binary Goppa codes. The algorithm corrects, in polynomial time, approximately $n - \sqrt{n(n-2t-2)}$ errors in a length-n classical irreducible degree-t binary Goppa code. Compared to the best previous polynomial-time list-decoding algorithms for the same codes, the new algorithm corrects approximately $t^2/2n$ extra errors.

U2 - 10.1007/978-3-642-20901-7_4

DO - 10.1007/978-3-642-20901-7_4

M3 - Conference contribution

SN - 978-3-642-20900-0

T3 - Lecture Notes in Computer Science

SP - 62

EP - 80

BT - Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings)

A2 - Chee, Y.M.

PB - Springer

CY - Berlin

ER -

Bernstein DJ. List decoding for binary Goppa codes. In Chee YM, editor, Coding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings). Berlin: Springer. 2011. p. 62-80. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-20901-7_4