# If I know an element and it's inverse, can I learn the modulus?

If I know an element $$x$$ in a group, and it's inverse $$x^{-1}$$, can I guess the modulo, or with a probability?

• The question makes sense in the group $\Bbb Z_n^*$ for unknown $n$. Hint: what do you know about the ordinary product $x^{-1}\,x$ ? – fgrieu Jan 15 '19 at 7:49
• @fgrieu The product $x^{-1}x= nk+1$ for an integer $k$, with the bits of $n$ increase and for larger $x$, it will be more complex? But even more complex, it will always get the modulo in polynomial time? – w.qi Jan 15 '19 at 13:04

As said in the comments above, you have that $$x \cdot x^{-1} = 1 \mod n$$. Another way to say that is $$k \times n=(x \cdot x^{-1}) -1$$

So no, you can't always find the exact value $$n$$ from $$x$$ and $$x^{-1}$$.

Take $$x=12 \$$ and $$x^{-1}=17$$. You have $$x \cdot x^{-1} = 204$$. So $$n$$ is a divisor of $$204-1=203$$, meaning, $$n \in \{29,203\}$$ (other divisors are smaller than $$\max(x,x^{-1})$$ so they can't be $$n$$)

The only cases where you can find $$n$$ is when the only divisor of $$kn$$ greater than $$x$$ and $$x^{-1}$$ is $$kn$$ itself. In this case, $$n=kn=(x \cdot x^{-1}) -1$$

• You are right, so can I think it is a difficult factoring problem as the $n$ is large enough? – w.qi Jan 15 '19 at 14:39
• Can you please give some details about your problem ? What I understand is, given $x$ and $x^{-1}$, can an adversary retrieve $p$ and $q$ such that $pq=n$ ? Is it correct ? – Bissi Jan 15 '19 at 14:49
• I'm sorry, I mean that while $x^{-1}x$ is large, so the $kn$ is large enough, so it can be seen as a hard problem: from $kn$ to find $k$ and $n$? – w.qi Jan 15 '19 at 15:00
• What would be the use of the $x$, $x^{-1}$ and $k$ values ? The public key would be $(x,x^{-1})$ and the secret one $(k,n)$ ? Your question need a bit more of contextualization. Where did you get this idea from ? – Bissi Jan 15 '19 at 15:22
• Note: you can add: if we know more than one pair we can find more about the $n$. – kelalaka Jan 15 '19 at 18:39