Classical and Quantum Function Reconstruction in Finite Fields. - Igor Shparlinski

Motivated by applications to pseudorandom generators and stream ciphers, we consider the problem of reconstruction of a function $f: F_p -> R$ defined on elements of a finite field and with real values. Examples includes: $f(x) = (x+s/p)$, the Legendre symbol, or $f(x) = MSB_k(g(x))$, $k$ most significant bits of the reduction of $g(x)$, where $g: F_p -> F_p$. In this problems the shift $s$, the functions $g$ (and sometimes the prime $p$) are unknown. We will give a short survey of known classical and quantum algorithms and try to exhibit some main ideas behind the proofs. mainly of number theoretic nature. We will also outline some open questions and directions for further research.