臺灣博碩士論文加值系統

餘數系統(Residue Number System，簡稱RNS)在運算上具有平行(Parallel)、沒有進位(Carry-Free)和快速(High-Speed)的特性。要利用餘數系統來執行大數運算，我們首先將大數根據基底轉換成餘數組，接著再分別對各個餘數平行作運算即可。因為可以將大數分散在餘數組下平行計算，又不需考慮進位的問題，因此能夠對大數運算提供很好的效率。然而，RNS無法將數字以進位制來運算，所以只在加、減、乘法的運算上有很好的效率，對於正負、溢位的偵測(Sign and Overflow Detection)和除法的運算就非常的困難。因此在1995年，Hisat和Zohdy提出了一個快速的RNS除法演算法，他們的演算法根據除數與被除數以二進位表示的最高次方來計算出暫時的商值，再利用它們來計算出正確的商值。然而，我們發現有些暫時的商值被低估了。因此，我們藉由額外處理除數與被除數的最高兩個位元，來改進Hisat和Zohdy的方法。進一步地，我們也考慮到額外處理大於兩個位元的情況。不幸地，在處理大於兩個位元的情況下，暫時的商值和處理兩個位元的情況差不多，因此，我們將提出了一個在餘數系統下基於兩個位元之快速除法演算法。根據我們的分析顯示，我們演算法執行的回合數將比Hisat和Zohdy的演算法少25%。

Residue Number System (RNS) has computational advantages for very large integer arithmetic because of its properties of parallel, carry free, and high-speed arithmetic. However, overflow detection, sign detection, relative-magnitude detection, and division in RNS are very difficult problems. In 1995, Hiasat and Zohdy proposed a high-speed division algorithm for RNS. Their algorithm computes the temporal quotient according to the highest powers of 2 in the dividend and the divisor. After computing the temporal quotient, the algorithm finds the actual quotient to be the sum of all temporal quotients. However, the temporal quotient is underestimated. Thus, we improve Hiasat and Zohdy’s division algorithm in RNS by additionally dealing with the highest 2 bits of the dividend and the divisor. Moreover, we also consider the case of handling the highest i bits, where i>2. Unfortunately, the improvement is in vain because the temporal quotients are nearly the same when i>=2. According to the above description, we propose a fast division algorithm based on the highest 2 bits of the dividend and divisor in RNS. Comparing with Hiasat and Zohdy’s algorithm, our algorithm reduces the number of execution rounds by 25%.

摘 要 ......................................................I
ABSTRACT .....................................................II
CONTENTS ....................................................III
LIST OF FIGURES AND TABLES ...................................IV
CHAPTER 1 INTRODUCTION........................................1
CHAPTER 2 RELATED SURVEY......................................3
2.1 Residue Number System (RNS)................................3
2.1.1 Chinese Remainder Throrem (CRT)..........................4
2.1.2 Mixed Radix Conversion (MRC).............................6
2.2 Division in RNS............................................8
2.2.1 Division Remainder Zero..................................8
2.2.2 Scaling..................................................9
2.2.3 General Division........................................13
2.2.4 Hiasat and Zohdy's Division Algorithm in RNS............17
CHAPTER 3 OUR ALGORITHM......................................19
3.1 Improvement of Hiasat and Zohdy's Algorithm...............19
3.2 Discussions...............................................21
CHAPTER 4 SIMULATION AND RESULTS.............................23
CHAPTER 5 CONCLUSIONS AND FUTURE WORKS.......................24
REFERENCE ....................................................25
APPENDIX A C++ CODE FOR TESTING HIASAT AND ZOHDY'S ALGORITHM..32
APPENDIX B C++ CODE FOR OUR ALGORITHM(2 BITS).................35

[1] E. Kinoshita, H. Kosako, and Y. Kojima, “General Division in the Symmetric Residue Number System,” IEEE Trans. Comput., C-22, pp.134-142, Feb. 1973.
[2] D. Banerji, T. Cheung, and V. Ganesan, “A High-Speed Division Method in Residue Arithmetic,” in Proc. 5th IEEE Symp. Comput. Arithmetic, pp.158-164, 1981.
[3] W. Chren Jr., “A New Residue Number Division Algorithm,” Computer Math. Appl., vol. 19, no. 7, pp.13-29, 1990.
[4] N. Szabo and R. Tanaka, Residue Arithmetic and Its Applications to Computer Technology, McGraw Hill, New York, 1967.
[5] D. Gamberger, “New Approach to Integer Division in Residue Number System,” in Proc. of 10th Symp. On Comput. Arith., pp.84-91, 1991.
[6] Y. Kier, P. Cheney and M. Tannenbaum, “Division and Overflow Detection in Residue Number Systems,” IRE Trans. Electron. Comput., pp.501-507, 1962.
[7] L. Lin, E. Leiss, and B. Mcinnis, “Division and Sign Detection Algorithm for Residue Number Systems,” Comput. Math. Appl., 10, pp.331-342, 1984.
[8] M. Lu and J. S. Chiang, “A Novel Division Algorithm for the Residue Number System,” IEEE Transactions on Computer, vol. 41, no. 8, pp. 1026-1032, 1992.
[9] A. A. Hiasat and H. S. Zohdy, “A High-Speed Division Algorithm for Residue Number System,” Proceedings-IEEE International Symposium on Circuits and Systems, part 3, pp.1996-1999, 1995.
[10] M. Abdallah and A. Skavantzos, “New Multi-Moduli Residue and Quadratic Residue Systems for Large Dynamic Ranges,” IEEE Proceedings of ASILOMAR-29, pp.961-965, 1996.
[11] F. Barsi and M. C. Pinotti, “Fast Base Extension and Precise Scaling in RNS for Look-Up table Implementations,” IEEE Trans. Signal Processing, Vol. 43, No. 10, pp.2427-2430, October 1995.
[12] P. F. Dietz, I. I. Macarie, and J. I. Seiferas, “Bits and Relative Order from Residues, Space Efficiently,” Information Processing Letters, Vol. 50, No. 3, pp.123-127, May 1994.
[13] A. Garcia and A. Lloris, “A Look-Up Scheme for Scaling in the RNS,” IEEE Trans. Computer, Vol. 48, No. 7, pp.748-751, July 1999.
[14] M. A. Hitz and E. Kaltofen, “Integer Division in Residue Number Systems,” IEEE Trans. Computer, Vol. 44, No. 8, pp.983-989, August 1995.
[15] D. E. Knuth, The Art of Computer Programming, Vol. 2, second ed. Addison-Wesley, 1981.
[16] F. J. Taylor, “Residue Arithmetic: A Tutorial with Examples,” IEEE Trans. Computer, pp.50-62, May 1984.
[17] J. Schwemmlein, K. C. Posch, and R. Posch, “RNS-Modulo Reduction Upon a Restricted Base Value Set and its Application to RSA Cryptography,” Computers and Security, Vol. 17, No. 7, pp.637-650, 1998.
[18] A. P. Shenoy and R. Kumaresan, “Fast Base Extension Using a Redundant Modulus in RNS,” IEEE Trans. Computer, Vol. 38, No. 2, pp.292-296, 1989.
[19] Y. Wang and M. Abd-El-Barr, “A New Algorithm for RNS Decoding,” IEEE Trans. Circuits and systems —I: Fundamental Theory and Applications, Vol. 43, No. 12, pp.998-1001, 1996.
[20] H. Wu and M. A. Hasan, “Closed-Form Expression for the Average Weight of Signed-Digit Representations,” IEEE Trans. Computer, Vol. 48, No. 8, pp.848-851, 1999.
[21] J. C. Bajard, L. S. Didier, and P. Kornerup, “An RNS Montgomery Modular Multiplication Algorithm,” IEEE Trans. Comput., vol. 47, no. 7, pp.766-776, 1998.
[22] W. L. Freking and K. K. Parhi, “Montgomery Modular Multiplication and Exponentiation in the Residue Number System,” in Proc. of the 33rd Asilomar Conference on Signals, Systems, and Computers, 1999.
[23] G. I. Davida and B. Litow, “Fast Parallel Arithmetic Via Modular Representation,” SIAM J. Comput., Vol. 20, No. 4, pp.756-765, 1991.
[24] A. Skavantzos and M. Abdallah, “Implementation Issues of the Two-Level Residue Number System with Pairs of Conjugate Moduli.” IEEE Transactions on Siginal Processing, Vol. 47, No. 3, March 1999.
[25] N. Burgess, “Efficient RNS-to-Binary Conversion Using High-Radix SRT Division,” IEE Proc-Comput. Digit. Tech., Vol. 148, No. 1, pp.49-52, January 2001.
[26] N. Burgess and T. E. Williams, “Choices of Operand Truncation in the SRT Division Algorithm,” IEEE Trans., C-44, No. 7, pp.993-938, 1995.
[27] H. L. Garner, “The Residue Number System,” IRE Trans. Electronic Computers, Vol. EC-8, pp.140-147, 1959.
[28] G. Dimauro, S.Impedovo, and G. Pirlo, “A New Technique for Fast Number Comparison in Residue Number System,” IEEE Trans. Comput., Vol. 42, No. 5, pp.608-612, 1993.
[29] T. V. Vu, “Efficient Implementations of Chinese Remainder Theorem for Sign Detection and Residue Decoding,” IEEE Trans. Comput., Vol. C-34, No. 7, pp.646-651, July 1985.
[30] D. Gallaher, F. E. Petry, and P. Srinivasan, “The Digit Parallel Method for Fast RNS to Weight Number System Conversion for Specific Moduli ,” IEEE Trans on Circuits and Systems, Analog and Signal Processing, Vol. 44, No. 1, pp.53-57, 1997.
[31] L. L. Yang and L. Hanzo, “Residue Number System Arithmetic Assisted M-Ary Modulation,” IEEE Communications Letters, Vol. 3, No. 2, pp.28-30, February 1999.