(57)【特許請求の範囲】
【請求項１】
有限体ＧＦ（３）＝｛０，１，２｝の元を係数とする既約多項式をｆ（ｘ）とし、ｆ（α）＝０を満たす根をαとし、ｎを１以上の整数とした場合における、或る多項式Ａ（α）＝ｓ０＋ｓ１・α＋…＋ｓｎ−１・αｎ−１の係数系列ｓ０，ｓ１，…，ｓｎ−１∈ＧＦ（３）を格納するメインメモリと、
メインメモリから読み込まれたデータを格納するレジスタと、
レジスタから２つの多項式にそれぞれ対応する２つの係数系列を読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式の係数系列としてレジスタに格納する加算手段と、
レジスタから１つの多項式に対応する１つの係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、当該１つの多項式の二倍算結果を示す多項式の係数系列としてレジスタに格納する二倍算手段と、
レジスタから１つの多項式に対応する１つの係数系列を読み込み、当該係数系列の各係数を１次数分だけ高次数側へシフトさせ、そのシフト結果である係数系列を、当該１つの多項式のα倍算結果を示す多項式の係数系列としてレジスタに格納するα倍算手段と、
処理に必要なデータがレジスタに格納されていない場合に、当該処理に必要なデータをメインメモリからレジスタに読み込む処理と、処理に必要な領域がレジスタに確保できない場合にレジスタから何れかのデータを削除する処理と、前記加算手段の処理と、前記二倍算手段の処理と、前記α倍算手段の処理とを制御し、或る整数ｉ≧２に対してＷ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ・αｉ（ｔ０，ｔ１，…，ｔｉ∈ＧＦ（３））で表現可能な多項式Ｗ（α）について、それぞれ、多項式Ｗ（α）・Ａ（α）の係数系列を算出させる制御手段と、を有し、
前記制御手段は、
前記加算手段、前記二倍算手段及び前記α倍算手段が、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ−１・αｉ−１（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３））で表現可能な０及び１を除くすべての多項式Ｗ（α）について、それぞれ、多項式Ｗ（α）・Ａ（α）の係数系列を生成する第１過程と、
前記α倍算手段が、前記第１過程で生成された多項式αｉ−１・Ａ（α）の係数系列をレジスタから読み込み、多項式αｉ・Ａ（α）の係数系列を生成し、当該多項式αｉ・Ａ（α）の係数系列をレジスタに格納する第２過程と、
多項式αｉ・Ａ（α）の係数系列を継続的にレジスタに保持した状態で、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ・αｉ（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３），ｔｉ＝１，２）で表現可能なαｉを除く多項式Ｗ（α）について、多項式Ｗ（α）・Ａ（α）の係数系列が算出するために、
前記二倍算手段が、１つ前の過程で算出され、既にレジスタに格納されている１つの係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、当該１つの多項式の二倍算結果を示す多項式の係数系列としてレジスタに格納する二倍算過程と、
前記加算手段が、前記第１過程で生成された何れか１つの多項式の係数系列又は多項式Ａ（α）の係数系列と、多項式αｉ・Ａ（α）の係数系列とをレジスタから読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式の係数系列としてレジスタに格納する加算過程と、を交互に実行する第３過程と、
を少なくとも制御するように構成される、
ことを特徴とする多項式乗算装置。
【請求項２】
有限体ＧＦ（３）＝｛０，１，２｝の元を係数とする既約多項式をｆ（ｘ）とし、ｆ（α）＝０を満たす根をαとし、ｎを１以上の整数とした場合における、或る多項式Ａ（α）＝ｓ０＋ｓ１・α＋…＋ｓｎ−１・αｎ−１の係数系列ｓ０，ｓ１，…，ｓｎ−１∈ＧＦ（３）を格納するメインメモリと、
メインメモリから読み込まれたデータを格納するレジスタと、
レジスタから２つの多項式にそれぞれ対応する２つの係数系列を読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式の係数系列としてレジスタに格納する加算手段と、
レジスタから１つの多項式に対応する１つの係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、当該１つの多項式の二倍算結果を示す多項式の係数系列としてレジスタに格納する二倍算手段と、
レジスタから１つの多項式に対応する１つの係数系列を読み込み、当該係数系列の各係数を１次数分だけ高次数側へシフトさせ、そのシフト結果である係数系列を、当該１つの多項式のα倍算結果を示す多項式の係数系列としてレジスタに格納するα倍算手段と、
レジスタから１つの多項式に対応する１つの係数系列を読み込み、当該係数系列の各係数を２次数分だけ高次数側へシフトさせ、そのシフト結果である係数系列を、当該１つの多項式のα２倍算結果を示す多項式の係数系列としてレジスタに格納するα２倍算手段と、
処理に必要なデータがレジスタに格納されていない場合に、当該処理に必要なデータをメインメモリからレジスタに読み込む処理と、処理に必要な領域がレジスタに確保できない場合にレジスタから何れかのデータを削除する処理と、前記加算手段の処理と、前記二倍算手段の処理と、前記α倍算手段の処理と、α２倍算手段とを制御し、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ・αｉ（ｔ０，ｔ１，…，ｔｉ∈ＧＦ（３），ｉ＝２）で表現可能な多項式Ｗ（α）について、それぞれ、多項式Ｗ（α）・Ａ（α）の係数系列を算出させる制御手段と、を有し、
前記制御手段は、
多項式αｉ−２・Ａ（α）の係数系列を継続的にレジスタに保持した状態で、前記加算手段、前記二倍算手段及び前記α倍算手段が、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ−１・αｉ−１（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３））で表現可能な０及び１を除くすべての多項式Ｗ（α）について、それぞれ、多項式Ｗ（α）・Ａ（α）の係数系列を生成する第１過程と、
前記α２倍算手段が、多項式αｉ−２・Ａ（α）の係数系列をレジスタから読み込み、多項式αｉ・Ａ（α）の係数系列を生成し、当該多項式αｉ・Ａ（α）の係数系列をレジスタに格納する第２過程と、
多項式αｉ・Ａ（α）の係数系列を継続的にレジスタに保持した状態で、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ・αｉ（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３），ｔｉ＝１，２）で表現可能なαｉを除く多項式Ｗ（α）について、多項式Ｗ（α）・Ａ（α）の係数系列を算出するために、少なくとも、
前記二倍算手段が、１つ前の過程で算出され、既にレジスタに格納されている１つの係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、当該１つの多項式の二倍算結果を示す多項式の係数系列としてレジスタに格納する二倍算過程と、
前記加算手段が、前記第１過程で生成された何れか１つの多項式の係数系列又は多項式Ａ（α）の係数系列と、多項式αｉ・Ａ（α）の係数系列とをレジスタから読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式の係数系列としてレジスタに格納する加算過程と、を交互に実行する第３過程と、
を少なくとも制御するように構成される、
ことを特徴とする多項式乗算装置。
【請求項３】
請求項２に記載の多項式乗算装置であって、
レジスタから１つの多項式に対応する１つの係数系列を読み込み、さらに、他の１つの多項式に対応する１つの係数系列を当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍した係数系列に変換して読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、当該１つの多項式と当該他の多項式の二倍算結果との加算結果を示す多項式の係数系列としてレジスタに格納する二倍算加算手段をさらに有し、
前記制御手段は、
前記二倍算加算手段が、多項式αｉ・Ａ（α）の係数系列をレジスタから読み込み、さらに、多項式αｉ−２・Ａ（α）の係数系列を多項式２αｉ−２・Ａ（α）の係数系列に変換して読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、多項式（２αｉ−２＋αｉ）・Ａ（α）の係数系列としてレジスタに格納する二倍算加算過程をさらに有する前記第３過程を制御し、
少なくとも前記第１過程から前記二倍算加算過程までが、多項式αｉ−２・Ａ（α）の係数系列を継続的にレジスタに保持した状態で実行されるように制御する、
ことを特徴とする多項式乗算装置。
【請求項４】
請求項１から３の何れかに記載の多項式乗算装置であって、
ｉ＝２に対応する前記第１過程は、
前記二倍算手段が、レジスタから多項式Ａ（α）の係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、多項式２・Ａ（α）の係数系列としてレジスタに格納する第４過程と、
前記α倍算手段が、レジスタから多項式Ａ（α）の係数系列を読み込み、当該係数系列の各係数を１次数分だけ高次数側へシフトさせ、そのシフト結果である係数系列を、多項式α・Ａ（α）の係数系列としてレジスタに格納する第５過程と、
前記二倍算手段が、レジスタから多項式α・Ａ（α）の係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、多項式２α・Ａ（α）の係数系列としてレジスタに格納する第６過程と、
前記加算手段が、レジスタから多項式Ａ（α）の係数系列と多項式α・Ａ（α）の係数系列とを読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、多項式（１＋α）・Ａ（α）の係数系列としてレジスタに格納する第７過程と、
前記加算手段が、レジスタから多項式Ａ（α）の係数系列と多項式（１＋α）・Ａ（α）の係数系列とを読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、多項式（２＋α）・Ａ（α）の係数系列としてレジスタに格納する第８過程と、
前記二倍算手段が、レジスタから多項式（１＋α）・Ａ（α）の係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、多項式（２＋２α）・Ａ（α）の係数系列としてレジスタに格納する第９過程と、
前記二倍算手段が、レジスタから多項式（２＋α）・Ａ（α）の係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、多項式（１＋２α）・Ａ（α）の係数系列としてレジスタに格納する第１０過程と、を有し、
前記前記第５過程の次に前記第６過程が実行され、前記第６過程の次に前記第７過程が実行され、前記第７過程の次に前記第８過程が実行され、前記第８過程の次に前記第９過程が実行され、前記第９過程の次に前記第１０過程が実行されるか、又は、前記前記第５過程の次に前記第６過程が実行され、前記第６過程の次に前記第７過程が実行され、前記第７過程の次に前記第９過程が実行され、前記第９過程の次に前記第８過程が実行され、前記第８過程の次に前記第１０過程が実行される、
ことを特徴とする多項式乗算装置。
【請求項５】
有限体ＧＦ（３）＝｛０，１，２｝の元を係数とする既約多項式をｆ（ｘ）とし、ｆ（α）＝０を満たす根をαとし、ｎを１以上の整数とした場合における、或る多項式Ａ（α）＝ｓ０＋ｓ１・α＋…＋ｓｎ−１・αｎ−１の係数系列ｓ０，ｓ１，…，ｓｎ−１∈ＧＦ（３）をレジスタに格納する過程と、
加算手段と二倍算手段とα倍算手段とが、或る整数ｉ≧２に対してＷ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ−１・αｉ−１（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３））で表現可能な０及び１を除くすべての多項式Ｗ（α）について、それぞれ、多項式Ｗ（α）・Ａ（α）の係数系列を生成する第１過程と、
前記α倍算手段が、前記第１過程で生成された多項式αｉ−１・Ａ（α）の係数系列をレジスタから読み込み、当該係数系列の各係数を１次数分だけ高次数側へシフトさせ、そのシフト結果である係数系列を、多項式αｉ・Ａ（α）の係数系列としてレジスタに格納する第２過程と、
多項式αｉ・Ａ（α）の係数系列を継続的にレジスタに保持した状態で、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ・αｉ（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３），ｔｉ＝１，２）で表現可能なαｉを除く多項式Ｗ（α）について、多項式Ｗ（α）・Ａ（α）の係数系列を算出するために、
前記二倍算手段が、１つ前の過程で算出され、既にレジスタに格納されている１つの係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、当該１つの多項式の二倍算結果を示す多項式の係数系列としてレジスタに格納する二倍算過程と、
前記加算手段が、前記第１過程で生成された何れか１つの多項式の係数系列又は多項式Ａ（α）の係数系列と、多項式αｉ・Ａ（α）の係数系列とをレジスタから読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式の係数系列としてレジスタに格納する加算過程と、を交互に実行する第３過程と、
を有することを特徴とする多項式乗算方法。
【請求項６】
有限体ＧＦ（３）＝｛０，１，２｝の元を係数とする既約多項式をｆ（ｘ）とし、ｆ（α）＝０を満たす根をαとし、ｎを１以上の整数とした場合における、或る多項式Ａ（α）＝ｓ０＋ｓ１・α＋…＋ｓｎ−１・αｎ−１の係数系列ｓ０，ｓ１，…，ｓｎ−１∈ＧＦ（３）をレジスタに格納する過程と、
多項式αｉ−２・Ａ（α）の係数系列を継続的にレジスタに保持した状態で、加算手段、二倍算手段及びα倍算手段が、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ−１・αｉ−１（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３），ｉ＝２）で表現可能な０及び１を除くすべての多項式Ｗ（α）について、それぞれ、多項式Ｗ（α）・Ａ（α）の係数系列を生成する第１過程と、
α２倍算手段が、多項式αｉ−２・Ａ（α）の係数系列をレジスタから読み込み、多項式αｉ・Ａ（α）の係数系列を生成し、当該多項式αｉ・Ａ（α）の係数系列をレジスタに格納する第２過程と、
多項式αｉ・Ａ（α）の係数系列を継続的にレジスタに保持した状態で、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ・αｉ（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３），ｔｉ＝１，２）で表現可能なαｉを除く多項式Ｗ（α）について、多項式Ｗ（α）・Ａ（α）の係数系列を算出するために、少なくとも、
前記二倍算手段が、１つ前の過程で算出され、既にレジスタに格納されている１つの係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、当該１つの多項式の二倍算結果を示す多項式の係数系列としてレジスタに格納する二倍算過程と、
前記加算手段が、前記第１過程で生成された何れか１つの多項式の係数系列又は多項式Ａ（α）の係数系列と、多項式αｉ・Ａ（α）の係数系列とをレジスタから読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式の係数系列としてレジスタに格納する加算過程と、を交互に実行する第３過程と、
を有することを特徴とする多項式乗算方法。
【請求項７】
請求項６に記載の多項式乗算方法であって、
前記第３過程は、
二倍算加算手段が、多項式αｉ・Ａ（α）の係数系列をレジスタから読み込み、さらに、多項式αｉ−２・Ａ（α）の係数系列を多項式２αｉ−２・Ａ（α）の係数系列に変換して読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、多項式（２αｉ−２＋αｉ）・Ａ（α）の係数系列としてレジスタに格納する二倍算加算過程をさらに有し、
少なくとも前記第１過程から前記二倍算加算過程までは、
多項式αｉ−２・Ａ（α）の係数系列を継続的にレジスタに保持した状態で実行される、
ことを特徴とする多項式乗算方法。
【請求項８】
請求項５から７の何れかに記載の多項式乗算方法であって、
ｉ＝２に対応する前記第１過程は、
前記二倍算手段が、レジスタから多項式Ａ（α）の係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、多項式２・Ａ（α）の係数系列としてレジスタに格納する第４過程と、
前記α倍算手段が、レジスタから多項式Ａ（α）の係数系列を読み込み、当該係数系列の各係数を１次数分だけ高次数側へシフトさせ、そのシフト結果である係数系列を、多項式α・Ａ（α）の係数系列としてレジスタに格納する第５過程と、
前記二倍算手段が、レジスタから多項式α・Ａ（α）の係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、多項式２α・Ａ（α）の係数系列としてレジスタに格納する第６過程と、
前記加算手段が、レジスタから多項式Ａ（α）の係数系列と多項式α・Ａ（α）の係数系列とを読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、多項式（１＋α）・Ａ（α）の係数系列としてレジスタに格納する第７過程と、
前記加算手段が、レジスタから多項式Ａ（α）の係数系列と多項式（１＋α）・Ａ（α）の係数系列とを読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、多項式（２＋α）・Ａ（α）の係数系列としてレジスタに格納する第８過程と、
前記二倍算手段が、レジスタから多項式（１＋α）・Ａ（α）の係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、多項式（２＋２α）・Ａ（α）の係数系列としてレジスタに格納する第９過程と、
前記二倍算手段が、レジスタから多項式（２＋α）・Ａ（α）の係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、多項式（１＋２α）・Ａ（α）の係数系列としてレジスタに格納する第１０過程と、を有し、
前記前記第５過程の次に前記第６過程が実行され、前記第６過程の次に前記第７過程が実行され、前記第７過程の次に前記第８過程が実行され、前記第８過程の次に前記第９過程が実行され、前記第９過程の次に前記第１０過程が実行されるか、又は、前記前記第５過程の次に前記第６過程が実行され、前記第６過程の次に前記第７過程が実行され、前記第７過程の次に前記第９過程が実行され、前記第９過程の次に前記第８過程が実行され、前記第８過程の次に前記第１０過程が実行される、
ことを特徴とする多項式乗算方法。
【請求項９】
請求項５から８の何れかに記載の多項式乗算方法の各過程をコンピュータ実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限体の元を係数とする多項式間の乗算をコンピュータ上で実行する技術に関し、特に、多項式間の乗算結果を利用して他の多項式間の乗算を行う多項式乗算技術に関する。
【背景技術】
【０００２】
有限体ＧＦ（３）＝｛０，１，２｝を基礎体とする拡大体ＧＦ（３ｍ）（ｍ≧２）の元は、有限体ＧＦ（３）の元を係数とするαについてのｍ−１次多項式で表現できる。なお、αは有限体ＧＦ（３）の元を係数とする既約多項式ｆ（ｘ）においてｆ（α）＝０を満たす。また、拡大体ＧＦ（３ｍ）の元を表現する２つの多項式をＡ（α），Ｂ（α）とすると、拡大体ＧＦ（３ｍ）上の乗算は、Ｃ（α）＝Ａ（α）・Ｂ（α） ｍｏｄ ｆ（α）と表現でき、多項式演算Ａ（α）・Ｂ（α）とｆ（α）による除算とによって計算できる。なお、多項式演算Ａ（α）・Ｂ（α）における各次数の係数間の演算は有限体ＧＦ（３）上の演算である。また、多項式演算Ａ（α）・Ｂ（α）は可換である。
【０００３】
この多項式演算Ａ（α）・Ｂ（α）を高速化する手法の一つにウィンドウ（Window）法がある（例えば、非特許文献１参照）。ウィンドウ法では、まず、多項式Ｂ（α）の次数ｍ−１以下の或る次数ｗ−１（ｗをウィンドウ幅と呼ぶ）の多項式Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｗ−１・αｗ−１（ｔ０，ｔ１，…，ｔｗ−１∈ＧＦ（３））で表現可能なすべてのＷ（α）について中間積Ａ（α）・Ｗ（α）を事前計算してメモリに格納する。そして、それらの中間積を用い、Ａ（α）・Ｂ（α）の計算が行われる。以下、中間積Ａ（α）・Ｗ（α）の一般的な計算方法を説明する。
【０００４】
［被演算子の実装方法］
中間積の被演算子となる各多項式ｔ０＋ｔ１・α＋…＋ｔｐ−１・αｐ−１（ｐは１以上の整数）は、係数系列ｔ０，ｔ１，…，ｔｐ−１∈ＧＦ（３）で表現され、各係数ｔｋ∈ＧＦ（３）（ｋは０以上ｐ−１の整数）はそれぞれｔｋ＝（（ｔｋ）Ｈｉ，（ｔｋ）Ｌｏ）（（ｔｋ）Ｈｉ，（ｔｋ）Ｌｏ∈ＧＦ（２））の２ビットで表現される。そして、それらの上位ビット系列（ｔ０）Ｈｉ，（ｔ１）Ｈｉ，…，（ｔｐ−１）Ｈｉと下位ビット系列（ｔ０）Ｈｉ，（ｔ１）Ｈｉ，…，（ｔｐ−１）Ｈｉとが、別個のレジスタに格納される。例えば、ｍ＝９７，ｗ≦３１であり、各レジスタのビット長（レジスタ長）が６４である場合、上位ビット系列及び下位ビット系列がそれぞれ２個ずつのレジスタ（合計４個のレジスタ）に格納される。
【０００５】
［演算子］
当該中間積の計算には、加算演算（ＡＤＤ演算）、二倍算演算（ＳＷＡＰ演算）及びα倍算演算（ＳＨＩＦＴ演算）の演算子が用いられる。
【０００６】
加算演算（ＡＤＤ演算）では、２つの多項式にそれぞれ対応する係数系列間で有限体ＧＦ（３）上の加算演算を行う。この演算には、被演算子である各多項式の係数系列を格納するレジスタと、中間変数を格納するためのレジスタと、演算結果を格納するためのレジスタとを必要とする。
【０００７】
二倍算演算（ＳＷＡＰ演算）では、１つの多項式に対応する１つの係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍する。この演算は、各係数ｔｋ＝（（ｔｋ）Ｈｉ，（ｔｋ）Ｌｏ）の上位ビットと下位ビットとを入れ替えることによって実現できる。この演算には、被演算子である１つの多項式の係数系列を格納するレジスタと、演算結果を格納するためのレジスタとを必要とする。
【０００８】
α倍算演算（ＳＨＩＦＴ演算）では、１つの多項式に対応する１つの係数系列の各係数を１次数分だけ高次数側へシフトさせる。この演算には、被演算子である１つの多項式の係数系列を格納するレジスタと、演算結果を格納するためのレジスタとを必要とする。
【０００９】
［演算手順］
以上の３演算のうち、最も多くのレジスタを必要とする演算は加算演算（ＡＤＤ演算）である。例えば、ｍ＝９７，ｗ≦３１であり、各レジスタのビット長が６４である場合、被演算子である各多項式の係数系列を格納する４×２個のレジスタと、中間変数を格納するための１個のレジスタと（中間変数はレジスタ単位で取り扱われるため１つで足りる）、演算結果を格納するための４×１個のレジスタとの合計１３個のレジスタを必要とする。そのため、例えば、１６個の６４ビットのレジスタを備えたＣＰＵの場合、実行しようとする加算演算（ＡＤＤ演算）に関連しない多項式の係数系列（さらに４個のレジスタが必要）をレジスタに格納した状態で当該加算演算（ＡＤＤ演算）を実行することはできない。よって、この例においてレジスタに加算演算（ＡＤＤ演算）に関連しない多項式の係数系列が格納されていた場合、その係数系列をメインメモリに格納（セーブ）し、その係数系列をレジスタから削除した後、当該加算演算（ＡＤＤ演算）を実行しなければならない。そして、その後の別の演算においてメインメモリにセーブしたデータが必要になった場合には、メインメモリからそのデータをレジスタに読み込まなければならない（ロード）。
【００１０】
図１９は、ウィンドウ幅３の各中間積を計算するための一般的な演算手順を説明するための表である。まず、この表の表記方法について説明する。
【００１１】
図１９の表では各演算の内容を各行の要素によって表現している。「レジスタ上の元の数」は、各演算の際にレジスタに格納される多項式の係数系列数を示し、「ロード数」は、各演算の際にデータがメインメモリからレジスタにロードされる回数を示し、「中間積の状態」の欄は、各演算時における各中間積Ａ（α）・Ｗ（α）の係数系列の状態を示す。
【００１２】
ここで、「中間積の状態」の欄の「１０」「２０」「０１」「１１」「２１」「０２」…「２２２」は、各多項式Ｗ（α）＝ｔ０＋ｔ１・α＋ｔ２・α２の係数系列を表現している。すなわち、「１０」は多項式Ｗ（α）＝１を示し、「２０」は多項式Ｗ（α）＝２を示し、「０１」は多項式Ｗ（α）＝αを示し、「１１」は多項式Ｗ（α）＝１＋αを示し、「２１」は多項式Ｗ（α）＝２＋αを示し、「０２」は多項式Ｗ（α）＝２・αを示し、・・・、「２２２」は多項式Ｗ（α）＝２＋２・α＋２１・α２を示す。なお、図１９ではＷ（α）＝０の項目については記載を省略している。
【００１３】
また、「ＡＤＤ」はそれらの列の中間積Ａ（α）・Ｗ（α）の係数系列が加算演算（ＡＤＤ演算）の被演算子であることを示し、「ＳＷＡＰ」はその列の中間積Ａ（α）・Ｗ（α）が二倍算演算（ＳＷＡＰ演算）の被演算子であることを示し、「ＳＨＩＦＴ」はその列の中間積Ａ（α）・Ｗ（α）がα倍算演算（ＳＨＩＦＴ演算）の被演算子であることを示す。また、太枠で囲んだ欄は、その列の演算の演算結果（列に対応する「１１」等の係数系列）が当該演算終了時に格納される記憶領域（ｒはレジスタ、ｍはメインメモリ）を示す。
【００１４】
以下、図１９に沿って、ウィンドウ幅３の各中間積を計算するための一般的な演算手順を説明する。なお、前提として多項式Ａ（α）がメインメモリに格納されているとする。また、表記の都合上、Ａ（α）・Ｗ（α）をＷ（α）・Ａ（α）と示す。これらの積は可換でありＡ（α）・Ｗ（α）＝Ｗ（α）・Ａ（α）を満たす。
【００１５】
《「０」（０・Ａ（α））の計算》
０・Ａ（α）＝０であり、中間積を求めるために演算を行う必要がないため０をメインメモリに格納する。
【００１６】
《「１０」（１・Ａ（α））の計算》
１・Ａ（α）＝Ａ（α）であり、中間積を求めるために演算を行う必要がない。ここでは、以下の他の演算のため多項式Ａ（α）の係数系列をレジスタにロードする。
【００１７】
《「２０」（２・Ａ（α））の計算》
レジスタから読み込んだ多項式Ａ（α）の係数系列「１０」を被演算子とした二倍算演算（ＳＷＡＰ演算）を行い、その演算結果「２０」をレジスタに格納する。次に、その演算結果「２０」をメインメモリにセーブし、当該レジスタに格納された演算結果「２０」を削除する。
【００１８】
《「０１」（α・Ａ（α））の計算》
レジスタから読み込んだ多項式Ａ（α）の係数系列「１０」を被演算子としたα倍算演算（ＳＨＩＦＴ演算）を行い、その演算結果「０１」をレジスタに格納する。
【００１９】
《「１１」（（１＋α）・Ａ（α））の計算》
レジスタから読み込んだ多項式Ａ（α）の係数系列「１０」とα・Ａ（α）の係数系列「０１」とを被演算子とした加算演算（ＡＤＤ演算）を行い、その演算結果「１１」をレジスタに格納する。
【００２０】
《「２１」（（２＋α）・Ａ（α））の計算》
多項式α・Ａ（α）の係数系列「０１」をメインメモリにセーブし、それをレジスタから削除する。次に、レジスタから読み込んだ多項式Ａ（α）の係数系列「１０」と（１＋α）・Ａ（α）の係数系列「１１」とを被演算子とした加算演算（ＡＤＤ演算）を行い、その演算結果「２１」をレジスタに格納する。
【００２１】
《「０２」（２α・Ａ（α））の計算》
多項式α・Ａ（α）の係数系列「０１」をレジスタにロードし、係数系列「０１」を被演算子とした二倍算演算（ＳＷＡＰ演算）を行い、その演算結果「０２」をレジスタに格納する。次に、その演算結果「０２」をメインメモリにセーブし、当該レジスタに格納された演算結果「０２」を削除する。
【００２２】
《「１２」（（１＋２α）・Ａ（α））の計算》
レジスタから読み込んだ多項式（２＋α）・Ａ（α）の係数系列「２１」を被演算子とした二倍算演算（ＳＷＡＰ演算）を行い、その演算結果「１２」をレジスタに格納する。次に、その演算結果「１２」をメインメモリにセーブし、当該レジスタに格納された演算結果「１２」を削除する。
【００２３】
《「２２」（（２＋２α）・Ａ（α））の計算》
多項式（２＋α）・Ａ（α）の係数系列「２１」をメインメモリにセーブし、当該レジスタに格納された演算結果「２１」を削除する。次に、レジスタから読み込んだ多項式（１＋α）・Ａ（α）の係数系列「１１」を被演算子とした二倍算演算（ＳＷＡＰ演算）を行い、その演算結果「２２」をレジスタに格納する。
【００２４】
以降同様にＷ（α）の値が小さな方から順番に各中間積の係数系列「００１」〜「２２２」が算出される。
【非特許文献１】川原祐人、白勢政明、高木剛、岡本栄司、“ηＴペアリングの高速ソフトウェア実装”、２００７年  暗号と情報セキュリティシンポジウム、ＳＣＩＳ  ２００７、２Ｅ３−２、２００７．
【発明の開示】
【発明が解決しようとする課題】
【００２５】
しかし、上記の方法では、演算を行うために多項式の係数系列をレジスタに格納し、中間積を求めた後、レジスタに格納された係数系列を用いて他の中間積の係数系列を計算できる場合があるにもかかわらず、単に小さなＷ（α）から順番に各中間積の係数系列を求めていた。そのため、レジスタに格納された係数系列を有効に演算に利用することなく、それらをレジスタから削除し、再度その係数系列が必要になるとメインメモリからレジスタにロードするといった非効率な手順で演算がなされていた。その結果、従来の方法では、メインメモリからレジスタへのロード回数が多くなってしまうという問題が生じていた。このような問題は、上述で例示したウィンドウ幅、レジスタのビット長及びレジスタ数にかかわらず、小さなＷ（α）から順番に各中間積の係数系列を求める場合に共通する問題である。さらに、このような問題はウィンドウ法における中間積の算出過程のみならず、多項式間の乗算結果を利用して他の多項式間の乗算を行う多項式乗算に共通する問題である。
【００２６】
本発明はこのような点に鑑みてなされたものであり、多項式間の乗算結果を利用して他の多項式間の乗算を行う多項式乗算を、これまでよりも少ないロード回数で実現する技術を提供することを目的とする。
【課題を解決するための手段】
【００２７】
本発明では、まず、有限体ＧＦ（３）＝｛０，１，２｝の元を係数とする既約多項式をｆ（ｘ）とし、ｆ（α）＝０を満たす根をαとし、ｎを１以上の整数とした場合における、或る多項式Ａ（α）＝ｓ０＋ｓ１・α＋…＋ｓｎ−１・αｎ−１の係数系列ｓ０，ｓ１，…，ｓｎ−１∈ＧＦ（３）をレジスタに格納する。次に、或る整数ｉ≧２に対してＷ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ−１・αｉ−１（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３））で表現可能な０及び１を除くすべての多項式Ｗ（α）について、それぞれ、多項式Ｗ（α）・Ａ（α）の係数系列を生成する（第１過程）。次に、第１過程で生成された多項式αｉ−１・Ａ（α）又はαｉ−２・Ａ（α）の係数系列をレジスタから読み込み、当該係数系列の各係数を高次数側へシフトさせ、そのシフト結果である係数系列を、多項式αｉ・Ａ（α）の係数系列としてレジスタに格納する（第２過程）。
【００２８】
そして、多項式αｉ・Ａ（α）の係数系列を継続的にレジスタに保持した状態で、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ・αｉ（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３），ｔｉ＝１，２）で表現可能なαｉを除く多項式Ｗ（α）について、多項式Ｗ（α）・Ａ（α）の係数系列を算出するために、二倍算手段が、１つ前の過程で算出され、既にレジスタに格納されている１つの係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、当該１つの多項式の二倍算結果を示す多項式の係数系列としてレジスタに格納する二倍算過程と、加算手段が、第１過程で生成された何れか１つの多項式の係数系列又は多項式Ａ（α）の係数系列と、多項式αｉ・Ａ（α）の係数系列とをレジスタから読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式の係数系列としてレジスタに格納する加算過程と、を交互に実行する（第３過程）。
【００２９】
ここで、多項式αｉ・Ａ（α）の係数系列と、第１過程で生成された何れか１つの多項式の係数系列又は多項式Ａ（α）の係数系列とを被演算子とし、順次、上記の有限体ＧＦ（３）上での加算演算を行うことにより、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ−１・αｉ−１＋αｉ（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３））で表現可能なαｉを除くすべての多項式Ｗ（α）について、多項式Ｗ（α）・Ａ（α）の係数系列を算出する（加算過程）。つまり、多項式αｉ・Ａ（α）の係数系列は、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ−１・αｉ−１＋αｉで表現可能なαｉを除くすべての多項式Ｗ（α）について、多項式Ｗ（α）・Ａ（α）の係数系列を算出するために常に必要なものである。よって、これらの係数系列がすべて算出されるまで多項式αｉ・Ａ（α）の係数系列を継続的にレジスタに保持しておくことは、レジスタ資源を有効に利用することになる。これはロード回数の低減につながる。
【００３０】
また、多項式αｉ・Ａ（α）の係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍した係数系列は、多項式２αｉ・Ａ（α）の係数系列となる。さらに、加算過程で算出された各多項式Ｗ（α）・Ａ（α）の係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍した各係数系列は、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ−１・αｉ−１＋２αｉで表現可能な２αｉを除くすべての多項式Ｗ（α）に対する多項式Ｗ（α）・Ａ（α）の係数系列となる（二倍算過程）。本発明では、第２過程の終了時点でレジスタに格納されているか、又は、加算過程でレジスタに格納される係数系列を用いて二倍算過程を実行するため、二倍算過程のためのロードは不要である。また、二倍算過程と加算過程とを交互に実行することにより、直前の加算過程でレジスタに格納された係数系列を用いて二倍算過程を実行できる。これにより、レジスタ資源を有効利用し、ロード回数を削減できる。
【発明の効果】
【００３１】
本発明では、多項式間の乗算結果を利用して他の多項式間の乗算を行う多項式乗算を、これまでよりも少ないロード回数で実現できる。
【発明を実施するための最良の形態】
【００３２】
以下、本発明の実施の形態を図面を参照して説明する。
〔第１実施形態〕
＜構成＞
図１は、本形態の多項式演算装置１の構成を示すブロック図である。
図１に示すように、本形態の多項式演算装置１は、メインメモリ１０と、複数個のレジスタ２０と、演算部３０と、制御部（「制御手段」に相当）４０とを有する。ここで、メインメモリ１０は、ＲＡＭ（Random Access Memory）等の半導体記憶素子である。レジスタ２０は、ＣＰＵ（Central Processing Unit）内部の記憶素子である。本形態では、ビット長６４ビットのレジスタ２０を１６個備える構成を例示する。演算部３０は、ＣＰＵに所定のプログラムが読み込まれて構成される処理部であり、加算部（加算手段）３１と、ビット交換部（「二倍算手段」に相当）３２と、シフト演算部（「α倍算手段」に相当）とを有する。また、制御部４０は、ＣＰＵに所定のプログラムが読み込まれて構成され、多項式演算装置１の処理全体を制御する。
【００３３】
＜処理＞
本形態の多項式演算装置１は、或る整数ｉ≧２に対してＷ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ・αｉ（ｔ０，ｔ１，…，ｔｉ−１，ｔｉ∈ＧＦ（３））で表現可能な各多項式Ｗ（α）と、或る多項式Ａ（α）＝ｓ０＋ｓ１・α＋…＋ｓｎ−１・αｎ−１（ｓ０，ｓ１，…，ｓｎ−１∈ＧＦ（３））との乗算Ｗ（α）・Ａ（α）をそれぞれ実行する。
【００３４】
なお、αは、有限体ＧＦ（３）＝｛０，１，２｝の元を係数とする既約多項式をｆ（ｘ）とした場合にｆ（α）＝０を満たす根である。また、ｉは固定値であり、例えば、多項式演算装置１をウィンドウ法の中間積の算出に用いる場合には、２≦ｉ≦ｗ−１（ｗはウィンドウ幅）を満たす整数がｉとして設定される。また、ｎは１以上の整数であり、例えば、多項式演算装置１が拡大体ＧＦ（３ｍ）上の乗算の中間積を算出するために用いられる場合にはｎ＝ｍを満たすｎが設定される。
【００３５】
［被演算子の実装方法］
各多項式演算の被演算子となる各多項式ｔ０＋ｔ１・α＋…＋ｔｐ−１・αｐ−１（ｐは１以上の整数）は、係数系列ｔ０，ｔ１，…，ｔｐ−１∈ＧＦ（３）で表現され、各係数ｔｋ∈ＧＦ（３）（ｋは０以上ｐ−１の整数）はそれぞれｔｋ＝（（ｔｋ）Ｈｉ，（ｔｋ）Ｌｏ）（（ｔｋ）Ｈｉ，（ｔｋ）Ｌｏ∈ＧＦ（２））の２ビットで表現される。そして、それらの上位ビット系列（ｔ０）Ｈｉ，（ｔ１）Ｈｉ，…，（ｔｐ−１）Ｈｉと下位ビット系列（ｔ０）Ｈｉ，（ｔ１）Ｈｉ，…，（ｔｐ−１）Ｈｉとが、別個のレジスタに格納される。
【００３６】
図２は、多項式ｔ０＋ｔ１・α＋…＋ｔｐ−１・αｐ−１の係数系列ｔ０，ｔ１，…，ｔｐ−１∈ＧＦ（３）のレジスタへの実装方法を説明するための図である。図２では、ｐ＝９７、各レジスタのビット長６４の場合に、多項式０＋１・α＋２・α２＋…＋０・α６３＋２・α６４＋…＋２・α９６を４つのレジスタに格納した例である。ここで、Ｌｏは各係数ｔｋ∈ＧＦ（３）を２ビットで表現した場合の下位ビットを示し、Ｈｉは上位ビットを示す。
【００３７】
［加算部３１（加算手段）の演算内容］
加算部３１は、レジスタ２０から２つの多項式にそれぞれ対応する２つの係数系列を読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式の係数系列としてレジスタ２０に格納する。
【００３８】
図３は、加算部３１の演算過程でレジスタに格納されるデータを例示した図である。なお、図３の例は、Ｙ（α）＝０＋１・α＋２・α２＋…＋０・α６３＋２・α６４＋…＋２・α９６の係数系列０，１，２，…，０，２，…，２と、多項式Ｚ（α）＝２＋１・α＋１・α２＋…＋２・α６３＋２・α６４の係数系列２，１，１，…，２，２との間で、係数毎の有限体ＧＦ（３）上の加算演算を行う場合の例である。また、図３（ａ）は、一方の被演算子である多項式の係数系列０，１，２，…，０，２，…，２がレジスタに格納された様子を例示しており、図３（ｂ）は、他方の被演算子である多項式の係数系列２，１，１，…，２，２がレジスタに格納された様子を例示している。また、図３（ｃ）は、中間変数がレジスタに格納された様子を例示しており、図３（ｄ）は、演算結果がレジスタに格納された様子を例示している。
【００３９】
ここで、多項式Ｙ（α）の係数ｙｋ∈ＧＦ（３）を（（ｙｋ）Ｈｉ，（ｙｋ）Ｌｏ）∈ＧＦ（２）とし、多項式Ｚ（α）の係数ｚｋ∈ＧＦ（３）を（（ｚｋ）Ｈｉ，（ｚｋ）Ｌｏ）∈ＧＦ（２）とし、ｙｋ＋ｚｋ∈ＧＦ（３）を（（ｙｋ＋ｚｋ）Ｈｉ，（ｙｋ＋ｚｋ）Ｌｏ）∈ＧＦ（２）とすると、ｙｋ＋ｚｋ∈ＧＦ（３）は、例えば、以下のように計算できる。なお、｜は論理和演算子を示し、＾は排他的論理和演算子を示し、＆は論理積演算子を示し、τｋは中間変数を示す。
【００４０】
τｋ＝（（ｙｋ）Ｈｉ｜（ｙｋ）Ｌｏ）＆（（ｚｋ）Ｈｉ｜（ｚｋ）Ｌｏ）  …(1)
（ｙｋ＋ｚｋ）Ｈｉ＝τｋ＾（（ｙｋ）Ｈｉ｜（ｚｋ）Ｈｉ）  …(2)
（ｙｋ＋ｚｋ）Ｌｏ＝τｋ＾（（ｙｋ）Ｌｏ｜（ｚｋ）Ｌｏ）  …(3)
加算部３１は、これらの各演算をレジスタ長単位で各ビットについて実行する。また、便宜上、図３（ｃ）には各中間変数τｋを格納するレジスタとして２つのレジスタを示しているが、中間変数の計算はレジスタ長単位で実行されるため、実際には１つのレジスタのみが用いられる。
【００４１】
［ビット交換部３２（二倍算手段）の演算内容］
ビット交換部３２は、レジスタ２０から１つの多項式に対応する１つの係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、当該１つの多項式の二倍算結果を示す多項式の係数系列としてレジスタ２０に格納する。
【００４２】
図４は、ビット交換部３２の演算過程でレジスタに格納されるデータを例示した図である。なお、図４は、Ｙ（α）＝０＋１・α＋２・α２＋…＋０・α６３＋２・α６４＋…＋２・α９６の係数系列０，１，２，…，０，２，…，２を被演算子とした例である。また、図４（ａ）は、被演算子である多項式の係数系列０，１，２，…，０，２，…，２がレジスタに格納された様子を例示しており、図４（ｂ）は、演算結果がレジスタに格納された様子を例示している。
【００４３】
ここで、多項式Ｙ（α）の係数ｙｋ∈ＧＦ（３）を（（ｙｋ）Ｈｉ，（ｙｋ）Ｌｏ）∈ＧＦ（２）とすると、係数ｙｋ∈ＧＦ（３）の２倍算は、（（ｙｋ）Ｈｉ，（ｙｋ）Ｌｏ）∈ＧＦ（２）のビットを（（ｙｋ）Ｌｏ，（ｙｋ）Ｈｉ）∈ＧＦ（２）と入れ替えることにより計算できる。ビット交換部３２は、このビットの入れ替えをレジスタ長単位で各ビットについて実行する。
【００４４】
［シフト交換部３３（α倍算手段）の演算内容］
シフト交換部３３は、レジスタ２０から１つの多項式に対応する１つの係数系列を読み込み、当該係数系列の各係数を１次数分だけ高次数側へシフトさせ、そのシフト結果である係数系列を、当該１つの多項式のα倍算結果を示す多項式の係数系列としてレジスタ２０に格納する。
【００４５】
図５は、シフト交換部３３の演算過程でレジスタに格納されるデータを例示した図である。なお、図４は、Ｙ（α）＝０＋１・α＋２・α２＋…＋０・α６３＋２・α６４＋…＋２・α９６の係数系列０，１，２，…，０，２，…，２を被演算子とした例である。また、図５（ａ）は、被演算子である多項式の係数系列０，１，２，…，０，２，…，２がレジスタに格納された様子を例示しており、図５（ｂ）は、演算結果がレジスタに格納された様子を例示している。
【００４６】
このシフト演算により、被演算子である多項式の係数系列の各係数に対応する次数がそれぞれ１次数分大きくなり、多項式のα倍算結果を示す多項式の係数系列が算出される。
【００４７】
［制御部４０（制御手段）の制御内容］
制御部４０（制御手段）は、処理に必要なデータがレジスタ２０に格納されていない場合に、当該処理に必要なデータをメインメモリ１０からレジスタ２０に読み込む処理と、処理に必要な領域がレジスタ２０に確保できない場合にレジスタから何れかのデータを削除する処理と、加算部３１（加算手段）の処理と、ビット交換部３２（二倍算手段）の処理と、シフト演算部３３（α倍算手段）の処理とを制御し、前述の或る整数ｉ≧２に対してＷ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ・αｉ（ｔ０，ｔ１，…，ｔｉ∈ＧＦ（３））で表現可能な多項式Ｗ（α）について、それぞれ、多項式Ｗ（α）とＡ（α）との乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列を算出させる。以下、乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明する。なお、以下では、説明の簡略化のため、ｉ＝２の場合を例にとって説明を行う。しかし、これをｉ≧３の場合に拡張することは容易である。また、この例では、ステップＳ１〜Ｓ１５が「第１過程」に相当し、ステップＳ１６〜１８が「第２過程」に相当し、ステップＳ１９からＳ５３までが「第３過程」に相当する。
【００４８】
図６から図１３は、本形態の多項式Ｗ（α）とＡ（α）との乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明するためのフローチャートである。なお、これらの図では、レジスタに格納されているデータの内容を各ステップの欄外に表記した。図１４は、本形態の多項式Ｗ（α）とＡ（α）との乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明するための表である。なお、この表の表記方法は前述の図１９と同じである。
【００４９】
以下、これらの図を用い、制御部４０（制御手段）の制御のもので実行される多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明する。
【００５０】
≪第１過程≫
まず、制御部４０が、多項式Ａ（α）＝ｓ０＋ｓ１・α＋…＋ｓｎ−１・αｎ−１の係数系列ｓ０，ｓ１，…，ｓｎ−１∈ＧＦ（３）と０とをメインメモリ１０に格納する（ステップＳ１）。なお、係数系列ｓ０，ｓ１，…，ｓｎ−１∈ＧＦ（３）は、Ｗ（α）＝１の場合の多項式Ｗ（α）・Ａ（α）の係数系列であり、０は、Ｗ（α）＝０の場合の多項式Ｗ（α）・Ａ（α）の係数系列である。
【００５１】
次に、制御部４０が、メインメモリ１０から多項式Ａ（α）の係数系列ｓ０，ｓ１，…，ｓｎ−１∈ＧＦ（３）をレジスタ２０に読み込む（ロード）（ステップＳ２）。次に、ビット交換部３２が、レジスタ２０から多項式Ａ（α）の係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し（SWAP）、それらの演算結果からなる係数系列を、多項式２・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ３／第４過程）。次に、制御部４０が、レジスタ２０の多項式２・Ａ（α）の係数系列をメインメモリ１０に書き込み（セーブ）、レジスタ２０から多項式２・Ａ（α）の係数系列を削除する（ステップＳ４）。
【００５２】
次に、シフト演算部３３が、レジスタ２０から多項式Ａ（α）の係数系列を読み込み、当該係数系列の各係数を１次数分だけ高次数側へシフトさせ（SHIFT）、そのシフト結果である係数系列を、多項式α・Ａ（ α ）の係数系列としてレジスタ２０に格納する（ステップＳ５／第５過程）。
【００５３】
次に、ビット交換部３２が、レジスタ２０から多項式α・Ａ（α）の係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍（SWAP）し、それらの演算結果からなる係数系列を、多項式２α・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ６／第６過程）。次に、制御部４０が、レジスタ２０の多項式２α・Ａ（α）の係数系列をメインメモリ１０に書き込み（セーブ）、レジスタ２０から多項式２α・Ａ（α）の係数系列を削除する（ステップＳ７）。
【００５４】
次に、加算部３１が、レジスタ２０から多項式Ａ（α）の係数系列と多項式α・Ａ（α）の係数系列とを読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算（ADD）を行い、それらの演算結果からなる係数系列を、多項式（１＋α）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ８／第７過程）。次に、制御部４０が、レジスタ２０の多項式α・Ａ（α）の係数系列をメインメモリ１０に書き込み（セーブ）、レジスタ２０から多項式α・Ａ（α）の係数系列を削除する（ステップＳ９）。
【００５５】
次に、加算部３１が、レジスタ２０から多項式Ａ（α）の係数系列と多項式（１＋α）・Ａ（α）の係数系列とを読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算（ADD）を行い、それらの演算結果からなる係数系列を、多項式（２＋α）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ１０／第８過程）。次に、制御部４０が、レジスタ２０から多項式Ａ（α）の係数系列を削除する（ステップＳ１１）。
【００５６】
次に、ビット交換部３２が、レジスタ２０から多項式（１＋α）・Ａ（α）の係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍（SWAP）し、それらの演算結果からなる係数系列を、多項式（２＋２α）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ１２／第９過程）。次に、制御部４０が、レジスタ２０の多項式（１＋α）・Ａ（α）及び（２＋２α）・Ａ（α）の係数系列をメインメモリ１０に書き込み（セーブ）、レジスタ２０から多項式（１＋α）・Ａ（α）及び（２＋２α）・Ａ（α）の係数系列を削除する（ステップＳ１３）。
【００５７】
次に、ビット交換部３２が、レジスタ２０から多項式（２＋α）・Ａ（α）の係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、多項式（１＋２α）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ１４／第１０過程）。次に、制御部４０が、レジスタの多項式（２＋α）・Ａ（α）及び（１＋２α）・Ａ（α）の係数系列をメインメモリに書き込み（セーブ）、レジスタから多項式（２＋α）・Ａ（α）及び（１＋２α）・Ａ（α）の係数系列を削除する（ステップＳ１５）。
【００５８】
ここまでの処理により、ｉ＝２の場合においてＷ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ−１・αｉ−１（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３））で表現可能な０及び１を除くすべての多項式Ｗ（α）について、それぞれ、多項式Ｗ（α）・Ａ（α）の係数系列が生成され。
【００５９】
≪第２過程≫
次に、制御部４０が、メインメモリ１０から多項式α・Ａ（α）の係数系列をレジスタ２０に読み込む（ロード）（ステップＳ１６）。次に、シフト演算部３３が、レジスタ２０から多項式α ・Ａ（α）の係数系列を読み込み、当該係数系列の各係数を１次数分だけ高次数側へシフトさせ（SHIFT） 、そのシフト結果である係数系列を、多項式α２・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ１７）。これにより、ｉ＝２の場合における多項式αｉ・Ａ（α）の係数系列が生成された。次に、制御部４０が、レジスタ２０から多項式α・Ａ（α）の係数系列を削除する（ステップＳ１８）。
【００６０】
≪第３過程≫
以下では、ｉ＝２の場合における多項式αｉ・Ａ（α）の係数系列を継続的にレジスタ２０に保持した状態で、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ・αｉ（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３），ｔｉ＝１，２）で表現可能なαｉを除くすべての多項式Ｗ（α）について、多項式Ｗ（α）・Ａ（α）の係数系列が算出されるまで、（ａ）ビット交換部３２が、１つ前の過程で算出され、既にレジスタ２０に格納されている１つの係数系列を読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し、それらの演算結果からなる係数系列を、当該１つの多項式の二倍算結果を示す多項式の係数系列としてレジスタ２０に格納する二倍算過程と、（ｂ）加算部３１が、第１過程で生成された何れか１つの多項式の係数系列又は多項式Ａ（α）の係数系列と、多項式αｉ・Ａ（α）の係数系列とをレジスタ２０から読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式の係数系列としてレジスタ２０に格納する加算過程と、が交互実行される。
【００６１】
まず、ビット交換部３２が、多項式α２・Ａ（α）の係数系列をレジスタ２０から読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し（SWAP） 、それらの演算結果からなる係数系列を、当該読み込んだ多項式α２・Ａ（α）の二倍算結果を示す多項式２α２・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ１９）。次に、制御部４０が、レジスタ２０の多項式２α２・Ａ（α）の係数系列をメインメモリ１０に書き込み（セーブ）、レジスタ２０から多項式２α２・Ａ（α）の係数系列を削除する（ステップＳ２０）。
【００６２】
次に、制御部４０が、メインメモリ１０から多項式Ａ（α）の係数系列をレジスタ２０に読み込む（ロード）（ステップＳ２１）。次に、加算部３１が、多項式Ａ（α）の係数系列と、多項式α２・Ａ（α）の係数系列とをレジスタ２０から読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算（ADD）を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式（１＋α２）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ２２）。次に、制御部４０が、レジスタ２０から多項式Ａ（α）の係数系列を削除する（ステップＳ２３）。
【００６３】
次に、ビット交換部３２が、多項式（１＋α２）・Ａ（α）の係数系列をレジスタ２０から読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し（SWAP）、それらの演算結果からなる係数系列を、当該読み込んだ多項式（１＋α２）・Ａ（α）の二倍算結果を示す多項式（２＋２α２）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ２４）。 次に、制御部４０が、レジスタ２０の多項式（２＋２α２ ）・Ａ（α）及び（１＋α２）・Ａ（α）の係数系列をメインメモリ１０に書き込み（セーブ）、レジスタ２０から多項式（２＋２α２）・Ａ（α）及び（１＋α２）・Ａ（α）の係数系列を削除する（ステップＳ２５）。
【００６４】
次に、制御部４０が、メインメモリ１０から多項式２・Ａ（α）の係数系列をレジスタ２０に読み込む（ロード）（ステップＳ２６）。次に、加算部３１が、多項式２・Ａ（α）の係数系列と、多項式α２・Ａ（α）の係数系列とをレジスタ２０から読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算（ADD）を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式（２＋α２）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ２７）。次に、制御部４０が、レジスタ２０から多項式２・Ａ（α）の係数系列を削除する（ステップＳ２８）。
【００６５】
次に、ビット交換部３２が、多項式（２＋α２）・Ａ（α）の係数系列をレジスタ２０から読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し（SWAP） 、それらの演算結果からなる係数系列を、当該読み込んだ多項式（２＋α２） ・Ａ（α）の二倍算結果を示す多項式（１＋２α２）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ２９）。次に、制御部４０が、レジスタ２０の多項式（２＋α２）・Ａ（α）及び（１＋２α２ ）・Ａ（α）の係数系列をメインメモリに書き込み（セーブ）、レジスタ２０から多項式（２＋α２）・Ａ（α）及び（１＋２α２）・Ａ（α）の係数系列を削除する（ステップＳ３０）。
【００６６】
次に、制御部４０が、多項式α ・Ａ（α）の係数系列をレジスタ２０に読み込む（ロード）（ステップＳ３１）。次に、加算部３１が、多項式α ・Ａ（α）の係数系列と、多項式α２・Ａ（α）の係数系列とをレジスタ２０から読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算（ADD）を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式（α＋α２）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ３２）。次に、制御部４０が、レジスタ２０から多項式α・Ａ（α）の係数系列を削除する（ステップＳ３３）。
【００６７】
次に、ビット交換部３２が、多項式（α ＋α２）・Ａ（α）の係数系列をレジスタ２０から読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し（SWAP） 、それらの演算結果からなる係数系列を、当該読み込んだ多項式（α＋α２）・Ａ（α）の二倍算結果を示す多項式（２＋２α２）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ３４）。次に、制御部４０が、レジスタ２０の多項式（α＋α２）・Ａ（α）及び（２＋２α２）・Ａ（α）の係数系列をメインメモリ１０に書き込み（セーブ）、レジスタ２０から多項式（α＋α２）・Ａ（α）及び（２＋２α２）・Ａ（α）の係数系列を削除する（ステップＳ３５）。
【００６８】
次に、制御部４０が、メインメモリ１０から多項式（１＋α）・Ａ（α）の係数系列をレジスタに読み込む（ロード）（ステップＳ３６）。次に、加算部３１が、多項式（１＋α） ・Ａ（α）の係数系列と、多項式α２・Ａ（α）の係数系列とをレジスタ２０から読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算（ADD）を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式（１＋α＋α２）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ３７）。次に、制御部４０が、レジスタ２０から多項式（１＋α）・Ａ（α）の係数系列を削除する（ステップＳ３８）。 
【００６９】
次に、ビット交換部３２が、多項式（１＋α＋α２）・Ａ（α）の係数系列をレジスタ２０から読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し（SWAP） 、それらの演算結果からなる係数系列を、当該読み込んだ多項式（１＋α＋α２）・Ａ（α）の二倍算結果を示す多項式（２＋２α＋２α２）・Ａ（α）の係数系列としてレジスタ２０に格納 する（ステップＳ３９）。次に、制御部４０が、レジスタの多項式（１＋α＋α２）・Ａ（α）及び（２＋２α＋２α２）・Ａ（α）の係数系列をメインメモリに書き込み（セーブ）、レジスタから多項式（１＋α＋α２）・Ａ（α）及び（２＋２α＋２α２）・Ａ（α）の係数系列を削除する（ステップＳ４０）。
【００７０】
次に、制御部４０が、メインメモリ１０から多項式（２＋α）・Ａ（α）の係数系列をレジスタ２０に読み込む（ロード）（ステップＳ４１）。次に、加算部３１が、多項式（２＋α）・Ａ（α）の係数系列と、多項式α２・Ａ（α）の係数系列とをレジスタ２０から読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算（ADD）を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式（２＋α＋α２）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ４２）。次に、制御部４０が、レジスタ２０から多項式（２＋α）・Ａ（α）の係数系列を削除する（ステップＳ４３）。
【００７１】
次に、ビット交換部３２が、多項式（２＋α＋α２）・Ａ（α）の係数系列をレジスタ２０から読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し（SWAP）、それらの演算結果からなる係数系列を、当該読み込んだ多項式（２＋α＋α２）・Ａ（α）の二倍算結果を示す多項式（１＋２α＋２α２）・Ａ（α）の係数系列としてレジスタ２０に格納 する（ステップＳ４４）。次に、制御部４０が、レジスタ２０の多項式（２＋α＋α２）・Ａ（α）及び（１＋２α＋２α２）・Ａ（α）の係数系列をメインメモリ１０に書き込み（セーブ）、レジスタ２０から多項式（２＋α＋α２）・Ａ（α）及び（１＋２α＋２α２）・Ａ（α）の係数系列を削除する（ステップＳ４５）。
【００７２】
次に、制御部４０が、メインメモリ１０から多項式２α・Ａ（α）の係数系列をレジスタ２０に読み込む（ロード）（ステップＳ４６）。次に、加算部３１が、多項式２α・Ａ（α）の係数系列と、多項式α２・Ａ（α）の係数系列とをレジスタ２０から読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算（ADD）を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式（２α＋α２）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ４７）。次に、制御部４０が、レジスタ２０から多項式２α・Ａ（α）の係数系列を削除する（ステップＳ４８）。
【００７３】
次に、ビット交換部３２が、多項式（２α＋α２）・Ａ（α）の係数系列をレジスタ２０から読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し（SWAP）、それらの演算結果からなる係数系列を、当該読み込んだ多項式（２α＋α２）・Ａ（α）の二倍算結果を示す多項式（α＋２α２）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ４９）。次に、制御部４０が、レジスタ２０の多項式（２α＋α２）・Ａ（α）及び（α＋２α２）・Ａ（α）の係数系列をメインメモリ１０に書き込み（セーブ）、レジスタ２０から多項式（２α＋α２）・Ａ（α）及び（α＋２α２）・Ａ（α）の係数系列を削除する（ステップＳ５０）。
【００７４】
次に、制御部４０が、メインメモリ１０から多項式（１＋２α）・Ａ（α）の係数系列をレジスタ２０に読み込む（ロード）（ステップＳ５１）。次に、加算部３１が、多項式（１＋２α）・Ａ（α）の係数系列と、多項式α２・Ａ（α）の係数系列とをレジスタ２０から読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算（ADD）を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式（１＋２α＋α２）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ５２）。制御部４０が、レジスタ２０から多項式（１＋２α）・Ａ（α）の係数系列を削除する（ステップＳ５３）。
【００７５】
次に、ビット交換部３２が、多項式（１＋２α＋α２）・Ａ（α）の係数系列をレジスタ２０から読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し（SWAP） 、それらの演算結果からなる係数系列を、当該読み込んだ多項式（１＋２α＋α２）・Ａ（α）の二倍算結果を示す多項式（２＋α＋２α２）・Ａ（α）の係数系列としてレジスタ２０に格納 する（ステップＳ５４）。次に、制御部４０が、レジスタ２０の多項式（１＋２α＋α２）・Ａ（α）及び（２＋α＋２α２）・Ａ（α）の係数系列をメインメモリ１０に書き込み（セーブ）、レジスタ２０から多項式（１＋２α＋α２）・Ａ（α）及び（２＋α＋２α２）・Ａ（α）の係数系列を削除する（ステップＳ５５）。
【００７６】
制御部４０が、メインメモリ１０から多項式（２＋２α）・Ａ（α）の係数系列をレジスタ２０に読み込む（ロード）（ステップＳ５６）。次に、加算部３１が、多項式（２＋２α）・Ａ（α）の係数系列と、多項式α２・Ａ（α）の係数系列とをレジスタ２０から読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算（ADD）を行い、それらの演算結果からなる係数系列を、当該２つの多項式の加算結果を示す多項式（２＋２α＋α２）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ５７）。制御部４０が、レジスタ２０から多項式（２＋２α）・Ａ（α）の係数系列を削除する（ステップＳ５８）。
【００７７】
次に、ビット交換部３２が、多項式（２＋２α＋α２）・Ａ（α）の係数系列をレジスタ２０から読み込み、当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍し（SWAP） 、それらの演算結果からなる係数系列を、当該読み込んだ多項式（２＋２α＋α２）・Ａ（α）の二倍算結果を示す多項式（１＋α＋２α２）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ５９）。次に、制御部４０が、レジスタ２０の多項式α２・Ａ（α）、（２＋２α＋α２）・Ａ（α）及び（１＋α＋２α２）・Ａ（α）の係数系列をメインメモリ１０に書き込み（セーブ）、レジスタ２０から多項式α２・Ａ（α）、（２＋２α＋α２）・Ａ（α）及び（１＋α＋２α２）・Ａ（α）の係数系列を削除する（ステップＳ６０）。
【００７８】
＜本形態の特徴＞
本形態では、ステップＳ１９からＳ６０までの第３過程において、多項式α２・Ａ（α）の係数系列を継続的にレジスタ２０に保持することとした。この係数系列は、第３過程の各加算過程で必ず必要となるものであり、これらの係数系列がすべて算出されるまで多項式αｉ・Ａ（α）の係数系列を継続的にレジスタに保持しておくことは、レジスタ資源を有効に利用することになる。そして、第３過程において多項式α２・Ａ（α）の係数系列をロードする必要がないため、従来よりもロード回数を削減できる。
【００７９】
また、多項式α２・Ａ（α）の係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍した係数系列は、多項式２α２・Ａ（α）の係数系列となる。さらに、加算過程で算出された各多項式Ｗ（α）・Ａ（α）の係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍した各係数系列は、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔ１・α１＋２α２で表現可能な２α２を除くすべての多項式Ｗ（α）に対する多項式Ｗ（α）・Ａ（α）の係数系列となる（二倍算過程）。本形態では、第２過程の終了時点でレジスタ２０に格納されているか、又は、各加算過程でレジスタ２０に格納される係数系列を用いて二倍算過程を実行するため、二倍算過程のためのロードは不要である。また、二倍算過程と加算過程とを交互に実行することにより、直前の加算過程でレジスタ２０に格納された係数系列を用いて二倍算過程を実行できる。これにより、レジスタ資源を有効利用し、ロード回数を削減できる。
【００８０】
以上の工夫により、本形態では従来よりもロード数を削減できる。具体的には、６４ビットのレジスタを１６個使用し、Ｗ（α）＝ｔ０＋ｔ１・α＋ｔ２・α２（ｔ０，ｔ１，ｔ２∈ＧＦ（３））で表現可能なすべてのＷ（α）に対するＷ（α）・Ａ（α）を行う場合のロード数を従来の１８から１０に削減することができる（図１４，１５参照）。これをｉについて一般化すると、従来の方法では、
【００８１】
【数１】
0004612698.tif 000002
回のロードが必要であったのに対し、本形態では、
【数２】
0004612698.tif 000003
回のロードで足りる。
【００８２】
また、本形態では、ステップＳ５（第５過程）のシフト演算（SHIFT）の次に、多くのレジスタを必要とするステップＳ８（第７過程）の加算演算(ADD)ではなく、ステップＳ５（第５過程）でレジスタに格納されたデータを用いて計算可能なステップＳ６（第６過程）の二倍算（SWAP）を行い、ステップＳ６（第６過程）の演算結果をメインメモリにセーブした後、ステップＳ８（第７過程）の加算演算(ADD)を行うこととした。これにより、多くのレジスタを必要とするステップＳ８（第７過程）の加算演算(ADD)に必要なデータの記憶領域を確保するためにレジスタのデータを削除し、ステップＳ５（第５過程）の演算を行うために新たにデータをレジスタにロードする必要がなくなる。その結果、ロード数を削減できる。
【００８３】
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の実施の形態では、ステップＳ５（第５過程）の次にステップＳ６（第６過程）が実行され、ステップＳ６（第６過程）の次にステップＳ８（第７過程）が実行され、ステップＳ８（第７過程）の次にステップＳ１０（第８過程）が実行され、ステップＳ１０（第８過程）の次にステップＳ１２（第９過程）が実行され、ステップＳ１２（第９過程）の次にステップＳ１４（第１０過程）が実行されることとした。しかし、ステップＳ５（第５過程）の次にステップＳ６（第６過程）が実行され、ステップＳ６（第６過程）の次にステップＳ８（第７過程）が実行され、ステップＳ８（第７過程）の次にステップＳ１２（第９過程）が実行され、ステップＳ１２（第９過程）の次にステップＳ１０（第８過程）が実行され、ステップＳ１０（第８過程）の次にステップＳ１４（第１０過程）が実行されてもよい。
【００８４】
また、上記の実施形態では、多項式αｉ・Ａ（α）の係数系列を継続的にレジスタに保持した状態で、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ・αｉ（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３），ｔｉ＝１，２）で表現可能なαｉを除くすべての多項式Ｗ（α）について、多項式Ｗ（α）・Ａ（α）の係数系列が算出されるまで、二倍算過程と加算過程とを交互に実行した（ステップＳ１９〜Ｓ６０）。しかし、ステップＳ１９〜Ｓ６０の一部において二倍算過程と加算過程とが交互に繰り返されないこととしてもよい。
【００８５】
また、上記の実施形態では、ｉ＝２の場合を例示したが、ｉ≧３として本発明を実施してもよい。また、レジスタのビット長、レジスタ数も上述の実施形態に限定されない。その場合であっても、上述した本発明の特徴によってロード数を削減できる。
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００８６】
〔第２実施形態〕
次に、本発明の第２実施形態を説明する。本形態は、第１実施形態の変形例である。
【００８７】
本形態では、レジスタから１つの多項式に対応する１つの係数系列を読み込み、さらに、他の１つの多項式に対応する１つの係数系列を当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍した係数系列に変換して読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、当該１つの多項式と当該他の多項式の二倍算結果との加算結果を示す多項式の係数系列としてレジスタに格納する二倍算加算手段を追加する。さらに本形態では、レジスタから１つの多項式に対応する１つの係数系列を読み込み、当該係数系列の各係数を２次数分だけ高次数側へシフトさせ、そのシフト結果である係数系列を、当該１つの多項式のα２倍算結果を示す多項式の係数系列としてレジスタに格納するα２倍算手段を追加する。これによって、ロード回数をさらに削減する。以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する部分については説明を省略する。
【００８８】
＜構成＞
図１を利用し、第１実施形態との相違点を説明する。なお、図１において点線で示したブロックが、本形態で追加される構成である。
【００８９】
図１に示すように、本形態の多項式演算装置１は、第１実施形態の構成に、さらにビット交換加算部１３２（二倍算加算手段）と２シフト演算部１３３（α２倍算手段）とが追加された構成である。これらも制御部４０によって制御される。
【００９０】
［ビット交換加算部１３２（二倍算加算手段）の演算内容］
ビット交換加算部１３２は、レジスタ２０から１つの多項式に対応する１つの係数系列を読み込み、さらに、他の１つの多項式に対応する１つの係数系列を当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍した係数系列に変換して読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、当該１つの多項式と当該他の多項式の二倍算結果との加算結果を示す多項式の係数系列としてレジスタ２０に格納する。
【００９１】
ビット交換加算部１３２の加算部３１との相違点は、レジスタ２０から読み込んだ１つの多項式に対応する１つの係数系列を示す“Ｌｏ”と“Ｈｉ”のビット列（図３等参照）を違いに入れ替えて有限体ＧＦ（３）上の加算演算の被演算子とする点である。このビット列の入れ替えは当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍することと等価である。なお、他方の被演算子である１つの多項式に対応する１つの係数系列についてはビット列の入れ替えを行わない。そして、係数系列を示す“Ｌｏ”と“Ｈｉ” のビット列が入れ替えられたビット列と、係数系列が入れ替えられていないビット列との間で、加算部３１と同様な処理を実行する。なお、係数系列を示す“Ｌｏ”と“Ｈｉ”のビット列を入れ替えたビット列を別のレジスタ２０に格納する必要はなく、ビット交換加算部１３２が“Ｌｏ”と“Ｈｉ”のビット列を入れ替えて読み込めばよいだけである（係数系列を当該係数系列の各係数を有限体ＧＦ（３）上でそれぞれ２倍した係数系列に変換して読み込む）。これにより、ビット交換加算部１３２は、一方の多項式を２倍し、他方の多項式と加算した加算結果である多項式の係数系列を算出する。
【００９２】
［２シフト演算部１３３（α２倍算手段）の演算内容］
２シフト演算部１３３は、レジスタ２０から１つの多項式に対応する１つの係数系列を読み込み、当該係数系列の各係数を２次数分だけ高次数側へシフトさせ、そのシフト結果である係数系列を、当該１つの多項式のα２倍算結果を示す多項式の係数系列としてレジスタ２０に格納する。
【００９３】
このシフト演算により、被演算子である多項式の係数系列の各係数に対応する次数がそれぞれ２次数分大きくなり、当該多項式のα２倍算結果を示す多項式の係数系列が算出される。
【００９４】
＜処理＞
次に、本形態の処理を説明する。以下では、第１実施形態との相違点を中心に説明する。
【００９５】
図１５から図１７は、第２実施形態の多項式Ｗ（α）・Ａ（α）係数系列の算出過程の第１実施形態との相違点を説明するためのフローチャートである。なお、これらの図でも、レジスタに格納されているデータの内容を各ステップの欄外に表記した。また、これらの図において第１実施形態と共通する過程については第１実施形態と同じ番号を付した。図１８は、本形態の多項式Ｗ（α）とＡ（α）との乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明するための表である。なお、この表の表記方法は前述の図１９と同じである。
【００９６】
以下、これらの図を用い、制御部４０（制御手段）の制御のもので実行される多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明する。なお、本形態はｉ＝２の例である。
【００９７】
≪第１過程≫
第２実施形態では、多項式αｉ−２・Ａ（α）の係数系列を継続的にレジスタに保持した状態で、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ−１・αｉ−１（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３））で表現可能な０及び１を除くすべての多項式Ｗ（α）について、それぞれ、多項式Ｗ（α）・Ａ（α）の係数系列を生成する。
【００９８】
まず、第１実施形態のステップＳ１〜Ｓ１０と同じ処理を実行する。しかし、第１実施形態のステップＳ１１は実行せず、レジスタ２０に多項式Ａ（α）の係数系列を保持しておく。
【００９９】
次に、第１実施形態のステップＳ１２〜Ｓ１５と同じ処理を実行する。これらの処理は、多項式Ａ（α）の係数系列を継続的にレジスタ２０に保持した状態で実行される。
【０１００】
ここまでの処理により、ｉ＝２の場合においてＷ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ−１・αｉ−１（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３））で表現可能な０及び１を除くすべての多項式Ｗ（α）について、それぞれ、多項式Ｗ（α）・Ａ（α）の係数系列が生成された。
【０１０１】
≪第２過程≫
次に、第１実施形態のステップＳ１６，Ｓ１７の代わりに、２シフト演算部１３３が、レジスタ２０から多項式Ａ（α）の係数系列を読み込み、当該係数系列の各係数を２次数分だけ高次数側へシフトさせ（2SHIFT） 、そのシフト結果である係数系列を、多項式α２ ・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ１１７）。次に、第１実施形態のステップＳ１８は実行せず、レジスタ２０に多項式Ａ（α）の係数系列を保持しておく。
【０１０２】
≪第３過程≫
次に、第１実施形態のステップＳ１９，Ｓ２０が実行され、ステップＳ２１が実行されることなくステップＳ２２が実行され、ステップＳ２３が実行されることなく、ステップＳ２４，Ｓ２５が実行される。ここまでの処理も、多項式Ａ（α）の係数系列を継続的にレジスタ２０に保持した状態で実行される。
【０１０３】
次に、ビット交換加算部１３２が、多項式Ａ（α）の係数系列を多項式２・Ａ（α）の係数系列に変換してレジスタ２０から読み込み、多項式α２・Ａ（α）の係数系列をレジスタ２０から読み込み（“Ｌｏ”と“Ｈｉ”のビット列を入れ替えて読み込み）、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算（S-ADD）を行い、それらの演算結果からなる係数系列を、当該読み込んだ２つの多項式の加算結果を示す多項式（２＋α２）・Ａ（α）の係数系列としてレジスタ２０に格納する（ステップＳ１２７）。
【０１０４】
次に、制御部４０が、レジスタ２０の多項式Ａ（α）の係数系列をメインメモリ１０に書き込み（セーブ）、レジスタ２０から多項式Ａ（α）の係数系列を削除する（ステップＳ１２８）。その後、第１実施形態と同じステップＳ２９〜Ｓ６０の処理が実行される。
【０１０５】
＜本形態の特徴＞
本形態では、ｉ＝２の場合において、多項式αｉ−２・Ａ（α）の係数系列を継続的にレジスタに保持した状態で、Ｗ（α）＝ｔ０＋ｔ１・α＋…＋ｔｉ−１・αｉ−１（ｔ０，ｔ１，…，ｔｉ−１∈ＧＦ（３））で表現可能な０及び１を除くすべての多項式Ｗ（α）について、それぞれ、多項式Ｗ（α）・Ａ（α）の係数系列を生成し（第１過程）、２シフト演算によって多項式αｉ・Ａ（α）の係数系列を生成する（第２過程）こととした。これにより、最初に多項式αｉ−２・Ａ（α）をレジスタ２０にロードした以降は、第１過程及び第２過程においてロードは不要となる。
【０１０６】
また、本形態では、第３過程において、ビット交換加算部１３２（二倍算加算手段）が、多項式αｉ・Ａ（α）の係数系列をレジスタ２０から読み込み、さらに、多項式αｉ−２・Ａ（α）の係数系列を多項式２αｉ−２・Ａ（α）の係数系列に変換して読み込み、これらの同一の次数に対応する係数間でそれぞれ有限体ＧＦ（３）上の加算演算を行い、それらの演算結果からなる係数系列を、多項式（２αｉ−２＋αｉ）・Ａ（α）の係数系列としてレジスタ２０に格納する二倍算加算過程（ステップＳ１２７）を実行し、少なくとも第１過程から二倍算加算過程までを、多項式αｉ−２・Ａ（α）の係数系列を継続的にレジスタ２０に保持した状態で実行することとした。
これらにより、第１実施形態よりもロード回数を削減できる。
【０１０７】
なお、本発明は上述の実施の形態に限定されるものではない。例えば、第３過程において二倍算加算過程（ステップＳ１２７）を実行するのではなく、第１実施形態と同様な第３過程を実行してもよい。
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１０８】
〔プログラム・記録媒体〕
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１０９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１１０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。
また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【０１１３】
例えば、本発明を拡大体ＧＦ（３ｍ）上での乗算演算を行うシステムの中間積演算に適用することにより、拡大体ＧＦ（３ｍ）上での乗算演算を高速化できる。
【図面の簡単な説明】
【０１１４】
【図１】図１は、実施形態の多項式演算装置の構成を示すブロック図である。
【図２】図２は、多項式ｔ０＋ｔ１・α＋…＋ｔｐ−１・αｐ−１の係数系列ｔ０，ｔ１，…，ｔｐ−１∈ＧＦ（３）のレジスタへの実装方法を説明するための図である。
【図３】図３は、加算部の演算過程でレジスタに格納されるデータを例示した図である。
【図４】図４は、ビット交換部の演算過程でレジスタに格納されるデータを例示した図である。
【図５】図５は、シフト交換部の演算過程でレジスタに格納されるデータを例示した図である。
【図６】図６は、第１実施形態の多項式Ｗ（α）とＡ（α）との乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明するためのフローチャートである。
【図７】図７は、第１実施形態の多項式Ｗ（α）とＡ（α）との乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明するためのフローチャートである。
【図８】図８は、第１実施形態の多項式Ｗ（α）とＡ（α）との乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明するためのフローチャートである。
【図９】図９は、第１実施形態の多項式Ｗ（α）とＡ（α）との乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明するためのフローチャートである。
【図１０】図１０は、第１実施形態の多項式Ｗ（α）とＡ（α）との乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明するためのフローチャートである。
【図１１】図１１は、第１実施形態の多項式Ｗ（α）とＡ（α）との乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明するためのフローチャートである。
【図１２】図１２は、第１実施形態の多項式Ｗ（α）とＡ（α）との乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明するためのフローチャートである。
【図１３】図１３は、第１実施形態の多項式Ｗ（α）とＡ（α）との乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明するためのフローチャートである。
【図１４】図１４は、第１実施形態の多項式Ｗ（α）とＡ（α）との乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明するための表である。
【図１５】図１５は、第２実施形態の多項式Ｗ（α）・Ａ（α）係数系列の算出過程の第１実施形態との相違点を説明するためのフローチャートである。
【図１６】図１６は、第２実施形態の多項式Ｗ（α）・Ａ（α）係数系列の算出過程の第１実施形態との相違点を説明するためのフローチャートである。
【図１７】図１７は、第２実施形態の多項式Ｗ（α）・Ａ（α）係数系列の算出過程の第１実施形態との相違点を説明するためのフローチャートである。
【図１８】図１８は、本形態の多項式Ｗ（α）とＡ（α）との乗算結果を示す多項式Ｗ（α）・Ａ（α）の係数系列の算出過程を説明するための表である。
【図１９】図１９は、ウィンドウ幅３の各中間積を計算するための一般的な演算手順を説明するための表である。
【符号の説明】
【０１１５】
１  多項式演算装置
１０  メインメモリ
２０  レジスタ
３１  加算部（加算手段）
３２  ビット交換部（二倍算手段）
３３  シフト演算部（α倍算手段）
１３２  ビット交換加算部（二倍算加算手段）
１３３  ２シフト演算部（α２倍算手段）
４０  制御部（制御手段）
【図１】
0004612698.tif 000004
【図２】
0004612698.tif 000005
【図３】
0004612698.tif 000006
【図４】
0004612698.tif 000007
【図５】
0004612698.tif 000008
【図６】
0004612698.tif 000009
【図７】
0004612698.tif 000010
【図８】
0004612698.tif 000011
【図９】
0004612698.tif 000012
【図１０】
0004612698.tif 000013
【図１１】
0004612698.tif 000014
【図１２】
0004612698.tif 000015
【図１３】
0004612698.tif 000016
【図１４】
0004612698.tif 000017
【図１５】
0004612698.tif 000018
【図１６】
0004612698.tif 000019
【図１７】
0004612698.tif 000020
【図１８】
0004612698.tif 000021
【図１９】
0004612698.tif 000022