Polynomial root finding over local rings and application to error correcting codes

Jérémy Berthomieu 1 Grégoire Lecerf 2 Guillaume Quintin 3, 2
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
2 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
3 GRACE - Geometry, arithmetic, algorithms, codes and encryption
Inria Saclay - Ile de France
Abstract : This article is devoted to algorithms for computing all the roots of a univariate polynomial with coefficients in a complete commutative Noetherian unramified regular local domain, which are given to a fixed common finite precision. We study the cost of our algorithms, discuss their practical performances, and apply our results to the Guruswami and Sudan list decoding algorithm over Galois rings.
Keywords : 94B05 12Y05 Galois ring List decoding Guruswami-Sudan algorithm Polynomial root finding
Type de document :
Article dans une revue
Applicable Algebra in Engineering, Communication and Computing, Springer Verlag, 2013, 24 (6), pp.413-443. 〈10.1007/s00200-013-0200-5〉
Liste complète des métadonnées

Littérature citée [45 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00642075
Contributeur : Guillaume Quintin <>
Soumis le : vendredi 20 décembre 2013 - 17:27:58
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : vendredi 21 mars 2014 - 09:26:04

Fichier

main36.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

INRIA | LIX | X-LIX | X | PARISTECH | UPMC | LIP6 | X-DEP-INFO

Citation

Jérémy Berthomieu, Grégoire Lecerf, Guillaume Quintin. Polynomial root finding over local rings and application to error correcting codes. Applicable Algebra in Engineering, Communication and Computing, Springer Verlag, 2013, 24 (6), pp.413-443. 〈10.1007/s00200-013-0200-5〉. 〈hal-00642075v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

658

Téléchargements de fichiers

427

Contact


archive-ouverte@inria.fr