0
$\begingroup$

Given two primes $p,q\in[T,2T]$, how many integers $m$ of size $O(T^{3/2+\epsilon})$ are there such that the residues $m\bmod p$ and $m\bmod q$ are both $O(polylog(T))$? Looking for an answer

Is it possible to construct any such in $polylog(T)$ time without integer programming? Answered below

Improve this question
$\endgroup$
2
  • $\begingroup$ Why ILP is disabled? $\endgroup$ Commented Apr 23, 2022 at 4:02
  • $\begingroup$ Lenstra's algorithm for fixed dim ILP which has to be used to be in poly time has never been implemented and is as good as non existent. $\endgroup$ Commented Apr 23, 2022 at 9:21

1 Answer 1

Reset to default
3
$\begingroup$

If such $m$ exists, then $m=up+a=vq+b$ for some $u,v\in O(T^{1/2+\epsilon})$ and $a,b\in O(\mathrm{polylog}(T))$. Then $up-vq=b-a$ and thus $\frac{p}q - \frac{v}u=\frac{b-a}{uq}$, implying that $\frac{v}u$ represents a rational approximation to $\frac{p}q$, which so good that it must be a convergent. So, it enough to compute a continuous fraction for $\frac{p}q$ and search for $\frac{v}u$ among its convergents.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Looks like up-vq=b-a can be solved by euclidean gcd. Should there exist multiple such m? $\endgroup$ Commented Apr 23, 2022 at 9:37
  • $\begingroup$ If one $m$ exists then, $m'=m+k$ for any positive $k\in O(\mathrm{polylog}(T))$ will also do a job. $\endgroup$ Commented Apr 23, 2022 at 11:00

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.