# Find integer $n$ modulo composite.

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$$?

Thanks.

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}$$).