Efficient digit-serial multiplier employing Karatsuba algorithm

Shyan-Ming Yuan*, Chiou Yng Lee, Chia Chen Fan

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper presents a efficient digit-serial GF(2m) multiplier. The proposed architecture using digit-serial of concept to combine the principle of Karatsuba multiplier which can reduce circuit space complexity, also it is suitable for Elliptic Curve Cryptography (ECC) technology. We knows that the password system’s operation core is a multiplier, however that password system’s multiplier is very big, so it is necessary for reduce the area and time’s complexity. This paper is implement three smaller multiplier and digit-serial in FPGA to reduce time and area complexity. This method uses (formula presented)3 2 dm AND gate, 6 m + n+ 3 2 2 dm m + +d-7 XORs and 3 m-3 registers. The paper using Altera FPGA Quartus II to simulate four different multipliers, 36 × 36, 84 × 84, 126 × 126 and 204 × 204, and implemented on Cyclone II EP2C70F896C8 experimental platform. The experimental results show that the proposed multipliers have lower time complexity than the existing digit-serial structures. The proposed architecture can reduce the time × space complexity decreasing when the bit-size of multiplier is increasing.

Original languageEnglish
Title of host publicationGenetic and Evolutionary Computing - Proceedings of the 9th International Conference on Genetic and Evolutionary Computing
EditorsJerry Chun-Wei Lin, Jeng-Shyang Pan, Thi Thi Zin, Pyke Tin, Mitsuhiro Yokota
PublisherSpringer Verlag
Pages221-231
Number of pages11
ISBN (Print)9783319232065
DOIs
StatePublished - 1 Jan 2015
Event9th International Conference on Genetic and Evolutionary Computing, ICGEC 2015 - Yangon, Myanmar
Duration: 26 Aug 201528 Aug 2015

Publication series

NameAdvances in Intelligent Systems and Computing
Volume388
ISSN (Print)2194-5357

Conference

Conference9th International Conference on Genetic and Evolutionary Computing, ICGEC 2015
CountryMyanmar
CityYangon
Period26/08/1528/08/15

Keywords

  • Digit-serial
  • Finite field
  • Karatsuba

Fingerprint Dive into the research topics of 'Efficient digit-serial multiplier employing Karatsuba algorithm'. Together they form a unique fingerprint.

  • Cite this

    Yuan, S-M., Lee, C. Y., & Fan, C. C. (2015). Efficient digit-serial multiplier employing Karatsuba algorithm. In J. C-W. Lin, J-S. Pan, T. T. Zin, P. Tin, & M. Yokota (Eds.), Genetic and Evolutionary Computing - Proceedings of the 9th International Conference on Genetic and Evolutionary Computing (pp. 221-231). (Advances in Intelligent Systems and Computing; Vol. 388). Springer Verlag. https://doi.org/10.1007/978-3-319-23207-2_22