A probabilistic algorithm for verifying polynomial middle product in linear time

DOI10.1016/j.ipl.2018.06.014zbMath1478.68455OpenAlexW2852668904WikidataQ129577688 ScholiaQ129577688MaRDI QIDQ1799565

Pascal Giorgi

Publication date: 19 October 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-01538453/file/giorgi-certification-midp.pdf

zbMATH Keywords

probabilistic algorithmpolynomial multiplicationdesign of algorithmcomputation on polynomials

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Symbolic computation and algebraic computation (68W30)

Related Items (1)

Polynomial modular product verification and its implications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Newton's method and FFT trading
• A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
• A probabilistic remark on algebraic program testing
• On short multiplications and divisions
• Middle-product Learning with Errors
• The middle product algorithm. I: Speeding up the division and square root of power series
• A long note on Mulders' short product
• Modern Computer Algebra
• Faster algorithms for the square root and reciprocal of power series
• Faster Polynomial Multiplication over Finite Fields
• Online order basis algorithm and its impact on the block Wiedemann algorithm
• Fast Probabilistic Algorithms for Verification of Polynomial Identities

This page was built for publication: A probabilistic algorithm for verifying polynomial middle product in linear time