【手続補正書】
【提出日】平成18年1月26日(2006.1.26)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】有限体GF(2m)上の任意の元a=(a0,a1,・・・,am-1)に対し２次多項式z2+z+aのGF(2m)上の根を求める回路であって、ｍはGF(2)上の多項式f=xm+xm-1+・・・x+1が既約となるように定めた拡大次数であり、前記多項式ｆをGF(2m)の生成多項式として用いた場合において、
前記元aの対応するビットを一方の入力とし、前段素子の出力若しくはX(1,0)においては前段素子の出力の代わりにam-1を他方の入力とする従属接続されたm-3個の排他論理和素子X(1,0)〜X(1, m-4)と、
am-1及びX(1,1),X(1,3),・・・, X(1, m-5)の出力を各々一方の入力とし、a0を他方の入力とするm/2-1個の排他論理和素子X(2,0)〜X(2,m/2-2)とから構成され、前記素子X(2,0)〜X(2,m/2-2)の出力、前記素子X(1,0),X(1,2),・・・, X(1, m-4)の出力及び前記a0をz2+z+aの根z=(z0,z1,・・・,zm-1)として出力することを特徴とする有限体上の２次多項式の求根回路。
【請求項２】前記元aの対応するビットとX(1, m-4)の出力とを入力とする排他論理和素子X(1, m-3)を有し、該素子X(1, m-3)の出力を前記他の各素子と共に出力とすることを特徴とする請求項１記載の有限体上の２次多項式の求根回路。
【請求項３】有限体GF(2m)上の任意の元a=(a0,a1,・・・,am-1)に対し２次多項式z2+z+aのGF(2m)の上の根を求める回路であって、ｍはGF(2)上の多項式f=xm+xm-1+・・・x+1が既約となるように定めた拡大次数であり、前記多項式ｆをGF(2m)の生成多項式として用いた場合において、
前記元aの対応するビットを一方の入力とし、前段素子の出力若しくはX(1,0)においては前段素子の出力の代わりにam/2を他方の入力とする従属接続されたm-3個の排他論理和素子X(1,0)〜X(1, m-4)と、
前記素子X(1,0),X(1,2),・・・, X(1, m-4)の出力を各々一方の入力とし、a0を他方の入力とするm/2-1個の排他論理和素子X(2,0)〜X(2,m/2-2)とから構成され、X(2,0)〜X(2,m/2-2)の出力、X(1,1),X(1,3), ・・・, X(1, m-5)の出力、am/2及びa0をz2+z+aの根z=(z0,z1,・・・,zm-1)として出力することを特徴とする有限体上の２次多項式の求根回路。
【請求項４】前記元aの対応するビットとX(1, m-4)の出力とを入力とする排他論理和素子X(1, m-3)を有し、該素子X(1, m-3)の出力を前記他の各素子と共に出力とすることを特徴とする請求項３記載の有限体上の２次多項式の求根回路。
【請求項５】請求項１記載の回路のうち初段から所定の段数までの素子によりn個(n<m-1)の出力zを求める第１の回路と、請求項３記載の回路のうち初段から所定の段数までの素子により前記第１の回路の出力zと重複しないm-1-n個の出力zを求める第２の回路とを互いに接続した構成からなり、前記z2+z+aの根z=(z0,z1,・・・,zm-1)を求めることを特徴とする有限体上の２次多項式の求根回路。
【請求項６】前記互いに接続された回路のうち、前記第１の回路における従属接続された排他論理和素子の最終段の出力を一方の入力とし、前記第２の回路における従属接続された排他論理和素子の最終段の出力を他方の入力とする排他論理和素子を有し、該素子の出力を前記他の各素子と共に出力とすることを特徴とする請求項5記載の有限体上の２次多項式の求根回路。
【請求項７】有限体GF(2m)の上の任意の元a=(a0,a1,・・・,am-1)に対し２次多項式z2+z+aのGF(2m)の上の根を求める方法であって、ｍはGF(2)上の多項式f=xm+xm-1+・・・x+1が既約となるように定めた拡大次数であり、前記多項式ｆをGF(2m) の生成多項式として用いた場合において、
前記元aの対応するビット同士の排他論理和を求めzの対応するビットの値とし、その後に前記元aの対応するビット及び直前に求めたzのビットの排他論理和をzの次の対応するビットの値とし、以下これを繰り返してzを求めることを特徴とする有限体上の２次多項式の求根方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００３
【補正方法】変更
【補正の内容】
【０００３】
（有限体の演算）
有限体GF(2m)は2m個の元からなる集合であり、各々の元はベクトル表現で表現される。GF(2m)において位数2m−1である元を原始元と呼ぶ。ベクトル表現は、GF(2m)をGF(2)のｍ次元ベクトル空間とみなし、任意の元ａをｍ次元数ベクトル(a0,a1,・・・,am-1)と表現するものである。ここで、ベクトルの各要素a1はGF(2)の元、即ち０または１である。ベクトル表現において、ベクトル空間の基底は一通りには決まらず、元の表現は用いる基底によって異なる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
この楕円暗号では、暗号文が楕円曲線Ｅ上の有理点（xc,yc）であることから、mビットのメッセージは暗号化されたとき2mビットとなり、有限体上の乗法群を用いた他の暗号方式と比較して暗号文の大きさが2倍になるという欠点が有る。そこでこの欠点を解決するためには、暗号文を有限体上の乗法群暗号を用いたときの大きさ＋１ビットにする方法があり、これを実現するためにGF(2m)上の2次多項式の根を求める必要が有る。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
また本発明の請求項５に係る２次多項式の求根回路においては、請求項１記載の回路のうち初段から所定の段数までの素子によりn個（n< m-1）の出力zを求める第１の回路と、請求項３記載の回路のうち初段から所定の段数までの素子により前記第１の回路の出力zと重複しないm-1-n個の出力zを求める第２の回路とを互いに接続した構成からなり、前記z2+z+aの根z=(z,z)=(z0,z1,・・・,zm-1)を求めることを特徴としている。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
また本発明の請求項７に係る２次多項式の求根方法においては、ｍはGF(2)上の多項式f=xm+xm-1+・・・x+1が既約となるように定めた拡大次数であり、前記多項式ｆをGF(2m) の生成多項式として用いた場合において、前記元aの対応するビット同士の排他論理和を求めzの対応するビットの値とし、その後に前記元aの対応するビット及び直前に求めたzのビットの排他論理和をzの次の対応するビットの値とし、以下これを繰り返してzを求めることを特徴としている。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００３９
【補正方法】変更
【補正の内容】
【００３９】
なお上記第３の実施例およびその変形例では、z6を境とし、シーケンス(S1)により(z5,z9,z7,z3,z6)=zを求める回路と、その逆のシーケンス(S2)により(z8,z4,z2,z1,) =zを求める回路とを共に用いる構成としているが、本発明はこれに限らず、どのzを境にしてもよい。