A Parallel Computation Algorithm for Generalized Aryabhata Remainder Theorem

[[abstract]]To solve the conversion problem in Residue Number System (RNS) with a general moduli set, a common solution is to use Chinese Remainder Theorem (CRT). In CRT, it has to compute a modular arithmetic with a large number to adjust the final result, which is a time-consuming operation. On the contrary, Aryabhata Remainder Theorem (ART) distributes this time-consuming operation into several modular arithmetic with smaller numbers in each iteration. Thus, ART is more suitable than CRT for the parallel processing. In this paper, we propose a parallel conversion algorithm based upon ART for RNS. Unlike the time complexities of the previous researches are O(n), ours is just O(log2n), where n is the number of the moduli in RNS. Therefore, our algorithm is more efficient than the previous ones