Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
    
see theorem 16 here : www2.cs.uni-paderborn.de/cs/ag-bloemer/lehre/proseminar_WS2005/… –  user996522 Feb 27 '12 at 14:23
    
@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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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