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.
Relation:
International Journal of Computer Sciences and Engineering Systems 5(7):2053-2060
