On the Hidden Shifted Power Problem

2011/10/04 by Bourgain, Jean, Garaev, Moubariz Z., Konyagin, Sergei V. +1 · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1110.0812

Abstract

We consider the problem of recovering a hidden element s of a finite field \F_q of q elements from queries to an oracle that for a given x∈ \F_q returns (x+s)^e for a given divisor e| q-1. We use some techniques from additive combinatorics and analytic number theory that lead to more efficient algorithms than the naive interpolation algorithm, for example, they use substantially fewer queries to the oracle.

Cited by

• Effective bounds for polynomial systems defined over the rationals

Related

• Identity Testing and Interpolation from High Powers of Polynomials of Large Degree over Finite Fields
• Polynomial Interpolation and Identity Testing from High Powers over\n Finite Fields
• Efficient Quantum Algorithm for Identifying Hidden Polynomials
• Computing e-th roots in number fields
• On Division Polynomial PIT and Supersingularity