Fast RNS division algorithms for fixed divisors with application to RSA encryption. (English) Zbl 0813.94008
Residue number systems (RNS) have received much attention for high- throughput computations due to its advantage of fast addition and multiplication over other number systems. This paper presents two algorithms for RNS division with fixed divisors that achieve \(O(n)\) time complexity for each division, where \(n\) is the number of moduli. The first algorithm uses the well-known division method of multiplying by the divisor reciprocal. The second algorithm, which is faster than the first one but requires more space, is based on the Chinese Remainder Theorem decoding and table lookup, and requires the divisor to be relative prime to all moduli. Adaptation of both algorithms for RSA encryption is also described. It is shown that the first and second algorithms respectively lead to \(4n + b\) and \(2n\) time steps per modular multiplication, where \(b\) is the number of bits in the largest modulus.
Reviewer: H.Shen (Nathan)
MSC:
| 94A60 | Cryptography |
| 11Y16 | Number-theoretic algorithms; complexity |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
residue number systems; cryptography; sign detection; computer arithmetic; complexity; RSA encryption; modular multiplicationReferences:
| [1] | Banerji, D. K.; Cheung, T.-Y.; Ganesan, V., A high-speed division method in residue arithmetic, (Proc. 5th Symp. on Computer Arithmetic (1981), IEEE Press: IEEE Press New York), 158-164 · Zbl 0538.68032 |
| [2] | Barrett, P., Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor, (Odlyzko, A. M., Advances in Cryptology, Proc. Crypto 86 (1986), Springer: Springer Berlin), 311-323 |
| [3] | Chren, W. A., A new residue number system division algorithm, Comput. Math. Appl., 19, 7, 13-29 (1990) · Zbl 0687.68022 |
| [4] | Dimauro, G.; Impedovo, S.; Pirlo, G., A new technique for fast number comparison in the residue number system, IEEE Trans. Comput., 42, 5, 608-612 (1993) · Zbl 1397.65330 |
| [5] | Hung, C. Y.; Parhami, B., An approximate sign detection method for residue numbers and its application to RNS division, Comput. Math. Appl., 27, 4, 23-35 (1994) · Zbl 0805.68059 |
| [6] | Kawamura, S.; Hirano, K., A fast modular arithmetic algorithm using a residue table, (Günther, C. G., Advances in Cryptology, Proc. Eurocrypt 88 (1988), Springer: Springer Berlin), 245-250 |
| [7] | Koç, Ç. K.; Hung, C.-Y., Adaptive \(m\)-ary segmentation and canonical recoding algorithms for multiplication of large binary numbers, Comput. Math. Appl., 24, 3, 3-12 (1992) · Zbl 0800.68401 |
| [8] | Lu, M.; Chiang, J.-S., A novel division algorithm for the residue number system, IEEE Trans. Comput., 41, 8, 1026-1032 (1992) · Zbl 1397.65334 |
| [9] | Szabó, N. S.; Tanaka, R. I., Residue Arithmetic and its Applications to Computer Technology (1967), McGraw-Hill: McGraw-Hill New York · Zbl 0168.15303 |
| [10] | Takagi, N., A radix-4 modular multiplication hardware algorithm for modular exponentiation, IEEE Trans. Comput., 41, 8, 949-956 (1992) |
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.
