Low-Complexity Multiplication Using Complement and Signed-Digit Recoding Methods

Abstract:

In this paper, a fast multiplication computing method utilizing the complement representation method and canonical recoding technique is proposed. By performing complements and canonical recoding technique, the number of partial products can be reduced. Based on these techniques, we propose algorithm provides an efficient multiplication method. On average, our proposed algorithm to reduce the number of k-bit additions from (0.25k+logk/k+2.5) to (k/6 +logk/k+2.5), where k is the bit-length of the multiplicand A and multiplier B. We can therefore efficiently speed up the overall performance of the multiplication. Moreover, if we use the new proposes to compute common-multiplicand multiplication, the computational complexity can be reduced from (0.5 k+2 logk/k+5) to (k/3+2 logk/k+5) k-bit additions.

• Periodical: Applied Mechanics and Materials (Volume 619)
• Pages: 342-346
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.619.342
• Online since: August 2014
• Authors: Te Jen Chang*, Ping Sheng Huang, Shan Jen Cheng, Ching Yin Chen, I Hui Pan
• Keywords: Algorithm Design, Canonical Recoding, Common-Multiplicand Multiplication, Complexity Analysis, Public Key Cryptography

References

[1] R. L. Rivest, A. Shamir and L. Adleman: A Method for Obtaining Digital Signatures and Public Key Cryptosystems, Communications of the ACM, Vol. 21 (1978), pp.120-126.

DOI: 10.1145/359340.359342

[2] W. Diffie and E. Hellmen: New Directions in Dryptography, IEEE Transactions on Information Theory, Vol. 22 (1976), pp.644-654.

[3] T. El Gamal: A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory, Vol. 31 (1985), pp.469-472.

DOI: 10.1109/tit.1985.1057074

[4] W. Stallings: Cryptography and Network Security Principles and Practice, 3rd ed. New York, Prentice-Hall (2002).

[5] C. C. Chang, Y. T. Kuo and C. H. Lin in: Fast Algorithms for Common Multiplicand Multiplication and Exponentiation by Performing Complements, Proceeding of 17th International Conference on Advanced Information Networking and Applications, pp.807-811 (2003).

DOI: 10.1109/aina.2003.1193005

[6] A. Avizienis: Signed-digit Number Representations for Fast Parallel Arithmetic, IRE Transactions on Electronic Computers, Vol. 10 (1961), pp.389-400.

DOI: 10.1109/tec.1961.5219227

[7] C. K. Koc and S. Johnson: Multiplication of Signed-digit Numbers, Electronics Letters, Vol. 30 (1994), pp.840-841.

DOI: 10.1049/el:19940623

[8] S. M. Yen and C. S. Laih: Common-multiplicand-multiplication and its Applications to Public Key Cryptography, Electronics Letters, Vol. 29 (1993), pp.1583-1584.

DOI: 10.1049/el:19931055

[9] T. C. Wu and Y. S. Chang: Improved Generalization Common -multiplicand-multiplications Algorithm of Yen and Laih, Electronics Letters, Vol. 31 (1995), pp.1738-1739.

DOI: 10.1049/el:19951189

[10] S. M. Yen: Improved common-multiplicand-multiplication and fast exponentiation by exponent decomposition, IEICE Transaction on Fundamentals, Vol. E80-A (1997), p.1160–1163.

[11] C. McIvor, M. McLoone and J. V. McCanny: Modified Montgomery Modular Multiplication and RSA Exponentiation Techniques, IEE Proceeding-Computers and Digital Techniques, Vol. 151 (2004), pp.402-408.

DOI: 10.1049/ip-cdt:20040791