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

Jérémy Berthomieu; Grégoire Lecerf; Guillaume Quintin

doi:10.1007/s00200-013-0200-5

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

Jérémy Berthomieu
, Grégoire Lecerf
, Guillaume Quintin

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	413-443
Number of pages	31
Journal	Applicable Algebra in Engineering, Communication and Computing
Volume	24
Issue number	6
DOIs	https://doi.org/10.1007/s00200-013-0200-5
Publication status	Published - 1 Dec 2013

Keywords

Galois ring
Guruswami-Sudan algorithm
List decoding
Polynomial root finding

Access to Document

10.1007/s00200-013-0200-5

Cite this

@article{aef2ad8033ac4f5d9edf724b42e4e38d,

title = "Polynomial root finding over local rings and application to error correcting codes",

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 = "Galois ring, Guruswami-Sudan algorithm, List decoding, Polynomial root finding",

author = "J{\'e}r{\'e}my Berthomieu and Gr{\'e}goire Lecerf and Guillaume Quintin",

year = "2013",

month = dec,

day = "1",

doi = "10.1007/s00200-013-0200-5",

language = "English",

volume = "24",

pages = "413--443",

journal = "Applicable Algebra in Engineering, Communication and Computing",

issn = "0938-1279",

number = "6",

}

TY - JOUR

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

AU - Berthomieu, Jérémy

AU - Lecerf, Grégoire

AU - Quintin, Guillaume

PY - 2013/12/1

Y1 - 2013/12/1

N2 - 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.

AB - 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.

KW - Galois ring

KW - Guruswami-Sudan algorithm

KW - List decoding

KW - Polynomial root finding

U2 - 10.1007/s00200-013-0200-5

DO - 10.1007/s00200-013-0200-5

M3 - Article

AN - SCOPUS:84890117914

SN - 0938-1279

VL - 24

SP - 413

EP - 443

JO - Applicable Algebra in Engineering, Communication and Computing

JF - Applicable Algebra in Engineering, Communication and Computing

IS - 6

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this