Publication: Polynomial evaluation over finite fields: new algorithms and complexity bounds
Polynomial evaluation over finite fields: new algorithms and complexity bounds
Date
Date
Date
Citations
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. https://doi.org/10.1007/s00200-011-0160-6
Abstract
Abstract
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.
Additional indexing
Creators (Authors)
- Elia, M
- Rosenthal, J
- Schipani, D
Journal/Series Title
Journal/Series Title
Journal/Series Title
Volume
Volume
Volume
Number
Number
Number
Page range/Item number
Page range/Item number
Page range/Item number
Page end
Page end
Page end
Item Type
Item Type
Item Type
In collections
Language
Language
Language
Publication date
Publication date
Publication date
Date available
Date available
Date available
ISSN or e-ISSN
ISSN or e-ISSN
ISSN or e-ISSN
OA Status
OA Status
OA Status
Publisher DOI
Citations
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. https://doi.org/10.1007/s00200-011-0160-6
