Polynomial modular product verification and its implications

DOI10.1016/J.JSC.2022.08.011MaRDI QIDQ2100047zbMATH OpenOpenAlexFDO

Authors Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray

Publication date 21 November 2022

Published in Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

bit complexitydense and sparse polynomialsmodular multiplicationpolynomial multiplicationverification algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx) Algorithms in computer science (68Wxx)

Recommendations

• A probabilistic algorithm for verifying polynomial middle product in linear time
• A note on probabilistically verifying integer and polynomial products
• Chunky and equal-spaced polynomial multiplication
• On the choice of a multiplication algorithm for polynomials and polynomial matrices
• On the bit-complexity of sparse polynomial and series multiplication

Cites work

• A note on probabilistically verifying integer and polynomial products
• A probabilistic algorithm for verifying polynomial middle product in linear time
• A probabilistic remark on algebraic program testing
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Approximate formulas for some functions of prime numbers
• Chunky and equal-spaced polynomial multiplication
• Computing Fibonacci numbers (and similarly defined functions) in log time
• Essentially optimal sparse polynomial multiplication
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
• Handbook of finite fields
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 3635490 (Why is no real title available?)
• Integer multiplication in time \(O(n\log n)\)
• Introduction to algorithms.
• Modern computer algebra
• Nearly Optimal Sparse Polynomial Multiplication
• On fast multiplication of polynomials over arbitrary algebras
• On the bit-complexity of sparse polynomial and series multiplication
• On the complexity of multivariate blockwise polynomial multiplication
• On the Evaluation of Powers
• Output-sensitive algorithms for sumset and sparse polynomial multiplication
• Parallel sparse polynomial multiplication using heaps
• Powers of tensors and fast matrix multiplication
• Sparse polynomial division using a heap
• Structured FFT and TFT: symmetric and lattice polynomials
• Verifying candidate matches in sparse and wildcard matching
• What can (and can't) we do with sparse polynomials?

Cited in

(1)

• Fast interpolation and multiplication of unbalanced polynomials

This page was built for publication: Polynomial modular product verification and its implications

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