# More Knowledge Integer Factorization

Say you have an integer that is produced by multiplying two random numbers

$$x_1 = a \cdot b_1 \bmod(p-1)$$ where $a$ and $b_1$ are relatively prime to $p-1$ and $p$ being a large prime.

Knowing $x_1$ leaves you with $p-1$ pairs of numbers for $a$ and $b_1$, so guessing the correct factorization is hard (right?).

Do you get any advantage in finding the correct pair if you get more $x_i$ where one of the factors is re-used? E.g.: $$x_2 = a \cdot b_2 \bmod(p-1)$$

• This is about the same problem as recovering the private key from DSA signatures: You always have at least one more unknown variable than equations. – SEJPM Dec 17 '16 at 13:25
• With a single pair, you have many possible solution, but the set of valid solutions is easy to compute, it cannot be seen as a hard problem. With two equations, you get the common factor by computing a gcd, and recovering the remaining factors takes one inversion and two modular multiplications then. – Geoffroy Couteau Dec 17 '16 at 14:02
• Knowing $x_1$ really leaves you with $\varphi(p−1)$ possible pairs of numbers, where $\varphi$ is the Euler totient function. Hint: show that for any fixed $a\in\mathbb Z_{p-1}^*$ (the subset of $\mathbb Z_{p-1}$ wich elements are coprime with $p-1$), the function $b_j\to x_j$ is a permutation of $\mathbb Z_{p-1}^*$; conclude. – fgrieu Dec 17 '16 at 17:49
• @fgrieu: Could you elaborate on your comment? What does it mean that every $b_j \rightarrow x_j$ is a permutation for my question? Does it help you find $a$? – ChaosCoder Dec 18 '16 at 12:58
• @ChaosCoder, Hint: do you learn anything about a permutation when given the images $x_j$ of unknown random elements $b_j$ by this permutation? – fgrieu Dec 19 '16 at 8:12

The question performs arithmetic in ${\mathbb Z_{p-1}}^*$, the integers reduced modulo $p-1$ that are coprime with this modulus. There are $\varphi(p-1)$ of these, where $\varphi$ is the Euler totient function. It is irrelevant that $p$ is prime, and the question has little to do with integer factorization.
For any $a\in{\mathbb Z_{p-1}}^*$, the application $\scr F_a:{\mathbb Z_{p-1}}^*\to{\mathbb Z_{p-1}}^*$, $b\to x=a\cdot b\bmod(p-1)$ is a permutation of ${\mathbb Z_{p-1}}^*$ (since $a$ has a multiplicative inverse). If follows that if $b$ is uniformly random on the set ${\mathbb Z_{p-1}}^*$, then $x$ is.
Therefore, no information is learned about $\scr F_a$, thus about $a$, from any number of $x_j$ disclosed without the corresponding $b_j$ (assumed independent and uniformly random on ${\mathbb Z_{p-1}}^*$), regardless of the size of parameters or computing power of adversary.