BASE EXTENSION USING A CONVOLUTION SUM IN RESIDUE NUMBER-SYSTEMS

Base extension is an important operation in residue number systems. Th e method for base extension proposed in this paper approaches the solu tion through an approximation which is correct in nearly all cases. Ra re occurrences of uncertainties about the correctness of the result ar e detected and corrected using iterations. The novel method is superio r to the method proposed by Shenoy and Kumaresan [5] as it does not ne ed the help of an additional redundant modulus. For a special class of problems the latter method cannot be used at all. The presented base extension provides a unique tool with time complexity of log2n with n denoting the amount of moduli.