Sparse interpolation over finite fields via low-order roots of unity

DOI10.1145/2608628.2608671zbMath1325.68261arXiv1401.4744OpenAlexW1991852511MaRDI QIDQ3452373

Daniel S. Roche, Andrew Arnold, Mark W. Giesbrecht

Publication date: 11 November 2015

Published in: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

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

zbMATH Keywords

complexityrandomizationfinite fieldsstraight-line programsparse interpolation

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Monte Carlo methods (65C05) Number-theoretic algorithms; complexity (11Y16) Numerical interpolation (65D05) Polynomials over finite fields (11T06) Interpolation in approximation theory (41A05) Randomized algorithms (68W20)

Related Items (6)

Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ Faster sparse multivariate polynomial interpolation of straight-line programs ⋮ Sparse polynomial interpolation based on derivatives ⋮ Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs ⋮ On the evaluation of some sparse polynomials ⋮ Sparse interpolation in terms of multivariate Chebyshev polynomials

Uses Software

• Jordan

Cites Work

• An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
• Cylindrical algebraic decomposition using validated numerics
• The Jordan Curve Theorem, Formally and Informally
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Definability and decision problems in arithmetic
• Unnamed Item
• Unnamed Item

This page was built for publication: Sparse interpolation over finite fields via low-order roots of unity