$\newcommand{\Z}{\mathbb{Z}}$
Suppose that $n$ is a large and known integer (say, with 100 digits) and that you are given access to a function


$$f(x) = x^a + x^b$$


with unknown exponents $a,b \in \Z/n$. You are allowed to evaluate $f$ on any cyclic ring $\Z/q$ with a solution to $x^n = 1$, where $x$ and $q$ are of your choosing as long as $\gcd(n,q) = 1$. You are allowed several evaluations with distinct $x$ and $q$. For simplicity you can assume that $q$ is a product of primes (which may not be distinct) that are all 1 mod $n$ and that $x$ is an $n$th root of unity, since for instance $n$ could be prime. Linnik's effective version of Dirichlet's theorem says that there is a ready supply of values of $q$.


My ultimate question: What algorithms in number theory are available to find the exponents $a$ and $b$? Of course you can find them in principle with one enormous value of $q$. The question is what is known about efficiency as a function of $d$, the number of digits of $n$. The problem is like discrete logarithm, but more complicated because there are two terms.


I am also interested in this more tangible question: Can you find a moderate value of $q$ such that $f$ is injective? Heuristically, $O(d)$ digits should be enough. I am thinking that GRH implies that $f$ is strictly injective for most values of $q$ with $O(d)$ digits --- is this true? Can you prove unconditionally $f$ that is usually injective in this range, or usually mostly injective?



Learning the exponents in a sum of two modular roots of unity
If you can compute discrete logarithms, there's an easy solution:


$$ f(\zeta) = \zeta^a + \zeta^b $$
$$ f(\zeta^2) = (\zeta^a)^2 + (\zeta^b)^2 $$


is a system of two equations in the quantities $\zeta^a$ and $\zeta^b$, allowing you to solve for $(\zeta^a, \zeta^b)$. There will be 2 solutions, but that just reflects the symmetry between $a$ and $b$.


