Back to overview

Polynomial evaluation over finite fields: new algorithms and complexity bounds

Type of publication Peer-reviewed
Publikationsform Original article (peer-reviewed)
Author Elia M., Rosenthal J., Schipani D.,
Project New Cryprosystems based on Algebra
Show all

Original article (peer-reviewed)

Journal Appl. Algebra Engrg. Comm. Comput.
Volume (Issue) 23(3-4)
Page(s) 129 - 141
Title of proceedings Appl. Algebra Engrg. Comm. Comput.
DOI 10.1007/s00200-011-0160-6

Open Access


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. Applications to the syndrome computation in the decoding of Reed-Solomon codes are highlighted.