$\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?

nevergoing to have order coprime to $n$. Still, there may be something one can do with $(1+x^{b-a})^n$ and suitable $q$. $\endgroup$14more comments