2
$\begingroup$

Supposing the product form $n=\prod_{i=1}^np_i^{e_i}$ is given with every prime $p_i$ and integer $e_i$ known and given $d\in\Bbb Z$ and $h\in\Bbb Z_n$ with $g^d=h\bmod p$ what is the complexity of finding $g$?

Is there an $O((\log(nd))^c)$ algorithm? $d$ is as high as $n^{1/2}$ in my case when $n=p$.

The best result I found is here https://www.ma.utexas.edu/users/voloch/Preprints/roots.pdf, but it is exponential in $d$. I am surprised this problem cannot have polynomial complexity.

Can we use $ad+b\phi(n)=1$? Then $h^{a}=c\bmod n\implies c^d=h^{ad}=h^{1-b\phi(n)}=h\bmod n$ and so $g=c$ holds. Am I right? How about for other $d$th roots?

Updates By comments below it looks like trick I mention will work iff $\mathsf{gcd}(d,\phi(n))=1$ and in that case it would be deterministic polynomial time. Or else nothing is known.

$\endgroup$
16
  • 1
    $\begingroup$ It's easy to work modulo prime powers and then combine results using CRT. In partucular, if you have one $d$-th power root $c$ modulo $p^k$, then all roots are computed as $c\cdot r^{i\cdot\varphi(p^k)/G}$, where $r$ is a primitive root modulo $p^k$, $G=\gcd(\varphi(p^k),d)$, and $i=0,1,\dots,G-1$ (so there are $G$ roots total). $\endgroup$ Oct 18 '16 at 20:12
  • 1
    $\begingroup$ No deterministic polynomial-time algorithm is known even for computing square roots modulo primes. $\endgroup$ Oct 19 '16 at 18:33
  • 1
    $\begingroup$ @EmilJeřábek But there are probabilistic ones, and deterministic ones under GRH, so I don't think this says anything about the intrinsic difficulty of the algorithmic problem; it only says something about the difficulty of proving the correct complexity of these algorithms. $\endgroup$
    – Aurel
    Oct 19 '16 at 21:08
  • $\begingroup$ @EmilJeřábek what about the trick I have written when $n$ is prime? $\endgroup$
    – Turbo
    Oct 20 '16 at 12:01
  • $\begingroup$ Find $a,b$ such that $ad+b\phi(p)=1\bmod p$ holds. We want $g$ such that $g^d = h\bmod p$ where $h,p$ are given. Claim $h^a=g\bmod p$. Proof: $h^{ad}=g^d\bmod p$ and $h^{ad}=h^{1-b\phi(p)}\bmod p=h\bmod p$ and so $g^d=h\bmod p$. QED. $\endgroup$
    – Turbo
    Oct 20 '16 at 12:08
1
$\begingroup$

Not a complete answer, but here is a partial reduction of the problem, that yields a better complexity than your reference with respect to $d$.

First, you probably know about the related Discrete Logarithm Problem (DLP): given a cyclic group $G$ with generator $g$ and an element $x\in G$, find an integer $k$ such that $g^k=x$. There are algorithms to solve this problem in an arbitrary such group in time $|G|^{1/2}$. In $G=\mathbb{F}_p^\times$, there are heuristic algorithms to solve it in subexponential time, and in practice you might want to use one of these in some cases. The DLP in $G=\mathbb{Z}/N\mathbb{Z}$ is trivial.

Your problem is weaker: given an abelian group $G$, an integer $d$ and an element $x\in G$, determine whether $x$ is a $d$-th power in $G$ and find a $d$-th root. Clearly if you can solve the DLP, then you can solve the power problem.

Note that if you have an exact sequence $$ 1 \to H \to G \to Q \to 1 $$ where you can compute images and preimages in polynomial time, then you can reduce the power problem in polynomial time to the same problem in $H$ and $Q$. If you can compute images by both morphisms, and preimages of the injective morphism in polynomial time, then you can reduce the DLP in $G$ to the same problem in $H$ and $Q$.

Now I will start the reduction.

Your general problem is the $d$-th power problem in $G = (\mathbb{Z}/n\mathbb{Z})^\times$ ($n$ given in factored form). By CRT and the remark above, the problem is reduced in polynomial time to the case where $n$ is a prime power.

Now if $G = (\mathbb{Z}/p^e\mathbb{Z})^\times$, let $G_0=G$ and for $i\ge 1$, $G_i = 1+p^i\mathbb{Z}/p^e\mathbb{Z}\subset G$. Then we have $G_0/G_1\cong (\mathbb{Z}/p\mathbb{Z})^\times$, for $i\ge 1$ we have $G_i/G_{i+1}\cong \mathbb{Z}/p\mathbb{Z}$, and $G_e=1$. Since all these isomorphisms are computable and the DLP is trivial in $\mathbb{Z}/p\mathbb{Z}$, we are reduced to the case where $e=1$.

If $G = (\mathbb{Z}/p\mathbb{Z})^\times$, let $d = \prod_i q_i^{a_i}$ and $p-1 = \prod_i q_i^{b_i}$ be the factorisation into coprimes of $d$ and $p-1$. This means factorisations as displayed, where the $q_i$ are pairwise coprime but not necessarily prime. Such a factorisation is computable in polynomial time. (Depending on whether you are willing to use probabilistic / heuristic algorithms, you may even want to use a complete factorisation into primes here). Clearly the $d$-th power problem reduces to the $q_i^{a_i}$ power problem for each $i$, i.e. we can assume that $d=q^a$ and $q^b$ divides $p-1$ exactly (i.e. divides it and is coprime to the quotient).

There are some nice cases:

  • First case: $b=0$, i.e. $d$ is coprime to $p-1$. In this case, every element of $G$ is a $d$-th power, and you can obtain them in polynomial time by writing $ud+v(p-1)=1$, so that $x = (x^u)^d$ for all $x\in G$.
  • Second case: $a=b$, i.e. $d$ divides $p-1$ and is coprime to $n=(p-1)/d$. Write $ud+vn = 1$, and let $x\in G$. If $x=y^d$ for some $y\in G$, then $(x^u)^d = x$. So $x$ is a $d$-th power if and only if $x^u$ is a $d$-th root of $x$, and we can solve the problem in polynomial time.

In general, you can repeatedly use the second case to reduce to $a<b$. If $a$ was a multiple of $b$, you are done.

Otherwise, I do not have anything clever to propose. Here is a possibility, which recovers classical algorithms for square roots and other fixed powers. Assume that you are given a generator of the $q^b$-subgroup $H$ of $G$ (this is possible in polynomial time if you are willing to accept a probabilistic algorithm or assume GRH). Now simply solve DLP in $H$ by repeatedly using the exact sequence $1\to H[q] \to H \to H^q\to 1$. The running time is $q^{1/2}(\log (pq))^{O(1)}$ using generic algorithms.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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