US 9,311,052 B2Granted

Method of performing multiplication operation in binary extension finite field

AssigneeElectronics and Telecommunications Research Institute

InventorsDongsoo Kim, Junyoung Son, Sangwoon Yang

Life of this patent

Estimating the term…

Loading patent…

Abstract

In a method of performing a multiplication operation in a binary extension finite field, a polynomial defined by ∑ n = 0 W - 1 ⁢ C n · z n is produced by expanding polynomial basis multiplication for multiplication of two polynomials a(z) and b(z) in a binary extension finite field. A mapping table is generated in which bit values having pieces of information about respective terms of the produced polynomial are mapped to respective rows. A code for calculating the polynomial, produced by expanding the polynomial basis multiplication for the multiplication of the two polynomials, with reference to the mapping table is generated. A multiplication operation of the two polynomials a(z) and b(z) in the binary extension finite field is performed by executing the code for calculating the polynomial wherein a ⁡ ( z ) = ∑ n = 0 m - 1 ⁢ a n · z n , b ⁡ ( z ) = ∑ n = 0 m - 1 ⁢ b n · z n , and W denotes a number of bits of a word that is an operation processing unit of a processor.

A method for optimizing a structure of a processor for performing a multiplication operation in a binary extension finite field, the optimization being performed by using algorithm, the method comprising:

producing a polynomial defined by
∑
n
=
0
W
-
1
⁢
C
n
·
z
n
by expanding polynomial basis multiplication for multiplication of two polynomials a(z) and b(z) in a binary extension finite field G F(2m);
generating a mapping table in which bit values having pieces of information about respective terms of the produced polynomial are mapped to respective rows;
and
generating a code for calculating the polynomial, produced by expanding the polynomial basis multiplication for the multiplication of the two polynomials a(z) and b(z), with reference to the mapping table;
wherein a multiplication operation of the two polynomials a(z) and b(z) in the binary extension finite field is calculated by a processor by executing the generated code for calculating the polynomial wherein
a
⁡
(
z
)
=
∑
n
=
0
m
-
1
⁢
a
n
·
z
n
,
b
⁡
(
z
)
=
∑
n
=
0
m
-
1
⁢
b
n
·
z
n
,
the W denotes a number of bits of a word that is an operation processing unit of the processor for performing the multiplication operation in the binary extension finite field,
wherein the multiplication operation in the binary extension finite field is implemented by using the recited algorithm rather than hardware, regardless of a structure of the processor, and
wherein producing the polynomial is configured to produce a polynomial
∑
n
=
0
W
-
1
⁢
C
n
·
z
n
=
{
∑
j
=
0
t
-
1
⁢
(
a
W
·
j
+
W
-
1
)
⁢
(
b
⁡
(
z
)
·
z
W
·
j
)
}
·
z
W
-
1
+
{
∑
j
=
0
t
-
1
⁢
(
a
W
·
j
+
W
-
2
)
⁢
(
b
⁡
(
z
)
·
z
W
·
j
)
}
·
z
W
-
2
+
…
+
⁢
⁢
⁢
{
∑
j
=
0
t
-
1
⁢
(
a
W
·
j
+
2
)
⁢
(
b
⁡
(
z
)
·
z
W
·
j
)
}
·
z
2
+
{
∑
j
=
0
t
-
1
⁢
(
a
W
·
j
+
1
)
⁢
(
b
⁡
(
z
)
·
z
W
·
j
)
}
·
z
1
+
{
∑
j
=
0
t
-
1
⁢
(
a
W
·
j
)
⁢
(
b
⁡
(
z
)
·
z
W
·
j
)
}
·
z
0
by expanding the polynomial basis multiplication given by the following equation
a
⁡
(
z
)
·
b
⁡
(
z
)
=
{
∑
j
=
0
t
-
1
⁢
(
a
W
·
j
+
W
-
1
)
⁢
(
b
⁡
(
z
)
·
z
W
·
j
)
}
·
z
W
-
1
+
{
∑
j
=
0
t
-
1
⁢
(
a
W
·
j
+
W
-
2
)
⁢
(
b
⁡
(
z
)
·
z
W
·
j
)
}
·
z
W
-
2
+
…
+
{
∑
j
=
0
t
-
1
⁢
(
a
W
·
j
+
2
)
⁢
(
b
⁡
(
z
)
·
z
W
·
j
)
}
·
z
2
+
{
∑
j
=
0
t
-
1
⁢
(
a
W
·
j
+
1
)
⁢
(
b
⁡
(
z
)
·
z
W
·
j
)
}
·
z
1
+
{
∑
j
=
0
t
-
1
⁢
(
a
W
·
j
)
⁢
(
b
⁡
(
z
)
·
z
W
·
j
)
}
·
z
0
for the multiplication of the two polynomials a(z) and b(z) wherein
t
=
[
m
W
]
,
and [x] denotes an operation for outputting a minimum integer equal to or greater than x.

462 more elements

Abstract

Claims5