@phdthesis{oai:nagoya.repo.nii.ac.jp:00009573, author = {Kobayashi, Katsuki and 小林, 克希}, month = {Mar}, note = {Galois field GF(2^m) has many important applications, such as cryptography and error correcting codes. For high-speed implementation of these applications, efficient implementation of arithmetic operations in GF(2^m) is important. In this dissertation, three methods for efficient implementation of arithmetic operations in GF(2^m) are proposed. These methods are based on the idea of hardware assist that yields higher-speed and lower-powerconsumption implementation. Chapter 2 shows arithmetic operations in GF(2^m), the extended Euclid’s algorithm, and a previously proposed hardware inversion algorithm as preliminaries. Chapter 3 proposes a software algorithm for inversion in GF(2^m) that is suitable for implementation with a polynomial multiply instruction on GF(2). Among previously proposed instruction set extensions for cryptography, ones for elliptic curve cryptography (ECC) or advanced encryption standard (AES) include a polynomial multiply instruction on GF(2), because this instruction can accelerate multiplication in GF(2^m). The algorithm proposed in the chapter employs the matrix that represents the operations required by several contiguous iterations of the previously reported algorithm, and computes inversion fast through the matrix with a polynomial multiply instruction on GF(2). When the word size of the processor is 32 and m is 571, the proposed algorithm computes inversion with approximately half the number of polynomial multiply instructions on GF(2) and XOR instructions required by the previously reported algorithm on the average. Chapter 4 proposes a fast hardware division algorithm in GF(2^m) with parallelization of modular reductions for fast division circuit. This algorithm requires only one iteration to perform the operations required by two iterations of a previously reported algorithm, and performs two modular reductions in parallel by changing the order of execution of the operations. A circuit based on the algorithm proposed in the chapter has almost the same critical path delay as previously reported circuits, nevertheless the number of clock cycles required by the circuit is almost half of that of previously reported circuits. The circuit is estimated to be over 35% faster than previously reported circuits with logic synthesis. Chapter 5 proposes a hardware algorithm for a combined circuit of multiplication and inversion in GF(2^m). Although both multiplication and inversion are employed for ECC, realization of two circuits for them yields large area. Thus, for reduction of hardware of these circuits, the algorithm proposed in the chapter is developed by focusing on the similarities between conventional multiplication and inversion algorithms so that almost all hardware components of a circuit based on the algorithm can be shared by multiplication and inversion. The combined circuit is estimated to be over 15% smaller than the previously proposed combined circuits with logic synthesis. Finally, Chap. 6 concludes that hardware-assist is a promising technique for efficient implementation of arithmetic operations in GF(2^m). In addition, by focusing on similarities and parallelism of algorithms, reduction and acceleration of them are possible. The knowledge obtained through the study should make hardware-assisted implementation of arithmetic operations in GF(2^m) as well as other operations necessary in important applications more efficiently., 名古屋大学博士学位論文 学位の種類:博士(情報科学) (課程) 学位授与年月日:平成21年3月25日}, school = {名古屋大学, Nagoya University}, title = {STUDIES ON HARDWARE-ASSISTED IMPLEMENTATION OF ARITHMETIC OPERATIONS IN GALOIS FIELD GF(2^m)}, year = {2009} }