0
$\begingroup$

Suppose $A,B,C,A',B',C'$ are random distinct primes in $[T,2T]$ and $u,v$ are integers in $[T,2T]$.

Suppose we know:

$$Au+Bv\equiv r\bmod C$$ $$A'u+B'v\equiv r'\bmod C'$$

can we identify $u,v$ in polynomial time without integer linear programming?

Assume unique solution exists.

Note because of polynomial time algorithm for fixed dimension integer linear programming a polynomial time algorithm for the problem exists. I want to avoid it.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Are you sure that the conditions even guarantee a unique u/v pair? $\endgroup$
    – Steven Stadnicki
    Commented Apr 28, 2022 at 20:19
  • $\begingroup$ @StevenStadnicki, doesn't distinctness+primality mean that the solution is determined modulo $C C' \ge T^2$, which, assuming $T > 1$, is strictly bigger than $T$? $\endgroup$
    – LSpice
    Commented Apr 28, 2022 at 21:24
  • 2
    $\begingroup$ @LSpice I don't think you can run the usual matrix methods since you can't necessarily take inverses mod $CC'$ and in fact the various terms that you're going to be working with ($AC'$, etc.) are all non-invertible mod $CC'$. $\endgroup$
    – Steven Stadnicki
    Commented Apr 28, 2022 at 21:31
  • 1
    $\begingroup$ Actually, a very simple (counter)example: consider $u-2v=1 \bmod 5$ and $u-4v=1\bmod 7$. Then $(0, 2)$ and $(1, 0)$ are solutions to both. $\endgroup$
    – Steven Stadnicki
    Commented Apr 28, 2022 at 21:45
  • $\begingroup$ It comes from a system which guarantees unique solution. $\endgroup$
    – Turbo
    Commented Apr 28, 2022 at 22:00

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .