The Approximate Greatest Common Divisor (AGCD) problem is the difficulty of obtaining the value $\ p\ $ when given samples of $\ pq_i + e_i$ for secret values $p, q_i, e_i$.
I would like to know how the difficulty of the problem changes when modular reduction is incorporated.
Specifically: is the problem of obtaining $\ p\ $ from samples of $\ pq_i + e_i \bmod x$ with secret $\ p, q_i, e_i$ and public $x$ equivalent in hardness to the previously mentioned variant of the problem that operates over integers?
I could not find information on this version of the problem when searching for the term "Modular AGCD", but I am not sure what to refer to it as. It may a negligible difference between the two that does not warrant classification as a separate problem, but I am not sure. Intuitively, it seems that the variant with the modulus would be more difficult to solve. But I would like quantitative details on any differences, if there are any.
Poncho's answer highlights the fact that the sizes of the parameters are important when discussing the hardness of the problem. I am interested in the problem with the following parameter sizes:
- $x$ is a 1792-bit prime
- $p$ is a uniformly random 1792-bit integer
- Each $q_i$ is a 1536-bit integer with the 1280 most significant bits uniformly random
- The next lower 255 bits are set to 0, and the least significant bit is set to 1
- Each $e_i$ is a 1024-bit random integer