# Efficient Big Integer Multiplication and Squaring Algorithms for Cryptographic Applications

Authors: Shahram Jahani; Azman Samsudin; Kumbakonam Govindarajan Subramanian
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Public-key cryptosystems are broadly employed to provide security for digital information. Improving the efficiency of public-key cryptosystem through speeding up calculation and using fewer resources are among the main goals of cryptography research. In this paper, we introduce new symbols extracted from binary representation of integers called Big-ones. We present a modified version of the classical multiplication and squaring algorithms based on the Big-ones to improve the efficiency of big integer multiplication and squaring in number theory based cryptosystems. Compared to the adopted classical and Karatsuba multiplication algorithms for squaring, the proposed squaring algorithm is 2 to 3.7 and 7.9 to 2.5 times faster for squaring 32-bit and 8-Kbit numbers, respectively. The proposed multiplication algorithm is also 2.3 to 3.9 and 7 to 2.4 times faster for multiplying 32-bit and 8-Kbit numbers, respectively. The number theory based cryptosystems, which are operating in the range of 1-Kbit to 4-Kbit integers, are directly benefited from the proposed method since multiplication and squaring are the main operations in most of these systems.


---

## Body

## 1. Introduction

The growth of digital technologies has an exponential trend and as a consequence the need of information security also increases even more than before [1, 2]. Cryptography is an essential tool in providing a reasonable solution for this necessity. The modern field of cryptography consists of two main areas, the symmetric-key cryptography and the public-key cryptography. The same key is used in symmetric-key cryptosystems to encrypt and decrypt a message, while the public-key cryptosystems use two keys in their protocols. Most of the public-key cryptosystems [3] use modular exponentiation in their calculation. For example, Diffie and Hellman introduced the first key exchange scheme in 1967 that is based on the modular exponentiation [4]. Few years later in 1978, one of the most used public-key cryptosystems, RSA [3], is also based on the modular exponentiation. ElGamal key exchange [5] is another example of public key that has been developed based on the modular exponentiation.Modular exponentiation,b
=
a
x
mod
⁡
n, is a one-way function because the inverse of a modular exponentiation (x
=
d
log
⁡
a
⁡
b) is a known hard problem [6–8]. To achieve a comfortable level of security, the length of the key material for these cryptosystems must be larger than 1024 bits [9], and in the near future, it is predicted that 2048-bit and 4096-bit systems will become standard [10].Calculating modular exponentiation for a large exponent and large modulo is a costly operation and therefore improving its efficiency has become an important research issue for researchers in cryptography and mathematics. There are two main approaches currently being employed in order to improve the efficiency of modular exponentiation: improving the involved operations, exponentiation, and division, separately, and improving both of the operations simultaneously. Residue number system (RNS) [11] and Montgomery modular multiplication [12] are examples of the first approach, while binary andm-ary exponentiation or Barrett reduction [13] are instances from the second approach. This paper focuses on the second approach, by proposing a new number representation, which will improve the squaring and multiplication operations, two of the three main operations in calculating modular exponentiation [14].The naive approach of calculating the exponentiation is by doing repetitive multiplication, which is not an efficient way for calculating large exponent. A better alternative for calculating exponentiation is by employing binary exponentiation; that is, ifb
=
∑
i
=
0
k
-
1
(
b
i
2
i
), where b
i
=
{
0,1
}, then a
b
=
∏
i
=
0
k
-
1
(
a
2
i
b
i
). The term a
2
ican be obtained by squaring the (
i
-
1
)th term, a
2
i
-
1. The number of operations for calculating a
b by using the naïve method is (
b
-
1
) multiplications. On the other hand, the binary method requires only (
k
-
1
) squarings and k
/
2 multiplications (on average), where k
=
log
⁡
2
⁡
b (see Algorithm 1). Consequently, improving the multiplication and squaring operations (as found in algorithm such as the right-to-left algorithm and its variants [6–8]) will inherently improve the efficiency of the exponentiation calculation [7].Algorithm 1:Right-to-left binary exponentiation,  b
=
a
x.
Input: positive integers a and x
>
1.
Output: b
=
a
x
(1) Setb
←
1 and s
←
a.
(2) Whilex
≠
0  do the following:
(2.1) If  x is odd then  b
←
b
×
s.       // (
k
/
2
) multiplication if  k
=
log
2
⁡
b.
(2.2) Set x
←
⌊
x
/
2
⌋.
(2.3) If  x
≠
0   then s
←
s
×
s.       // (
k
-
1
)  multiplication.
(3) Returnb.


## 2. Multiplication and Squaring Algorithms

The most well-known algorithms for multiplication of two large integers or two polynomials are classical [15], Karatsuba-Ofman’s [16], Toom-Cook’s [17, 18], and fast Fourier transform (FFT) multiplication algorithms [19]. In spite of all the differences in these methods, which sometimes make them apparently unrelated to each other, these methods have been founded based on the same idea, that is, how to represent a polynomial to behave efficiently in calculations. The classical method uses coefficient representation, while the other three methods use point-value representation. This representation conversion enables us to reduce the cost of convolution from O
(
n
2
) of classical method to a lower cost for point-to-point multiplication. The process of finding point-value representation from its coefficient representation is called “evaluation” or “point evaluation” and the reverse process is known as “interpolation.” Table 1 summarizes the differences among the multiplication algorithms by their complexity, technique, and representation used.Table 1
Comparison of the well-known polynomial multiplication algorithms.
Multiplication algorithm
Technique
Representation
Complexity
Divide and conquer
Point evaluation
Interpolation
Classical
—
—
—
Coefficient representation
O
(
n
2
)
Karatsuba
√
—
—
Coefficient representation
O
(
n
1.58
)
Toom-Cook
√
√
√
Point-value representation
O
(
n
log
⁡
(
2
k
-
1
)
/
log
⁡
k
)
FFT
√
√
√
Point-value representation
O
(
n
log
⁡
n
log
⁡
log
⁡
n
)Algorithms such as FFT and Toom-Cook have lower algorithm complexity. However, because of the preprocessing overheads such as the divide and conquer, evaluation, and interpolation, the operating cost of these algorithms is actually much higher, making them useful only when the integers are extremely large. Consequently, only classical and Karatsuba multiplication algorithms and their combination are being used in current cryptosystem. This is especially true after considering circumstances such as memory constraints and the practical finite field size.


### 2.1. Classical Multiplication and Squaring Algorithms

In positional numeral system [15], the natural way of multiplying numbers, known as classical multiplication algorithm, is by multiplying each digit of the multiplicand by each digit of the multiplier and then adding up all the properly shifted results. This method requires a multiplication table for single digits available to the algorithm. Knuth’s classical multiplication algorithm [15] can be stated as shown in Algorithm 2.Algorithm 2:Multiple-precision classical multiplication,  CM(A
,
B).
Input: positive integers A
=
(
a
n
,
…
,
a
0
)
r  having n
+
1 base r digits and B
=
(
b
m
,
…
,
b
0
)
r having  m
+
1 base r digits.
Output: the product A
·
B
=
(
c
m
+
n
+
1
,
…
,
c
0
)
r in base r.
Note:(
u
v
)
r are two single-precision digits in base r, indicating the result of the addition.
(1) Fori from 0  up to m
+
n
+
1  do: c
i
←
0.
(2) Fori from 0  up to  m  do the following:
(2.1)c
a
r
r
y
←
0.
(2.2) Forj from 0  up to  n  do the following:
(2.2.1) Compute (
u
v
)
r
=
c
i
+
j
+
a
j
·
b
i
+
c
a
r
r
y, set c
i
+
j
←
v, and c
a
r
r
y
←
u.     // u and v are
(2.3)c
i
+
n
+
1
←
u.
// single-precision
(3) Return(
c
m
+
n
+
1
,
…
,
c
0
).                             // digits in base rThe complexity of the classical multiplication algorithm isO
(
n
2
). Therefore, the number representation that has fewer digits theoretically should run faster than the number representation that has more digits in its representation. In addition, the density of nonzero digits in the numbers influences the number of addition that has to be carried out by the classical multiplication algorithm as well.Algorithm3 shows the modified version of Algorithm 2 that computes the squaring operation efficiently for binary numbers. The efficiency of the modified squaring algorithm comes from Steps 2.1 to 2.2.1. Since the products of a
j
·
a
i and a
i
·
a
j are the same, this product is therefore calculated just once in Step  2.2.1. Note that (
u
v
)
r in Step  2.2.1 of Algorithm 3 is the result of the addition. In Algorithm 3, v is a single-precision digit, while u is a multiple-precision digit. With this improvement, the number of partial products in the squaring algorithm is n
(
n
-
1
)
/
2 less than what was found in Algorithm 1.Algorithm 3:Multiple-precision classical squaring,  SQ(A).
Input: positive integer A
=
(
a
n
,
…
,
a
0
)
r  having n
+
1 base r digits.
Output: the square A
·
A
=
A
2
=
(
c
2
n
+
1
,
…
,
c
0
)
r in base r representation.
Note:(
u
v
)
r are digits in base r, indicating the result of the addition.
(1) Fori from 0  up to  2
n
+
1  do: c
i
←
0.
(2) Fori from 0  up to  n  do the following:
(2.1) Compute(
u
v
)
r
=
c
2
i
+
a
i
·
a
i, set c
2
i
←
v, and  c
a
r
r
y
←
u.
(2.2) Forj from i
+
1  up to  n  do the following:
// v  is a  single-
(2.2.1) Compute (
u
v
)
r
=
c
i
+
j
+
2
a
j
·
a
i
+
c
a
r
r
y, set c
i
+
j
←
v, and c
a
r
r
y
←
u.    // precision digit and u
(2.3)c
i
+
n
+
1
←
u.
// is a multi-precision
(3) Return(
c
2
n
+
1
,
…
,
c
0
).                           // digit in base r


### 2.2. Karatsuba Multiplication and Squaring Algorithms

Karatsuba’s algorithm is an efficient scheme for multiplying two large numbers or two polynomials. It was introduced by Karatsuba and Ofman in 1960 and published in 1962 [20]. This algorithm is a remarkable example of the divide and conquer paradigm [21, 22], specifically for its binary splitting [23]. This method requires three multiplications and four additions in each iteration. To apply the algorithm both numbers are split into a lower and an upper half (for simplicity, assume n is even):
(1)
A
=
A
L
×
r
n
/
2
+
A
R
,
B
=
B
L
×
r
n
/
2
+
B
R
.The halvesA
R
,
A
L
,
B
R, and B
L are split again in half in the next iteration step. Since every step exactly halves the number of coefficients, the algorithm terminates after t
=
log
2
⁡
n steps. Algorithm 4 shows the recursive Karatsuba algorithm (assuming the lengths of A and B are even). We can use Karatsuba algorithm for squaring with small modification. Algorithm 5 shows these modifications in Steps  2-3.Algorithm 4:Recursive Karatsuba algorithm, C
=
KA
(
A
,
B
).
Input: positive integers A
=
(
a
n
,
…
,
a
0
)
r  and B
=
(
b
n
,
…
,
b
0
)
r  having  n
+
1 base r digits.
Output: the product C
=
A
·
B.
(1) Ifn
=
1  then return C
=
A
×
B.
(2) SplitA, B into two equal parts:
A
=
A
L
×
r
n
/
2
+
A
R, and  B
=
B
L
×
r
n
/
2
+
B
R.
(3) Compute the following:
d
1
=
KA
(
A
L
,
B
L
); d
0
=
KA
(
A
R
,
B
R
), and  d
0,1
=
KA
(
A
R
+
A
L
,
B
R
+
B
L
).
(4) ReturnC
=
d
1
×
r
n
+
(
d
0,1
-
d
0
-
d
1
)
×
r
n
/
2
+
d
0.Algorithm 5:Recursive Karatsuba squaring algorithm, C
=
SQKA
(
A
).
Input: positive integers A
=
(
a
n
,
…
,
a
0
)
r  having  n
+
1 base r digits.
Output: the product C
=
A
·
A
=
A
2.
(1) If n
=
1  then return C
=
A
×
A
=
A
2.
(2) Split A into two equal parts A
L and A
R:
A
=
A
L
×
r
n
/
2
+
A
R.
(3) Compute the following:
d
1
=
SQKA
(
A
L
);  d
0
=
SQKA
(
A
R
), and   d
0,1
=
SQKA
(
A
R
+
A
L
).
(4) Return  C
=
d
1
×
r
n
+
(
d
0,1
-
d
0
-
d
1
)
×
r
n
/
2
+
d
0.Combining other multiplication algorithms with Karatsuba algorithm is another technique that has been used by researchers [24]. The study on squaring and multiplying large integers by Zuras has shown the 2-way, 3-way, and 4-way approaches for calculating big integer multiplication [25]. Sadiq and Ahmed [26] have extended the work further and summarized the results after splitting the long numbers into multi partitions (up to 10 partitions). More details on squaring algorithms can be found in the literature [6, 8, 27–29].


## 2.1. Classical Multiplication and Squaring Algorithms

In positional numeral system [15], the natural way of multiplying numbers, known as classical multiplication algorithm, is by multiplying each digit of the multiplicand by each digit of the multiplier and then adding up all the properly shifted results. This method requires a multiplication table for single digits available to the algorithm. Knuth’s classical multiplication algorithm [15] can be stated as shown in Algorithm 2.Algorithm 2:Multiple-precision classical multiplication,  CM(A
,
B).
Input: positive integers A
=
(
a
n
,
…
,
a
0
)
r  having n
+
1 base r digits and B
=
(
b
m
,
…
,
b
0
)
r having  m
+
1 base r digits.
Output: the product A
·
B
=
(
c
m
+
n
+
1
,
…
,
c
0
)
r in base r.
Note:(
u
v
)
r are two single-precision digits in base r, indicating the result of the addition.
(1) Fori from 0  up to m
+
n
+
1  do: c
i
←
0.
(2) Fori from 0  up to  m  do the following:
(2.1)c
a
r
r
y
←
0.
(2.2) Forj from 0  up to  n  do the following:
(2.2.1) Compute (
u
v
)
r
=
c
i
+
j
+
a
j
·
b
i
+
c
a
r
r
y, set c
i
+
j
←
v, and c
a
r
r
y
←
u.     // u and v are
(2.3)c
i
+
n
+
1
←
u.
// single-precision
(3) Return(
c
m
+
n
+
1
,
…
,
c
0
).                             // digits in base rThe complexity of the classical multiplication algorithm isO
(
n
2
). Therefore, the number representation that has fewer digits theoretically should run faster than the number representation that has more digits in its representation. In addition, the density of nonzero digits in the numbers influences the number of addition that has to be carried out by the classical multiplication algorithm as well.Algorithm3 shows the modified version of Algorithm 2 that computes the squaring operation efficiently for binary numbers. The efficiency of the modified squaring algorithm comes from Steps 2.1 to 2.2.1. Since the products of a
j
·
a
i and a
i
·
a
j are the same, this product is therefore calculated just once in Step  2.2.1. Note that (
u
v
)
r in Step  2.2.1 of Algorithm 3 is the result of the addition. In Algorithm 3, v is a single-precision digit, while u is a multiple-precision digit. With this improvement, the number of partial products in the squaring algorithm is n
(
n
-
1
)
/
2 less than what was found in Algorithm 1.Algorithm 3:Multiple-precision classical squaring,  SQ(A).
Input: positive integer A
=
(
a
n
,
…
,
a
0
)
r  having n
+
1 base r digits.
Output: the square A
·
A
=
A
2
=
(
c
2
n
+
1
,
…
,
c
0
)
r in base r representation.
Note:(
u
v
)
r are digits in base r, indicating the result of the addition.
(1) Fori from 0  up to  2
n
+
1  do: c
i
←
0.
(2) Fori from 0  up to  n  do the following:
(2.1) Compute(
u
v
)
r
=
c
2
i
+
a
i
·
a
i, set c
2
i
←
v, and  c
a
r
r
y
←
u.
(2.2) Forj from i
+
1  up to  n  do the following:
// v  is a  single-
(2.2.1) Compute (
u
v
)
r
=
c
i
+
j
+
2
a
j
·
a
i
+
c
a
r
r
y, set c
i
+
j
←
v, and c
a
r
r
y
←
u.    // precision digit and u
(2.3)c
i
+
n
+
1
←
u.
// is a multi-precision
(3) Return(
c
2
n
+
1
,
…
,
c
0
).                           // digit in base r


## 2.2. Karatsuba Multiplication and Squaring Algorithms

Karatsuba’s algorithm is an efficient scheme for multiplying two large numbers or two polynomials. It was introduced by Karatsuba and Ofman in 1960 and published in 1962 [20]. This algorithm is a remarkable example of the divide and conquer paradigm [21, 22], specifically for its binary splitting [23]. This method requires three multiplications and four additions in each iteration. To apply the algorithm both numbers are split into a lower and an upper half (for simplicity, assume n is even):
(1)
A
=
A
L
×
r
n
/
2
+
A
R
,
B
=
B
L
×
r
n
/
2
+
B
R
.The halvesA
R
,
A
L
,
B
R, and B
L are split again in half in the next iteration step. Since every step exactly halves the number of coefficients, the algorithm terminates after t
=
log
2
⁡
n steps. Algorithm 4 shows the recursive Karatsuba algorithm (assuming the lengths of A and B are even). We can use Karatsuba algorithm for squaring with small modification. Algorithm 5 shows these modifications in Steps  2-3.Algorithm 4:Recursive Karatsuba algorithm, C
=
KA
(
A
,
B
).
Input: positive integers A
=
(
a
n
,
…
,
a
0
)
r  and B
=
(
b
n
,
…
,
b
0
)
r  having  n
+
1 base r digits.
Output: the product C
=
A
·
B.
(1) Ifn
=
1  then return C
=
A
×
B.
(2) SplitA, B into two equal parts:
A
=
A
L
×
r
n
/
2
+
A
R, and  B
=
B
L
×
r
n
/
2
+
B
R.
(3) Compute the following:
d
1
=
KA
(
A
L
,
B
L
); d
0
=
KA
(
A
R
,
B
R
), and  d
0,1
=
KA
(
A
R
+
A
L
,
B
R
+
B
L
).
(4) ReturnC
=
d
1
×
r
n
+
(
d
0,1
-
d
0
-
d
1
)
×
r
n
/
2
+
d
0.Algorithm 5:Recursive Karatsuba squaring algorithm, C
=
SQKA
(
A
).
Input: positive integers A
=
(
a
n
,
…
,
a
0
)
r  having  n
+
1 base r digits.
Output: the product C
=
A
·
A
=
A
2.
(1) If n
=
1  then return C
=
A
×
A
=
A
2.
(2) Split A into two equal parts A
L and A
R:
A
=
A
L
×
r
n
/
2
+
A
R.
(3) Compute the following:
d
1
=
SQKA
(
A
L
);  d
0
=
SQKA
(
A
R
), and   d
0,1
=
SQKA
(
A
R
+
A
L
).
(4) Return  C
=
d
1
×
r
n
+
(
d
0,1
-
d
0
-
d
1
)
×
r
n
/
2
+
d
0.Combining other multiplication algorithms with Karatsuba algorithm is another technique that has been used by researchers [24]. The study on squaring and multiplying large integers by Zuras has shown the 2-way, 3-way, and 4-way approaches for calculating big integer multiplication [25]. Sadiq and Ahmed [26] have extended the work further and summarized the results after splitting the long numbers into multi partitions (up to 10 partitions). More details on squaring algorithms can be found in the literature [6, 8, 27–29].


## 3. Big-Ones Representation and the Proposed Algorithms

In this section, the Big-one (Bo) integer representation and the proposed multiplication and squaring algorithms, which are based on this representation, are presented. Big-one representation is created based on the binary number representation. Big-one is a compact representation with low Hamming weight (HW) compared to the binary number representation.A Big-one is the numeric value of a sequence ofn consecutive binary symbol “1” with length n and is denoted by O
n. Examples of Bo’s are O
1
=
1
2
=
1 and O
3
=
11
1
2
=
7. Consider
(2)
O
n
=
1
⋯
1
︷
n
2
=
∑
i
=
0
n
-
1
2
i
=
2
n
-
1
.
A set of all Bo’s is called Big-ones’ set and is denoted by O
^
=
{
O
1
,
O
2
,
O
3
,
…
} =  {
1
2
,
11
2
,
111
2
,
…
}
=
{
1,3
,
7,15
,
…
}.Big-Ones Number System (BONS). Let A
=
(
a
n
…
a
2
a
1
a
0
)
2 be a number in radix 2, where a
i
∈
O
^
∪
{
0
}. This number system is called Big-one number system and denoted as BONS. For example, A
=
11101010101111
2 can be represented by O
3
0
O
1
0
O
1
0
O
1
0
000
O
4 in BONS. This number system is redundant. To transform BONS into a canonic (not redundant) representation, the maximum length of Big-ones is used. The canonical version of BONS is known as CBONS. CBONS is a compressed representation of Big-one, by ignoring all the zeros and modifying the notation O
n to O
(
n
,
P
), where P shows the position of the specified Big-one in the binary number. Specifically, P is the position of the least significant bit of the specified Big-one in the binary number. For example, we can write 1110101111000011
2 in CBONS as O
(
3,13
)
O
(
1,11
)
O
(
4,6
)
O
(
2,0
). To optimize the calculations based on CBONS, we can limit the length of maximum Big-ones to “w” (O
(
n
,
P
)such that n
≤
w) which we identified in this paper as themaximum length of Big-ones [30–32].


### 3.1. Big-Ones Analysis

From the definition of CBONS, it is apparent that there will be at least one digit zero bounding from the left and at least another digit zero bounding from the right of each Big-one digit (except for the least and most significant bits). Consequently, to calculate the number ofO
ls in any given binary number, we have to calculate the probability of “0O
l0” patterns appearing in the binary number. Since the probability of digit “1” and digit “0” appearing in a binary digit is 1
/
2, therefore it follows that the probability of O
l appearing in a binary number is P
(
O
l
)
=
1
/
2
l
+
2. As a result, the number of O
ls in an n-bit binary number is N
(
O
l
)
=
n
/
2
l
+
2. To calculate the Hamming weight of Bo’s in a Big-one number system, it is enough to calculate the total number of Big-ones, N
(
O
l
), where 1
≤
l
≤
n. Consider
(3)
HW
(
in
CBONS
)
=
∑
l
=
1
n
N
(
O
l
)
=
∑
l
=
1
n
n
2
l
+
2
=
n
4
∑
l
=
1
n
2
-
l
=
n
4
(
∑
l
=
0
n
2
-
l
-
1
)
.
Since
(4)
∑
n
=
0
m
2
-
n
=
2
-
m
(
2
m
+
1
-
1
)
,
(3) can therefore be written as
(5)
HW
(
in
CBONS
)
=
n
4
(
2
-
n
(
2
n
+
1
-
1
)
-
1
)
=
n
4
(
2
-
2
-
n
-
1
)
=
n
4
(
1
-
2
-
n
)
.
For large enough n, the number of Big-ones (Hamming weight of CBONS) would be
(6)
HW
BONS
(
calculated
)
≅
n
4
.Table2 shows the result of calculating the number of Big-one digits in an 8-Kbit binary number from 10,000 randomly generated binary numbers. As the table indicates, the experimental result does agree with the value found in (6).Table 2
The Hamming weight of Big-ones in CBONS for an 8-Kbit binary number.
Big-one’s length  (w)
1
2
3
4
5
6
7
8
9
10
11
>12
(
N
n
)
1024
510
257
127
64
33
16
8
4
2
1
2
(
∑
k
=
1
n
N
k
)
1024
1534
1791
1918
1982
2015
2031
2039
2043
2045
2046
2048
HW
/
w
(
∑
k
=
1
n
N
k
8192
)
=
2048
8192
=
1
4Table2 also indicates that the occurrence of Big-ones decreases as the length of Big-ones increases. The goal of the following experiment is therefore to find the optimized length for CBONS, to be used in LCBONS (limited length CBONS).The length, identified asw, is important for applications such as multiplication and squaring. This is because the size of w will determine the size of the look-up table (LUT) that needs to be used by the respective algorithms. Table 3 indicates that the practical value for w is 5 since the Hamming weight when w
=
5 is only slightly bigger than the optimum Hamming weight for CBONS (25.8% compared to 25%) but at the same time will produce a relatively compact LUT. Consequently, the following proposed multiplication and squaring algorithms will use LCBONS with w
=
5.Table 3
Big-ones’ distribution in an 8-Kbit binary number in LCBONS for different Big-one’s length.
Maximum size of Big-ones (w)
9
8
7
6
5
Big-ones’ length
1
1026
1028
1032
1040
1057
2
511
512
514
518
527
3
258
258
259
261
266
4
127
128
128
129
131
5
64
64
64
65
133
6
33
33
33
66
7
16
16
33
8
8
16
9
8
HW
2051
2055
2063
2079
2114
(HW/w) %
25.0
25.1
25.2
25.4
25.8


### 3.2. Converting Binary Representation to Big-Ones Representation

Algorithm6 shows how to convert a binary representation to CBONS representation. In Step  2.2.1, the flagNewBois set to true if a
i
a
i
-
1
=
“
10
” and at the same time the position of the new Big-one is saved in “pos.” In Step  2.3.1, while the flagNewBois true, the length of current Big-one (Length) is increased by one in each iteration of the loop until a
i
a
i
-
1
=
“
01
” is found. The end of Big-one is identified by setting the flagNewBo to false in Step  2.3.2. Then, the length and position of the newly discovered Big-one digit are saved in c
i
L and c
i
p, respectively, where i is the position of new Big-one in array C.Algorithm 6:Binary to Big-one converter algorithm, B
i
n
2
B
O
(
A
).
Input: positive integers A
=
(
a
n
,
…
,
a
0
)
2  having  n
+
1 base 2 digits.
Output: C
=
(
c
n
,
…
,
c
0
)
2  having n
+
1  digits in CBONS and non-zero c
i
=
(
c
i
L
,
c
i
P
).
(1) Set;a
-
1
←
0, a
n
+
1
←
0.
(2) Fori from 0  up to  n
+
1  do the following:
(2.1) SetL
e
n
g
t
h
←
0
(2.2) Ifa
i
a
i
-
1
=
10 then  do the following:
(2.2.1) Set N
e
w
B
o
←
T
r
u
e; p
o
s
←
i.
(2.3) While(
N
e
w
B
o
)  do the following:
(2.3.1) Increase  L
e
n
g
t
h and  i by 1.
(2.3.2) If a
i
a
i
-
1
=
01 thenSet N
e
w
B
o
←
F
a
l
s
e.
(2.4) IfL
e
n
g
t
h
>
0 then  do the following:
(2.4.1) Set c
i
L
←
L
e
n
g
t
h and c
i
P
←
(
p
o
s
-
1
).
(3) Return(
c
n
,
…
,
c
0
).Algorithm7 is the modified version of Algorithm 6 after applying the maximum length of Big-one in BONS. In Step  2.3.3 of Algorithm 7, the length of the current Big-one digit is checked. If the length of the Big-one is bigger than w, then the relevant pointer will backtrack one bit and set the value a
i to 0. Step  2.4 of Algorithm 7 acts similar to Step  2.4 in Algorithm 6 which has been explained earlier.Algorithm 7:Binary to limited Big-one converter algorithm, B
i
n
2
L
B
O
(
A
).
Input: positive integers A
=
(
a
n
,
…
,
a
0
)
2  having n
+
1 base 2 digits and positive integer w.
Output: C
=
(
c
n
,
…
,
c
0
)
2  having n
+
1  digits in LCBONS and non-zero c
i
=
(
c
i
L
,
c
i
P
).
(1) Set;a
-
1
←
0, a
n
+
1
←
0.
(2) Fori from 0  up to  n
+
1  do the following:
(2.1) SetL
e
n
g
t
h
←
0
(2.2) Ifa
i
a
i
-
1
=
10 then  do the following:
(2.2.1) Set N
e
w
B
o
←
T
r
u
e; p
o
s
←
i.
(2.3) While(
N
e
w
B
o
)  do the following:
(2.3.1) Increase  L
e
n
g
t
h and  i by 1.
(2.3.2) If a
i
a
i
-
1
=
01 thenSet N
e
w
B
o
←
F
a
l
s
e.
(2.3.3) If  L
e
n
g
t
h
=
w then  do the following:
(2.3.3.1) Set N
e
w
B
o
←
F
a
l
s
e and a
i
-
1
←
0.
(2.3.3.2) Decrease  i by 1.
(2.4) IfL
e
n
g
t
h
>
0 then  do the following:
(2.4.1) Set c
i
L
←
L
e
n
g
t
h and c
i
P
←
(
p
o
s
-
1
).
(3) Return(
c
n
,
…
,
c
0
).To use Algorithms6 and 7 efficiently in squaring and multiplication, we assume that the output of these algorithms is in the form of (
d
n
,
…
d
0
), where d
i
=
c
i
L. To show this point, we change the names of algorithms toBin2BO-LandBin2LBO-L accordingly.


### 3.3. Proposed Multiplication and Squaring Algorithm

Algorithm8 is a modification of Algorithm 2, which has been designed based on the LBONS. In Step  1, by using functionBin2LBO-L, A is converted to A
′. Output A
′ is a special representation of A in LCBONC representation that shows the length of Big-ones. Step  3.1 is introduced to ignore the zeros in A
′ and consequently will help reduce the number of operations. Another difference is related to Step  3.2.1.1 which uses the function LUT
(
a
j
′
,
b
i
′
). This function fetches the product of two Big-ones by lengths of a
j
′ and b
i
′ from a precalculated look-up table.Algorithm 8:Multiple-precision classical multiplication,  BOCM
(
A
,
B
).
Input: positive integers A
=
(
a
n
,
…
,
a
0
)
2 and B
=
(
b
m
,
…
,
b
0
)
2  having  n
+
1 base 2 digits.
Output: the product A
·
B
=
(
c
m
+
n
+
1
,
…
,
c
0
)
2 in base 2 representation.
(1) ComputeA
′
=
B
i
n
2
L
B
O
-
L
(
A
) and   B
′
=
B
i
n
2
L
B
O
-
L
(
B
).          //
A
′
=
(
a
′
n
,
…
,
a
′
0
)
(2) Fori from 0  up to  m
+
n
+
1  do: c
i
←
0.
//
B
′
=
(
b
′
n
,
…
,
b
′
0
)
(3) Fori from 0  up to  m  do the following:
(3.1) Setc
a
r
r
y
←
0
(3.2) Ifb
i
≠
0 then do the following:
(3.2.1) For  j from 0  up to  n  do the following:
(3.2.1.1) Compute (
u
v
)
b
=
c
i
+
j
+
LUT(
a
′
j
,
b
′
i
)
+
c
a
r
r
y.
// u is a multi-precision binary digit
(3.2.1.2) Set c
i
+
j
←
v and c
a
r
r
y
←
u.
// v is a single-precision binary digit
(3.3)c
i
+
n
+
1
←
u.
(4) Return(
c
2
n
+
1
,
…
c
0
).The proposed squaring algorithm (see Algorithm9) is a modified version of Algorithm 3. In Step  1, by executing the converterBin2LBO-L, A is converted to A
′ which is a special representation of A in LCBONS representation with maximum length being employed (w
=
5). Other differences are related to Step  3.1, which has been proposed by Knuth [15] to ignore the zeros in A
′. Similar to Algorithm 8, in Step  3.1.2.1 the function LUT
(
a
j
′
,
a
i
′
) is used to fetch the product of two Big-ones from a precalculated look-up table.Algorithm 9:Multiple-precision classical squaring,  BOSQ
(
A
).
Input: positive integer A
=
(
a
n
,
…
,
a
0
)
2  having n
+
1 base 2 digits.
Output: the square A
·
A
=
A
2
=
(
c
2
n
+
1
,
…
,
c
0
)
2 in base 2 representation.
(1) ComputeA
′
=
B
i
n
2
L
B
O
-
L
(
A
).                   //
A
′
=
(
a
′
n
,
…
,
a
′
0
)
(2) Fori from 0  up to  2
n
+
1  do: c
i
←
0.
(3) Fori from 0  up to  m  do the following:
(3.1) Ifa
i
≠
0 then do the following:
(3.1.1) Compute (
u
v
)
b
=
c
2
i
+
LUT
(
a
′
i
,
a
′
i
), and set c
2
i
←
v, c
a
r
r
y
←
u.
(3.1.2) For  j from i
+
1  up to  n  do the following:
(3.1.2.1) Compute (
u
v
)
b
=
c
i
+
j
+
2LUT
(
a
′
j
,
a
′
i
)
+
c
a
r
r
y.     // u is a multi-precision binary
(3.1.2.2) Set c
i
+
j
←
v and c
a
r
r
y
←
u.             // digit and v is a single-precision
// binary digit
(3.2)c
i
+
n
+
1
←
u.
(4) Return(
c
2
n
+
1
,
…
,
c
0
)


## 3.1. Big-Ones Analysis

From the definition of CBONS, it is apparent that there will be at least one digit zero bounding from the left and at least another digit zero bounding from the right of each Big-one digit (except for the least and most significant bits). Consequently, to calculate the number ofO
ls in any given binary number, we have to calculate the probability of “0O
l0” patterns appearing in the binary number. Since the probability of digit “1” and digit “0” appearing in a binary digit is 1
/
2, therefore it follows that the probability of O
l appearing in a binary number is P
(
O
l
)
=
1
/
2
l
+
2. As a result, the number of O
ls in an n-bit binary number is N
(
O
l
)
=
n
/
2
l
+
2. To calculate the Hamming weight of Bo’s in a Big-one number system, it is enough to calculate the total number of Big-ones, N
(
O
l
), where 1
≤
l
≤
n. Consider
(3)
HW
(
in
CBONS
)
=
∑
l
=
1
n
N
(
O
l
)
=
∑
l
=
1
n
n
2
l
+
2
=
n
4
∑
l
=
1
n
2
-
l
=
n
4
(
∑
l
=
0
n
2
-
l
-
1
)
.
Since
(4)
∑
n
=
0
m
2
-
n
=
2
-
m
(
2
m
+
1
-
1
)
,
(3) can therefore be written as
(5)
HW
(
in
CBONS
)
=
n
4
(
2
-
n
(
2
n
+
1
-
1
)
-
1
)
=
n
4
(
2
-
2
-
n
-
1
)
=
n
4
(
1
-
2
-
n
)
.
For large enough n, the number of Big-ones (Hamming weight of CBONS) would be
(6)
HW
BONS
(
calculated
)
≅
n
4
.Table2 shows the result of calculating the number of Big-one digits in an 8-Kbit binary number from 10,000 randomly generated binary numbers. As the table indicates, the experimental result does agree with the value found in (6).Table 2
The Hamming weight of Big-ones in CBONS for an 8-Kbit binary number.
Big-one’s length  (w)
1
2
3
4
5
6
7
8
9
10
11
>12
(
N
n
)
1024
510
257
127
64
33
16
8
4
2
1
2
(
∑
k
=
1
n
N
k
)
1024
1534
1791
1918
1982
2015
2031
2039
2043
2045
2046
2048
HW
/
w
(
∑
k
=
1
n
N
k
8192
)
=
2048
8192
=
1
4Table2 also indicates that the occurrence of Big-ones decreases as the length of Big-ones increases. The goal of the following experiment is therefore to find the optimized length for CBONS, to be used in LCBONS (limited length CBONS).The length, identified asw, is important for applications such as multiplication and squaring. This is because the size of w will determine the size of the look-up table (LUT) that needs to be used by the respective algorithms. Table 3 indicates that the practical value for w is 5 since the Hamming weight when w
=
5 is only slightly bigger than the optimum Hamming weight for CBONS (25.8% compared to 25%) but at the same time will produce a relatively compact LUT. Consequently, the following proposed multiplication and squaring algorithms will use LCBONS with w
=
5.Table 3
Big-ones’ distribution in an 8-Kbit binary number in LCBONS for different Big-one’s length.
Maximum size of Big-ones (w)
9
8
7
6
5
Big-ones’ length
1
1026
1028
1032
1040
1057
2
511
512
514
518
527
3
258
258
259
261
266
4
127
128
128
129
131
5
64
64
64
65
133
6
33
33
33
66
7
16
16
33
8
8
16
9
8
HW
2051
2055
2063
2079
2114
(HW/w) %
25.0
25.1
25.2
25.4
25.8


## 3.2. Converting Binary Representation to Big-Ones Representation

Algorithm6 shows how to convert a binary representation to CBONS representation. In Step  2.2.1, the flagNewBois set to true if a
i
a
i
-
1
=
“
10
” and at the same time the position of the new Big-one is saved in “pos.” In Step  2.3.1, while the flagNewBois true, the length of current Big-one (Length) is increased by one in each iteration of the loop until a
i
a
i
-
1
=
“
01
” is found. The end of Big-one is identified by setting the flagNewBo to false in Step  2.3.2. Then, the length and position of the newly discovered Big-one digit are saved in c
i
L and c
i
p, respectively, where i is the position of new Big-one in array C.Algorithm 6:Binary to Big-one converter algorithm, B
i
n
2
B
O
(
A
).
Input: positive integers A
=
(
a
n
,
…
,
a
0
)
2  having  n
+
1 base 2 digits.
Output: C
=
(
c
n
,
…
,
c
0
)
2  having n
+
1  digits in CBONS and non-zero c
i
=
(
c
i
L
,
c
i
P
).
(1) Set;a
-
1
←
0, a
n
+
1
←
0.
(2) Fori from 0  up to  n
+
1  do the following:
(2.1) SetL
e
n
g
t
h
←
0
(2.2) Ifa
i
a
i
-
1
=
10 then  do the following:
(2.2.1) Set N
e
w
B
o
←
T
r
u
e; p
o
s
←
i.
(2.3) While(
N
e
w
B
o
)  do the following:
(2.3.1) Increase  L
e
n
g
t
h and  i by 1.
(2.3.2) If a
i
a
i
-
1
=
01 thenSet N
e
w
B
o
←
F
a
l
s
e.
(2.4) IfL
e
n
g
t
h
>
0 then  do the following:
(2.4.1) Set c
i
L
←
L
e
n
g
t
h and c
i
P
←
(
p
o
s
-
1
).
(3) Return(
c
n
,
…
,
c
0
).Algorithm7 is the modified version of Algorithm 6 after applying the maximum length of Big-one in BONS. In Step  2.3.3 of Algorithm 7, the length of the current Big-one digit is checked. If the length of the Big-one is bigger than w, then the relevant pointer will backtrack one bit and set the value a
i to 0. Step  2.4 of Algorithm 7 acts similar to Step  2.4 in Algorithm 6 which has been explained earlier.Algorithm 7:Binary to limited Big-one converter algorithm, B
i
n
2
L
B
O
(
A
).
Input: positive integers A
=
(
a
n
,
…
,
a
0
)
2  having n
+
1 base 2 digits and positive integer w.
Output: C
=
(
c
n
,
…
,
c
0
)
2  having n
+
1  digits in LCBONS and non-zero c
i
=
(
c
i
L
,
c
i
P
).
(1) Set;a
-
1
←
0, a
n
+
1
←
0.
(2) Fori from 0  up to  n
+
1  do the following:
(2.1) SetL
e
n
g
t
h
←
0
(2.2) Ifa
i
a
i
-
1
=
10 then  do the following:
(2.2.1) Set N
e
w
B
o
←
T
r
u
e; p
o
s
←
i.
(2.3) While(
N
e
w
B
o
)  do the following:
(2.3.1) Increase  L
e
n
g
t
h and  i by 1.
(2.3.2) If a
i
a
i
-
1
=
01 thenSet N
e
w
B
o
←
F
a
l
s
e.
(2.3.3) If  L
e
n
g
t
h
=
w then  do the following:
(2.3.3.1) Set N
e
w
B
o
←
F
a
l
s
e and a
i
-
1
←
0.
(2.3.3.2) Decrease  i by 1.
(2.4) IfL
e
n
g
t
h
>
0 then  do the following:
(2.4.1) Set c
i
L
←
L
e
n
g
t
h and c
i
P
←
(
p
o
s
-
1
).
(3) Return(
c
n
,
…
,
c
0
).To use Algorithms6 and 7 efficiently in squaring and multiplication, we assume that the output of these algorithms is in the form of (
d
n
,
…
d
0
), where d
i
=
c
i
L. To show this point, we change the names of algorithms toBin2BO-LandBin2LBO-L accordingly.


## 3.3. Proposed Multiplication and Squaring Algorithm

Algorithm8 is a modification of Algorithm 2, which has been designed based on the LBONS. In Step  1, by using functionBin2LBO-L, A is converted to A
′. Output A
′ is a special representation of A in LCBONC representation that shows the length of Big-ones. Step  3.1 is introduced to ignore the zeros in A
′ and consequently will help reduce the number of operations. Another difference is related to Step  3.2.1.1 which uses the function LUT
(
a
j
′
,
b
i
′
). This function fetches the product of two Big-ones by lengths of a
j
′ and b
i
′ from a precalculated look-up table.Algorithm 8:Multiple-precision classical multiplication,  BOCM
(
A
,
B
).
Input: positive integers A
=
(
a
n
,
…
,
a
0
)
2 and B
=
(
b
m
,
…
,
b
0
)
2  having  n
+
1 base 2 digits.
Output: the product A
·
B
=
(
c
m
+
n
+
1
,
…
,
c
0
)
2 in base 2 representation.
(1) ComputeA
′
=
B
i
n
2
L
B
O
-
L
(
A
) and   B
′
=
B
i
n
2
L
B
O
-
L
(
B
).          //
A
′
=
(
a
′
n
,
…
,
a
′
0
)
(2) Fori from 0  up to  m
+
n
+
1  do: c
i
←
0.
//
B
′
=
(
b
′
n
,
…
,
b
′
0
)
(3) Fori from 0  up to  m  do the following:
(3.1) Setc
a
r
r
y
←
0
(3.2) Ifb
i
≠
0 then do the following:
(3.2.1) For  j from 0  up to  n  do the following:
(3.2.1.1) Compute (
u
v
)
b
=
c
i
+
j
+
LUT(
a
′
j
,
b
′
i
)
+
c
a
r
r
y.
// u is a multi-precision binary digit
(3.2.1.2) Set c
i
+
j
←
v and c
a
r
r
y
←
u.
// v is a single-precision binary digit
(3.3)c
i
+
n
+
1
←
u.
(4) Return(
c
2
n
+
1
,
…
c
0
).The proposed squaring algorithm (see Algorithm9) is a modified version of Algorithm 3. In Step  1, by executing the converterBin2LBO-L, A is converted to A
′ which is a special representation of A in LCBONS representation with maximum length being employed (w
=
5). Other differences are related to Step  3.1, which has been proposed by Knuth [15] to ignore the zeros in A
′. Similar to Algorithm 8, in Step  3.1.2.1 the function LUT
(
a
j
′
,
a
i
′
) is used to fetch the product of two Big-ones from a precalculated look-up table.Algorithm 9:Multiple-precision classical squaring,  BOSQ
(
A
).
Input: positive integer A
=
(
a
n
,
…
,
a
0
)
2  having n
+
1 base 2 digits.
Output: the square A
·
A
=
A
2
=
(
c
2
n
+
1
,
…
,
c
0
)
2 in base 2 representation.
(1) ComputeA
′
=
B
i
n
2
L
B
O
-
L
(
A
).                   //
A
′
=
(
a
′
n
,
…
,
a
′
0
)
(2) Fori from 0  up to  2
n
+
1  do: c
i
←
0.
(3) Fori from 0  up to  m  do the following:
(3.1) Ifa
i
≠
0 then do the following:
(3.1.1) Compute (
u
v
)
b
=
c
2
i
+
LUT
(
a
′
i
,
a
′
i
), and set c
2
i
←
v, c
a
r
r
y
←
u.
(3.1.2) For  j from i
+
1  up to  n  do the following:
(3.1.2.1) Compute (
u
v
)
b
=
c
i
+
j
+
2LUT
(
a
′
j
,
a
′
i
)
+
c
a
r
r
y.     // u is a multi-precision binary
(3.1.2.2) Set c
i
+
j
←
v and c
a
r
r
y
←
u.             // digit and v is a single-precision
// binary digit
(3.2)c
i
+
n
+
1
←
u.
(4) Return(
c
2
n
+
1
,
…
,
c
0
)


## 4. Results and Discussion

To compute the Big-ones Hamming weight, 10,000 random numbers [33] were generated with different maximum lengths, w
=
2
,
…
,
10, and different number lengths ranging from 32 bits to 8 Kbits. The results are summarized in Tables 2 and 3. According to this data, the Hamming weight for the numbers larger than 64 bits with w
=
5 is about 25.8%. If we increase the value of w to 10, we can achieve slightly better Hamming weight value, that is, about 25%. However, to create a look-up table that can support w
=
10, we have to use four times more memory than the case of w
=
5. The size of LUT for the case of w
=
5 is 50 bytes (5
×
5
×
2 bytes) for squaring and multiplication. In this paper, the result gathered is based on the case of w
=
5.Tables2 and 3 indicate the execution time of the classical squaring (CLSQ) and multiplication (CM_MUL), Karatsuba squaring (KASQ) and multiplication (KA_MUL), and also the proposed squaring and multiplication algorithm against different bit lengths, which are randomly generated. The tests were conducted on a machine with an AMD Phenom (TM) 9950 Quad-Core processor, 3 GB RAM, Windows XP (Service Pack 3) OS, and Dev-C++ version 4.9.9.2 compiler.According to Table4 the proposed multiplication algorithm is more efficient than CM_MUL and KA_MUL algorithms for multiplication numbers ranging from 32 bits to 8 Kbits, which is the range of numbers used by the current number theory based cryptosystems. The proposed multiplication algorithm is about 2.3 times faster than CM_MUL for multiplying 32-bit numbers and about 3 times faster for multiplying 64-bit numbers. For numbers ranging from 128 bits to 8 Kbits, this ratio fluctuates between 3.3 and 3.9. Generally, the Karatsuba multiplication algorithm (KA_MUL) with algorithm complexity O
(
n
1.58
) is slower than the proposed algorithm (with algorithm complexity O
(
n
2
)) for multiplying numbers ranging from 32 bits to 8 Kbits. Table 4 shows that the proposed algorithm is about 7 times to 9.6 times faster than Karatsuba algorithm for multiplying 32-bit to 64-bit numbers. The speed-up ratio continuously declines from 9.6 to about 2.4 times faster for multiplying numbers in the range of 64-bit to 8-Kbit numbers.Table 4
Execution time (msec) of multiplication algorithms.
Algorithm
Length of numbers (bits)
32
64
128
256
512
1024
2048
4096
8192
CM_MUL
0.007
0.024
0.082
0.316
1.15
4.41
18.01
63.8
285
KA_MUL
0.021
0.077
0.260
0.754
2.35
7.28
21.32
64.9
199
Proposed multiplication
0.003
0.008
0.028
0.087
0.32
1.34
4.66
19.6
84According to Table5, the proposed squaring algorithm is more efficient than CLSQ and KASQ algorithms for squaring numbers ranging from 32 bits to 8 Kbits. The proposed algorithm is about 2 times faster than CLSQ for squaring 32-bit numbers and this ratio gradually increases to 3.7 times for squaring 8-Kbit numbers. In general, the Karatsuba algorithm (KASQ) is slower than the proposed algorithm for squaring numbers between the ranges of 32 bits and 8 Kbits. Table 5 shows that the proposed algorithm is about 7.9 times to 10.4 times faster than Karatsuba algorithm for squaring 32-bit to 64-bit numbers. The speed-up ratio continuously declines from 10.4 to about 2.5 times faster for squaring numbers in the range of 64-bit to 8-Kbit numbers.Table 5
Execution time (msec) of squaring algorithms.
Algorithm
Length of numbers (bits)
32
64
128
256
512
1024
2048
4096
8192
CLSQ
0.00494
0.0162
0.056
0.221
0.812
3.09
12.61
44.2
192
KASQ
0.01917
0.0599
0.179
0.533
1.653
4.91
15.02
45.1
141
Proposed squaring
0.00247
0.0058
0.019
0.059
0.231
0.97
3.4
13.2
57


## 5. Conclusion

A multiplication and a squaring algorithm with a small look-up table, which are based on the classical multiplication algorithm and Big-ones’ representation, are presented in this paper to speed up the squaring and multiplication calculation in public-key cryptography algorithms. The efficiency of the classical multiplication and squaring algorithm does not cover the whole range of numbers that is used by number theory based cryptosystems. In many instances, it has been reported that, at the threshold of 255 digits, the Karatsuba algorithm is performing better than the classical algorithm. In the proposed method, binary numbers are first converted to Big-one representation before being processed by the proposed multiplication or squaring algorithms. Compact representation with low Hamming weight of the Big-one representation decreases the number of submultiplication operations in the squaring and multiplication calculation. The experimental result gathered indicates that the proposed squaring and multiplication algorithm are efficient enough to substitute either the classical algorithm or Karatsuba algorithm or the hybrid of the two algorithms for squaring numbers. This finding should increase the performance of number theory based cryptosystems which depend heavily on the process of exponentiation (a process that depends on squaring and multiplication) of large integers in achieving the desired level of security.



---

*Source: 107109-2014-07-24.xml*