0
$\begingroup$

Say, $X= a\cdot b$, where $(a, b) \in Z_q^*$ and $q$ is a large prime. If $X$ is given, then what is the complexity (or hardness) of finding $a$ and $b$?

Note that, either $a$ or $b$ can be reused to compute another $X'$ which is also public.

Edited: (more details)

Let's say Alice chooses two random numbers $a, b\in Z^∗_q$ and computes $X=a\cdot b$. Alice publishes $X$. What is the complexity of Bob to guess (or compute) $a$ and $b$ from the known $X$ and $Z^∗_q$?

$\endgroup$
  • $\begingroup$ If the multiplication $X=a\cdot b$ is in $\Bbb N$, you are asking the complexity of integer factorization. For an heuristic and conjectured answer as useful in cryptography, see GNFS. $\endgroup$ – fgrieu Feb 19 at 7:15
2
$\begingroup$

Say, $X= a\cdot b$, where $(a, b) \in Z_q^*$ and $q$ is a large prime. If $X$ is given, then what is the complexity (or hardness) of finding $a$ and $b$?

If the multiplication is done within $Z_q^*$, then it's easy - pick an arbitrary nonzero $a$ and compute $b = a^{-1}X$; you're done. You can compute $a^{-1}$ by either the Extended Euclidean method, or by using $a^{-1} = a^{p-2}$

This will find a $(a, b)$ pair that satisfies the equation. If you're looking for the unique one that someone else had in mind, well, you're out of luck - there are $q-1$ pairs that satisfy the equation, and with no other information, there is no way to determine which is the correct one.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ thanks @poncho for your answer. I wanted to know the hardness of computing $a$ and $b$ ($a$ and $b$ are unique numbers chosen by a user) from $X$. Let's say Alice chooses two random numbers $a, b\in Z_q^*$ and computes $X= a\cdot b$. Alice publishes $X$. What is the complexity of Bob to guess (or compute) $a$ and $b$ from the known value $X$ and $Z_q^*$? $\endgroup$ – Naz Feb 19 at 4:45
  • $\begingroup$ @Naz: Poncho's answer assumes that $X=a\cdot b$ is computed in $\Bbb Z^*_q$, that is modulo $q$, because your question suggests so. In that case, as explained in the last sentence of the answer, any guess of Bob with $a\cdot b\bmod q=X$, including $(a,b)=(1,X)$ or $(a,b)=(X,1)$, is as bad as any other, with low probability $1/(q-1)$ to be right, and complexity that of copying $X$, that is $\mathcal O(\log(X))$. Even if Bob chooses $a$ at random, complexity is the similarly low $\mathcal O((\log\log(q))^2\log(q))$. $\endgroup$ – fgrieu Feb 19 at 7:19

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.