2026-04-14T22:55:36Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00044566 2025-01-19T23:35:09Z 1164:3925:3936:3938

Type-IIAllOnePolynomialField上での平方根導出アルゴリズムの高速実装 Square Root Calculation Algorithm over Type-II All One Polynomial Field 加藤, 英洋 王, 鳳 野上, 保之 森川, 良孝 Hidehiro, KATOU Feng, WANG Yasuyuki, NOGAMI Yoshitaka, MORIKAWA 近年，WeilペアリングやTateペアリング等のペアリング技術を用いたグループ署名の研究が行われており，このペアリングには有限体上で定義される楕円曲線が用いられている．この楕円曲線上の有理点を求めるために定義体上の平方根導出が必要となるが，一般に平方根導出は他の計算に比べて時間がかかることが知られている．著者らは，Ｆpｍにおける高速な平方根導出アルゴリズムを提案しており，高速な四則演算が行える拡大体ＡＯＰＦ（allonepolynomialfield)を提案している．上述の平方根導出アルゴリズムでは，計算にフロベニアス写像を用いている．また，ＡＯＰＦはフロベニアス写像に計算を一切必要としないので上述の平方根導出アルゴリズムの実装に適している．本稿では，具体的にはFp6等の拡大次数において実装高速な平方根導出アルゴリズムを実装し，計算機シミュレーションを行った結果について報告する． The authors proposes a square root (SQRT) algorithm in Fpm (m = r0r1 .....rn_12d,r1 : odd prime,d > 0 : integer). We compute the inverse SQRT in Fp2* 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 Fpm 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 Fp6, 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 Fp6, compared to the Smart algorithm. 情報処理学会 2006-07-20 jpn technical report https://ipsj.ixsq.nii.ac.jp/records/44566 AA11235941 情報処理学会研究報告コンピュータセキュリティ（CSEC） 2006 81(2006-CSEC-034) 7 12 https://ipsj.ixsq.nii.ac.jp/record/44566/files/IPSJ-CSEC06034002.pdf application/pdf 422.8 kB 2008-07-20