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

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$