1
$\begingroup$

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

Thanks in advance.

$\endgroup$

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.