Skip to main content

09.01.2025

ATP-Optimized Implementation of Four-Way Toom-Cook Multiplications on FPGAs for Large Integer Arithmetic

verfasst von: Monalisa Das, Babita Jajodia

Erschienen in: Circuits, Systems, and Signal Processing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Toom-Cook multiplication algorithm is one of the most efficient method compared to other traditional large-integer multiplication algorithms. However, in most cases, implementation of this algorithm in hardware is practically avoided due to presence of exact-divisions at intermediate steps of computation. Thus this paper proposes ways to overcome the limitation by designing a hardware-optimized, division-free Toom-4 multiplication algorithm. This is done by eliminating the effects of division due to odd factors in the denominator using a scaling factor, at the interpolation step of the algorithm. Further optimization is done by replacing the direct point-wise multiplication with an optimized Schoolbook multiplication. The overall performance of the proposed architecture is estimated using Area-Time-Product (ATP) and hardware implementation is done using Virtex-7 FPGA device in Xilinx-ISE platform. Practically, the proposed design performs better in terms of speed and resource utilization for higher input bits compared to other state-of-the-art designs; for example for 512 input bits, the percentage ATP of the proposed design is 75.077%, 98.822% and 57.316% superior performance compared to Traditional Schoolbook Multiplication, Karatsuba (Toom-2) multiplication and Toom-4 multiplication respectively.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

ATZelektronik

Die Fachzeitschrift ATZelektronik bietet für Entwickler und Entscheider in der Automobil- und Zulieferindustrie qualitativ hochwertige und fundierte Informationen aus dem gesamten Spektrum der Pkw- und Nutzfahrzeug-Elektronik. 

Lassen Sie sich jetzt unverbindlich 2 kostenlose Ausgabe zusenden.

ATZelectronics worldwide

ATZlectronics worldwide is up-to-speed on new trends and developments in automotive electronics on a scientific level with a high depth of information. 

Order your 30-days-trial for free and without any commitment.

Weitere Produktempfehlungen anzeigen
Literatur
1.
Zurück zum Zitat F. Antognazza, A. Barenghi, G. Pelosi, R. Susella, Performance and efficiency exploration of hardware polynomial multipliers for post-quantum lattice-based cryptosystems. SN Comput. Sci. 5, 212 (2024)CrossRefMATH F. Antognazza, A. Barenghi, G. Pelosi, R. Susella, Performance and efficiency exploration of hardware polynomial multipliers for post-quantum lattice-based cryptosystems. SN Comput. Sci. 5, 212 (2024)CrossRefMATH
2.
Zurück zum Zitat H. Becker, J. Bermudo Mera, A. Karmakar, J. Yiu, I. Verbauwhede, Polynomial multiplication on embedded vector architectures. IACR Transact. Cryptogr. Hardw. Embed. Syst. 2022, 482–505 (2021)CrossRef H. Becker, J. Bermudo Mera, A. Karmakar, J. Yiu, I. Verbauwhede, Polynomial multiplication on embedded vector architectures. IACR Transact. Cryptogr. Hardw. Embed. Syst. 2022, 482–505 (2021)CrossRef
3.
Zurück zum Zitat G. Bilardi, L. De Stefani, The I/O complexity of toom-cook integer multiplication. Proceedings Of The Thirtieth Annual ACM-SIAM Symposium On Discrete Algorithms. pp. 2034-2052 (2019) G. Bilardi, L. De Stefani, The I/O complexity of toom-cook integer multiplication. Proceedings Of The Thirtieth Annual ACM-SIAM Symposium On Discrete Algorithms. pp. 2034-2052 (2019)
4.
Zurück zum Zitat M. Das, B. Jajodia, Hardware design of optimized large integer schoolbook polynomial multiplications on FPGA. 2022 IEEE 19th Int. SoC Design Conf. (ISOCC). pp. 1-2 (2022) M. Das, B. Jajodia, Hardware design of optimized large integer schoolbook polynomial multiplications on FPGA. 2022 IEEE 19th Int. SoC Design Conf. (ISOCC). pp. 1-2 (2022)
5.
Zurück zum Zitat J. Ding, S. Li, Z. Gu, High-speed ECC processor over NIST prime fields applied with toom-cook multiplication. IEEE Trans. Circuits Syst. I Reg. Papers. 66, 1003–1016 (2019)CrossRefMATH J. Ding, S. Li, Z. Gu, High-speed ECC processor over NIST prime fields applied with toom-cook multiplication. IEEE Trans. Circuits Syst. I Reg. Papers. 66, 1003–1016 (2019)CrossRefMATH
6.
Zurück zum Zitat M. Elia, Loss of Precision in Implementations of the Toom-Cook Algorithm. Graduate College Dissertations And Theses. (2021) M. Elia, Loss of Precision in Implementations of the Toom-Cook Algorithm. Graduate College Dissertations And Theses. (2021)
7.
Zurück zum Zitat Francisco Pajuelo-Holguera, José M. Granado-Criado, Juan A. Gómez-Pulido, Fast montgomery modular multiplier using FPGAs. IEEE Embedded Sys. Lett. 14, 19–22 (2022)CrossRef Francisco Pajuelo-Holguera, José M. Granado-Criado, Juan A. Gómez-Pulido, Fast montgomery modular multiplier using FPGAs. IEEE Embedded Sys. Lett. 14, 19–22 (2022)CrossRef
8.
Zurück zum Zitat T. Fritzmann, J. Sepúlveda, Efficient and Flexible Low-Power NTT for Lattice-Based Cryptography. 2019 IEEE Int. Symp. On Hardware Oriented Security And Trust (HOST). pp. 141-150 (2019) T. Fritzmann, J. Sepúlveda, Efficient and Flexible Low-Power NTT for Lattice-Based Cryptography. 2019 IEEE Int. Symp. On Hardware Oriented Security And Trust (HOST). pp. 141-150 (2019)
9.
Zurück zum Zitat Z. Gu, S. Li, A division-free Toom-Cook multiplication-based montgomery modular multiplication. IEEE Trans. Circuits Syst. II Exp. Briefs. 66, 1401–1405 (2019)MATH Z. Gu, S. Li, A division-free Toom-Cook multiplication-based montgomery modular multiplication. IEEE Trans. Circuits Syst. II Exp. Briefs. 66, 1401–1405 (2019)MATH
10.
Zurück zum Zitat M. Imran, Z. Abideen, S. Pagliarini, An Open-source Library of Large Integer Polynomial Multipliers. 2021 24th International Symposium On Design And Diagnostics Of Electronic Circuits & Systems (DDECS). pp. 145-150 (2021) M. Imran, Z. Abideen, S. Pagliarini, An Open-source Library of Large Integer Polynomial Multipliers. 2021 24th International Symposium On Design And Diagnostics Of Electronic Circuits & Systems (DDECS). pp. 145-150 (2021)
11.
Zurück zum Zitat M. Imran, Z. Abideen, S. Pagliarini, A versatile and flexible multiplier generator for large integer polynomials. J. Hardw. Syst. Secur. 7, 55 (2023)CrossRefMATH M. Imran, Z. Abideen, S. Pagliarini, A versatile and flexible multiplier generator for large integer polynomials. J. Hardw. Syst. Secur. 7, 55 (2023)CrossRefMATH
12.
Zurück zum Zitat A. Jose Maria Bermudo Mera, I. Verbauwhede, Time-memory trade-off in Toom-Cook multiplication: an application to module-lattice-based cryptography. Cryptology EPrint Archive, Paper 2020/268. (2020) A. Jose Maria Bermudo Mera, I. Verbauwhede, Time-memory trade-off in Toom-Cook multiplication: an application to module-lattice-based cryptography. Cryptology EPrint Archive, Paper 2020/268. (2020)
13.
Zurück zum Zitat R. Kadu, D. Adane, Hardware Implementation of Elliptic Curve Cryptosystem Using Optimized Scalar Multiplication (Smart Trends In Computing And Communications, Springer, 2020), pp.307–316MATH R. Kadu, D. Adane, Hardware Implementation of Elliptic Curve Cryptosystem Using Optimized Scalar Multiplication (Smart Trends In Computing And Communications, Springer, 2020), pp.307–316MATH
14.
Zurück zum Zitat A. Karatsuba, Y. Ofman, Multiplication of multidigit numbers on automata. Soviet Phys. Doklady. 7, 595–596 (1963)MATH A. Karatsuba, Y. Ofman, Multiplication of multidigit numbers on automata. Soviet Phys. Doklady. 7, 595–596 (1963)MATH
16.
Zurück zum Zitat C. Lee, P. Meher, and W. Lee, Subquadratic space complexity digit-serial multiplier over binary extension fields using Toom-Cook algorithm. 2014 Int. Symp. On Integrated Circuits (ISIC). pp. 176-179 (2014) C. Lee, P. Meher, and W. Lee, Subquadratic space complexity digit-serial multiplier over binary extension fields using Toom-Cook algorithm. 2014 Int. Symp. On Integrated Circuits (ISIC). pp. 176-179 (2014)
17.
Zurück zum Zitat R. Liu, S. Li, A low area ASIC implementation of 272 bit multiplier. 2017 International Conference On Electron Devices And Solid-State Circuits (EDSSC). pp. 1-2 (2017) R. Liu, S. Li, A low area ASIC implementation of 272 bit multiplier. 2017 International Conference On Electron Devices And Solid-State Circuits (EDSSC). pp. 1-2 (2017)
20.
Zurück zum Zitat D. Putranto, R. Wardhani, H. Larasati, H. Kim, Space and time-efficient quantum multiplier in post quantum cryptography era. IEEE Access 11, 21848–21862 (2023)CrossRefMATH D. Putranto, R. Wardhani, H. Larasati, H. Kim, Space and time-efficient quantum multiplier in post quantum cryptography era. IEEE Access 11, 21848–21862 (2023)CrossRefMATH
21.
Zurück zum Zitat A. Qadir, N. Varol, A Review Paper on Cryptography. 2019 7th International Symposium On Digital Forensics And Security (ISDFS). pp. 1-6 (2019) A. Qadir, N. Varol, A Review Paper on Cryptography. 2019 7th International Symposium On Digital Forensics And Security (ISDFS). pp. 1-6 (2019)
22.
Zurück zum Zitat C. Rafferty, M. O’Neill, N. Hanley, Evaluation of large integer multiplication methods on hardware. IEEE Transact. Comput. 66, 1369–1382 (2017)MathSciNetCrossRefMATH C. Rafferty, M. O’Neill, N. Hanley, Evaluation of large integer multiplication methods on hardware. IEEE Transact. Comput. 66, 1369–1382 (2017)MathSciNetCrossRefMATH
23.
Zurück zum Zitat B. Rashidi, Throughput/area efficient implementation of scalable polynomial basis multiplication. J. Hardw. Syst. Secur. 4, 120 (2020)CrossRefMATH B. Rashidi, Throughput/area efficient implementation of scalable polynomial basis multiplication. J. Hardw. Syst. Secur. 4, 120 (2020)CrossRefMATH
24.
Zurück zum Zitat A. Toom, The complexity of a scheme of functional elements simulating the multiplication of integers. Soviet Math. Doklady. 7, 714–716 (1963)MATH A. Toom, The complexity of a scheme of functional elements simulating the multiplication of integers. Soviet Math. Doklady. 7, 714–716 (1963)MATH
25.
Zurück zum Zitat Q. Tian, Y. Wang, G. Liu, X. Liu, J. Diao, H. Xu, Hardware-Efficient Parallel FIR Filter Structure Based on Modified Cook-Toom Algorithm. 2018 IEEE Asia Pacific Conf. On Circuits And Syst. (APCCAS). pp. 342-345 (2018) Q. Tian, Y. Wang, G. Liu, X. Liu, J. Diao, H. Xu, Hardware-Efficient Parallel FIR Filter Structure Based on Modified Cook-Toom Algorithm. 2018 IEEE Asia Pacific Conf. On Circuits And Syst. (APCCAS). pp. 342-345 (2018)
26.
Zurück zum Zitat J. Wang, C. Yang, F. Zhang, Y. Meng, Y. Su, TCPM a reconfigurable and efficient toom-cook-based polynomial multiplier over rings using a novel compressed postprocessing algorithm. IEEE Transact. Very Large Scale Integr. (VLSI) Syst. 31, 1153–1166 (2023)CrossRefMATH J. Wang, C. Yang, F. Zhang, Y. Meng, Y. Su, TCPM a reconfigurable and efficient toom-cook-based polynomial multiplier over rings using a novel compressed postprocessing algorithm. IEEE Transact. Very Large Scale Integr. (VLSI) Syst. 31, 1153–1166 (2023)CrossRefMATH
Metadaten
Titel
ATP-Optimized Implementation of Four-Way Toom-Cook Multiplications on FPGAs for Large Integer Arithmetic
verfasst von
Monalisa Das
Babita Jajodia
Publikationsdatum
09.01.2025
Verlag
Springer US
Erschienen in
Circuits, Systems, and Signal Processing
Print ISSN: 0278-081X
Elektronische ISSN: 1531-5878
DOI
https://doi.org/10.1007/s00034-024-02978-7