2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This appears to be a homework problem. Please show what work you have already done to solve these questions yourself, and keep in mind that posting homework problems is strongly frowned upon. $\endgroup$ – floor cat Apr 23 '17 at 2:02
  • 1
    $\begingroup$ That said, you can ask homework problems but you'll need to follow the help center guidelines. If you want to show what you've done to solve this yourself, I'll consider removing the down vote. crypto.stackexchange.com/help/on-topic $\endgroup$ – floor cat Apr 24 '17 at 1:36
  • $\begingroup$ I have put more efforts in the question. $\endgroup$ – user147687 Apr 24 '17 at 3:30
  • 1
    $\begingroup$ Some remarks: It is possible to rule out values of $r$ such that $\exists i$ with $c_i-r$ prime; this allows to construct a sieve on an interval for $r$. Independently, if we know how $p_i$ and $q_i$ are chosen (mean/variance, or interval), we can find some likely approximation of $r$, or/and interval embedding $r$. $\endgroup$ – fgrieu Apr 24 '17 at 7:00
  • 1
    $\begingroup$ To continue @fgrieu's remarks: you can also rule out values $r$ with $c_i - r$ of the form $ph$, where $p$ is a large prime, and $h$ is smooth; this happens rather more frequently than $c_i-r$ being prime. In addition, depending on how $p_i, q_i$ are chosen, you can get a guess on the value $r \bmod s$ for small values of $s$; if $p_i, q_i$ is selected randomly, then $p_iq_i$ has twice the expected probability of being 0 modulo $s$. $\endgroup$ – poncho Apr 24 '17 at 16:30
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.