Learning the exponents in a sum of two modular roots of unity $\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?
 A: 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$.
A: To get things started, a straightforward algorithm is to use $\mathbb{Z} / (2^n - 1)$, and read $a$ and $b$ off of the only two bits set in the smallest positive representative of $f(2)$.
Of course, this is a very large modulus — but if $n$ factors as a product of small prime powers $q$, then we can use this method for $\mathbb{Z} / (2^q - 1)$ to obtain $a \bmod q$ and $b \bmod q$. (if a single digit is set, then $a \equiv b \bmod q$ and you can still obtain it)
Then for each pair of prime powers $q$ and $q'$, you know the sets $\{ a \bmod q, b \bmod q \}$ and $\{ a \bmod q', b \bmod q' \}$, and you have to figure out which elements of each pair go with each other. This can be done by using the same method to find $\{ a \bmod (qq'), b \bmod (qq') \}$.
Once you know which classes go together, the Chinese Remainder Theorem lets you reassemble $a \bmod n$ and $b \bmod n$.

Naturally, if you have a better algorithm for the mod-$q$ residues of $a$ and $b$, you could use the same high level algorithm described above, but with using the better algorithm in place of the stated one.
