Parallelization of Integer Squaring Algorithms with Delayed Carry

Korchenko Oleksandr, Kovtun Vladislav, Okhrimenko Andrew

  Open Access OPEN ACCESS  Peer Reviewed PEER-REVIEWED

Parallelization of Integer Squaring Algorithms with Delayed Carry

Korchenko Oleksandr1, Kovtun Vladislav1, Okhrimenko Andrew1,

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

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.

At a glance: Figures

Cite this article:

  • Oleksandr, Korchenko, Kovtun Vladislav, and Okhrimenko Andrew. "Parallelization of Integer Squaring Algorithms with Delayed Carry." Journal of Computer Networks 2.2 (2014): 10-17.
  • Oleksandr, K. , Vladislav, K. , & Andrew, O. (2014). Parallelization of Integer Squaring Algorithms with Delayed Carry. Journal of Computer Networks, 2(2), 10-17.
  • Oleksandr, Korchenko, Kovtun Vladislav, and Okhrimenko Andrew. "Parallelization of Integer Squaring Algorithms with Delayed Carry." Journal of Computer Networks 2, no. 2 (2014): 10-17.

Import into BibTeX Import into EndNote Import into RefMan Import into RefWorks

1. Introduction

Cryptographic transformation with public key (CTPK) are the basis for most modern cryptosystems. Increasing amounts of information that needs to be protected, makes specific demands for CTPK. Multiplicative operations [2, 3], such as multiplication and squaring of integers, are the most frequently used in CTPK. One of the performance increasing approaches in CTPK is increasing the productivity of basic operations, such as multiplication, squaring, modular reduction and multiplicative inversion. Performance increasing approaches in CTPK by increasing the productivity of integer multiplication were reviewed in [4, 5, 6]. The main goal of this paper is to find ways of increasing performance of CTPK, by increasing productivity of squaring integers, using the delayed carry mechanism [5, 6] and efficient parallelization approaches [4].

Squaring is a special case of multiplication where both multipliers are equal [1, 3]. Show features of multiplication and squaring by considering "schoolbook" multiplication of two integers 123 and 456, Figure 1.

Figure 1 shows that to calculate the product of two integers 123 and 456, it should complete 9 unique multiplication operations. Squaring using "schoolbook" multiplication allows some optimizations. Multiply integer 123 by itself, using "schoolbook" multiplication Figure 2.

Figure 1. "Schoolbook" multiplication of two integers
Figure 2. "Schoolbook" multiplication integer by itself

Figure 2 shows how to multiply decimals in a different order, such as products in rows 0 and 2 in column 2 (3 * 1 = 1 * 3), products in rows 0 and 1 in column 1 (3 * 2 = 2 * 3) and products in rows 1 and 2 in column 3: (1 * 2 = 2 * 1). Therefore, for squaring for n-digit number, there are only unique multiplications required ( operations required for multiplication in common case).

Let be integer being squared, а -th term of . It is easy to notice features:

1. In row the product in column has a term in it. In Figure 2 it 3 * 3, 2 * 2, 1 * 1.

2. Every non-square term of a column will appear twice (product in column in row , where has a pair). In Figure 2 it 3 * 1 = 1 * 3, 3 * 2 = 2 * 3 and 1 * 2 = 2 * 1. Every odd column is made-up entirely of product pairs.

3. For row , such as and , the first unique product that is not a square, is located in the column . In Figure 2 it 2 * 1.

2. Multiplication Algorithm Modified Comba

In [5] proposed generalized modified algorithm Comba for integer multiplication – Modified Comba (MC), which uses the idea of delayed carry. The basis of the algorithm is loops (p.2 and p.3), and inner loops (p.2.1 and p.3.1). At the lowest level of the hierarchy, in loops p.2.1, p.3.1 there are multiplication and accumulation of delayed carry. Accumulated carry is taken into account in the final iterations of the loops p.2 and p.3. Using 2w-bit variables for storing w-bit variables eliminates the carry accounting of w-bit variable after each arithmetic operation. Carry accumulated in the higher part of the 2w-bit variable and is taken into account when needed, Figure 3. The generalized algorithm MC [5] for the w-bit systems is given below.

Multiplication algorithm 1. Modified Comba

INPUT: , ,

OUTPUT:

1. , , .

2. For , , do

2.1. For , , , , do

2.1.1. .

2.1.2. ,

2.2. ,

2.3. , , , .

3. For , ,, , do

3.1. For , , , , do

3.1.1. .

3.1.2. ,

3.2. ,

3.3. , , , .

4. .

5. Return .

where n – number of w-bit machine words required to store the multiplier of given size, – a multiplication operation for w-bit words, – an addition operation for 2w-bit and w-bit words. Assignment operations do not take into account in computational complexity of the algorithms.

Using the idea of delayed carry it can independently produce addition of multiplication results corresponding by columns, that enables to perform the accumulation of sum of high and least significant bit in separate parallel threads. However, it is necessary to make an adjustment (account carry) , and set result after sum accumulation in each thread. Figure 3 and Figure 4 is a graphical interpretation of the MC algorithm, for n=3, where well-defined results addition for corresponding products in columns.

Figure 3. Graphical interpretation of loop 2 in MC algorithm
Figure 4. Graphical interpretation of loop 3 in MC algorithm

3. Squaring Algorithms

3.1. Squaring algorithm Modified Comba SQR

Using delayed carry mechanism [5, 6] and approaches to parallelization [4, 5], were offer three squaring algorithms that take account the above features. Consider squaring features, the MC algorithm was modified in inner loops of delayed carry accumulation (p.2.1 and p.3.1), and added an additional check to avoid duplication in the sum accumulation (p.2.1.2 and p.3.1.2 ).

Modified Comba SQR (MCSQR) is squaring algorithm for w-bit machine words, based on multiplication algorithm MC [4, 5, 6].

Squaring algorithm 1. Modified Comba SQR.

INPUT: , ,

OUTPUT:

1. , , .

2. For , , do

2.1. For , , , , do

2.1.1. .

2.1.2. if then ,

;

else ,

2.2. ,

2.3. , , , .

3. For , ,, , do

3.1. For , , , , do

3.1.1. .

3.1.2. if then ,

;

else ,

3.2. ,

3.3. , , , .

4. .

5. Return .

The computational complexity of the MCSQR algorithm:

where n – number of w-bit machine words required to store the multiplier of given size, – a multiplication operation for w-bit words, – an addition operation for 2w-bit and w-bit words, – a word shift operation. Assignment operations do not take into account in computational complexity of the algorithms.

The evaluation results of computational complexity of MCSQR for different bit length multipliers are shown in Table 1 and Table 2 (MUL, ADD and SHIFT – amount of required multiplication, addition and shift operations).

Table 1. The number of operations for MCSQR (w=32 bit)

Table 2. The number of operations for MCSQR (w=64 bit)

Table 2 shows that using 64-bit machine words in MCSQR algorithm can significantly reduce the number of necessary operations (including reducing the number of multiplications by 4 times).

3.2. Squaring Algorithms with Parallelization Techniques

The delayed carry mechanism allows formulating several approaches to the MCSQR parallelization:

•  Parallel execution (in two parallel threads) of loops in the step 2 and 3 with further final result correction.

•  Parallel execution (number of parallel threads) of iterations in loops in step 2 and 3 with further intermediate results (from parallel threads) merging.


3.2.1. Algorithm Modified Comba SQR 2x

Algorithm with two parallel processing threads and paralleling features of the MCSQR algorithm was proposed. Modified Comba SQR 2x (MCSQR2x) is squaring algorithm for w-bit platforms, based on multiplication algorithm Modified Comba 2x (MC2x) [4, 5] with two parallel processing threads.

Squaring algorithm 2. Modified Comba SQR 2x with two parallel processing threads:

INPUT: , ,

OUTPUT:

1. #pragma omp parallel sections begin

1.1. #pragma omp section begin

1.1.1. , , .

1.1.2. For , , do

1.1.2.1. For , , , , do

1.1.2.1.1. .

1.1.2.1.2. if then ,

;

else ,

1.1.2.2. ,

1.1.2.3., ,

, .

1.1.3. .

#pragma omp section end

1.2. #pragma omp section begin

1.2.1. , , .

1.2.2. For , ,, , do

1.2.2.1. For , , , , do

1.2.2.1.1. .

1.2.2.1.2. if then ,

;

else ,

1.2.2.2. ,

1.2.2.3. , ,

, .

#pragma omp section end

#pragma omp parallel sections end

2. For , , do

2.1. .

2.2. .

2.3. .

3. .

4. Return .

The computational complexity of the MCSQR2x algorithm:

where n – number of w-bit machine words required to store the multiplier of given size, – a multiplication operation for w-bit words, – an addition operation for 2w-bit and w-bit words, – a shift operation. Assignment operations do not take into account in computational complexity of the algorithms.

The evaluation results of computational complexity of MCSQR2x for different bit length multipliers are shown in Table 3 and Table 4 (MUL, ADD and SHIFT – amount of required multiplication, addition and shift operations):

Table 3. The number of operations for MCSQR2X (w=32 bit)

Table 4. The number of operations for MCSQR2x (w=64 bit)


3.2.2. Algorithm Modified Comba SQR Mx

Modified Comba SQR Mx (MCSQRMx) is the squaring algorithm for w-bit platforms, based on multiplication algorithm Modified Comba Mx (MCMx) with multiple parallel processing threads [4, 5] :

Squaring algorithm 3. Modified Comba SQR Mx with multiple parallel processing threads

INPUT: , ,

OUTPUT:

1. .

2. Arrays and , .

3. #pragma omp parallel begin

4. #pragma omp for nowait begin

4.1. For , , do

4.1.1. , .

4.1.2. For , , , , do

4.1.2.1. .

4.1.2.2. if then ,

;

else ,

4.1.3. ,

#pragma omp for end

5. #pragma omp for nowait begin

5.1. For , , do

5.1.1. , .

5.1.2. For , , , , do

5.1.2.1. .

5.1.2.2. if then ,

;

else ,

5.1.3. ,

5.1.4. .

#pragma omp for end

#pragma omp parallel end

6.

7. For , , do

7.1. .

7.2. .

7.3. .

7.4. .

8. .

9. Return .

The computational complexity of the MCSQRMx algorithm:

where Z – parallel threads count, n – number of w-bit machine words required to store the multiplier of given size, – a multiplication operation for w-bit words, – an addition operation for 2w-bit and w-bit words, – a word shift operation. Assignment operations do not take into account in computational complexity of the algorithms.

The evaluation results of computational complexity of MCSQR2x for different bit length multipliers are shown in Table 5 and Table 6 for Z=4 (MUL, ADD and SHIFT – amount of required multiplication, addition and shift operations):

Table 5. The number of operations for MCSQRMX (w=32 bit)

Table 6. The number of operations for MCSQRMx (w=64 bit)

Theoretical calculations show that the parallel squaring algorithms have a lower computational complexity, primarily due to the parallel execution of the elementary operations of addition and multiplication. Furthermore, the use of 64-bit machine words reduces the number of multiplications by 4 times.

4. Field Research

Squaring algorithms MCSQR, MCSQR2x and MCSQRMx as previously proposed algorithms for multiplication MC, MC2x and MCMx (Kovtun et al., 2012), (Kovtun and Okhrimenko, 2012), (Kovtun and Okhrimenko, 2013) have been implemented in software in C++ using the Intel C + + Compiler XE 13. The proposed algorithms have been implemented for 32- and 64-bit platforms. Measurements were performed on a computer running Microsoft Windows 7 Ultimate x64 SP1 and the processor Intel Core i5-3570 (6M Cache, 3.40 GHz) with four physical cores. For multiplication of two 64-bit integers, have been used the built-in compiler intrinsic function _umul128, (128-bit result of the multiplication is represented as an array of 64-bit words). Comparison of the results occurred by comparing the average time of multiplication operations in software implementation MC, MC2x and MCMx and the proposed algorithms squaring MCSQR, MCSQR2x and MCSQRMx, for 1 million iterations. The experimental results for 32-bit platforms are shown in Table 7 and Table 8.

Table 7. The experimental results for squaring (w=32 bit)

Table 8. The experimental results for multiplication (w=32 bit)

It is proposed to normalize the results by dividing the results of MC, MC2x and MCMx to results MCSQR, MCSQR2x and MCSQRMx. The normalized results are shown in Table 9.

Table 9. Normalized results of experiments for w = 32 bit

Table 9 shows that all proposed squaring algorithms for 32-bit platforms are effectively than multiplying algorithms. Single-threaded algorithm MCSQR is more efficient than algorithm MC by 5%, and advantage increases to 15% with the increase of the multipliers bit size. The algorithm MCSQR2x is more efficient than algorithm MC2x by 6%, and advantage increases to 56% with the increase of the multipliers bit size. Multi-threaded algorithm MCSQRMx is more effectively than algorithm MCMx by 6%, and advantage increases to 9% with the increase of the multipliers bit size.

The experimental results for 64-bit platforms are shown in Table 10 and Table 11.

Table 10. The experimental results for squaring (w=64 bit)

Table 11. The experimental results for multiplication (w=64 bit)

It is proposed to normalize the results for 64-bit platforms by dividing the results of MC, MC2x and MCMx to results MCSQR, MCSQR2x and MCSQRMx too. The normalized results are shown in Table 12.

Table 12. Normalized results of experiments for w = 64 bit

Table 12 shows that all proposed squaring algorithms for 64-bit platforms are effectively than multiplying algorithms. Single-threaded algorithm MCSQR is more efficient than algorithm MC by 7%, and advantage increases to 36% with the increase of the multipliers bit size. The algorithm MCSQR2x is more efficient than algorithm MC2x by 30%, and advantage increases to 41% with the increase of the multipliers bit size. Multi-threaded algorithm MCSQRMx is more effectively than algorithm MCMx in average of 37%.

To compare the performance of software implementations of squaring algorithms for 32 and 64 bit platforms, the results obtained on 32-bit platform were divided by results on 64-bit platform, for the same algorithms. The comparison results are shown in Table 13 and Table 14.

Table 14 shows that, as in case of multiplication, software implementations of squaring algorithms for 64-bit platforms were more effective than the same implementation for 32-bit platforms (up to 4 times for the algorithm MCSQR, up to 3,6 times for the algorithm MCSQR2x). Multithreaded multiplication and squaring algorithms for 32-bit platforms was more effective than for 64-bit, because there are not support 128-bit operations in modern compilers, that’s why it require software emulation such operations. MCSQRMx algorithm for 64-bit platforms is more effectively on 128-512 bits multipliers (4-6%), which are widely used in cryptography.

Table 13. Performance comparing of squaring software implementations

Table 14. Performance comparing of multiplication software implementations

Theoretical estimation for MCSQR and MCSQR2x confirmed by practical results of research. MCSQRMx algorithm test results for 64-bit platforms indicate that there are no operations performed on 128-bit data array.

5. Conclusions

Using previously proposed approaches to improve the performance of the integers multiplication [4, 5, 6] have developed squaring algorithms Modified Comba SQR, Modified Comba SQR 2x and Modified Comba SQR Mx.

Theoretical calculations show that the parallel squaring algorithms have a lower computational complexity, primarily due to the parallel execution of the elementary operations of addition and multiplication. Furthermore, the use of 64-bit machine words reduces the number of multiplications by 4 times.

Software implementations of squaring algorithms for 64-bit platforms were more effective than the same implementation for 32-bit platforms (up to 4 times for the algorithm MCSQR, up to 3,6 times for the algorithm MCSQR2x). MCSQRMx algorithm for 64-bit platforms is more effectively on 128-512 bits multipliers (4-6%), which are widely used in cryptography. Multithreaded multiplication and squaring algorithms for 32-bit platforms was more effective than for 64-bit, because there are not support 128-bit operations in modern compilers, that’s why it require software emulation such operations.

Experimental researches have shown the effectiveness of the proposed squaring algorithms over multiplication algorithms for 32-bit and 64-bit platforms. The theoretical results are confirmed by practice.

The most perspective algorithm is MCSQRMx, which shows significantly better results than other presented algorithms. MCSQRMx has a high degree of parallelism, which allows implementing it on various microprocessor platforms, that’s why further research will focus on its development using specialized software and hardware (e.g., NVIDIA CUDA and OpenCL).

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.
In article      
 
[2]  Denis, T., Rose G. (2006). BigNum Math: Implementing Cryptographic Multiple Precision Arithmetic, Elsevier/Syngress, 2006, 315.
In article      
 
[3]  Hankerson, D., Menezes, A.J., Vanstone, S. Guide to Elliptic Curve Cryptography, Springer-Verlag Professional Computing Series, 2004, 332.
In article      
 
[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.
In article      
 
[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.
In article      
 
[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.
In article      
 
comments powered by Disqus
  • CiteULikeCiteULike
  • MendeleyMendeley
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn