12
$\begingroup$

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

$\endgroup$
19
  • $\begingroup$ I think you're allowing enough information to evaluate $f$ at any $n$-th root of unity in any ring at all. Methods for finding $a,b$ are probably easier to first work out for $\mathbf{Z}[\zeta_m]$ with $m \mid n$ before worrying about finite fields. $\endgroup$
    – user13113
    Aug 28, 2015 at 17:12
  • $\begingroup$ Yes, that's the point. The crux of the matter is computational complexity. $\mathbb{Z}[\zeta_n]$ is clearly impractical in the terms of this question, hence I consider finite quotients. $\endgroup$ Aug 28, 2015 at 17:14
  • 1
    $\begingroup$ $f$ should not be injective if $q>n^4$ is prime, as the curve $(f(x)-f(y))/(x-y) = 0$ will have points in $\mathbb{F}_q$ by Weil. $\endgroup$ Aug 28, 2015 at 18:00
  • 2
    $\begingroup$ This is a very preliminary thought, please let me know if it makes any sense: Suppose $n || q - 1$, and write $x^a+ x^b = x^a(1 + x^{b-a})$. The value $x^a$ is always an n-th root of unity, where as $1 + x^{b-a}$ is very likely to have its order coprime to n. Then one can actually extract the values $x^a$ and $1 + x^{b-a}$ from each evaluation. $\endgroup$
    – Hao Chen
    Aug 28, 2015 at 20:17
  • 1
    $\begingroup$ @Hao: As an extreme counterexample, suppose $q$ is prime and $n = q-1$. Then $1 + x^{b-a}$ is never going to have order coprime to $n$. Still, there may be something one can do with $(1+x^{b-a})^n$ and suitable $q$. $\endgroup$
    – user13113
    Aug 28, 2015 at 22:20

2 Answers 2

9
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ Duh, I think you're right, this works. I'm not entirely sure why I missed it, other than that I was moving too quickly. I actually had a different question at first that I simplified to this one with a similar trick. $\endgroup$ Aug 28, 2015 at 23:41
  • $\begingroup$ At least if you fix q, then problem cannot be any easier than discrete logarithm. If you know b, then it simply is the discrete logarithm problem. $\endgroup$ Aug 28, 2015 at 23:42
  • $\begingroup$ If you could send me your name by private e-mail, I'd be more than happy to thank you for this, even though you just basically caught me in a mistake. $\endgroup$ Aug 28, 2015 at 23:54
  • $\begingroup$ @GregKuperberg anything came out of this? $\endgroup$
    – user76479
    Sep 14, 2015 at 0:58
  • 1
    $\begingroup$ Yes, this paper on lens spaces: arxiv.org/abs/1509.02887 $\endgroup$ Sep 14, 2015 at 5:16
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I agree that the question is easy if $n$ factors into small prime powers. This is not the difficult end of the question, but it is a useful remark. What if $n$ is prime? $\endgroup$ Aug 28, 2015 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.