Method of performing multiplication operation in binary extension finite field

Patent metadata

Field	Value
Publication number	US-9311052-B2
Application number	US-201314084767-A
Country	US
Kind code	B2
Filing date	Nov 20, 2013
Priority date	Nov 29, 2012
Publication date	Apr 12, 2016
Grant date	Apr 12, 2016

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.

First claim

What is claimed is:

1. 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(2 m );
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

Assignees

• Korea Electronics Telecomm

Inventors

• Kim Dongsoo
• Son Junyoung
• Yang Sangwoon

Classifications

• G06F7/523

  Multiplying only · CPC title

• G06F7/724 Primary

  Finite field arithmetic (for error detection or correction in general H03M13/00, in computers G06F11/10) · CPC title