Polynomial evaluation over finite fields: new algorithms and complexity bounds

DOI10.1007/S00200-011-0160-6zbMATH Open1298.11110OpenAlexW2111554860MaRDI QIDQ694568FDOQ694568

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Semi-Fast Fourier Transforms over GF(2^m).
• Title not available (Why is that?)
• ON THE NUMBER OF MULTIPLICATIONS REQUIRED TO COMPUTE CERTAIN FUNCTIONS

Cited In (9)

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

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)