Arithmetic division in RNS using Galois field \(GF(p)\). (English) Zbl 0958.68005
Summary: This paper develops an enhanced algorithm for the arithmetic division problem in the residue number system. The proposed algorithm is based on Galois Field theory \(\text{GF}(p)\). Mapping the arithmetic division problem over the Galois Field \(\text{GF}(p)\) eliminates many of the limitations of existing algorithms. The advantage of the proposed algorithm is that it has no restriction on the dividend and the divisor, no mixed radix conversion, no quotient estimation before division, no reciprocal estimation of the divisor, and no based extension operation.
MSC:
| 68M07 | Mathematical problems of computer architecture |
| 68W30 | Symbolic computation and algebraic computation |
| 12Y05 | Computational aspects of field theory and polynomials (MSC2010) |
References:
| [1] | Szabó, N. S.; Tanaka, R. I., Residue Arithmetic and Its Applications to Computer Technology (1967), McGraw-Hill: McGraw-Hill New York · Zbl 0168.15303 |
| [2] | Hung, C.; Parhami, B., Fast RNS division algorithms for fixed divisors with application to RSA encryption, Information Processing Letters, 51, 163-169 (1994) · Zbl 0813.94008 |
| [3] | Hung, C.; Parhami, B., An approximate sign detection method for residue numbers and its application to RNS division, Computers Math. Applic., 27, 4, 23-35 (1994) · Zbl 0805.68059 |
| [4] | Julien, G. A., Residue number scaling and other operations using ROM arrays, IEEE Trans. Comput., C-27, 4, 325-336 (1978) · Zbl 0379.68045 |
| [5] | Claudio, E. D.; Piazza, F.; Orlandi, G., Fast combinatorial RNS processors for DSP applications, IEEE Trans. Comput., 44, 5, 624-633 (1995) · Zbl 1041.68502 |
| [6] | Waser, S.; Flynn, M. J., Introduction to Arithmetic for Digital System Designers (1982), Holt, Rinehart & Winston: Holt, Rinehart & Winston New York |
| [7] | Taylor, F. J., Residue arithmetic: A tutorial with examples, IEEE Comput., 17, 5, 50-62 (1984) |
| [8] | Lu, M.; Chiang, J., A novel division algorithm for the residue number system, IEEE Trans. Comput., 41, 8, 1026-1032 (1992) · Zbl 1397.65334 |
| [9] | Chren, W. A., A new residue number system division algorithm, Computers Math. Applic., 19, 7, 13-29 (1990) · Zbl 0687.68022 |
| [10] | Banerji, D. K.; Cheung, T. Y.; Ganesan, V., A high-speed division method in residue arithmetic, (IEEE Symp. Comput. Arithmetic. (1981)), 158-164, (5) · Zbl 0538.68032 |
| [11] | Hits, M. A.; Kaltofen, E., Integer division in residue number systems, IEEE Trans. Comput., 44, 8, 983-989 (1995) · Zbl 1053.68501 |
| [12] | Kinoshita, E.; Kosako, H.; Kojima, Y., General division in the symmetric residue number system, IEEE Trans. Comput., C-22, 134-142 (1973) · Zbl 0248.68030 |
| [13] | Lin, M. L.; Leiss, E.; McInnis, B., Division and sign detection algorithm for residue number systems, Computers Math. Applic., 10, 4/5, 331-342 (1984) · Zbl 0598.68040 |
| [14] | Radhakrishnan, D.; Yuan, Y., Novel approaches to the design of VLSI RNS multipliers, IEEE Trans. Circuits and System—II, 39, 1, 52-57 (1992) · Zbl 0776.11072 |
| [15] | Beyer, W., CRC-Standard Mathematical Tables and Formulae (1991), CRC Press · Zbl 0744.00008 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
