Suppose we want to find a positive integer $n < M$ where $M$ is a constant value of which we know a good approximation.

For every prime $p$, an oracle gives us a set $B_p$ of residuals modulo $p$ composed of $n(B_p)=(p-1)/2$ distinct elements. The residual $b = n\mod p$ belongs to $B_p$.

We don't know what the value of $b$ is among the known values of $B_p$.

If we pick a number $k \gg\log_{2}M$ of these sets, we can assume that $n$ is the smallest integer that belongs at the same time to them.

Is there an efficient algorithm to find $n$?


Edit: i want to share some ideas to approach the problem.

-) Coppersmith method

Chosen a set of $N$ prime numbers $p_i$, it's easy to define an univariate Polynomial $P(x)$ of degree $\frac{p_{max}-1}{2}$ (where $p_{max}$ is the greatest prime number chosen) that takes value $0$ for every integer whose residual modulo $p_i$ is contained in $B_{p_{i}}$ (for every $p_i$ simultaneously). The idea is to find the smallest $x$ such that:

$$P(x) \equiv 0 \ \ mod \ \prod_{i=1}^{N}{p_i} $$

The problem of this method is that the value of $n$ (the first zero in our case) must be bounded by $$\sqrt[\frac{p_{max}-1}{2}]{\prod_{i=1}^{N}{p_i}}$$

-) Define one or more functions in another domain (es: $\mathbb{R}$) which takes the first zero in $n$ and find the first zero of those functions with analytical methods.

-) integer programming

I have not found a possible application of these methods (or other methods) that can handle cases in which $n$ is large (es: $> 10^{10}$).

Thanks in advance.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.