有限体の上の開平演算

概要

論文の詳細を見る
拡大体における平方根計算は,その計算に先立って平方剰余(QR)テストが必要である。今までに知られている平方根計算アルゴリズムはスマート法である。しかし、平方根計算とQRテストに多くの重複計算が存在していた。本論文は新たにQRテストと平方根計算アルゴリズムを提案して、すべての重複計算を取り除いて効率を上げること目的にしている。平方根計算アルゴリズムの計算途上で必要となるすべてのデータはすでにQRテストで計算したものを用いる手法を説明して、計算時間と計算量が大幅に減少することを示す。P=2^<16>+1とp=2^<16>+3の場合、Pentium4(2.6GHz)上でC++言語を用いて,GF(p)とGF(p^2)における、スマート法と提案法のシミュレーションを行った。P=2^<16>+1の場合、提案法は平均としてスマート法よりGF(p)で2倍速く、GF(p^2)で10倍速い。またp=2^<16>+3の場合、提案法は平均としてスマート法よりGF(p)で20倍速く、GF(p^2)で6倍速い。
一般社団法人情報処理学会の論文
2004-07-20