Header

UZH-Logo

Maintenance Infos

Polynomial evaluation over finite fields: new algorithms and complexity bounds


Elia, M; Rosenthal, J; Schipani, D (2012). Polynomial evaluation over finite fields: new algorithms and complexity bounds. Applicable Algebra in Engineering, Communication and Computing, 23(3-4):129-141.

Abstract

An efficient evaluation method is described for polynomials in finite fields. Its complexity is shown to be lower than that of standard techniques, when the degree of the polynomial is large enough compared to the field characteristic. Specifically, if n is the degree of the polynomiaI, the asymptotic complexity is shown to be O(root n), versus O(n) of classical algorithms. Applications to the syndrome computation in the decoding of Reed-Solomon codes are highlighted.

Abstract

An efficient evaluation method is described for polynomials in finite fields. Its complexity is shown to be lower than that of standard techniques, when the degree of the polynomial is large enough compared to the field characteristic. Specifically, if n is the degree of the polynomiaI, the asymptotic complexity is shown to be O(root n), versus O(n) of classical algorithms. Applications to the syndrome computation in the decoding of Reed-Solomon codes are highlighted.

Statistics

Citations

1 citation in Web of Science®
2 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

67 downloads since deposited on 25 Jan 2013
4 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, not refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Language:English
Date:November 2012
Deposited On:25 Jan 2013 15:20
Last Modified:07 Dec 2017 18:24
Publisher:Springer
ISSN:0938-1279
Publisher DOI:https://doi.org/10.1007/s00200-011-0160-6

Download

Download PDF  'Polynomial evaluation over finite fields: new algorithms and complexity bounds'.
Preview
Content: Published Version
Language: English
Filetype: PDF
Size: 171kB
View at publisher