Polynomial evaluation over finite fields: new algorithms and complexity bounds

DOI10.1007/S00200-011-0160-6MaRDI QIDQ694568zbMATH OpenOpenAlexFDO

Authors Michele Elia, Joachim Rosenthal, Davide Schipani

Publication date 13 December 2012

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.4772

zbMATH Keywords

finite fieldsReed-Solomon codespolynomial evaluationsyndrome computation

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Finite fields (field-theoretic aspects) (12E20) Cyclic codes (94B15)

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

Recommendations

• scientific article; zbMATH DE number 177888
• STACS 2005
• Faster polynomial multiplication over finite fields
• A Lower Bound on the Complexity of Polynomial Multiplication over Finite Fields
• Multiplicative complexity of polynomial multiplication over finite fields

Cites work

• scientific article; zbMATH DE number 3910296 (Why is no real title available?)
• scientific article; zbMATH DE number 4023423 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 3628385 (Why is no real title available?)
• scientific article; zbMATH DE number 1026591 (Why is no real title available?)
• scientific article; zbMATH DE number 3276110 (Why is no real title available?)
• ON THE NUMBER OF MULTIPLICATIONS REQUIRED TO COMPUTE CERTAIN FUNCTIONS
• On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
• Semi-Fast Fourier Transforms over GF(2^m).

Cited in

(9)

• Enhanced public key security for the McEliece cryptosystem
• Evaluation of Polynomials Using the Structure of the Coefficients
• Homomorphic polynomial evaluation using Galois structure and applications to BFV bootstrapping
• Good reduction of puiseux series and complexity of the Newton-Puiseux algorithm over finite fields
• New polynomial-time algorithms for Camion bases
• Trace-based cryptanalysis of cyclotomic \(R_{q, 0} \times R_q\)-PLWE for the non-split case
• scientific article; zbMATH DE number 5244190 (Why is no real title available?)
• On evaluating multivariate polynomials over finite fields
• Lower bounds of complexity for polarized polynomials over finite fields

This page was built for publication: Polynomial evaluation over finite fields: new algorithms and complexity bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q694568)