# Question about finding the nth root in a modulus.

Some notation:

$\mathbb Z_n$ denotes the set of integers up to n i.e. $\mathbb Z_n=\{i│i ∈ \mathbb Z,0≤i < n \}$.

$\mathbb Z_n^*$ denotes invertible elements of $\mathbb Z_n$ i.e. $\mathbb Z_n^*=\{i|i ∈ \mathbb Z,0 ≤ i < n,gcd⁡(i,n)=1 \}$.

Suppose:

$m$ is a member of $\mathbb Z_n$,

$n$ is a composite of two large primes $p$ and $q$.

$g$ is a member of $\mathbb Z_{n^2}^*$, where $g$'s order in modulo $n^2$ is divisible by $n$.

$r$ is a member of $\mathbb Z_n^*$

then, it has been proven that the function $P(m,r) = g^m \cdot r^n \bmod n^2$ is a bijection $(\mathbb Z_n \times \mathbb Z_n^* → \mathbb Z_{n^2}^*)$

my question is, given that one knows the factorization of $n=p\cdot q$, $g,m,n$ can one efficiently find $r$?

-
Do you mean $\mathbb Z_n \times \mathbb Z_n^*$? That $x$ there makes no sense to me. – Patrick Da Silva Feb 27 '12 at 8:00
I don't understand the definition of the mapping $P(m,r)$. Unless the order of $g$ in $\mathbb{Z}_{n^2}^*$ is a factor of $n$ the power $g^m$ with $m\in\mathbb{Z}_n$ is not a well-defined element of $\mathbb{Z}_{n^2}$. IOW, if you select different integers to represent $m$ you get different values for the power? – Jyrki Lahtonen Feb 27 '12 at 8:42
@user996522: My question was not about injectivity/surjectivity. The problem I have is that it is not a function. Assume that $g$ has order $>n$. Then $g^n\not\equiv 1\pmod{n^2}$, but $g^0\equiv 1\pmod{n^2}$. Here $n$ and $0$ are the same element of $\mathbb{Z}_n$, so for your mapping to be well-defined, $g^0$ and $g^n$ need to be equal (modulo $n^2$). – Jyrki Lahtonen Feb 27 '12 at 19:35
I am mostly nitpicking about your notation :-). If you call elements of $\mathbb{Z}_n^*$ invertible elements of $\mathbb{Z}_n$, then you must have a ring structure of $\mathbb{Z}_n$. To that end the elements of $\mathbb{Z}_n$ must be residue classes of integers as opposed to a finite subset of integers that is not closed under ring operations. – Jyrki Lahtonen Feb 27 '12 at 19:47

I assume that the question is: Given $p,q,n,g,m$ and an element $x=P(m,r)$, one wants to have a method for finding $r$.

First I need to redefine the mappings so that they make sense to me. Please bear with me, this is just me tuning up. I will get to the answer. But I also need the following extra assumptions: $$\gcd(p,q-1)=\gcd(p,q)=\gcd(p-1,q)=1.$$ These assumptions are not overly restrictive, and most likely e.g. won't slow down key generation noticeably.

Much of the arithmetic takes place in the group $G=\mathbb{Z}_{n^2}^*$ that has size $pq(p-1)(q-1)$. This has a subgroup $$U=(1+n\mathbb{Z}_{n^2})=\{\overline{a}\in\mathbb{Z}_{n^2}\mid a\equiv1\pmod{n}\}$$ of order $n$.

There is an injective homomorphism $f:\mathbb{Z}_n^*\rightarrow G$ defined as follows. Let $r$ be an integer coprime to $n$. If $r\equiv r'\pmod n$, then a well-known calculation shows that $r^p\equiv r'^p\pmod{p^2}$, and hence $r^{pq}=r^n\equiv r'^n\pmod{p^2}$. By changing the roles of $p$ and $q$ in the preceding argument, we similarly see that $r^n\equiv r'^n\pmod{q^2}$. By Chinese Remainder Theorem we deduce that $r^n\equiv r'^n\pmod{n^2}$. The mapping $f:\overline{r}\mapsto\overline{r^n}$ is thus well-defined, and it is obviously a homomorphism of groups. Let us write $H=Im(f)$.

The homomorphism $f$ is actually injective. This follows (in the spirit of Lemma 13 from the seminar notes linked to by OP) from the facts that $H=G^n$ and the $U$ is the kernel of the $n$th power mapping $G\rightarrow G$ (see the link). A calculation of orders shows that we have a direct product decomposition $$G=U\times H.$$

If $ord_G(g)$ is a multiple of $n$, then the elements $g^i, i=1,2,\ldots,n-1$ all have orders that are divisible by at least one of $p$ or $q$, and thus won't belong $H$, so the powers $g^i=\{0,1,\ldots,n-1\}$ form a complete set of representatives of cosets of $H$. Thus (Theorem 16 of the linked seminar notes) the mapping $$P:\{0,1,2,\ldots,n-1\}\times \mathbb{Z}_n^*\rightarrow \mathbb{Z}_{n^2}^*, (m,r)\mapsto g^m f(r)$$ is a bijection.

Now we can reformulate the question to read: Given $x\in G$ that is known to be in the coset $g^m H$, how can we find $r\in \mathbb{Z}_n^*$ such that $x=g^mf(r)$, if we have the (trapdoor) information that we know $p$ and $q$. By CRT it suffices to compute $r$ modulo $p$ and modulo $q$. We first compute $f(r)=g^{-m}x$. Here $r^p\equiv r\pmod p$ by Little Fermat, so $f(r)\equiv r^n\equiv r^q\pmod p$. Let $i_1$ be the modular inverse of $q$ modulo $p-1$ (I need the extra assumption $gcd(p-1,q)=1$ here!), so $i_1q= 1+k(p-1)$ for some integer $k$. Therefore $$f(r)^{i_1}\equiv (r^q)^{i_1}=r^{1+k(p-1)}=r\cdot r^{k(p-1)}\equiv r\pmod{p}.$$ Similarly, if $i_2$ is the modular inverse of $p$ modulo $q-1$, we get that $$f(r)^{i_2}\equiv r\pmod{q}.$$ Thus in order to compute $r$ modulo $n$, we need to raise $f(r)$ to the powers $i_1$ and $i_2$, compute their respective residues modulo $p$ and $q$, and apply the CRT to the results.

-
Note that this method also solves the $n$-th residue problem, but only when we know the factorization of $n$. The reason is that this method inverts the function $f$, so it is trivial to check, whether something is in $Im(f)$. Compute the only possible inverse, and check whether it gives back the correct number. – Jyrki Lahtonen Feb 27 '12 at 22:10
@Gerry Myerson: Thanks for the edits and for spotting the typo! – Jyrki Lahtonen Feb 27 '12 at 22:30
wow, that was a comprehensive answer, thank you very much - i will go though it later tonight. – user996522 Feb 28 '12 at 3:44