Parallelization of Integer Squaring Algorithms with Delayed Carry

Korchenko Oleksandr¹, Kovtun Vladislav¹ and Okhrimenko Andrew^1,

¹Academic Department of IT-Security, National Aviation University, Kiev, Ukraine

Cite this paper:
Korchenko Oleksandr, Kovtun Vladislav and Okhrimenko Andrew. Parallelization of Integer Squaring Algorithms with Delayed Carry. Journal of Computer Networks. 2014; 2(2):10-17. doi: 10.12691/jcn-2-2-2

Abstract

Increasing amounts of information that needs to be protected put in claims specific requirements for information security systems. The main goal of this paper is to find ways to increase performance of cryptographic transformation with public key by increasing performance of integers squaring. Authors use delayed carry mechanism and approaches of effective parallelization for Comba multiplication algorithm, which was previously proposed by authors. They use the idea of carries accumulation by addition products of multiplying the relevant machine words in columns. As a result, it became possible to perform addition of such products in the column independently of each other. However, independent accumulation of products and carries require correction of the intermediate results to account for the accumulated carries. Due to the independence of accumulation in the columns, it became possible to parallelize the process of products accumulation that allowed formulating several approaches. In this paper received theoretical estimates of the computational complexity for proposed squaring algorithms. Software implementations of algorithms in C++ allowed receiving practical results of the performance, which are not contrary to theoretical estimates. The authors first proposed applying the method of delayed carry and parallelization techniques for squaring algorithms, which was previously proposed for integers multiplication.

Keywords:
squaring multiplication integers delayed carry parallelization

This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

References:

[1]	Cohen H., Frey G., Avanzi R., Doche C., Lange T., Nguyen K., Vercauteren F. Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall/CRC, 2006, 843.
[2]	Denis, T., Rose G. (2006). BigNum Math: Implementing Cryptographic Multiple Precision Arithmetic, Elsevier/Syngress, 2006, 315.
[3]	Hankerson, D., Menezes, A.J., Vanstone, S. Guide to Elliptic Curve Cryptography, Springer-Verlag Professional Computing Series, 2004, 332.
[4]	Kovtun, V.Y., Okhrimenko, A.O. “Approaches for the Parallelization of Software Implementation of Integer Multiplication”, Radiotehnika. Vseukrainskij mezhvedomstvennyj nauchno-tehnicheskij sbornik, 171, 123-132. 2012.
[5]	Kovtun, V.Y., Okhrimenko, A.O. “Integer multiplication algorithms with delayed carry for public-key cryptosystems”. In: V.S. Ponomarenko (Eds.), Informacionnye tehnologi i sistemy v upravlenii, obrazovanii, nauke. Kharkiv: Cifrova drukarnja №1. 69-82. 2013.
[6]	Kovtun, V.Y., Okhrimenko, A.O., Nechiporuk, V.V. “Approaches for the performance increasing of software implementation of integer multiplication in prime fields”, Zashchita informacii, 1 (54), 68-75. 2012.