Values of rational functions in small subgroups of finite fields and the identity testing problem from powers

DOI10.1142/S1793042120500128MaRDI QIDQ5221454zbMATH OpenOpenAlexFDO

Authors László Mérai

Publication date 26 March 2020

Published in International Journal of Number Theory (Search for Journal in Brave)

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

zbMATH Keywords

deterministic algorithmhidden polynomial poweridentity testing from powersNullstellensatz

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25)

Abstract: Motivated by some algorithmic problems, we give lower bounds on the size of the multiplicative groups containing rational function images of low-dimensional affine subspaces of a finite field~$mathbb{F}_{q^n}$ considered as a linear space over a subfield $mathbb{F}_q$. We apply this to the recently introduced algorithmic problem of identity testing of "hidden" polynomials $f$ and $g$ over a high degree extension of a finite field, given oracle access to $f(x{)}^e$ and $g(x{)}^e$

Recommendations

• Identity testing and interpolation from high powers of polynomials of large degree over finite fields
• Polynomial interpolation and identity testing from high powers over finite fields
• Products with variables from low-dimensional affine spaces and shifted power identity testing in finite fields
• Subgroups generated by rational functions in finite fields
• Polynomial values in small subgroups of finite fields

Cites work

• Algebraic function fields and codes
• An introduction to the theory of numbers. Edited and revised by D. R. Heath-Brown and J. H. Silverman. With a foreword by Andrew Wiles
• Factorization in generalized arithmetic progressions and application to the Erdős-Szemerédi sum-product problems
• Heights of varieties in multiprojective spaces and arithmetic nullstellensätze
• On the hidden shifted power problem
• Polynomial interpolation and identity testing from high powers over finite fields
• Polynomial values in small subgroups of finite fields
• Product Sets of Rationals, Multiplicative Translates of Subgroups in Residue Rings, and Fixed Points of the Discrete Logarithm
• Products with variables from low-dimensional affine spaces and shifted power identity testing in finite fields
• Subgroups generated by rational functions in finite fields

Cited in

(4)

• Polynomial interpolation and identity testing from high powers over finite fields
• Identity testing and interpolation from high powers of polynomials of large degree over finite fields
• Products with variables from low-dimensional affine spaces and shifted power identity testing in finite fields
• A Special Case of Rational Identity Testing and the Brešar-Klep Theorem.

This page was built for publication: Values of rational functions in small subgroups of finite fields and the identity testing problem from powers

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