List decoding for binary Goppa codes

D.J. Bernstein

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

    18 Citations (Scopus)


    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 languageEnglish
    Title of host publicationCoding and Cryptology (Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings)
    EditorsY.M. Chee
    Place of PublicationBerlin
    ISBN (Print)978-3-642-20900-0
    Publication statusPublished - 2011

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    Dive into the research topics of 'List decoding for binary Goppa codes'. Together they form a unique fingerprint.

    Cite this