Difficulty of a congruence problem

Question

The problem is described as follows. Let $c_1=p_1q_1+r$, $c_2=p_2q_2+r$, $\cdots$, $c_n=p_nq_n+r$, where $p_i$'s, $q_i$'s, $r$ are all large positive integers, and $p_i$'s and $q_i$'s are randomly chosen. Notice that $p_i$'s and $q_i$'s are different while $r$ is the same. Now one knows $c_1,\cdots,c_n$, and he knows the above structure of $c_1,\cdots,c_n$, but he does not know $p_i$'s or $q_i$'s. He aims to extract the value of $r$ from $c_1,\cdots,c_n$. Is this problem hard (either proven to be hard, or no polynomial solving algorithm found yet)? Does this problem have a name?

A similar (but easier) problem is solving the system of linear congruences: by knowing $c_1,\cdots,c_n$ and $p_1,\cdots,p_n$, solve $r$ from the equations $r\equiv c_1\mod p_1$, $r\equiv c_2\mod p_2$, $\cdots$, $r\equiv c_n\mod p_n$. This problem is related to the Chinese remainder theorem and I know that it has polynomial-time solving algorithms. However, in my question in the first paragraph above, one only knows $c_1,\cdots,c_n$, but does not know the moduli $p_1,\cdots,p_n$ (or $q_1,\cdots,q_n$), the problem of my question might be harder. I can only find works on linear congruences but cannot find related works on my question. Is anyone familiar with this question? I just wonder is this a problem that has been ever studied.

Answer 1

Combining fgrieu's and my observation, it appears that a large $r$ can be recovered given enough $p_iq_i + r$ values.

In particular, we will assume that both $p_i$ and $q_i$ are selected uniformly.

Then, $(p_iq_i + r) = r \pmod s$ will hold will probability at least $(2s-1)/s^2 \approx 2/s$ (as it will hold if either $p_i$ or $q_i$ is 0 modulo $s$, $(p_iq_i + r) \bmod s$ will be any other specific values with probability circa $1/s$. Actually, the bias is even stronger if $s$ is a power of a smaller prime, we'll ignore that for now.

Hence, what we can do is, for various small prime-power $s$, take our $p_iq_i + r$ values, and compute $p_iq_i + r \bmod s$, and see what value happens the most often. That'll give us the likely value of $r \bmod s$. Then, we take all our likely values, and use the Chinese Remainder Theorem to reconstruct $r$.

If we have 10,000 such values, we can use the prime-power's up to 710; for each value of $s$, the correct value of $r \bmod s$ will be at least 3 standard deviations over the rest (and hence the most common value is likely to be the correct one), and that'll give us enough relations to recover a 1024 bit $r$.

We can then use fgrieu's observation to validate the $r$ we recovered.