Afficher la notice abrégée

hal.structure.identifierAlgorithmic number theory for cryptology [TANC]
dc.contributor.authorAUGOT, Daniel
hal.structure.identifierAlgorithmic number theory for cryptology [TANC]
dc.contributor.authorBARBIER, Morgan
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorCOUVREUR, Alain
dc.date.accessioned2024-04-04T02:27:41Z
dc.date.available2024-04-04T02:27:41Z
dc.date.issued2010-12-15
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/190037
dc.description.abstractNous étudions le décodage en liste des codes alternants, dont notamment les codes de Goppa classiques. La considération majeure est de prendre en compte la taille de l'alphabet, qui influe sur la capacité de correction, surtout dans le cas de l'alphabet binaire. Cela revient à comparer la borne de Johnson que nous appelons générique, à la borne de Johnson que nous appelons $q$-aire, qui prend en compte la taille $q$ du corps. Cette différence est d'autant plus sensible que $q$ est petit. Essentiellement, le cas le plus favorable est celui de l'alphabet binaire pour lequel on peut augmenter significativement le rayon du décodage en liste. Et ce, d'autant plus que la distance minimale relative construite du code alternant binaire est proche de $1/2$. Bien que le résultat annoncé ici, à savoir le rayon de décodage en liste des codes de Goppa binaires, soit nouveau, il peut assez facilement être déduit de sources relativement peu connues (V.~ Guruswami, R.~M.~Roth and I.~Tal, R~.M.~Roth) et dont les auteurs n'ont apparemment pas pensé à aborder les codes de Goppa binaires. Seul D.~J.~Bernstein a traité le décodage en liste des codes de Goppa dans une prépublication. Les références sont données dans l'introduction. Nous proposons un contenu autonome, et aussi une analyse de la complexité de l'algorithme étudié, qui est quadratique en la longueur $n$ du code, si on se tient à distance du rayon relatif de décodage maximal, et en $O(n^7)$ pour le rayon de décodage maximal.
dc.description.abstractEnWe study the list-decoding problem of alternant codes, with the notable case of classical Goppa codes. The major consideration here is to take into account the size of the alphabet, which shows great influence on the list-decoding radius. This amounts to compare the \emph{generic} Johnson bound to the \emph{$q$-ary} Johnson bound. This difference is important when $q$ is very small. Essentially, the most favourable case is $q=2$, for which the decoding radius is greatly improved, notably when the relative minimum distance gets close to $1/2$. Even though the announced result, which is the list-decoding radius of binary Goppa codes, is new, it can be rather easily made up from previous sources (V.~ Guruswami, R.~M.~Roth and I.~Tal, R~.M.~Roth), which may be a little bit unknown, and in which the case of binary Goppa codes has apparently not been thought at. Only D.~J.~Bernstein treats the case of binary Goppa codes in a preprint. References are given in the introduction. We propose an autonomous treatment and also a complexity analysis of the studied algorithm, which is quadratic in the blocklength $n$, when decoding at some distance of the relative maximum decoding radius, and in $O(n^7)$ when reaching the maximum radius.
dc.language.isoen
dc.subject.enerror correcting codes
dc.subject.enlist decoding
dc.subject.enbinary Goppa codes
dc.title.enList-decoding of binary Goppa codes up to the binary Johnson bound
dc.typeRapport
dc.subject.halInformatique [cs]/Théorie de l'information [cs.IT]
dc.subject.halMathématiques [math]/Théorie de l'information et codage [math.IT]
dc.identifier.arxiv1012.3439
bordeaux.page23
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.type.institutionINRIA
bordeaux.type.reportrr
hal.identifierinria-00547106
hal.version1
hal.audienceNon spécifiée
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00547106v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2010-12-15&rft.spage=23&rft.epage=23&rft.au=AUGOT,%20Daniel&BARBIER,%20Morgan&COUVREUR,%20Alain&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée