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.
