# Techniques for Performance Improvement of Integer Multiplication in Cryptographic Applications

Authors: Robert Brumnik; Vladislav Kovtun; Andrew Okhrimenko; Sergii Kavun
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The problem of arithmetic operations performance in number fields is actively researched by many scientists, as evidenced by significant publications in this field. In this work, we offer some techniques to increase performance of software implementation of finite field multiplication algorithm, for both 32-bit and 64-bit platforms. The developed technique, called “delayed carry mechanism,” allows to preventing necessity to consider a significant bit carry at each iteration of the sum accumulation loop. This mechanism enables reducing the total number of additions and applies the modern parallelization technologies effectively.


---

## Body

## 1. Introduction

The cryptographic transformations with public key are revolutionized from Diffie and Hellman consideration to modern algebraic curves cryptosystems [1]. However, transformations have stayed permanent—with operations in the number field G
F
(
p
). The integer multiplication takes a special place in number field operations; see Figure 1. One of the urgent problems of public key cryptosystem improvements is an increase of software performance and hardware implementation. One of the approaches to increasing cryptosystems performance is the increasing of the performance of finite field arithmetic in multiplication operations.Figure 1
Operation hierarchy of elliptic curve cryptosystem.The problem of the speedup of arithmetic operation in number fields is actively researched by many scientists, as evidenced by significant publications in this area [2–11]. Except the arithmetic operations algorithms, it is interesting to look at/study approaches to the architecture of software libraries [12–21] with field operations, which allow decreasing overheads on field operations in whole.Publications analysis [2–10] enabled extracting the most effective multiplication algorithms, Comba [2, 3] and Karatsuba [3, 8, 10]. However, the Comba algorithm shows better results in tests performance (benchmark) of software implementations on modern platforms [3–9]. Karatsuba-Comba described multiplication (KCM) algorithm for the RISC processors in the article [8]. The KCM algorithm is an interesting symbiosis of Comba and Karatsuba algorithms, where Karatsuba algorithm is specially used for machine word multiplication. As a result, the main goal of this paper is to provide a suggestion for the effective increasing of software implementation of finite field number G
F
(
p
) multiplication (squaring) via well-known Comba algorithm [2, 3, 8]. Such researches were caused by the necessity of effective confirmation of software implementation of known algorithms for continuous development of modern 32-bit and 64-bit platforms. It is important to mention that last ten years have seen much development in the direction of the multicore CPU and multi-CPU systems [8, 9].


## 2. Multiplication Algorithm-Prototype Description and Its Modification

Let us begin by introducing some notation and basic definitions. Carry is a digit that is transferred from one column of digits to another column of more significant digits during a calculation algorithm;w is machine word size and n is the number of machine words required to store a large integer. We present large integers (multipliers) as a set of n machine words; see Figure 2. For example, if we have 65-bit integer, we need three 32-bit machine words to store it.Figure 2
Representation of large integers.The Comba algorithm [2] is based on main loops p. 2 and p. 3 and nested loops p. 2.1 and p. 3.1 (Algorithm 1). In the low level of hierarchy, in loops p. 2.1 and p. 3.1 we will compute 64-bit integer product (
u
v
)
(
2
w
) which consists of two 32-bit integers  u
(
w
) and v
(
w
).Algorithm 1:Comba’s integer multiplication.
Input: integersa
,
b
∈
G
F
(
p
), w
=
32 bit, n
=
lo
g
2
w
a.
Output:c
=
a
·
b
(1)r
0
(
w
)
←
0, r
1
(
w
)
←
0, r
2
(
w
)
←
0.
(2) Fork
←
0, k
<
n, k
+
+ do
(2.1)  Fori
←
0, j
←
k, i
≤
k, i
+
+, j
-
- do
(2.1.1)(
u
v
)
(
w
)
←
a
i
(
w
)
·
b
j
(
w
).
(2.1.2)r
0
(
w
)
←
r
0
(
w
)
+
v
(
w
), r
1
(
w
)
←
r
1
(
w
)
+
u
(
w
)
+
carry, carry
←
0.
(2.1.3)r
2
(
w
)
←
r
2
(
w
)
+
carry, carry
←
0.
(2.2)c
k
(
w
)
←
r
0
(
w
), r
0
(
w
)
←
r
1
(
w
), r
1
(
w
)
←
r
2
(
w
), r
2
(
w
)
←
0.
(3) Fork
←
n, l
←
1, k
<
n
k, k
+
+, l
+
+ do
(3.1) Fori
←
l, j
←
k
-
l, i
<
n, i
+
+, j
-
- do
(3.1.1)(
u
v
)
(
w
)
←
a
i
(
w
)
·
b
j
(
w
).
(3.1.2)r
0
(
w
)
←
r
0
(
w
)
+
v
(
w
), r
1
(
w
)
←
r
1
(
w
)
+
u
(
w
)
+
carry, carry
←
0.
(3.1.3)r
2
(
w
)
←
r
2
(
w
)
+
carry, carry
←
0.
(3.2)c
k
(
w
)
←
r
0
(
w
), r
0
(
w
)
←
r
1
(
w
), r
1
(
w
)
←
r
2
(
w
), r
2
(
w
)
←
0.
(4)c
n
k
(
w
)
←
r
0
(
w
).
(5)  Return(
c
).The sum accumulation occurs in 32-bit temporary variablesr
0, r
1, and r
2, on each iteration p. 2.1.2 and p. 2.1.3.The final result of the assignment is temporary variablesr
0, r
1, and r
2 which are changing at each iteration on p. 2.2.Comba’s algorithm main drawbacks are as follows.(i)
In nested loops p. 2.1 and p. 3.1 there is a sum accumulation with carry in 32-bit temporary variablesr
0, r
1, and r
2, p. 2.1.2, p. 2.1.3 and p. 3.1.2, p. 3.1.3:
2.1.2.
r
0
(
w
)
←
r
0
(
w
)
+
v
(
w
), r
1
(
w
)
←
r
1
(
w
)
+
u
(
w
)
+
carry, carry
←
0.
2.1.3.
r
2
(
w
)
←
r
2
(
w
)
+
carry, carry
←
0.In this case there are 3 additions of 32-bit integer (includes 2 additions with carry) and 3 assignments of 32-bit variablesr
0, r
1 and r
2. The sum accumulation with carry takes place in each iteration of loop p. 2.1.(ii)
In nested loops p. 2.1 and p. 3.1, for the sum accumulation, for 32-bit variablesr
0, r
1, and r
2 the transfers are considered using the assembler code for the implementation of addition operation with carry. This does not allow pairing and parallelizing [22]; therefore we observe an ineffective processor resource usage.
(iii)
Loops p. 2 and p. 3 cannot be effectively parallelized due to high internal linkage code because of carry consideration.It is easy to obtain a computational complexity for Comba’s algorithm:(1)
I
mul
Comba
=
4
I
assign
w
+
(
n
+
1
2
n
+
1
+
n
-
1
2
(
n
-
1
)
)
×
(
1
I
mul
w
+
4
I
add
w
+
6
I
assign
w
)
+
4
(
2
n
-
1
)
I
assign
w
=
4
I
assign
w
+
n
2
(
1
I
mul
w
+
4
I
add
w
+
6
I
assign
w
)
+
4
(
2
n
-
1
)
I
assign
w
,
where I
assign
w is an assignment operation of 32-bit integers, I
add
w is an addition operation of 32-bit integers, and I
mul
w is a multiplication operation of 32-bit integer.Figure2 illustrates the drawbacks of algorithm for n
=
3 and its impact on computational complexity of algorithm.Modern CPUs allow the use of 64-bit data types and operations to achieve better performance, but the algorithm is not adapted for their use.In the upper part of the figure, there are two big coefficientsa and b represented by three 32-bit integers a
=
(
a
2
,
a
1
,
a
0
) and b
=
(
b
2
,
b
1
,
b
0
), where a
i and b
i have a machine-word bit size. Algorithm iterations are presented under the solidus. It should be noted that Comba’s algorithm implements well-known long multiplication technique, with a small difference where the multiplier part a
i
i
=
1
,
n
¯ multiplies all parts of other multipliers b
j
j
=
1
,
n
¯, in case of fulfillment condition (
i
+
j
=
k
) (in columns).Such approach leads not to strings addition (multiplication of intermediate results) as long multiplication but to columns addition. That allows finding a part of resulting productc
i (under the solidus). Each multiplication is accompanied by the sum accumulation, as shown in Figure 3.Figure 3
Graphic interpretation of Comba’s algorithm.The computational complexity forn
=
3 will be
(2)
I
mul
Comba
=
4
I
assign
w
+
9
(
1
I
mul
w
+
4
I
add
w
+
6
I
assign
w
)
+
20
I
assign
w
=
78
I
assign
w
+
9
I
mul
w
+
36
I
add
w
.In the following steps of calculation procedure we eliminate the drawbacks.(i)
The modern 32-bit CPUs effectively implement the addition operations of 32-bit and 64-bit integers, using 32-bit CPUs commands. That allows implementing a carry accumulation by the addition of 32-bit variables in 64-bit variable-accumulator that obviate the need for carry accounting and correction requirements after the addition of variablesr
0, r
1, and r
2. An accumulated carry will be accounted in the final iterations in the loops in p. 2 and p. 3.
(ii)
Modern CPUs have multicore architecture that allows them to execute several instruction flows at the same time. This property brings to parallel iterations execution in loops p. 2 and p. 3 by the OpenMP library [22–24].The following notations are introduced in Algorithm2.(i)
Variablet
(
2
w
) is used to denote 64-bit variables, t
(
w
) is used to denote 32-bit variables;
(ii)
Operationh
i
(
w
)
(
t
(
2
w
)
) is used to extract 32 the most significant bits in 64-bit variable, and operation lo
w
(
w
)
(
t
(
2
w
)
) is used to extract 32 the least significant bits in 64-bit variable.Algorithm 2:Modified Comba’s integer multiplication.
Input: integersa
,
b
∈
G
F
(
p
), w
=
32 bit, n
=
lo
g
2
w
a, n
k
=
2
n
-
1.
Output:c
=
a
·
b
(
1
)  r
0
(
2
w
)
←
0, r
1
(
2
w
)
←
0, r
2
(
2
w
)
←
0.
(
2
)   For k
←
0, k
<
n, k
+
+ do
(
2.1
)   For i
←
0, j
←
k, i
≤
k, i
+
+, j
-
- do
(
2.1
.
1
)  (
u
v
)
(
2
w
)
←
a
i
(
w
)
·
b
j
(
w
).
(
2.1
.
2
)  r
0
(
2
w
)
←
r
0
(
2
w
)
+
v
(
w
), r
1
(
2
w
)
←
r
1
(
2
w
)
+
u
(
w
)
(
2.2
)   r
1
(
2
w
)
←
r
1
(
2
w
)
+
h
i
(
w
)
(
r
0
(
2
w
)
), r
2
(
2
w
)
←
r
2
(
2
w
)
+
h
i
(
w
)
(
r
1
(
2
w
)
)
(
2.3
)   c
k
(
w
)
←
lo
w
(
w
)
(
r
0
(
2
w
)
), r
0
(
2
w
)
←
lo
w
(
w
)
(
r
1
(
2
w
)
), r
1
(
2
w
)
←
lo
w
(
w
)
(
r
2
(
2
w
)
), r
2
(
2
w
)
←
0.
(
3
)   For k
←
n, l
←
1, k
<
n
k, k
+
+, l
+
+ do
(
3.1
)   For i
←
l, j
←
k
-
l, i
<
n, i
+
+, j
-
- do
(3.1.1)(
u
v
)
(
2
w
)
←
a
i
(
w
)
·
b
j
(
w
).
(
3.1
.
2
)  r
0
(
2
w
)
←
r
0
(
2
w
)
+
v
(
w
), r
1
(
2
w
)
←
r
1
(
2
w
)
+
u
(
w
)
(
3.2
)   r
1
(
2
w
)
←
r
1
(
2
w
)
+
h
i
(
w
)
(
r
0
(
2
w
)
), r
2
(
2
w
)
←
r
2
(
2
w
)
+
h
i
(
2
)
(
r
1
(
2
w
)
)
(
3.3
)   c
k
(
w
)
←
lo
w
(
w
)
(
r
0
(
2
w
)
), r
0
(
2
w
)
←
lo
w
(
w
)
(
r
1
(
2
w
)
), r
1
(
2
w
)
←
lo
w
(
w
)
(
r
2
(
2
w
)
), r
2
(
2
w
)
←
0.
(
4
)   c
n
k
(
w
)
←
lo
w
(
w
)
(
r
0
(
2
w
)
).
(
5
)   Return (
c
).It is not difficult to get a computational complexity of modified Comba’s algorithm:(3)
I
mul
Mod
.
Comba
=
4
I
assign
2
w
+
(
n
+
1
2
n
+
1
+
n
-
1
2
(
n
-
1
)
)
×
(
1
I
mul
w
+
2
I
add
2
w
∣
w
+
2
I
assign
2
w
)
+
(
2
n
-
1
)
(
2
I
add
2
w
∣
w
+
1
I
assign
2
w
+
1
I
assign
w
)
=
4
I
assign
2
w
+
n
2
(
1
I
mul
w
+
2
I
add
2
w
∣
w
+
2
I
assign
2
w
)
+
(
2
n
-
1
)
(
2
I
add
2
w
∣
w
+
1
I
assign
2
w
+
1
I
assign
w
)
,
where I
assign
w is an assignment operation of 32-bit integers, I
assign
2
w is an assignment operations of 64-bit integers, I
add
w is an addition operation of 32-bit integers, I
add
2
w
∣
w is an addition operation of 32-bit and 64-bit integers, and I
mul
w is a multiplication of 32-bit integers.Figures4 and 5 illustrate Algorithm 2 for n
=
3; computational complexity in this case will be
(4)
I
mul
Mod
.
Comba
=
27
I
assign
2
w
+
9
I
mul
w
+
28
I
add
2
w
∣
w
+
5
I
assign
w
.Figure 4
Graphic interpretation of loop 2 in modified Comba’s algorithm.Figure 5
Graphic interpretation of loop 3 in modified Comba’s algorithm.


## 3. Comparison with Other Algorithms

In order to provide an objective comparison of given results, the authors have made the review of well-known software math libraries [12–21] for public key cryptography. According to results review [25, 26], the software library GMP was an etalon [12]. GMP uses Karatsuba’s integer multiplication algorithm [12]. The comparison of software implementations will be done by comparing the execution average time of software implementation of Comba and modified Comba’s algorithms and implemented in GMP library for one million iterations.To measure the algorithm performance of software implementation we can use protocols in fields of Table1 from [27], except G
F
(
p
82
). These fields are recommended [3, 27] for usage in cryptographic application for different security levels. Table 1 gives a brief definition of fields and prime modules.Table 1
Performance measurements of fields.
Field
Prime module
G
F
(
p
82
)
5000000000000000008503491
G
F
(
p
164
)
24999999999994130438600999402209463966197516075699
G
F
(
p
192
)
6277101735386680763835789423 176059013767194773182842284081
G
F
(
p
224
)
26959946667150639794667015087019630673557916260026308143510066298881
G
F
(
p
256
)
1157920892103562487626974469494075735300861434152903141955336313088670 97853951
G
F
(
p
320
)
4271974071841820164790042159200669057836414062331724137933565193825968 686576267080087081984838097
G
F
(
p
384
)
3940200619639447921227904010014361380507973927046544666794690527962765  939911326356939895 6308152294913554433653942643
G
F
(
p
521
)
68647976601306097149819007990813932172694353001433054093944634591855431833976553942450577463332171975329639963713633211138647686124403803403 72808892707005449The proposed modified algorithm Comba and its prototype-algorithm Comba were implemented in C++, compiled with Microsoft Visual Studio 2010 in Release Win32 configuration with Maximize Speed parameter and SSE2 instruction support.We will use the etalon library GMP v4.1.2 compiled with Microsoft Visual Studio. NET and instrumental application compiled with Microsoft Visual Studio 2010 in Win32 release configuration with Maximize Speed parameter and SSE2 instruction support.In testing mainstream mobile platform with Intel Core i3 350 M CPU and desktop platform with Intel Pentium Dual Core E5400 were used.Performance measurement timings for different algorithms, implementations, and CPU are shown in Table2.Table 2
Experimental results of software implementation of multiplication algorithms.
Field
Time,µs
Core i3
Pentium dual core
Mod. Comba
Comba
GMP4.1
Mod. Comba
Comba
GMP4.1
G
F
(
p
82
)
0,075
0,120
0,121
0,0687
0,119
0,125
G
F
(
p
164
)
0,21
0,393
0,4
0,209
0,363
0,407
G
F
(
p
192
)
0,276
0,393
0,41
0,289
0,363
0,414
G
F
(
p
224
)
0,343
0,69
0,549
0,364
0,59
0,522
G
F
(
p
256
)
0,422
0,875
0,638
0,456
0,744
0,648
G
F
(
p
320
)
0,6973
1,278
0,97
0,686
1,053
0,969
G
F
(
p
384
)
0,961
1,75
1,38
0,94
1,45
1,36
G
F
(
p
521
)
1,63
2,8
2,663
1,486
2,41
2,643As we can see from the timing in Table2, the proposed modification of the algorithm Comba has 1.5 times better time characteristic compared with GMP. Classic implementation of Comba’s algorithm is the slowest, which is confirmed by the theoretical estimation (as it contains a larger number of additions and assignment operations). In addition, proposed software implementation of multiplication algorithms is more efficient on Dual Pentium CPU with higher frequency than on Core i3 CPU with several instruction streams. This implementation of multiplication algorithms does not support parallelization; thus, a more powerful multicore CPU Core i3 with 4 instructions processing flows does not realize their full potential.


## 4. Conclusions

The research resulted in the following conclusions.(1)
We ensure an increase in performance of software implementation of Comba’s integer multiplication algorithm for 1.5–2 times and surpass of performance of the popular math library GMP v4.1.2, an average for 1.5 times.
(2)
Modified Comba’s multiplication algorithm is preferred to Karatsuba’s algorithm [2] which is used in GMP library, because implementation of modified Comba’s algorithm is faster than Karastuba [2] implementation in GMP for modern hardware platform (32- and 64-bit).
(3)
Delayed carry mechanism allows applying different parallelization techniques to modified Comba’s algorithm, for example, OpenMP [23], Intel Threading Building Blocks [28], NVIDIA CUDA [29], and OpenCL [30].Recently, the microprocessors development increases the number of instruction processing flows. Thus, we should perform the necessity of suitable algorithms development for efficient parallelization.NVIDIA has already proposed GPU with more than 256 cores and suitable CUDA toolkit [29] which allows creating valid multithread applications. This area is already under close monitoring and is demonstrated in publication [9, 31]. A further line of our research will focus on investigation and effective parallelization algorithms for arithmetic operations with integers.



---

*Source: 863617-2014-02-04.xml*