An algorithm for list decoding number field codes

Jean-François Biasse; Guillaume Quintin

hal-00712441, version 1

An algorithm for list decoding number field codes

Jean-François Biasse (, ) ^1, 2, 3, Guillaume Quintin () ^1, 4

Résumé : We present an algorithm for list decoding codewords of algebraic number field codes in polynomial time. This is the first explicit procedure for decoding number field codes whose construction were previously described by Lenstra [12] and Guruswami [8]. We rely on a new algorithm for computing the Hermite normal form of the basis of an OK -module due to Biasse and Fieker [2] where OK is the ring of integers of a number field K.

1 : Laboratoire d'informatique de l'école polytechnique (LIX)
CNRS : UMR7161 – Polytechnique - X
2 : LFANT (INRIA Bordeaux - Sud-Ouest)
INRIA – Université de Bordeaux – CNRS : UMR5251
3 : Department of Computer Science [Calgary] (CPSC)
University of Calgary
4 : TANC (INRIA Saclay - Ile de France)
INRIA – Polytechnique - X – CNRS : UMR7161

hal-00712441, version 1
http://hal.inria.fr/hal-00712441
oai:hal.inria.fr:hal-00712441
Contributeur : Guillaume Quintin <>
Soumis le : Mercredi 27 Juin 2012, 10:01:01
Dernière modification le : Mercredi 27 Juin 2012, 10:16:34

Voir la fiche détaillée

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Documents sans référence de publication (Preprint)</head>
<biblStruct type="article" xml:id="hal-00712441"><analytic>
<author><persName><forename>Jean-François</forename><surname>Biasse</surname></persName>
<affiliation>
<orgName type="laboratory">LIX</orgName>
<orgName type="team">Laboratoire d'informatique de l'école polytechnique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7161</orgName>
<orgName type="institution">Polytechnique - X</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Bordeaux - Sud-Ouest</orgName>
<orgName type="team">LFANT</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Bordeaux</orgName>
<orgName type="institution">CNRS : UMR5251</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">CPSC</orgName>
<orgName type="team">Department of Computer Science [Calgary]</orgName>
<country>CA</country>
<orgName type="institution">University of Calgary</orgName>
</affiliation>
</author>
<author><persName><forename>Guillaume</forename><surname>Quintin</surname></persName>
<affiliation>
<orgName type="laboratory">LIX</orgName>
<orgName type="team">Laboratoire d'informatique de l'école polytechnique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7161</orgName>
<orgName type="institution">Polytechnique - X</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Saclay - Ile de France</orgName>
<orgName type="team">TANC</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Polytechnique - X</orgName>
<orgName type="institution">CNRS : UMR7161</orgName>
</affiliation>
</author>
<title type="main" level="a">An algorithm for list decoding number field codes</title></analytic><monogr><imprint/></monogr><idno type="HALid">http://hal.inria.fr/hal-00712441</idno><idno type="HALFile">http://hal.inria.fr/hal-00712441/PDF/bare_conf.pdf</idno></biblStruct>
</listBibl>
</listBibl>