A fast algorithm for mixed-radix conversion in residue arithmetic

An algorithm based on a partitioning of the coefficient matrix when the mixed-radix conversion problem is cast as a set of linear congruent equations is presented. The algorithm partitions the moduli set into disjoint subsets such that the product of the moduli in each subset is less than the largest integer representable by the computer. It is shown that, with this partitioning strategy, mixed-radix representation of a residue number can be computed using less than O (n²) arithmetic steps where n is the cardinality of the moduli set. It is also shown that if a good partitioning exists, then the algorithm requires only O(n ^1.5) arithmetic steps. The algorithm is particularly suitable for single processor implementation of algorithms from the residue number system applications