No |
116599 |
標題(和) |
GF(P)上の3次多項式の既約判定 |
標題(英) |
Testing Irreducibility of Polynomial of degree 3 over GF(P). |
研究会名(和) |
情報理諭 |
研究会名(英) |
Information Theory |
開催年月日 |
2000-01-20 |
終了年月日 |
2000-01-20 |
会議種別コード |
2 |
共催団体名(和) |
IEEE |
資料番号 |
IT99-61 |
抄録(和) |
素数体GF(P)上の楕円曲線y^2=f(χ)〓χ^3+αχ+bは短い鍵長で公開鍵暗号を提供することができることから,近年この曲線の性質が多方面から研究されている.この暗号が安全であるためには,3次多項式f(χ)がGF(P)上で既約であることが必要である.既約判定法には逐次代入法が考えられるが,関連してStickelbergerの定理が有名である.この定理によれば,f(χ)の判別式D(f)がGF(P)において平方非剰余ならf(χ)は非既約と判定できるが、平方剰余なら判定不可能である.そこで本論文では,複素数体上の3次多項式の解法を与えるCardanoの公式をGF(P)上に適用する.3根すべてがGF(P^3)上の真性元であれば,f(χ)は既約と判定できる.この条件を整理することより,極めて高速な3次多項式の既約判定法を導出する. |
抄録(英) |
Properties of elliptic curve y^2=f(χ)*χ^3+aχ+b over prime field; GF(P) have been studied from many aspects, since the curve may yield a diverse of public key cryptsystems with short length key. Whereas for secure cryptststem the cublic polynomial f(χ) has to be irreducible over GF(P), only the theorem of Stickelberger is known concerning decision of the reducibility. By means of the theorem, we can decide reducibility if the discriminant of f(χ)is quadratic power residue, but not otherwise. In this paper, we apply Cardano's formula for solution of third order equation over complex field to the one over GF(P) and derive the condition for all solutions to be proper elements of cubic extension field GF(P^3). We also show the proposed algorithm for test of reducibility are very fast. |
収録資料名(和) |
電子情報通信学会技術研究報告 |
収録資料の巻号 |
Vol.99 No.562 |
ページ開始 |
19 |
ページ終了 |
24 |
キーワード(和) |
ルジャンドルの記号 |
キーワード(英) |
Legendre symbol |
本文の言語 |
JPN |
著者(和) |
森川良孝 |
著者(ヨミ) |
モリカワヨシタカ |
著者(英) |
Morikawa Yoshitaka |
所属機関(和) |
岡山大学工学部電気電子工学科 |
所属機関(英) |
Faculty of Engineering Okayama University |
著者(和) |
野上保之 |
著者(ヨミ) |
ノガミヤスユキ |
著者(英) |
Nogami Yasuyuki |
所属機関(和) |
岡山大学工学部電気電子工学科 |
所属機関(英) |
Faculty of Engineering Okayama University |
著者(和) |
矢野敏行 |
著者(ヨミ) |
ヤノトシユキ |
著者(英) |
Yano Toshiyuki |
所属機関(和) |
岡山大学工学部電気電子工学科 |
所属機関(英) |
Faculty of Engineering Okayama University |
著者(和) |
平本琢士 |
著者(ヨミ) |
ヒラモトタクジ |
著者(英) |
Hiramoto Takuji |
所属機関(和) |
岡山大学工学部電気電子工学科 |
所属機関(英) |
Faculty of Engineering Okayama University |