Polynomial evaluation over finite fields: new algorithms and complexity bounds |
| |
Authors: | Michele Elia Joachim Rosenthal Davide Schipani |
| |
Affiliation: | 1. Politecnico di Torino, Turin, Italy 2. University of Zurich, Zurich, Switzerland
|
| |
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(sqrt{n})}$ , versus O(n) of classical algorithms. Applications to the syndrome computation in the decoding of Reed-Solomon codes are highlighted. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|