# Ways to tell from residues modulo prime factors if $z$ is below half point

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, 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.

• 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. Dec 11, 2022 at 22:26
• 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 Dec 19, 2022 at 16:40