Journal of Computer Networks
ISSN (Print): 2372-4749 ISSN (Online): 2372-4757 Website: http://www.sciepub.com/journal/jcn Editor-in-chief: Sergii Kavun, Naima kaabouch
Open Access
Journal Browser
Go
Journal of Computer Networks. 2014, 2(2), 10-17
DOI: 10.12691/jcn-2-2-2
Open AccessResearch Article

Parallelization of Integer Squaring Algorithms with Delayed Carry

Korchenko Oleksandr1, Kovtun Vladislav1 and Okhrimenko Andrew1,

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

Pub. Date: June 03, 2014
(This article belongs to the Special Issue Parallel computing and Protection Information)

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

Creative CommonsThis 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.