On Using the Carry-Save Technique in the Arithmetic of Long Integer Numbers
DOI:
https://doi.org/10.24160/1993-6982-2018-6-96-102Keywords:
multiplication of long integer numbers, Karatsuba algorithm, shift and add method, carry-save techniqueAbstract
Possible versions of using the carry-save technique (CST) for speeding up multiplication of long integer numbers are described. Application of the CST makes it possible to reduce the overhead computing associated with performing intermediate carryover operations the necessity of which arises in the course of computations. The efficiency of the technique for the modified shift and add method and for the Karatsuba method was investigated. Methods for implementing the multiplication algorithms by means of software featuring high efficiency and portability to various computing platforms have been developed. Theoretical estimates of the number of multiplication, addition, and memory access instructions needed for implementing the algorithms by means of software are obtained. The efficiency of the methods utilizing the CST in comparison with the basic shift and add methods, and the Karatsuba method is experimentally evaluated. The experiments showed high efficiency of the algorithms utilizing the CST including comparison with the existing solutions based on the GMP software library. Application of the CST made it possible to increase the performance of computing by 18% for the modified shift and add method (for 1024-bit numbers) and by 31% for the Karatsuba method (in comparison with the linear implementation of the modified shift and add method). The considered algorithms for multiplying long integer numbers with application of the CST can be effectively used in elaborating portable (without assembler-based insertions) computer algebra software libraries. It is concluded that the optimal choice of a library depends essentially on both the particular application and on the used computing architecture.
References
2. Brent R.Р., Zimmermann P. Modern Computer Arithmetic. N.-Y.: Cambridge University Press, 2010.
3. Карацуба А.А., Офман Ю.П. Умножение многозначных чисел на автоматах // ДАН СССР. 1962. Т. 145. № 2. С. 293—294.
4. Comba P.G. Exponentiation Cryptosystems on the IBM PC // IBM Systems J. 1990. No. 29. Pp. 526—538.
5. Карацуба А.А. Сложность вычислений // Труды МИАН. 1995. Т. 211. С. 186—202.
6. Куляс М.Е. О синтезе программ умножения длинных целых чисел // Программная инженерия. 2017. № 2. С. 66—75.
7. Weimerskirch A., Paar C. Generalization of the Karatsuba Algorithm for efficient Implementation // Cryptology ePrint Archive. 2006. Rep. 224 [Электрон. ресурс] http://eprint.iacr.org/2006/224 (дата обращения 10.10.2017).
8. Khachatrian G., Kuregian M., Ispiryan K., Massey J. Faster Multiplication of Integers for Public-key Applications // Selected Areas in Cryptography. 2001. V. 2259. P. 245—254.
9. Kovtun V.Yu., Okhrimenko A.O. Integer Squaring Algorithm with Delayed Carry Mechanism // Безпека iнформацii. 2013. V 19. No. 3. Pp. 188—192.
10. Scott M. Missing a Trick: Karatsuba Variations // Cryptology ePrint Archive. 2015. Rep. 1247 [Электрон. ресурс] http://eprint.iacr.org/2015/1247 (дата обращения 10.10.2017).
11. Paoloni G. How to Benchmark Code Execution Times on Intel IA-32 and IA-64 Instruction Set Architectures 2010. [Электрон. ресурс] http://www.intel.com/content/dam/www/ public/us/en/documents/white-papers/ia-32-ia-64-benchmarkcode-execution-paper.pdf (дата обращения 12.10.2017).
12. Granlund T. The GMP development team: GNU MP: The GNU Multiple Precision Arithmetic Library [Электрон. ресурс] http://gmplib.org (дата обращения 12.10.2017).
---
Для цитирования: Куляс М.Е. Об использовании техники отложенного переноса в арифметике длинных целых чисел // Вестник МЭИ. 2018. № 6. С. 96—102. DOI: 10.24160/1993-6982-2018-6-96-102.
#
1. Knut D.E. Iskusstvo Programmirovaniya. T. 2. Poluchislennye Algoritmy. M.: Vil'yams, 2007. (in Russian).
2. Brent R.R., Zimmermann P. Modern Computer Arithmetic. N.-Y.: Cambridge University Press, 2010.
3. Karatsuba A.A., Ofman YU.P. Umnozhenie Mnogoznachnyh Chisel na Avtomatah. DAN SSSR. 1962; 145;2: 293—294. (in Russian).
4. Comba P.G. Exponentiation Cryptosystems on the IBM PC. IBM Systems J. 1990;29:526—538.
5. Karatsuba A.A. Slozhnost' Vychisleniy. Trudy MIAN. 1995; 211:186—202. (in Russian).
6. Kulyas M.E. O Sinteze Programm Umnozheniya Dlinnyh Tselyh Chisel. Programmnaya Inzheneriya. 2017;2: 66—75. (in Russian).
7. Weimerskirch A., Paar C. Generalization of the Karatsuba Algorithm for Efficient Implementation. Cryptology ePrint Archive. 2006; 224 [Elektron. Resurs] http://eprint.iacr. org/2006/224 (Data Obrashcheniya 10.10.2017).
8. Khachatrian G., Kuregian M., Ispiryan K., Massey J. Faster Multiplication of Integers for Public-key Applications. Selected Areas in Cryptography. 2001;2259:245—254.
9. Kovtun V.Yu., Okhrimenko A.O. Integer Squaring Algorithm with Delayed Carry Mechanism. Bezpeka informatsii. 2013;19;3:188—192.
10. Scott M. Missing a Trick: Karatsuba Variations. Cryptology ePrint Archive. 2015;1247 [Elektron. Resurs] http:// eprint.iacr.org/2015/1247 (Data Obrashcheniya 10.10.2017).
11. Paoloni G. How to Benchmark Code Execution Times on Intel IA-32 and IA-64 Instruction Set Architectures 2010. [Elektron. Resurs] http://www.intel.com/content/dam/www/ public/us/en/documents/white-papers/ia-32-ia-64-benchmarkcode-execution-paper.pdf (Data Obrashcheniya 12.10.2017).
12. Granlund T. The GMP development team: GNU MP: The GNU Multiple Precision Arithmetic Library [Elektron. Resurs] http://gmplib.org (Data Obrashcheniya 12.10.2017).
---
For citation: Kulyas M.Е. On Using the Carry-Save Technique in the Arithmetic of Long Integer Numbers. MPEI Vestnik. 2018;6: 96—102. (in Russian). DOI: 10.24160/1993-6982-2018-6-96-102.
