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, 2016 at 20:12
  • 1
    $\begingroup$ No deterministic polynomial-time algorithm is known even for computing square roots modulo primes. $\endgroup$ Oct 19, 2016 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, 2016 at 21:08
  • $\begingroup$ @EmilJeřábek what about the trick I have written when $n$ is prime? $\endgroup$
    – Turbo
    Oct 20, 2016 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, 2016 at 12:08

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .