WEKO3
AND
Item
{"_buckets": {"deposit": "bc90b5528b7542eb8b8e2e8244f156b6"}, "_deposit": {"id": "9573", "owners": [], "pid": {"revision_id": 0, "type": "depid", "value": "9573"}, "status": "published"}, "_oai": {"id": "oai:nagoya.repo.nii.ac.jp:00009573"}, "item_12_biblio_info_6": {"attribute_name": "\u66f8\u8a8c\u60c5\u5831", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "20090325", "bibliographicIssueDateType": "Issued"}, "bibliographic_titles": [{}]}]}, "item_12_date_granted_64": {"attribute_name": "\u5b66\u4f4d\u6388\u4e0e\u5e74\u6708\u65e5", "attribute_value_mlt": [{"subitem_dategranted": "20090325"}]}, "item_12_description_4": {"attribute_name": "\u6284\u9332", "attribute_value_mlt": [{"subitem_description": "Galois field GF(2^m) has many important applications, such as cryptography and error correcting codes. For highspeed 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 higherspeed and lowerpowerconsumption implementation. Chapter 2 shows arithmetic operations in GF(2^m), the extended Euclid\u2019s 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 hardwareassist 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 hardwareassisted implementation of arithmetic operations in GF(2^m) as well as other operations necessary in important applications more efficiently.", "subitem_description_type": "Abstract"}]}, "item_12_description_5": {"attribute_name": "\u5185\u5bb9\u8a18\u8ff0", "attribute_value_mlt": [{"subitem_description": "\u540d\u53e4\u5c4b\u5927\u5b66\u535a\u58eb\u5b66\u4f4d\u8ad6\u6587 \u5b66\u4f4d\u306e\u7a2e\u985e:\u535a\u58eb(\u60c5\u5831\u79d1\u5b66) (\u8ab2\u7a0b) \u5b66\u4f4d\u6388\u4e0e\u5e74\u6708\u65e5:\u5e73\u621021\u5e743\u670825\u65e5", "subitem_description_type": "Other"}]}, "item_12_dissertation_number_65": {"attribute_name": "\u5b66\u4f4d\u6388\u4e0e\u756a\u53f7", "attribute_value_mlt": [{"subitem_dissertationnumber": "13901\u7532\u7b2c8393\u53f7"}]}, "item_12_identifier_60": {"attribute_name": "URI", "attribute_value_mlt": [{"subitem_identifier_type": "HDL", "subitem_identifier_uri": "http://hdl.handle.net/2237/11369"}]}, "item_12_select_15": {"attribute_name": "\u8457\u8005\u7248\u30d5\u30e9\u30b0", "attribute_value_mlt": [{"subitem_select_item": "publisher"}]}, "item_12_text_14": {"attribute_name": "\u30d5\u30a9\u30fc\u30de\u30c3\u30c8", "attribute_value_mlt": [{"subitem_text_value": "application/pdf"}]}, "item_12_text_63": {"attribute_name": "\u5b66\u4f4d\u6388\u4e0e\u5e74\u5ea6", "attribute_value_mlt": [{"subitem_text_value": "2008"}]}, "item_creator": {"attribute_name": "\u8457\u8005", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Kobayashi, Katsuki"}], "nameIdentifiers": [{"nameIdentifier": "29147", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "\u5c0f\u6797, \u514b\u5e0c"}], "nameIdentifiers": [{"nameIdentifier": "29148", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "\u30d5\u30a1\u30a4\u30eb\u60c5\u5831", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "20180220"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "k8393_thesis.pdf", "filesize": [{"value": "280.5 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 280500.0, "url": {"label": "k8393_thesis.pdf", "url": "https://nagoya.repo.nii.ac.jp/record/9573/files/k8393_thesis.pdf"}, "version_id": "df22c13a7c4d43cfaf09262834c09c40"}]}, "item_language": {"attribute_name": "\u8a00\u8a9e", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "\u8cc7\u6e90\u30bf\u30a4\u30d7", "attribute_value_mlt": [{"resourcetype": "thesis", "resourceuri": "http://purl.org/coar/resource_type/c_46ec"}]}, "item_title": "STUDIES ON HARDWAREASSISTED IMPLEMENTATION OF ARITHMETIC OPERATIONS IN GALOIS FIELD GF(2^m)", "item_titles": {"attribute_name": "\u30bf\u30a4\u30c8\u30eb", "attribute_value_mlt": [{"subitem_title": "STUDIES ON HARDWAREASSISTED IMPLEMENTATION OF ARITHMETIC OPERATIONS IN GALOIS FIELD GF(2^m)"}]}, "item_type_id": "12", "owner": "1", "path": ["312/651/734"], "permalink_uri": "http://hdl.handle.net/2237/11369", "pubdate": {"attribute_name": "\u516c\u958b\u65e5", "attribute_name_i18n": "\u516c\u958b\u65e5", "attribute_value": "20090330"}, "publish_date": "20090330", "publish_status": "0", "recid": "9573", "relation": {}, "relation_version_is_last": true, "title": ["STUDIES ON HARDWAREASSISTED IMPLEMENTATION OF ARITHMETIC OPERATIONS IN GALOIS FIELD GF(2^m)"], "weko_shared_id": 3}
STUDIES ON HARDWAREASSISTED IMPLEMENTATION OF ARITHMETIC OPERATIONS IN GALOIS FIELD GF(2^m)
http://hdl.handle.net/2237/11369
035fc265b9694b5baf796c4edb36afb4
Name / File  License  Actions  

k8393_thesis.pdf (280.5 kB)


item type  学位論文 / Thesis or Dissertation(1)  

公開日  20090330  
タイトル  
タイトル  STUDIES ON HARDWAREASSISTED IMPLEMENTATION OF ARITHMETIC OPERATIONS IN GALOIS FIELD GF(2^m)  
著者 
Kobayashi, Katsuki
× Kobayashi, Katsuki× 小林, 克希 

抄録  
内容記述タイプ  Abstract  
内容記述  Galois field GF(2^m) has many important applications, such as cryptography and error correcting codes. For highspeed 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 higherspeed and lowerpowerconsumption 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 hardwareassist 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 hardwareassisted implementation of arithmetic operations in GF(2^m) as well as other operations necessary in important applications more efficiently.  
内容記述  
内容記述タイプ  Other  
内容記述  名古屋大学博士学位論文 学位の種類:博士(情報科学) (課程) 学位授与年月日:平成21年3月25日  
言語  
言語  eng  
資源タイプ  
資源  http://purl.org/coar/resource_type/c_46ec  
タイプ  thesis  
書誌情報  発行日 20090325  
学位授与年度  
学位授与年度  2008  
学位授与年月日  
学位授与年月日  20090325  
学位授与番号  
学位授与番号  13901甲第8393号  
フォーマット  
application/pdf  
著者版フラグ  
値  publisher  
URI  
識別子  http://hdl.handle.net/2237/11369  
識別子タイプ  HDL 