Let $N=\prod_{k=0}^{k=m}{ p_k }$ be a square-free odd integer where $p_k$ is a prime. If we are given any integer $g$ such that $0<g<N$, it is very easy to tell if $g < \frac{N}{2}$ or not. Now supose that instead we are given the tuple $ T_z = ( z \bmod p_0, \dotsc, z \bmod p_m) $, how can we tell if $T_z$ corresponds to a integer Mod N such that $z < \frac{N}{2}$?

In particular, we can use the Chinese remainder theorem (CRT) to recover $z$ from $T_z$ and we are back to the case of $g$ mentioned above…but, this way of doing it is computationally expensive in terms of the number of multiplies, modulo reductions and the inverses we need to find to apply CRT. If $N$ is large, think 50 digits or more, and we are given one million of these tuples…is there a pattern or structure that would allows to tell at a much cheaper computational cost if $z < \frac{N}{2}$? If we can find more than one way of doing it even better.

CRT is the only way I know how to do this. Any more approaches are welcome, especially cheaper approaches in terms of computation.

  • 2
    $\begingroup$ The hardest part of CRT is the Bézout identity $1=a_1 N/p_1 +\cdots+a_m N/p_m$. After that each case is just an evaluation of a linear combination mod N. I can't see how to hope to be quicker than that. $\endgroup$ Dec 11, 2022 at 22:26
  • 1
    $\begingroup$ The best algorithm that I know to solve CRT works in time $O(\log(N)^2)$, so you can do this in $O(\log(N)^2)$. On the other hand, I don't think you can do this better than $O(\log(N))$. If you can tell whether the solution to CRT is less than $N/2$ or not, then in the first case by adding $N/4$ to your tuple and run you algorithm again, you can tell if it's less than $N/4$ or not and in the second case by subtracting $N/4$ you can compare it to $3N/4$ and so on. Therefore, by $\log(N)$ steps you can actually find the solution to CRT. One might still hope for something between $O(\log(N))$ and $\endgroup$ Dec 19, 2022 at 16:40


Your Answer

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