0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$ ? $\endgroup$ – fgrieu Jan 15 at 7:49
  • $\begingroup$ @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? $\endgroup$ – w.qi Jan 15 at 13:04
6
$\begingroup$

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 $

$\endgroup$
  • $\begingroup$ You are right, so can I think it is a difficult factoring problem as the $n$ is large enough? $\endgroup$ – w.qi Jan 15 at 14:39
  • $\begingroup$ 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 ? $\endgroup$ – Bissi Jan 15 at 14:49
  • $\begingroup$ 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$? $\endgroup$ – w.qi Jan 15 at 15:00
  • $\begingroup$ 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 ? $\endgroup$ – Bissi Jan 15 at 15:22
  • $\begingroup$ Note: you can add: if we know more than one pair we can find more about the $n$. $\endgroup$ – kelalaka Jan 15 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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