Polynomial interpolation and identity testing from high powers over finite fields
From MaRDI portal
Publication:1709581
DOI10.1007/s00453-016-0273-1zbMath1390.11128arXiv1502.06631MaRDI QIDQ1709581
Nitin Saxena, Marek Karpinski, Gábor Ivanyos, Igor E. Shparlinski, Miklos Santha
Publication date: 6 April 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.06631
rational function; quantum algorithm; deterministic algorithm; randomised algorithm; black-box interpolation; hidden polynomial power; nullstellensatz
68Q25: Analysis of algorithms and problem complexity
11Y16: Number-theoretic algorithms; complexity
11T06: Polynomials over finite fields
68Q12: Quantum algorithms and complexity in the theory of computing
Related Items
Values of rational functions in small subgroups of finite fields and the identity testing problem from powers, Identity testing and interpolation from high powers of polynomials of large degree over finite fields
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Concentration of points on curves in finite fields
- Polynomial values in small subgroups of finite fields
- Factorization in generalized arithmetic progressions and application to the Erdős-Szemerédi sum-product problems
- Classical and quantum function reconstruction via character evaluation
- Sharp estimates for the arithmetic Nullstellensatz
- Quantum algorithms for weighing matrices and quadratic residues
- Subgroups generated by rational functions in finite fields
- Products with variables from low-dimensional affine spaces and shifted power identity testing in finite fields
- Heights of varieties in multiprojective spaces and arithmetic Nullstellensatze
- Modern Computer Algebra
- Arithmetic Circuits: A survey of recent results and open questions
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Quantum Algorithms for Some Hidden Shift Problems
- Algorithms for Black-Box Fields and their Application to Cryptography
- Product Sets of Rationals, Multiplicative Translates of Subgroups in Residue Rings, and Fixed Points of the Discrete Logarithm
- Progress on Polynomial Identity Testing - II
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- On the Hidden Shifted Power Problem
