Faculty Profiles - NOGAMI Yasuyuki

Scopus

Square Root Calculation Algorithm over Type-II All One Polynomial Field

Extension Fields Efficient for Pairing Operation

OBARA Mayumi, AKANE Masataka, OKIMOTO Takumi, NOGAMI Yasuyuki, MORIKAWA Yoshitaka

29 ( 1 ) 391 - 394 2006.11

Representation and multiplication of finite field that used TypeII ONB like normal basis

KOBAYASHI Shigeki, NOGAMI Yasuyuki, SUGIMURA Tatsuo

29 ( 1 ) 169 - 172 2006.11

An extension field for variable extension degree and characteristic

NAMBA Ryo, KATOU Hidehiro, YOSHIDA Tomoki, NOGAMI Yasuyuki, MORIKAWA Yoshitaka

29 ( 1 ) 395 - 398 2006.11

KATOU Hidehiro, WANG FENG, NOGAMI Yasuyuki, MORIKAWA Yoshitaka

IPSJ SIG Notes 2006 ( 81 ) 7 - 12 2006.7

Language：Japanese Publisher：Information Processing Society of Japan (IPSJ)

The authors proposes a square root (SQRT) algorithm in F_p^m (m = r_0r_1…r_<n-1>2^d,r_2: odd prime, d>0: integer). We compute the inverse SQRT in F_p^2^d using MW-ST algorithm. Then the Frobenius mappings with an addition chain are adopted for this SQRT algorithm, in which a lot of computations in a given extension field F_p^m are also reduce to those in a proper subfield by the norm computations. Those reductions of the field degree increases efficiency in the SQRT implementation. More specifically the Smart algorithm and proposed algorithm in F_p^6, for example, were implemented on a Pentium4 (3.8FHz) computer using the C++ programming language and NTL Library. The computer simulations showed that, on average, the proposed algoithm accelerates the SQRT computation by 3 times in F_p^6, compared to the Smart algorithm.

Pairing Computation with MNT Curve over All One Polynomial Field

Other Link： http://id.nii.ac.jp/1001/00044566/

AKANE Masataka, OKIMOTO Takumi, NOGAMI Ysuyuki, MORIKAWA Yoshitaka

IPSJ SIG Notes 2006 ( 81 ) 13 - 18 2006.7

Language：Japanese Publisher：Information Processing Society of Japan (IPSJ)

In recent years, many cryptographic applications with bilinear-pairing over elliptic curves have been proposed. The well-known MNT curves, that are non-supersingular elliptic curves, provide bilinear-pairings over extension fields of degree 3, 4, and 6. When the embedding degree is equal to 3, MNT curves cannot be defined over optimal extension field (OEF). Even when the embedding degree is equal to 4 or 6, MNT curves cannot be always defined over OEF. For some of such cases, it can be defined over all one polynomial field (AOPF). Since Frobenius mapping can be fast carried out in the AOPFs, this paper gives considered some improvements for Tate pairing calculation. Then, some examples and simulation results are shown.

A Translation Matrix between Two Isomorphic Extension Fields via Optimal Normal Basis Representation

Other Link： http://id.nii.ac.jp/1001/00044567/

NAMBA Ryo, NOGAMI Yasuyuki, MORIKAWA Yoshitaka

IPSJ SIG Notes 2006 ( 81 ) 1 - 6 2006.7

Language：Japanese Publisher：Information Processing Society of Japan (IPSJ)

Some extension fields efficient for fast implementation have been proposed. Such extension fields adopt unique modular polynomial and basis. Therefore, an element can have some different vector representations in the isomorphic extension fields. This paper proposes a method for generating a basis translation matrix between two isomorphic extension fields. First, this paper shows that the translation matrix can be obtained via TypeI Optimal Normal Basis (ONB). TypeI ONB plays key role since it has the following properties; TypeI ONB is a set of conjugate elements and of course a normal basis, these conjugates have the same order, they are zeros of a certain irreducible all one polynomial. Then, some examples of translation matrix are shown. From the experimental result, it is shown that the proposed method is enough practical.

Square Root Calculation Algorithm over Type-II All One Polynomial Field

Other Link： http://id.nii.ac.jp/1001/00044565/

KATOU Hidehiro, WANG FENG, NOGAMI Yasuyuki, MORIKAWA Yoshitaka

IEICE technical report 106 ( 174 ) 7 - 12 2006.7

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

The authors proposes a square root (SQRT) algorithm in F_<p^m> (m=r_0r_1…r_<n-1>2^d, r_i: odd prime, d>0: integer). We compute the inverse SQRT in F_<p^2^d> using MW-ST algorithm. Then the Frobenius mappings with an addition chain are adopted for this SQRT algorithm, in which a lot of computations in a given extension field F_<p^m> are also reduce to those in a proper sub field by the norm computations. Those reductions of the field degree increases efficiency in the SQRT implementation. More specifically the Smart algorithm and proposed algorithm in F_<p^6>, for example, were implemented on a Pentium4 (3.8FHz) computer using the C++ programming language and NTL Library. The computer simulations showed that, on average, the proposed algoithm accelerates the SQRT computation by 3 times in F_<p^6>, compared to the Smart algorithm.

A high-speed square root algorithm in extension fields

Hidehiro Katou, Feng Wang, Yasuyuki Nogami, Yoshitaka Morikawa

INFORMATION SECURITY AND CRYPTOLOGY - ICISC 2006, PROCEEDINGS 4296 94 - + 2006

Language：English Publisher：SPRINGER-VERLAG BERLIN

A square root (SQRT) algorithm in GF(p(m)) (m = r(0)r(1)center dot center dot center dot r(n-1)2(d), r(i): odd prime, d > 0: integer) is proposed in this paper. First, the Tonelli-Shanks algorithm is modified to compute the inverse SQRT in GF (p(2d)), where most of the computations are performed in the corresponding subfields GF(p(2d)) for 0 <= i <= d-1. Then the Frobenius mappings with an addition chain are adopted for the proposed SQRT algorithm, in which a lot of computations in a given extension field GF(p(m)) are also reduce to those in a proper subfield by the norm computations. Those reductions of the field degree increase efficiency in the SQRT implementation. More specifically the Tonelli-Shanks algorithm and the proposed algorithm in GF(p(22)), GF(P-44) and GF(P-88) were implemented on a Pentium4 (2.6 GHz) computer using the C++ programming language. The computer simulations showed that, on average, the proposed algorithm accelerates the SQRT computation by 25 times in GF (P-22), by 45 times in GF (P-44), and by 70 times in GF(p(88)), compared to the Tonelli-Shanks algorithm, which is supported by the evaluation of the number of computations.

DOI： 10.1007/11927587_10

Scopus

Other Link： https://dblp.uni-trier.de/db/conf/icisc/icisc2006.html#KatouWNM06

A high-speed square root algorithm in extension fields

Hidehiro Katou, Feng Wang, Yasuyuki Nogami, Yoshitaka Morikawa

INFORMATION SECURITY AND CRYPTOLOGY - ICISC 2006, PROCEEDINGS 4296 94 - + 2006

Language：English Publisher：SPRINGER-VERLAG BERLIN

The Orders of Elliptic Curves y(2) = x(3) + b, b ∈ F(* q)

A Method for Checking the Parity of (#Jc-1)/2

M.Akane, Y.Nogami, Y.Morikawa

The 2006 International Symposium on Information Theory and its Applications 2006

Nogami Yasuyuki, Morikawa Yoshitaka

Memoirs of the Faculty of Engineering, Okayama University 40 ( 1 ) 83 - 94 2006

Cyclic vector multilication algorithm makes an inversion in F_{p^3} fastest

Yasuyuki Nogami, Hidehiro Katou, Yoshitaka Morik

JWIS2006(Joint workshop on information security) 2006

Cyclic Vector Multiplication is Efficient for Small Extension Degrees

Hidehiro Katou, Feng Wang, Yasuyuki Nogami, Yoshitaka Morikawa

Second International Congress on Mathematical Software ICMS2006 2006

A Consideration on Cyclic Vector Multiplication Algorithm

KATOU Hidehiro, NOGAMI Yasuyuki, NANBA Ryou, MORIKAWA Yoshitaka

28 ( 1 ) 295 - 298 2005.11

A Consideration on the Order of Genus 2 Hyperelliptic Curve

NOGAMI Yasuyuki, MORIKAWA Yoshitaka

28 ( 2 ) 889 - 892 2005.11

An efficient square root computation in finite fields GF(p(2d))

F Wang, Y Nogami, Y Morikawa

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E88A ( 10 ) 2792 - 2799 2005.10

Language：English Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG

This paper focuses on developing a square root (SQRT) algorithm in finite fields GF(p(2d)) (d >= 0). Examining the Smart algorithm, a well-known SQRT algorithm, we can see that there is some computation overlap between the Smart algorithm and the quadratic residue (QR) test, which must be implemented before a SQRT computation. It makes the Smart algorithm inefficient. In this paper, we propose a new QR test and a new SQRT algorithm in GF(p(2d)), in which not only there is no computation overlap, but also most of computations required for the proposed SQRT algorithm in GF(p2d) can be implemented in the corresponding subfields GF(p(2d-i)) for 1 <= i <= d, which yields many reductions in the computational time and complexity. The computer simulation also shows that the proposed SQRT algorithm is much faster than the Smart algorithm.

DOI： 10.1093/ietfec/e88-a.10.2792

Scopus

The Representation of typeII ONB by self-reciprocal transformation

KOBAYASHI Shigeki, NOGAMI Yasuyuki, SUGIMURA Tatsuo

IEICE technical report. Information theory 105 ( 311 ) 25 - 30 2005.9

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

This paper make relation of All One Polynomials and Irreducible Polynomials with TypeIIONB clear, by using polynomial conversion technique from polynomial of degree m to polynomial of degree 2m called self-reciprocal transformation and polynomial conversion technique from polynomial of degree 2m to polynomial of degree m called self-reciprocal reverse transformation. If irreducible polynomial of degree m become All One Polynomial by self-reciprocal traneformation, we show that original irreducible polynomial of degree m is irreducible polynomial with TypeIIONB. When there is TypeIIONB, we show that we can find irreducible polynomial with TypeIIONB by doing self-reciprocal reverse tranceformation for All One Polynomial. As application, we give technique to make an irreducible polynomial of prime degree.