Let:$\left\{m_1, ~...~, m_k\right\}$ be a set of coprime natural numbers,$M=\prod_{i=1}^{k} m_i$$X$ be a natural integer, such that $X < M$Then $X$ can be expressed in the Residue Number System as:$$X={\left(x_1, ~...~, x_k\right)}_{RNS\left(m_1, ~...~, m_k\right)}~.$$Where $\forall_{m_i} \left[\left(x_i \equiv X \mod m_i\right) ~~~ \wedge ~~~0 \le x_i < m_i \right]$.There are a plethora of papers attacking the problem of parity/magnitude comparison in Residue Number Systems; however many of these papers are focused on chip-depth or shaving large constants off of chip-area. I am finding it difficult to decipher if there are any exact algorithms that run faster than full binary reconstruction, which takes $\sim \mathcal{O}(k^2)$  time. (For simplicty/brevity, I am assuming small $m_i$, and constant-time modulo-multiplication/addition of each RNS digit).Most of the papers' novelties lie in some seeming gimmick, but no real complexity decrease; examples of results:Fast inexact parity algorithms (usually work terribly when $X < \sqrt{M}$, or $|X| \ll |M|$, where $\left|n\right|=\text{size of }n=\left\lceil\log_2n\right\rceil$)Algorithms that work quickly most of the time; ie. they use an inexact algorithm, and then the full CRT reconstruction or equivalent in the worst caseThe circuit they present competes with some other paper's circuit by some constant, or area/depth tradeoff, but makes no complexity advanceFull CRT reconstruction of $X$, perhaps using some trick to save some constantsReconstruct/convert to another number system (including binary) where parity/comparison is easy, but:this conversion/reconstruction takes $\sim \mathcal{O}(k^2)$ time,or it runs in $\sim \mathcal{O}(k)$, time but with $k$ processors,or it runs in $\sim \mathcal{O}(k)$ time because that is the depth of the circuit, but this is not algorithmic complexity,or it reuses previous components that must be there for RNS multiplication (saving circuit space), but still runs in $\sim \mathcal{O}(k^2)$ sequential-time, or $\sim \mathcal{O}(k)$ parallel-timeUsing a core function which basically boils down to a constant-trimmed-CRT, or an approximate CRTUsing special moduli, makes individual operations simpler, but parity complexity stays the sameUsing special moduli, but limited number of moduli or can't have small $m_i$Base extension, saves some constant or allows parallel-ness, but complexity is again $\sim \mathcal{O}(k^2)$ sequential-time, or $\sim \mathcal{O}(k)$ parallel-time (for multiplication)Redundant moduli, but maintaining the redundant moduli takes  $\sim \mathcal{O}(k^2)$ sequential-time, or $\sim \mathcal{O}(k)$ parallel-timeUsing lookup tables to reduce depth of some parity, no complexity improvementMany of the papers do not address complexity at all, or do not address sequential complexity, or even more confusingly, some state the depth/parallel complexity without being precise that it is not sequential; until you read and decipher the entire paper, and discover it yourself.Bottom lineWhat are the best sequential, worst-case, complexity results in RNS* for exact parity checking or magnitude comparison?*Results for RNS-like system would also be interesting, including special moduli setsMore background info: Multiplication of two numbers in the same RNS base is simply pointwise modulo multiplication of the two numbers (this can be approximately linear time). However, overflow detection is difficult (it is difficult with addition as well). Multiplication seems much simpler, but parity and magnitude comparison of two numbers seems much more difficult. Magnitude comparison is simply determining which of two numbers is greater, $X \stackrel{?}{<} Y$, given only their RNS form with the same RNS bases. Parity is simply deciding if a number, $X={\left(x_1, ~...~, x_k\right)}_{RNS\left(m_1, ~...~, m_k\right)}$ is even or odd (obviously, $X$ is not given, only its RNS form). An interesting thing is that magnitude comparison and parity are related: If you were able to compute parity, then you can do comparison. To do comparison with parity, you do $(X - Y)$ (in RNS), and if it underflows, the parity will be unexpected. That is, normally, assuming $p(X) = X \mod 2, ~~~ p(X) \in \{0,1\}$ is the parity function, $p(X-Y) \equiv p(X) + p(Y) \mod 2$. However, if it underflows, it will wrap around to $M-1$. Therefore if the parity is off after $X-Y$, you know that $Y > X$.
Best complexity of parity/comparison in the Residue Number System
algorithms;reference request;integers;number theory