# Factorization problem

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

• 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.
– fgrieu
Feb 19 '20 at 7:15

## 1 Answer

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.

• 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^*$?
– Naz
Feb 19 '20 at 4:45
• @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))$.
– fgrieu
Feb 19 '20 at 7:19