An improvement of fast base extension in RNS

New techniques to evaluate base extension have been previuosly presented in the literature allowing faster computation times. These techniques are based on the Chinese Remainder Theorem and are implemented by using lookup tables. However, the proposed methods require a sligth redundancy to be added to the number representation. In this paper, it is shown that this redundancy can be avoided if the terms of the Chinese Remander Theorem are properly expanded. The average base extension execution time is again bounded by log n table lookup cycles whereas area is sligthly increased.