# finding r-th root in $\mathbb{Z}/n\mathbb{Z}$

I was reading the paper One-way Accumulators: A Decentralized Alternative to Digital Signatures by Benaloh and de Mare [link], and in section 4.2, they say that given $$z\in (\mathbb{Z}/n\mathbb{Z})^*$$ and a set $$\{(z^{1/m_1}, m_1),(z^{1/m_2}),\dots, (z^{1/m_k}, m_k)\}$$ with $$m_i \in \mathbb{Z}$$, computing $$z^{1/r}$$ for $$r \in \mathbb{Z}$$ is hard, which I get since the order of $$(\mathbb{Z}/n\mathbb{Z})^*$$ is unknown.

However, they say that the problem becomes easy if $$r \mid m_1m_2\cdots m_k$$, and I do not get how it becomes easy.

For the case $$k=1$$, we have $$z, (z^{1/m_1}, m_1) \text{ and } r \mid m_1$$, this is easy since $$m_1 = k\cdot r$$ for $$k\in \mathbb{Z}$$ and $$(z^{1/m_1})^k = z^{1/r}$$

For the case $$k=2$$, when we have $$m_1 m_2 = k^\prime \cdot r$$, we can compute $$z^{1/m_1}z^{1/m_2} = z^{(m_1+m_2)/m_1m_2}$$ and get $$z^{(m_1+m_2)/r}$$. However, I do not know how to get rid of the value $$m_1+m_2$$ to obtain $$z^{1/r}$$

The case $$k>2$$ seems even harder.

Any hint on how to move forward will be welcomed

• HINT: Bezout's identity Aug 9 at 7:51
• Would it be better to have the title say "r-th root" in $\mathbb Z/n\mathbb Z$? For consistency with the body of your Question. Aug 9 at 12:40

The key is to use extended euclidean algorithm. Here's a numerical example, see if you can figure it out yourself.

Given $$z, a := z^{1 / 3}, b := z^{1 / 5}$$, we can compute $$z^{1 / 15} = a^{-1} \cdot b^2 = z^{-5 / 15 + 6 / 15}$$.

Cheers!

• but this only works if for $z^{1/m_1}, z^{1/m_2}$, $m_1$ and $m_2$ are coprime. However, in the paper, they didn't mention something about the gcd of the $m_i$
– vxek
Aug 9 at 14:24
• @vxek nope, read about extended euclidean algorithm again Aug 9 at 15:08
• it seems like using extended euclidean algorithm/ Bezout's identity, I can find $z^{1/r}$ if $r = \dfrac{m_1m_2}{\gcd({m_1,m_2})}$ But I am still struggling to see how the $r$-th root is easy if $r$ is a random integer that divides $m_1m_2$
– vxek
Aug 9 at 15:59
• @vxek Ah, so you are asking how is computing $z^{1 / 24}$ easy when given $z^{1 / 4}$ and $z^{1 / 6}$. Yes, you are correct that it is hard here. The paper assumes that $m_i$ are mutually coprime e.g. when they're all primes. Stop using symbols :) Aug 9 at 17:22