Fast evaluation of polynomials by rational preparation

DOI10.1002/CPA.3160250405MaRDI QIDQ5648442zbMATH OpenOpenAlexWikidataFDO

Authors Michael O. Rabin, Shmuel Winograd

Publication date 1972

Published in Communications on Pure and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/cpa.3160250405

zbMATH Keywords

asymptotic resultsevaluation of monic polynomialsmatrix polynomialsnumber of additions and multiplicationspolynomials in several variablespreconditioningrational functionssolution of high-order algebraic equations

Mathematics Subject Classification ID

Polynomials in number theory (11C08) Polynomials (irreducibility, etc.) (11R09) Number-theoretic algorithms; complexity (11Y16) Symbolic computation and algebraic computation (68W30)

Recommendations

• Simple proofs of lower bounds for polynomial evaluation
• scientific article; zbMATH DE number 1405666
• A new approach to fast polynomial interpolation and multipoint evaluation
• Evaluation of a rational function
• Evaluation of Polynomials Using the Structure of the Coefficients

Cited in

(15)

• An efficient raster evaluation method for univariate polynomials
• Fast methods for computing the values of the derivatives of a rational function
• Evaluating Bernstein-Rabin-Winograd polynomials
• On rate-1 and beyond-the-birthday bound secure online ciphers using tweakable block ciphers
• Tweakable enciphering schemes using only the encryption function of a block cipher
• Modes of operations for encryption and authentication using stream ciphers supporting an initialisation vector
• \textsf{FAST}: disk encryption and beyond
• A trade-off between collision probability and key size in universal hashing using polynomials
• Fast evaluation of trigonometric polynomials from hyperbolic crosses
• A new multi-linear universal hash family
• Evaluation of Polynomials Using the Structure of the Coefficients
• Simple proofs of lower bounds for polynomial evaluation
• Polynomial hashing over prime order fields
• Efficient instances of docked double decker with AES, and application to authenticated encryption
• Algorithms for accurate, validated and fast polynomial evaluation

This page was built for publication: Fast evaluation of polynomials by rational preparation

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