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

2019/07/04 by László Mérai, Mérai, László
Computer Science · #Coding theory and cryptography #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.1907.02302

openalex publication_date 2019/07/04 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28

Abstract

Motivated by some algorithmic problems, we give lower bounds on the size of\nthe multiplicative groups containing rational function images of\nlow-dimensional affine subspaces of a finite field~ mathbbF_qⁿ\nconsidered as a linear space over a subfield mathbbF_q. We apply this to\nthe recently introduced algorithmic problem of identity testing of "hidden"\npolynomials f and g over a high degree extension of a finite field, given\noracle access to f(x)^e and g(x)^e\n

Related

• Polynomial Values in Small Subgroups of Finite Fields
• Subgroups Generated by Rational Functions in Finite Fields
• Identity Testing and Interpolation from High Powers of Polynomials of Large Degree over Finite Fields
• Polynomial Values in Subfields and Affine Subspaces of Finite Fields
• Sparsity of curves and additive and multiplicative expansion of rational maps over finite fields