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.
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.
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.
| Item Type: | Journal Article, not_refereed, original work |
|---|---|
| Communities & Collections: | 07 Faculty of Science > Institute of Mathematics |
| Dewey Decimal Classification: | 510 Mathematics |
| Scopus Subject Areas: | Physical Sciences > Algebra and Number Theory
Physical Sciences > Applied Mathematics |
| Language: | English |
| Date: | November 2012 |
| Deposited On: | 25 Jan 2013 15:20 |
| Last Modified: | 23 Jan 2022 23:27 |
| Publisher: | Springer |
| ISSN: | 0938-1279 |
| OA Status: | Green |
| Publisher DOI: | https://doi.org/10.1007/s00200-011-0160-6 |
Elia, M