(57)【要約】【課題】縮約演算を効率化する。【解決手段】多項式ｒ（ｘ）＝（ｈｎ−１×ｘｎ−１＋・・・＋ｈ０×ｘ０）×ｘｎ＋（ｋｎ−１×ｘｎ−１＋・・・＋ｋ０×ｘ０）に対して、ｎ個の元ｈｎ−１，・・・，ｈ０∈ＧＦ（ｑ）からなる列ｈ∈ＧＦ（ｑｎ）およびｎ個の元ｋｎ−１，・・・，ｋ０∈ＧＦ（ｑ）からなる列ｋ∈ＧＦ（ｑｎ）を得る。次に、Ｈ＝ｈ＋ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得、Ｒ＝ｋ＋Ｈ≪ｎ（１）＋・・・＋Ｈ≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得る。【選択図】図１
2014021237.tif 000002
【特許請求の範囲】
【請求項１】
ｒ（ｘ）  ｍｏｄ  ｆ（ｘ）の計算を行う縮約装置であって、
ｑが２以上の整数であり、ｎが３以上の整数であり、ｔが３≦ｔ≦ｎの整数であり、ＧＦ（ｑ）が位数ｑの有限体であり、ＧＦ（ｑｎ）が有限体ＧＦ（ｑ）のｎ次拡大体であり、ｘが不定元であり、ｎ（ｔ−１），・・・，ｎ（１）がｎ／２＞ｎ（ｔ−１）＞・・・＞ｎ（１）＝０を満たす整数であり、ｆ０（ｘ）が多項式ｆ０（ｘ）＝ｘｎ（ｔ−１）＋・・・＋ｘｎ（１）であり、ｆ（ｘ）＝ｘｎ−ｆ０（ｘ）であり、α≫ｊがｎ個の有限体ＧＦ（ｑ）の元からなる列α∈ＧＦ（ｑｎ）に対する右ｊシフト演算であり、α≪ｊがｎ個の有限体ＧＦ（ｑ）の元からなる列α∈ＧＦ（ｑｎ）に対する左ｊシフト演算であり、
多項式ｒ（ｘ）＝（ｈｎ−１×ｘｎ−１＋・・・＋ｈ０×ｘ０）×ｘｎ＋（ｋｎ−１×ｘｎ−１＋・・・＋ｋ０×ｘ０）に対して、ｎ個の元ｈｎ−１，・・・，ｈ０∈ＧＦ（ｑ）からなる列ｈ∈ＧＦ（ｑｎ）およびｎ個の元ｋｎ−１，・・・，ｋ０∈ＧＦ（ｑ）からなる列ｋ∈ＧＦ（ｑｎ）を得る分割部と、
Ｈ＝ｈ＋ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得る第１演算部と、
Ｒ＝ｋ＋Ｈ≪ｎ（１）＋・・・＋Ｈ≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得る第２演算部と、
を有する縮約装置。
【請求項２】
請求項１の縮約装置であって、
ｎ個の元γｎ−１，・・・，γ０∈ＧＦ（ｑ）からなるｑｎ種類の列γ∈ＧＦ（ｑｎ）に対するγ≫ｎ−ｎ（ｔ−１）によって得られるｑｎ（ｔ−１）種類の列のそれぞれに対し、対応する列Γ＝γ≫ｎ−ｎ（２）＋・・・＋γ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）を対応付けたテーブルを格納したテーブル記憶部をさらに有し、
前記第１演算部は、前記テーブル記憶部を参照し、ｈ≫ｎ−ｎ（ｔ−１）によって得られる列に対応するｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得、得られたｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）を用いてＨを得る、縮約装置。
【請求項３】
請求項１の縮約装置であって、
ｃが１≦ｃ≦ｎの整数であり、ｈｎ−１＝・・・＝ｈｎ−ｃ＝０であり、
γｎ−１＝・・・＝γｎ−ｃ＝０であり、ｎ個の元γｎ−１，・・・，γ０∈ＧＦ（ｑ）からなるｑｎ−ｃ種類の列γ∈ＧＦ（ｑｎ）に対するγ≫ｎ−ｎ（ｔ−１）によって得られるｑｎ（ｔ−１）−ｃ種類の列のそれぞれに対し、対応する列Γ＝γ≫ｎ−ｎ（２）＋・・・＋γ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）を対応付けたテーブルを格納したテーブル記憶部をさらに有し、
前記第１演算部は、前記テーブル記憶部を参照し、ｈ≫ｎ−ｎ（ｔ−１）によって得られる列に対応するｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得、得られたｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）を用いてＨを得る、縮約装置。
【請求項４】
ｒ（ｘ）  ｍｏｄ  ｆ（ｘ）の計算を行う縮約装置であって、
ｑが２以上の整数であり、ｎが３以上の整数であり、ｔが３≦ｔ≦ｎの整数であり、ＧＦ（ｑ）が位数ｑの有限体であり、ＧＦ（ｑｎ）が有限体ＧＦ（ｑ）のｎ次拡大体であり、ｘが不定元であり、ｎ（ｔ−１），・・・，ｎ（１）がｎ／２＞ｎ（ｔ−１）＞・・・＞ｎ（１）＝０を満たす整数であり、ｆ０（ｘ）が多項式ｆ０（ｘ）＝ｘｎ（ｔ−１）＋・・・＋ｘｎ（１）であり、ｆ（ｘ）＝ｘｎ−ｆ０（ｘ）であり、α≫ｊがｎ個の有限体ＧＦ（ｑ）の元からなる列α∈ＧＦ（ｑｎ）に対する右ｊシフト演算であり、α≪ｊがｎ個の有限体ＧＦ（ｑ）の元からなる列α∈ＧＦ（ｑｎ）に対する左ｊシフト演算であり、
多項式ｒ（ｘ）＝（ｈｎ−１×ｘｎ−１＋・・・＋ｈ０×ｘ０）×ｘｎ＋（ｋｎ−１×ｘｎ−１＋・・・＋ｋ０×ｘ０）に対して、ｎ個の元ｈｎ−１，・・・，ｈ０∈ＧＦ（ｑ）からなる列ｈ∈ＧＦ（ｑｎ）およびｎ個の元ｋｎ−１，・・・，ｋ０∈ＧＦ（ｑ）からなる列ｋ∈ＧＦ（ｑｎ）を得る分割部と、
ｈ’＝ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）であり、η＝ｈ’≪ｎ（１）＋・・・＋ｈ’≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）であり、Ｒ＝ｋ＋ｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１）＋η∈ＧＦ（ｑｎ）を得る第１演算部と、
を有する縮約装置。
【請求項５】
請求項４の縮約装置であって、
ｎ個の元γｎ−１，・・・，γ０∈ＧＦ（ｑ）からなるｑｎ種類の列γ∈ＧＦ（ｑｎ）に対するγ≫ｎ−ｎ（ｔ−１）によって得られるｑｎ（ｔ−１）種類の列のそれぞれに対し、γ’＝γ≫ｎ−ｎ（２）＋・・・＋γ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）とした場合における、対応する列Γ’＝γ’≪ｎ（１）＋・・・＋γ’≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）を対応付けたテーブルを格納したテーブル記憶部をさらに有し、
前記第１演算部は、前記テーブル記憶部を参照し、ｈ≫ｎ−ｎ（ｔ−１）によって得られる列に対応するηを得、得られたηを用いてＲを得る、縮約装置。
【請求項６】
請求項４の縮約装置であって、
ｃが１≦ｃ≦ｎの整数であり、ｈｎ−１＝・・・＝ｈｎ−ｃ＝０であり、
γｎ−１＝・・・＝γｎ−ｃ＝０であり、ｎ個の元γｎ−１，・・・，γ０∈ＧＦ（ｑ）からなるｑｎ−ｃ種類の列γ∈ＧＦ（ｑｎ）に対するγ≫ｎ−ｎ（ｔ−１）によって得られるｑｎ（ｔ−１）−ｃ種類の列のそれぞれに対し、γ’＝γ≫ｎ−ｎ（２）＋・・・＋γ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）とした場合における、対応する列Γ’＝γ’≪ｎ（１）＋・・・＋γ’≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）を対応付けたテーブルを格納したテーブル記憶部をさらに有し、
前記第１演算部は、前記テーブル記憶部を参照し、ｈ≫ｎ−ｎ（ｔ−１）によって得られる列に対応するηを得、得られたηを用いてＲを得る、縮約装置。
【請求項７】
請求項４の縮約装置であって、
ｈｎ−１＝０であり、ｔ＝５であり、ｑ＝２であり、ｎ（４）＝４，ｎ（３）＝３，ｎ（２）＝１，ｎ（１）＝０であり、
ｔ１＝ｈ≫ｎ−４を得る第２演算部と、
ｔ１がｎ個の元εｎ−１，・・・，ε０∈ＧＦ（ｑ）からなり、ｎ個の元０，・・・，０，ε０∈ＧＦ（ｑ）からなる列がｔ０∈ＧＦ（ｑｎ）であり、ｔ２＝ｔ１≪１＋ｔ０＋ｈ≫ｎ−３∈ＧＦ（ｑｎ）を得る第３演算部と、
η＝ｔ２＋ｔ２≪３∈ＧＦ（ｑｎ）を得る第４演算部と、をさらに有し、
前記第１演算部は、前記第４演算部で得られたηを用いてＲを得る、縮約装置。
【請求項８】
請求項４の縮約装置であって、
ｔ＝５であり、ｎ（４）＝４，ｎ（３）＝３，ｎ（２）＝１，ｎ（１）＝０であり、
ｈ’＝ｈ≫ｎ−１＋ｈ≫ｎ−３＋ｈ≫ｎ−４∈ＧＦ（ｑｎ）を得る第２演算部と、
ｔ２’＝ｈ’＋ｈ’≪１∈ＧＦ（ｑｎ）またはｔ２’’＝ｈ’＋ｈ’≪３∈ＧＦ（ｑｎ）を得る第３演算部と、
η＝ｔ２’＋ｔ２’≪３∈ＧＦ（ｑｎ）またはη＝ｔ２’’＋ｔ２’’≪１を得る第４演算部と、をさらに有し、
前記第１演算部は、前記第４演算部で得られたηを用いてＲを得る、縮約装置。
【請求項９】
請求項４から８の何れかの縮約装置であって、
ｔ＝５であり、ｎ（４）＝４，ｎ（３）＝３，ｎ（２）＝１，ｎ（１）＝０であり、
ｔ３＝ｈ＋ｈ≪１∈ＧＦ（ｑｎ）またはｔ４＝ｈ＋ｈ≪３∈ＧＦ（ｑｎ）を得る第５演算部と、
ρ＝ｔ３＋ｔ３≪３∈ＧＦ（ｑｎ）またはρ＝ｔ４＋ｔ４≪１∈ＧＦ（ｑｎ）を得る第６演算部と、をさらに有し、
前記第１演算部は、前記第６演算部で得られたρをｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）として用いてＲを得る、縮約装置。
【請求項１０】
請求項４の縮約装置であって、
ｔ＝５であり、ｎ（４）＝４，ｎ（３）＝３，ｎ（２）＝１，ｎ（１）＝０であり、
ν＝ｈ＋ｈ’∈ＧＦ（ｑｎ）を得る第２演算部と、
υ＝ν＋ν≪１∈ＧＦ（ｑｎ）またはι＝ν＋ν≪３∈ＧＦ（ｑｎ）を得る第３演算部と、
σ＝υ＋υ≪３∈ＧＦ（ｑｎ）またはσ＝ι＋ι≪１∈ＧＦ（ｑｎ）を得る第４演算部と、をさらに有し、
前記第１演算部は、前記第４演算部で得られたσをｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１）＋η∈ＧＦ（ｑｎ）として用いてＲを得る、縮約装置。
【請求項１１】
請求項１の縮約装置であって、
ｈｎ−１＝０、ｎ（４）＝７，ｎ（３）＝２，ｎ（２）＝１，ｎ（１）＝０であり、
前記第１演算部が、ｈ＋ｈ≫ｎ−７＋ｈ≫ｎ−２∈ＧＦ（ｑｎ）によって前記列Ｈを得る、縮約装置。
【請求項１２】
請求項１から１１の何れかに記載された縮約装置であって、
ｑ＝２であり、ＧＦ（２）がビット集合｛０，１｝であり、ＧＦ（２ｎ）がｎビットのビット列の集合｛０，１｝ｎである、縮約装置。
【請求項１３】
ｒ（ｘ）  ｍｏｄ  ｆ（ｘ）の計算を行う縮約方法であって、
ｑが２以上の整数であり、ｎが３以上の整数であり、ｔが３≦ｔ≦ｎの整数であり、ＧＦ（ｑ）が位数ｑの有限体であり、ＧＦ（ｑｎ）が有限体ＧＦ（ｑ）のｎ次拡大体であり、ｘが不定元であり、ｎ（ｔ−１），・・・，ｎ（１）がｎ／２＞ｎ（ｔ−１）＞・・・＞ｎ（１）＝０を満たす整数であり、ｆ０（ｘ）が多項式ｆ０（ｘ）＝ｘｎ（ｔ−１）＋・・・＋ｘｎ（１）であり、ｆ（ｘ）＝ｘｎ−ｆ０（ｘ）であり、α≫ｊがｎ個の有限体ＧＦ（ｑ）の元からなる列α∈ＧＦ（ｑｎ）に対する右ｊシフト演算であり、α≪ｊがｎ個の有限体ＧＦ（ｑ）の元からなる列α∈ＧＦ（ｑｎ）に対する左ｊシフト演算であり、
分割部で、多項式ｒ（ｘ）＝（ｈｎ−１×ｘｎ−１＋・・・＋ｈ０×ｘ０）×ｘｎ＋（ｋｎ−１×ｘｎ−１＋・・・＋ｋ０×ｘ０）に対して、ｎ個の元ｈｎ−１，・・・，ｈ０∈ＧＦ（ｑ）からなる列ｈ∈ＧＦ（ｑｎ）およびｎ個の元ｋｎ−１，・・・，ｋ０∈ＧＦ（ｑ）からなる列ｋ∈ＧＦ（ｑｎ）を得る分割ステップと、
第１演算部で、Ｈ＝ｈ＋ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得る第１ステップと、
第２演算部で、Ｒ＝ｋ＋Ｈ≪ｎ（１）＋・・・＋Ｈ≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得る第２ステップと、
を有する縮約方法。
【請求項１４】
ｒ（ｘ）  ｍｏｄ  ｆ（ｘ）の計算を行う縮約方法であって、
ｑが２以上の整数であり、ｎが３以上の整数であり、ｔが３≦ｔ≦ｎの整数であり、ＧＦ（ｑ）が位数ｑの有限体であり、ＧＦ（ｑｎ）が有限体ＧＦ（ｑ）のｎ次拡大体であり、ｘが不定元であり、ｎ（ｔ−１），・・・，ｎ（１）がｎ／２＞ｎ（ｔ−１）＞・・・＞ｎ（１）＝０を満たす整数であり、ｆ０（ｘ）が多項式ｆ０（ｘ）＝ｘｎ（ｔ−１）＋・・・＋ｘｎ（１）であり、ｆ（ｘ）＝ｘｎ−ｆ０（ｘ）であり、α≫ｊがｎ個の有限体ＧＦ（ｑ）の元からなる列α∈ＧＦ（ｑｎ）に対する右ｊシフト演算であり、α≪ｊがｎ個の有限体ＧＦ（ｑ）の元からなる列α∈ＧＦ（ｑｎ）に対する左ｊシフト演算であり、
分割部で、多項式ｒ（ｘ）＝（ｈｎ−１×ｘｎ−１＋・・・＋ｈ０×ｘ０）×ｘｎ＋（ｋｎ−１×ｘｎ−１＋・・・＋ｋ０×ｘ０）に対して、ｎ個の元ｈｎ−１，・・・，ｈ０∈ＧＦ（ｑ）からなる列ｈ∈ＧＦ（ｑｎ）およびｎ個の元ｋｎ−１，・・・，ｋ０∈ＧＦ（ｑ）からなる列ｋ∈ＧＦ（ｑｎ）を得る分割ステップと、
演算部で、ｈ’＝ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）であり、η＝ｈ’≪ｎ（１）＋・・・＋ｈ’≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）であり、Ｒ＝ｋ＋ｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１）＋η∈ＧＦ（ｑｎ）を得る演算ステップと、
を有する縮約方法。
【請求項１５】
請求項１から１２の何れかの縮約装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算技術に関し、特に縮約演算に関する。
【背景技術】
【０００２】
拡大体ＧＦ（２ｎ）（ただしｎは正整数）上の演算は、多項式演算結果（例えば、多項式乗算結果）に対する、ｎ次多項式ｆ（ｘ）を法とした剰余演算（縮約）によって実現できる。ｆ（ｘ）による剰余演算を効率的に実行するため、通常、ｆ（ｘ）として項数の少ないものが選ばれる。一般にｆ（ｘ）＝ｘｎ−ｆ０（ｘ）（ただし、ｄｅｇ  ｆ０＜ｎ）と書けるが、多くのｎに対し、ｄｅｇ  ｆ０＜ｎ／２となるものを選ぶことが出来る。このとき２ｎ次未満の多項式である多項式演算結果をｒ（ｘ）とおくと、ｆ（ｘ）を法とした剰余演算は、ｘｎ≡ｆ０（ｘ）（ｍｏｄ  ｆ（ｘ））を利用し、次のように記述できる（例えば、非特許文献１参照）。
【０００３】
＜アルゴリズム１＞
入力：ｒ（ｘ），ｆ（ｘ）＝ｘｎ−ｆ０（ｘ）
出力：Ｒ（ｘ）＝ｒ（ｘ）  ｍｏｄ  ｆ（ｘ）
１：ｈ（ｘ）×ｘｎ＋ｋ（ｘ）←ｒ（ｘ）（ただし、ｄｅｇ  ｋ（ｘ）＜ｎ）
２：ｒ’（ｘ）←ｋ（ｘ）＋ｈ（ｘ）×ｆ０（ｘ）
３：Ｈ（ｘ）×ｘｎ＋ｋ（ｘ）←ｒ’（ｘ）
４：Ｒ（ｘ）←ｋ（ｘ）＋Ｈ（ｘ）×ｆ０（ｘ）
【０００４】
さらにｆ０（ｘ）を以下のようにおく。
【数１】
2014021237.tif 000003
ただし、ｔは正整数であり、ｎ（ｉ）＝ｎ（ｔ−１），・・・，ｎ（１）はｎ／２＞ｎ（ｔ−１）＞・・・＞ｎ（１）＝０を満たす整数である。すると、ｆ（ｘ）を法とした剰余演算は、次のように記述できる。
【０００５】
＜アルゴリズム２＞
入力：ｒ（ｘ），ｆ（ｘ）＝ｘｎ−ｆ０（ｘ）
出力：Ｒ（ｘ）＝ｒ（ｘ）  ｍｏｄ  ｆ（ｘ）
１：ｈ（ｘ）×ｘｎ＋ｋ（ｘ）←ｒ（ｘ）
２：ｒ’（ｘ）←ｋ（ｘ）＋ｈ（ｘ）×（ｘｎ（ｔ−１）＋・・・＋ｘｎ（１））
３：Ｈ（ｘ）×ｘｎ＋ｋ（ｘ）←ｒ’（ｘ）
４：Ｒ（ｘ）←ｋ（ｘ）＋Ｈ（ｘ）×（ｘｎ（ｔ−１）＋・・・＋ｘｎ（１））
【０００６】
さらにｒ（ｘ）の係数列ｒが２×ｎビットのレジスタに保存され、その他の多項式の係数列がｎビットのレジスタに保存されるとする。すると、ｆ（ｘ）を法とした剰余演算は、次のように記述できる。
【０００７】
＜アルゴリズム３＞
入力：ｒ∈ＧＦ（２）２×ｎ，ｎ（ｔ−１），・・・，ｎ（１）
出力：ｒ（ｘ）  ｍｏｄ  ｆ（ｘ）の係数列Ｒ∈ＧＦ（２）ｎ
１：ｈ｜ｋ←ｒ（ただし、ｈ，ｋ∈ＧＦ（２）ｎ）
２：ｋ’←ｋ＋ｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１）∈ＧＦ（２）ｎ
３：ｈ’’←ｈ≪ｎ−ｎ（２）＋・・・＋ｈ≪ｎ−ｎ（ｔ−１）∈ＧＦ（２）ｎ
４：Ｒ←ｋ’＋ｈ’’≪ｎ（１）＋・・・＋ｈ’’≪ｎ（ｔ−１）∈ＧＦ（２）ｎ
ただし、α≫ｊはｎ個の有限体ＧＦ（２）の元からなる列α∈ＧＦ（２）ｎに対する右ｊシフト演算を表し、α≪ｊが列α∈ＧＦ（２）ｎに対する左ｊシフト演算を表す。またα｜βは列αと列βとの結合（例えばビット結合）を表す。
【０００８】
図８Ａ〜図８Ｃおよび図９に＜アルゴリズム３＞の処理を図示する。図８Ａがｈ｜ｋ←ｒ（ステップ１）、図８Ｂがｋ’←ｋ＋ｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１）（ステップ２）、図８Ｃがｈ’’←ｈ≪ｎ−ｎ（２）＋・・・＋ｈ≪ｎ−ｎ（ｔ−１）（ステップ３）、図９がＲ←ｋ’＋ｈ’’≪ｎ（１）＋・・・＋ｈ’’≪ｎ（ｔ−１）（ステップ４）を、それぞれ表す。図８Ａ〜図８Ｃおよび図９での演算子＋は、拡大体ＧＦ（２ｎ）上での加算を表す。図８Ｂおよび図８Ｃに示すように、ステップ４はステップ３での左シフト演算によってｎビットのレジスタから溢れた値ｈ（２），・・・，ｈ（ｔ−１）についての演算を行っている。またｄｅｇ  ｆ０＜ｎ／２、すなわちｎ／２＞ｎ（ｔ−１）であるため、図９に示すようにステップ４での左シフト演算によってｎビットのレジスタから溢れる値はすべて０である。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Darrel Hankerson, Julio Lopez Hernandez, Alfred Menezes, “Software Implementation of Elliptic Curve Cryptography over Binary Fields,” CHES 2000, LNCS 1965, pp. 1-24, 2000.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
アルゴリズム３では、ｔ−１回の左ｎ（ｉ）シフト演算（ｉ＝１，・・・，ｔ−１）とｔ−１回の拡大体ＧＦ（２ｎ）上での加算をそれぞれ２回ずつ行うため（ステップ２および４）、演算効率が悪い。
【００１１】
本発明はこのような点に鑑みてなされたものであり、従来よりも演算効率のよい縮約技術を提供することを目的とする。
【課題を解決するための手段】
【００１２】
以下のようにｒ（ｘ）  ｍｏｄ  ｆ（ｘ）の計算を行う。ただし、ｑが２以上の整数であり、ｎが３以上の整数であり、ｔが３≦ｔ≦ｎの整数であり、ＧＦ（ｑ）が位数ｑの有限体であり、ＧＦ（ｑｎ）が有限体ＧＦ（ｑ）のｎ次拡大体であり、ｘが不定元であり、ｎ（ｔ−１），・・・，ｎ（１）がｎ／２＞ｎ（ｔ−１）＞・・・＞ｎ（１）＝０を満たす整数であり、ｆ０（ｘ）が多項式ｆ０（ｘ）＝ｘｎ（ｔ−１）＋・・・＋ｘｎ（１）であり、ｆ（ｘ）＝ｘｎ−ｆ０（ｘ）であり、α≫ｊがｎ個の有限体ＧＦ（ｑ）の元からなる列α∈ＧＦ（ｑｎ）に対する右ｊシフト演算であり、α≪ｊがｎ個の有限体ＧＦ（ｑ）の元からなる列α∈ＧＦ（ｑｎ）に対する左ｊシフト演算である。
【００１３】
まず、多項式ｒ（ｘ）＝（ｈｎ−１×ｘｎ−１＋・・・＋ｈ０×ｘ０）×ｘｎ＋（ｋｎ−１×ｘｎ−１＋・・・＋ｋ０×ｘ０）に対して、ｎ個の元ｈｎ−１，・・・，ｈ０∈ＧＦ（ｑ）からなる列ｈ∈ＧＦ（ｑｎ）およびｎ個の元ｋｎ−１，・・・，ｋ０∈ＧＦ（ｑ）からなる列ｋ∈ＧＦ（ｑｎ）を得る。次に、Ｈ＝ｈ＋ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得、Ｒ＝ｋ＋Ｈ≪ｎ（１）＋・・・＋Ｈ≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得る。
【発明の効果】
【００１４】
シフト演算およびＧＦ（ｑｎ）上での加減算は可換であるため、本発明によって得られる列Ｒはｒ（ｘ）  ｍｏｄ  ｆ（ｘ）の係数列となる。また本発明では、従来それぞれ２回ずつ行う必要があったｔ−１回の左ｎ（ｉ）シフト演算および拡大体ＧＦ（２ｎ）上での加算を１回にまとめることができるため、従来よりも効率よく縮約を実行できる。
【図面の簡単な説明】
【００１５】
【図１】図１Ａは実施形態の縮約装置の構成を説明するためのブロック図であり、図１Ｂは実施形態の縮約方法を説明するためのフロー図である。
【図２】図２は実施形態の縮約方法を示した図である。
【図３】図３Ａは実施形態の縮約装置の構成を説明するためのブロック図であり、図３Ｂは実施形態の縮約方法を説明するためのフロー図である。
【図４】図４は実施形態の縮約方法を説明するためのフロー図である。
【図５】図５は実施形態の縮約方法を説明するためのフロー図である。
【図６】図６は実施形態の縮約方法を説明するためのフロー図である。
【図７】図７は実施形態の縮約方法を説明するためのフロー図である。
【図８】図８Ａ〜８Ｃは従来の縮約方法を示した図である。
【図９】図９は従来の縮約方法を示した図である。
【発明を実施するための形態】
【００１６】
以下、図面を参照して実施形態を説明する。
〔定義〕
用語および記号を定義する。
ＧＦ（ｑ）は位数ｑの有限体を表し、ＧＦ（ｑｎ）は有限体ＧＦ（ｑ）のｎ次拡大体を表す。ただし、ｑは２以上の整数（定数）であり、ｎは３以上の整数（定数）である。例えば、ｑ＝２であり、ＧＦ（２）がビット集合｛０，１｝であり、ＧＦ（２ｎ）がｎビットのビット列の集合｛０，１｝ｎである。ｎの例はｎ＝８，６４，１２８などである。
【００１７】
ｆ（ｘ）＝ｘｎ−ｆ０（ｘ）であり、ｆ０（ｘ）は多項式ｆ０（ｘ）＝ｘｎ（ｔ−１）＋・・・＋ｘｎ（１）を表す。また、ｔは３≦ｔ≦ｎの整数（定数）であり、ｘは不定元であり、ｎ（ｔ−１），・・・，ｎ（１）はｎ／２＞ｎ（ｔ−１）＞・・・＞ｎ（１）＝０を満たす整数である。
【００１８】
α≫ｊはｎ個の元αｎ−１，・・・，α０∈ＧＦ（ｑ）からなる列α∈ＧＦ（ｑｎ）に対する右ｊシフト演算を表す。ただし、ｊは正整数である。α≫ｊによってｎ個の元βｎ−１，・・・，β０∈ＧＦ（ｑ）からなる列β∈ＧＦ（ｑｎ）が得られるとすると、βｎ−１，・・・，βｎ−ｊが０，・・・，０であり、βｎ−１−ｊ，・・・，β０がαｎ−１，・・・，αｊである。α≫０は無操作を表し、α≫０のための処理や構成は不要である。
【００１９】
α≪ｊはｎ個の元αｎ−１，・・・，α０∈ＧＦ（ｑ）からなる列α∈ＧＦ（ｑｎ）に対する左ｊシフト演算である。α≪ｊによってｎ個の元βｎ−１，・・・，β０∈ＧＦ（ｑ）からなる列β∈ＧＦ（ｑｎ）が得られるとすると、βｎ−１，・・・，βｊがαｎ−１−ｊ，・・・，α０であり、βｊ−１，・・・，β０が０，・・・，０である。なお、右ｊシフト演算や左ｊシフト演算は、シフト命令によって実行されてもよいし、ｎ個の有限体ＧＦ（ｑ）の元からなる列を整数とみた場合の加算命令の組み合わせによって実行されてもよい。α≪０は無操作を表し、α≪０のための処理や構成は不要である。
【００２０】
α＋β∈ＧＦ（ｑｎ）は、列α，β∈ＧＦ（ｑｎ）の拡大体ＧＦ（ｑｎ）上での加算を表す。拡大体ＧＦ（ｑｎ）がビット列の集合｛０，１｝ｎである場合、α＋β∈ＧＦ（ｑｎ）はα（＋）β∈｛０，１｝ｎとなる。ただし、α（＋）βは、ｎ個のビットαｎ−１，・・・，α０∈｛０，１｝からなるビット列αとｎ個のビットβｎ−１，・・・，β０∈｛０，１｝からなるビット列β∈｛０，１｝ｎとのビットごとの排他的論理和演算
【数２】
2014021237.tif 000004
を表す。
【００２１】
α＆βは、ｎ個のビットαｎ−１，・・・，α０∈｛０，１｝からなるビット列αとｎ個のビットβｎ−１，・・・，β０∈｛０，１｝からなるビット列β∈｛０，１｝ｎとのビットごとのＡＮＤ演算αｎ−１＆βｎ−１，・・・，α０＆β０を表す。
【００２２】
〔第１実施形態〕
＜構成＞
図１Ａに例示するように、第１実施形態の縮約装置１は、入力部１１、分割部１２、演算部１３，１４（第１，２演算部）、出力部１５、制御部１６、および記憶部１７を有する。縮約装置１は、例えば、ＣＰＵ（central processing unit）、レジスタ、ＲＡＭ（random-access memory）、ハードディスクなどを有する公知または専用のコンピュータに所定のプログラムが読み込まれることによって構成される特別な装置である。縮約装置１は、制御部１６の制御のもとで各処理を行う。入力部１１に入力されたデータおよび各処理で得られたデータは、逐一、記憶部１７に格納される。記憶部１７に格納されたデータは、必要に応じて読み出され、各部に入力されて各処理に用いられる。
【００２３】
＜方法＞
図１Ｂに例示するように、入力部１１には、多項式ｒ（ｘ）＝（ｈｎ−１×ｘｎ−１＋・・・＋ｈ０×ｘ０）×ｘｎ＋（ｋｎ−１×ｘｎ−１＋・・・＋ｋ０×ｘ０）を特定するための情報ｒが入力される。例えば、多項式ｒ（ｘ）の係数列ｈｎ−１，・・・，ｈ０，ｋｎ−１，・・・，ｋ０がｒとして入力される。なお、多項式ｒ（ｘ）の例は、ｎ次以下の多項式どうしの乗算結果である（ステップＳ１１）。
【００２４】
分割部１２に情報ｒが入力される。図２Ａに例示するように、分割部１２は、多項式ｒ（ｘ）＝（ｈｎ−１×ｘｎ−１＋・・・＋ｈ０×ｘ０）×ｘｎ＋（ｋｎ−１×ｘｎ−１＋・・・＋ｋ０×ｘ０）に対して、ｎ個の元ｈｎ−１，・・・，ｈ０∈ＧＦ（ｑ）からなる列ｈ∈ＧＦ（ｑｎ）およびｎ個の元ｋｎ−１，・・・，ｋ０∈ＧＦ（ｑ）からなる列ｋ∈ＧＦ（ｑｎ）を得（ｈ｜ｋ←ｒ）、列ｈおよびｋを出力する。例えば、ＧＦ（ｑｎ）がｎビットのビット列の集合｛０，１｝ｎである場合、分割部１２は、ビット列ｈ｜ｋを分割してｎビットのビット列ｈ，ｋ∈｛０，１｝ｎを得、ビット列ｈ，ｋを出力する（ステップＳ１２）。
【００２５】
演算部１３に列ｈが入力される。図２Ｂに例示するように、演算部１３は、列Ｈ＝ｈ＋ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得、列Ｈを出力する。すなわち、演算部１３は、ｈ≫ｎ−ｎ（ｉ）（ｉ＝１，・・・，ｔ−１）の拡大体ＧＦ（ｑｎ）上での加算値を列Ｈとして出力する。例えば、ＧＦ（ｑｎ）がｎビットのビット列の集合｛０，１｝ｎである場合、演算部１３は、ビット列Ｈ＝ｈ（＋）ｈ≫ｎ−ｎ（２）（＋）・・・（＋）ｈ≫ｎ−ｎ（ｔ−１）∈｛０，１｝ｎを得、ビット列Ｈを出力する。なお、図２Ｂにおけるｈ（ｉ）は、ｈｎ−１，・・・，ｈｎ−ｎ（ｉ）からなる列を表す（ステップＳ１３）。
【００２６】
演算部１４に列Ｈおよび列ｋが入力される。図２Ｃに例示するように、演算部１４は、列Ｒ＝ｋ＋Ｈ≪ｎ（１）＋・・・＋Ｈ≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得、列Ｒを出力する。すなわち、演算部１４は、ｋ，Ｈ≪ｎ（１），・・・，Ｈ≪ｎ（ｔ−１）の拡大体ＧＦ（ｑｎ）上での加算値を列Ｒとして出力する。例えば、ＧＦ（ｑｎ）がｎビットのビット列の集合｛０，１｝ｎである場合、演算部１４は、ビット列Ｒ＝ｋ（＋）Ｈ≪ｎ（１）（＋）・・・（＋）Ｈ≪ｎ（ｔ−１）∈｛０，１｝ｎを得、ビット列Ｒを出力する（ステップＳ１４）。
【００２７】
出力部１５は、演算部１４で得られた列Ｒを出力する（ステップＳ１５）。
【００２８】
＜本形態の特徴＞
本形態では、従来のアルゴリズム３のステップ３および４（図８Ｃおよび図９）での左シフト演算とＧＦ（ｑｎ）上での演算（例えば排他的論理和演算）とをステップＳ１３（図２Ｂ）でまとめて実行している。シフト演算およびＧＦ（ｑｎ）上での加減算（例えば排他的論理和演算）は可換であるため、これらの演算の順序を入れ替えても得られる結果は同一であり、ステップＳ１４で得られる列Ｒはｒ（ｘ）  ｍｏｄ  ｆ（ｘ）の係数列となる。よって、本形態では従来よりも効率よく高速に縮約演算を行うことができる。
【００２９】
〔第２実施形態〕
本形態は第１実施形態の変形例であり、事前計算値が格納されたテーブルを用いて演算効率を向上させる。さらに本形態では、事前計算対象を工夫し、必要なテーブルのサイズを小さくする。以下の説明では、すでに説明した事項と共通する部分については同じ参照符号を用いて説明を省略する。
【００３０】
＜構成＞
図１Ａに例示するように、第２実施形態の縮約装置２は、入力部１１、分割部１２、演算部２３，１４（第１，２演算部）、出力部１５、制御部１６、記憶部１７、およびテーブル記憶部２８を有する。縮約装置２は、例えば、公知または専用のコンピュータに所定のプログラムが読み込まれることによって構成される特別な装置である。縮約装置２は、制御部１６の制御のもとで各処理を行う。入力部１１に入力されたデータおよび各処理で得られたデータは、逐一、記憶部１７に格納される。記憶部１７に格納されたデータは、必要に応じて読み出され、各部に入力されて各処理に用いられる。
【００３１】
［テーブル記憶部２８］
テーブル記憶部２８は、ｎ個の元γｎ−１，・・・，γ０∈ＧＦ（ｑ）からなるｑｎ種類の列γ∈ＧＦ（ｑｎ）に対するγ≫ｎ−ｎ（ｔ−１）によって得られるｑｎ（ｔ−１）種類の列のそれぞれに対し、対応する列Γ＝γ≫ｎ−ｎ（２）＋・・・＋γ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）を対応付けたテーブルを格納する。例えば、ＧＦ（ｑｎ）がｎビットのビット列の集合｛０，１｝ｎである場合、テーブル記憶部２８は、ｎ個のビットγｎ−１，・・・，γ０∈｛０，１｝からなる２ｎ種類のビット列γ∈｛０，１｝ｎに対するγ≫ｎ−ｎ（ｔ−１）によって得られる２ｎ（ｔ−１）種類のビット列のそれぞれに対し、対応するビット列Γ＝γ≫ｎ−ｎ（２）＋・・・＋γ≫ｎ−ｎ（ｔ−１）∈｛０，１｝ｎを対応付けたテーブルを格納する。
【００３２】
γ≫ｎ−ｎ（ｉ）は０，・・・，０，γｎ−１，・・・，γｎ−ｎ（ｉ）からなり、γ≫ｎ−ｎ（ｔ−１）は０，・・・，０，γｎ−１，・・・，γｎ−ｎ（ｔ−１）からなる。列Γ＝γ≫ｎ−ｎ（２）＋・・・＋γ≫ｎ−ｎ（ｔ−１）は、ｑｎ（ｔ−１）種類の列γｎ−１，・・・，γｎ−ｎ（ｔ−１）のみに依存し、ｑｎ（ｔ−１）種類の列Γのみが存在する。テーブル記憶部２８に格納されるテーブルは、これらのｑｎ（ｔ−１）種類の列γｎ−１，・・・，γｎ−ｎ（ｔ−１）とそれぞれに対応する列Γとを対応付けたものである。ここでｎ／２＞ｎ（ｔ−１）であるため、テーブル記憶部２８に格納されるテーブルのサイズは、ｎ個のＧＦ（ｑ）の元の組み合わせからなるｑｎ種類の列についてのテーブルのサイズに比べて小さい。
【００３３】
＜方法＞
図１Ｂに例示するように、まず第１実施形態で説明したステップＳ１１およびＳ１２が実行される。
【００３４】
次に演算部２３に列ｈが入力される。演算部２３は、テーブル記憶部２８を参照し、ｈ≫ｎ−ｎ（ｔ−１）によって得られる列に対応する列ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）（すなわちｈ≫ｎ−ｎ（ｔ−１）に対応する列ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１））を得る。言い換えると、演算部２３は、入力されたｈから列ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）を得、列ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）に一致する列Γ＝γ≫ｎ−ｎ（２）＋・・・＋γ≫ｎ−ｎ（ｔ−１）に対応する列γｎ−１，・・・，γｎ−ｎ（ｔ−１）をテーブルから抽出し、それをｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）として得る。さらに演算部２３は、得られたｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）を用いて列Ｈ＝ｈ＋（ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１））∈ＧＦ（ｑｎ）を得、列Ｈを出力する（ステップＳ２３）。
【００３５】
その後、第１実施形態で説明したステップＳ１４およびＳ１５が実行される。
【００３６】
＜本形態の特徴＞
本形態では、ｑｎ（ｔ−１）種類の列γｎ−１，・・・，γｎ−ｎ（ｔ−１）とそれぞれに対応する列Γとを対応付けた小さなサイズのテーブルを用い、列ｈに対応する列ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）を抽出し、抽出した列ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）を用いて列Ｈ＝ｈ＋（ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１））を計算する。これにより、大きなサイズのテーブルを用いることなく、演算効率をさらに向上させることができる。
【００３７】
〔第３実施形態〕
本形態は第１，２実施形態の変形例である。多項式ｒ（ｘ）＝（ｈｎ−１×ｘｎ−１＋・・・＋ｈ０×ｘ０）×ｘｎ＋（ｋｎ−１×ｘｎ−１＋・・・＋ｋ０×ｘ０）の次数が２ｎ−１次未満であることが分かっている場合（すなわち、ｈｎ−１＝・・・＝ｈｎ−ｃ＝０、ｃが１≦ｃ≦ｎの整数の場合）には、テーブル記憶部に格納するテーブルのサイズをさらに縮小できる。例えば、多項式ｒ（ｘ）がｎ−１次多項式どうしの乗算結果である場合などである。
【００３８】
＜構成＞
図１Ａに例示するように、第３実施形態の縮約装置３は、入力部１１、分割部１２、演算部３３，１４（第１，２演算部）、出力部１５、制御部１６、記憶部１７、およびテーブル記憶部３８を有する。縮約装置３は、例えば、公知または専用のコンピュータに所定のプログラムが読み込まれることによって構成される特別な装置である。縮約装置３は、制御部１６の制御のもとで各処理を行う。入力部１１に入力されたデータおよび各処理で得られたデータは、逐一、記憶部１７に格納される。記憶部１７に格納されたデータは、必要に応じて読み出され、各部に入力されて各処理に用いられる。
【００３９】
［テーブル記憶部３８］
テーブル記憶部３８は、ｎ個の元γｎ−１，・・・，γ０∈ＧＦ（ｑ）からなるｑｎ−ｃ種類の列γ∈ＧＦ（ｑｎ）に対するγ≫ｎ−ｎ（ｔ−１）によって得られるｑｎ（ｔ−１）−ｃ種類の列のそれぞれに対し、対応する列Γ＝γ≫ｎ−ｎ（２）＋・・・＋γ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）を対応付けたテーブルを格納する。ただし、γｎ−１＝・・・＝γｎ−ｃ＝０であり、ｈｎ−１＝・・・＝ｈｎ−ｃ＝０である。またｃが１≦ｃ≦ｎの整数であり、例えばｃ＝１である。
【００４０】
γ≫ｎ−ｎ（ｉ）は０，・・・，０，γｎ−１，・・・，γｎ−ｎ（ｉ）からなり、γ≫ｎ−ｎ（ｔ−１）は０，・・・，０，γｎ−１，・・・，γｎ−ｎ（ｔ−１）からなる。しかしながら、本形態ではｈｎ−１＝・・・＝ｈｎ−ｃ＝０であるため、γｎ−１＝・・・＝γｎ−ｃ＝０としてよい。この場合の列Γ＝γ≫ｎ−ｎ（２）＋・・・＋γ≫ｎ−ｎ（ｔ−１）は、ｑｎ（ｔ−１）−ｃ種類の列γｎ−ｃ−１，・・・，γｎ−ｎ（ｔ−１）のみに依存し、ｑｎ（ｔ−１）−ｃ種類の列Γのみが存在する。テーブル記憶部３８に格納されるテーブルは、これらのｑｎ（ｔ−１）−ｃ種類の列γｎ−ｃ−１，・・・，γｎ−ｎ（ｔ−１）とそれぞれに対応する列Γとを対応付けたものである。このテーブルのサイズは第２実施形態のものよりも小さい。
【００４１】
＜方法＞
図１Ｂに例示するように、まず第１実施形態で説明したステップＳ１１およびＳ１２が実行される。
【００４２】
次に演算部３３に列ｈが入力される。演算部３３は、テーブル記憶部３８を参照し、ｈ≫ｎ−ｎ（ｔ−１）によって得られる列に対応する列ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）（すなわちｈ≫ｎ−ｎ（ｔ−１）に対応する列ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１））を得る。言い換えると、演算部３３は、入力されたｈから列ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）を得、列ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）に一致する列Γ＝γ≫ｎ−ｎ（２）＋・・・＋γ≫ｎ−ｎ（ｔ−１）に対応する列γｎ−１，・・・，γｎ−ｎ（ｔ−１）をテーブルから抽出し、それをｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）として得る。さらに演算部３３は、得られたｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）を用いてＨ＝ｈ＋（ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１））∈ＧＦ（ｑｎ）を得、列Ｈを出力する（ステップＳ２３）。
【００４３】
その後、第１実施形態で説明したステップＳ１４およびＳ１５が実行される。
【００４４】
＜本形態の特徴＞
以上のように、多項式ｒ（ｘ）＝（ｈｎ−１×ｘｎ−１＋・・・＋ｈ０×ｘ０）×ｘｎ＋（ｋｎ−１×ｘｎ−１＋・・・＋ｋ０×ｘ０）の次数が２ｎ−１次未満であることが分かっている場合には、テーブル記憶部３８に格納するテーブルのサイズをさらに縮小できる。
【００４５】
〔第４実施形態〕
本形態は第１実施形態の変形例であり、拡大体ＧＦ（ｑｎ）上での加算とシフト演算との順序を入れ替えたものである。すなわち、ステップＳ１３で列Ｈ＝ｈ＋（ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１））∈ＧＦ（ｑｎ）を計算することなく、列ｋと、列ｈについてのｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）と、列ｈ’＝ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）についてのη＝ｈ’≪ｎ（１）＋・・・＋ｈ’≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）とから、Ｒ＝ｋ＋ｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１）＋η∈ＧＦ（ｑｎ）を得る。
【００４６】
＜構成＞
図３Ａに例示するように、第４実施形態の縮約装置４は、入力部１１、分割部１２、演算部４４、出力部１５、制御部１６、および記憶部１７を有する。縮約装置４は、例えば、公知または専用のコンピュータに所定のプログラムが読み込まれることによって構成される特別な装置である。縮約装置４は、制御部１６の制御のもとで各処理を行う。入力部１１に入力されたデータおよび各処理で得られたデータは、逐一、記憶部１７に格納される。記憶部１７に格納されたデータは、必要に応じて読み出され、各部に入力されて各処理に用いられる。
【００４７】
＜方法＞
図３Ｂに例示するように、まず第１実施形態で説明したステップＳ１１およびＳ１２が実行される。
【００４８】
次に演算部４４に列ｈ，ｋが入力される。演算部４４は、列ｈ’＝ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得、列η＝ｈ’≪ｎ（１）＋・・・＋ｈ’≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得、列Ｒ＝ｋ＋ｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１）＋η∈ＧＦ（ｑｎ）を得、列Ｒを出力する（ステップＳ４４）。
【００４９】
その後、第１実施形態で説明したＳ１５が実行される。
【００５０】
＜本形態の特徴＞
シフト演算およびＧＦ（ｑｎ）上での加減算は可換であるため、本形態の方法でもｒ（ｘ）  ｍｏｄ  ｆ（ｘ）の係数列Ｒを求めることができ、環境によっては第１実施形態の方法よりも効率よく高速に縮約演算を行うことができる。
【００５１】
〔第４実施形態の変形例１〕
第４実施形態の変形例１では、第４実施形態において事前計算値が格納されたテーブルを用い、演算効率を向上させる。
【００５２】
＜構成＞
図３Ａに例示するように、第４実施形態の変形例１の縮約装置４’は、入力部１１、分割部１２、演算部４４’、出力部１５、制御部１６、記憶部１７、およびテーブル記憶部４８’を有する。
【００５３】
［テーブル記憶部４８’］
テーブル記憶部４８’は、ｎ個の元γｎ−１，・・・，γ０∈ＧＦ（ｑ）からなるｑｎ種類の列γ∈ＧＦ（ｑｎ）に対するγ≫ｎ−ｎ（ｔ−１）によって得られるｑｎ（ｔ−１）種類の列のそれぞれに対し、対応する列Γ’＝γ’≪ｎ（１）＋・・・＋γ’≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）を対応付けたテーブルを格納する。ただし、γ’＝γ≫ｎ−ｎ（２）＋・・・＋γ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）である。
【００５４】
＜方法＞
図３Ｂに例示するように、まず第１実施形態で説明したステップＳ１１およびＳ１２が実行される。
【００５５】
次に演算部４４’に列ｈが入力される。演算部４４’は、テーブル記憶部４８’を参照し、ｈ≫ｎ−ｎ（ｔ−１）によって得られる列に対応するη＝ｈ’≪ｎ（１）＋・・・＋ｈ’≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）（すなわちｈ≫ｎ−ｎ（ｔ−１）に対応する列η）を抽出する。ただし、ｈ’＝ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）である。演算部４４’にはさらに列ｋが入力され、演算部４４’は、列ｋ，ｈおよびηを用いて列Ｒ＝ｋ＋ｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１）＋η∈ＧＦ（ｑｎ）を得、列Ｒを出力する（ステップＳ４４’）。
【００５６】
その後、第１実施形態で説明したＳ１５が実行される。
【００５７】
＜本形態の特徴＞
本形態では、ｑｎ（ｔ−１）種類の列のそれぞれに対し、対応する列Γ’＝γ’≪ｎ（１）＋・・・＋γ’≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）を対応付けたサイズの小さなテーブルを用い、さらに効率よく高速に縮約演算を行うことができる。
【００５８】
〔第４実施形態の変形例２〕
多項式ｒ（ｘ）＝（ｈｎ−１×ｘｎ−１＋・・・＋ｈ０×ｘ０）×ｘｎ＋（ｋｎ−１×ｘｎ−１＋・・・＋ｋ０×ｘ０）の次数が２ｎ−１次未満であることが分かっている場合（すなわち、ｈｎ−１＝・・・＝ｈｎ−ｃ＝０、ｃが１≦ｃ≦ｎの整数の場合）には、テーブル記憶部に格納するテーブルのサイズをさらに縮小できる。
【００５９】
＜構成＞
図３Ａに例示するように、第４実施形態の変形例２の縮約装置４’’は、入力部１１、分割部１２、演算部４４’’、出力部１５、制御部１６、記憶部１７、およびテーブル記憶部４８’’を有する。
【００６０】
［テーブル記憶部４８’’］
テーブル記憶部４８’’は、ｎ個の元γｎ−１，・・・，γ０∈ＧＦ（ｑ）からなるｑｎ−ｃ種類の列γ∈ＧＦ（ｑｎ）に対するγ≫ｎ−ｎ（ｔ−１）によって得られるｑｎ（ｔ−１）−ｃ種類の列のそれぞれに対し、対応する列Γ’＝γ’≪ｎ（１）＋・・・＋γ’≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）を対応付けたテーブルを格納する。ただし、γ’＝γ≫ｎ−ｎ（２）＋・・・＋γ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）であり、ｈｎ−１＝・・・＝ｈｎ−ｃ＝０であり、γｎ−１＝・・・＝γｎ−ｃ＝０である。ｃが１≦ｃ≦ｎの整数であり、ｃの例はｃ＝１である。
【００６１】
＜方法＞
図３Ｂに例示するように、まず第１実施形態で説明したステップＳ１１およびＳ１２が実行される。
【００６２】
次に演算部４４’’に列ｈが入力される。演算部４４’’は、テーブル記憶部４８’’を参照し、ｈ≫ｎ−ｎ（ｔ−１）によって得られる列に対応する列η＝ｈ’≪ｎ（１）＋・・・＋ｈ’≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）（すなわちｈ≫ｎ−ｎ（ｔ−１）に対応する列η）を抽出する。ただし、ｈ’＝ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）である。演算部４４’’にはさらに列ｋが入力され、演算部４４’’は、列ｋ，ｈおよびηを用いて列Ｒ＝ｋ＋ｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１）＋η∈ＧＦ（ｑｎ）を得、列Ｒを出力する（ステップＳ４４’’）。
【００６３】
その後、第１実施形態で説明したＳ１５が実行される。
【００６４】
＜本形態の特徴＞
以上のように、多項式ｒ（ｘ）＝（ｈｎ−１×ｘｎ−１＋・・・＋ｈ０×ｘ０）×ｘｎ＋（ｋｎ−１×ｘｎ−１＋・・・＋ｋ０×ｘ０）の次数が２ｎ−１次未満であることが分かっている場合には、テーブル記憶部４８’’に格納するテーブルのサイズをさらに縮小できる。
【００６５】
〔第５実施形態〕
本形態は第４実施形態の変形例である。ｈｎ−１＝０、ｑ＝２、ｔ＝５、ｎ（４）＝４，ｎ（３）＝３，ｎ（２）＝１，ｎ（１）＝０（例えばｆ０（ｘ）＝ｘ４＋ｘ３＋ｘ＋１）の場合には、第４実施形態で説明した列η＝ｈ’≪ｎ（１）＋・・・＋ｈ’≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）（ただし、ｈ’＝ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ））を効率よく計算することができる。なお、ｑ＝２，ｆ０（ｘ）＝ｘ４＋ｘ３＋ｘ＋１，ｎ＝８，６４，３２０のとき、ｆ（ｘ）＝ｘｎ−ｆ０（ｘ）は既約多項式である。
【００６６】
すなわち、ｎ（４）＝４，ｎ（３）＝３，ｎ（２）＝１，ｎ（１）＝０の場合、列ηは以下のように変形できる。
η＝ｈ’＋ｈ’≪１＋ｈ’≪３＋ｈ’≪４∈ＧＦ（ｑｎ）
＝（ｈ’＋ｈ’≪１）＋（ｈ’＋ｈ’≪１）≪３  …(1)
従って、（ｈ’＋ｈ’≪１）を中間値として計算し、その中間値を用いて列ηを計算することで、演算量を削減できる。
【００６７】
さらに本形態ではｈｎ−１＝０であり、列ｈ≫ｎ−１の要素がすべて０となることを利用し、中間値（ｈ’＋ｈ’≪１）を効率的に計算する。すなわち、本形態の条件の場合、列ｈ’は以下のように変形できる。
ｈ’＝ｈ≫ｎ−１＋ｈ≫ｎ−３＋ｈ≫ｎ−４∈ＧＦ（ｑｎ）
＝ｈ≫ｎ−３＋ｈ≫ｎ−４
【００６８】
従って、（ｈ’＋ｈ’≪１）∈ＧＦ（ｑｎ）は、以下のように変形できる。
（ｈ’＋ｈ’≪１）∈ＧＦ（ｑｎ）
＝（ｈ≫ｎ−３＋ｈ≫ｎ−４）＋（ｈ≫ｎ−３＋ｈ≫ｎ−４）≪１
＝（ｈ≫ｎ−４）≪１＋（ｈ≫ｎ−４＋（ｈ≫ｎ−３）≪１）＋ｈ≫ｎ−３
＝（ｈ≫ｎ−４）≪１＋ｔ０＋ｈ≫ｎ−３  …(2)
ただし、列ｔ０∈ＧＦ（ｑｎ）は、ｎ個の元０，・・・，０，ε０∈ＧＦ（ｑ）からなる列であり、ｈ≫ｎ−４がｎ個の元εｎ−１，・・・，ε０∈ＧＦ（ｑ）からなるとする。
【００６９】
なお、ｑ＝２のときにｔ０＝（ｈ≫ｎ−４＋（ｈ≫ｎ−３）≪１）となることは容易に確認できる。例えばｎ＝６４の場合、列ｈ＝（ａ６３，ａ６２，ａ６１，ａ６０，ａ５９，..，ａ０）とおくと、以下が成り立つ。
ｈ≫ｎ−４＝（０，・・・，０，ａ６３，ａ６２，ａ６１，ａ６０）
ｈ≫ｎ−３＝（０，・・・，０，ａ６３，ａ６２，ａ６１）
（ｈ≫ｎ−３）≪１＝（０，・・・，０，ａ６３，ａ６２，ａ６１，０）
ｔ０＝（ｈ≫ｎ−４＋（ｈ≫ｎ−３）≪１）＝（０，・・・，０，ａ６０）∈ＧＦ（２ｎ）
【００７０】
以上より、式（２）を用いて中間値（ｈ’＋ｈ’≪１）を計算し、中間値を用いて式（１）を計算することで列ηを効率的に得ることができる。
【００７１】
＜構成＞
図１Ａに例示するように、第５実施形態の縮約装置５は、入力部１１、分割部１２、演算部５３（第２〜４演算部）、演算部５４（第１演算部）、出力部１５、制御部１６、および記憶部１７を有する。縮約装置５は、例えば、公知または専用のコンピュータに所定のプログラムが読み込まれることによって構成される特別な装置である。縮約装置５は、制御部１６の制御のもとで各処理を行う。
【００７２】
＜方法＞
図４に例示するように、まず第１実施形態で説明したステップＳ１１およびＳ１２が実行される。
【００７３】
演算部５３には列ｈが入力される。演算部５３は、列ｔ１＝ｈ≫ｎ−４∈ＧＦ（ｑｎ）を得、列ｔ１を出力する。ただし、ｈｎ−１＝０であり、ｔ＝５であり、ｎ（４）＝４，ｎ（３）＝３，ｎ（２）＝１，ｎ（１）＝０である（ステップＳ５３−１）。
【００７４】
演算部５３には列ｔ１，ｈが入力される。演算部５３は、列ｔ２＝ｔ１≪１＋ｔ０＋ｈ≫ｎ−３∈ＧＦ（ｑｎ）を得、列ｔ２を出力する。ただし、ｔ１がｎ個の元εｎ−１，・・・，ε０∈ＧＦ（ｑ）からなり、ｎ個の元０，・・・，０，ε０∈ＧＦ（ｑ）からなる列がｔ０∈ＧＦ（ｑｎ）である。例えば、拡大体ＧＦ（ｑｎ）がビット列の集合｛０，１｝ｎである場合、ｔ０＝ｔ１＆（０，・・・，０，１）∈｛０，１｝ｎを満たす（ステップＳ５３−２）。
【００７５】
演算部５３には列ｔ２が入力される。演算部５３は、列η＝ｔ２＋ｔ２≪３∈ＧＦ（ｑｎ）を得、列ηを出力する（ステップＳ５３−３）。
【００７６】
演算部５４には、列ｋ，ηおよびｈが入力される。演算部５４は、これらを用いて列Ｒ＝ｋ＋ｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１）＋η∈ＧＦ（ｑｎ）を得、列Ｒを出力する（ステップＳ５４）
【００７７】
その後、第１実施形態で説明したＳ１５が実行される。
【００７８】
＜本形態の特徴＞
本形態では、式（２）を用いて中間値（ｈ’＋ｈ’≪１）を計算し、中間値を用いて式（１）を計算することで、演算量を削減できる。
【００７９】
〔第５実施形態の変形例〕
ｔ＝５、ｎ（４）＝４，ｎ（３）＝３，ｎ（２）＝１，ｎ（１）＝０の場合、列ηは以下のように変形できる。
η＝ｈ’＋ｈ’≪１＋ｈ’≪３＋ｈ’≪４∈ＧＦ（ｑｎ）
＝（ｈ’＋ｈ’≪１）＋（ｈ’＋ｈ’≪１）≪３  …(1)
＝（ｈ’＋ｈ’≪３）＋（ｈ’＋ｈ’≪３）≪１  …(3)
【００８０】
従って、演算部５３が、ステップＳ５３−１およびＳ５３−２に代えて、ｈ’＝ｈ≫ｎ−１＋ｈ≫ｎ−３＋ｈ≫ｎ−４∈ＧＦ（ｑｎ）を計算し、ｔ２’＝ｈ’＋ｈ’≪１∈ＧＦ（ｑｎ）またはｔ２’’＝ｈ’＋ｈ’≪３∈ＧＦ（ｑｎ）を計算し、Ｓ５３−３に代えて、η＝ｔ２’＋ｔ２’≪３∈ＧＦ（ｑｎ）またはη＝ｔ２’’＋ｔ２’’≪１を計算してもよい。
【００８１】
〔第６実施形態〕
本形態は第４，５実施形態の変形例である。ｔ＝５、ｎ（４）＝４，ｎ（３）＝３，ｎ（２）＝１，ｎ（１）＝０（例えばｆ０（ｘ）＝ｘ４＋ｘ３＋ｘ＋１）の場合には、列ρ＝ｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）を効率よく計算することができる。
【００８２】
すなわち、ｔ＝５、ｎ（４）＝４，ｎ（３）＝３，ｎ（２）＝１，ｎ（１）＝０の場合、列ρは以下のように変形できる。
ρ＝ｈ＋ｈ≪１＋ｈ≪３＋ｈ≪４∈ＧＦ（ｑｎ）
＝（ｈ＋ｈ≪１）＋（ｈ＋ｈ≪１）≪３  …(4)
＝（ｈ＋ｈ≪３）＋（ｈ＋ｈ≪３）≪１  …(5)
従って、（ｈ＋ｈ≪１）または（ｈ＋ｈ≪３）を中間値として計算し、その中間値を用いて式（４）または式（５）を計算することで、演算量を削減できる。
【００８３】
＜構成＞
図１Ａに例示するように、第６実施形態の縮約装置６は、入力部１１、分割部１２、演算部６３（第５，６演算部）、演算部６４（第１演算部）、出力部１５、制御部１６、および記憶部１７を有する。縮約装置６は、例えば、公知または専用のコンピュータに所定のプログラムが読み込まれることによって構成される特別な装置である。縮約装置６は、制御部１６の制御のもとで各処理を行う。
【００８４】
＜方法＞
図５に例示するように、まず第１実施形態で説明したステップＳ１１およびＳ１２が実行される。
【００８５】
次に演算部６３に列ｈが入力される。演算部６３は、列η＝ｈ’≪ｎ（１）＋・・・＋ｈ’≪ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得、列ηを出力する。ただし、ｈ’＝ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）であり、ｔ＝５であり、ｎ（４）＝４，ｎ（３）＝３，ｎ（２）＝１，ｎ（１）＝０である。列ηの計算方法に限定はない。例えば演算部６３は、列ｈ’＝ｈ≫ｎ−１＋ｈ≫ｎ−３＋ｈ≫ｎ−４∈ＧＦ（ｑｎ）を得てから、列η＝ｈ’＋ｈ’≪１＋ｈ’≪３＋ｈ’≪４∈ＧＦ（ｑｎ）を得てもよいし、第５実施形態で説明した方法で列ηを得てもよい（ステップＳ６３−１）。
【００８６】
演算部６３は、列ｔ３＝ｈ＋ｈ≪１∈ＧＦ（ｑｎ）または列ｔ４＝ｈ＋ｈ≪３∈ＧＦ（ｑｎ）を得、列ｔ３または列ｔ４を出力する（ステップＳ６３−２）。
【００８７】
演算部６３には、列ｔ３または列ｔ４が入力される。演算部６３は、列ρ＝ｔ３＋ｔ３≪３∈ＧＦ（ｑｎ）または列ρ＝ｔ４＋ｔ４≪１∈ＧＦ（ｑｎ）を得、列ρを出力する（ステップＳ６３−３）。
【００８８】
演算部６４に列ｋ，ηおよびρが入力される。演算部６４は、列ηをｈ’＋ｈ’≪１＋ｈ’≪３＋ｈ’≪４とし、列ρをｈ＋ｈ≪１＋ｈ≪３＋ｈ≪４∈ＧＦ（ｑｎ）として用いて列Ｒを得、列Ｒを出力する。すなわち、演算部６４は、列Ｒ＝ｋ＋ρ＋η∈ＧＦ（ｑｎ）を得、列Ｒを出力する（ステップＳ６４）。
【００８９】
その後、第１実施形態で説明したＳ１５が実行される。
【００９０】
＜本形態の特徴＞
本形態では、（ｈ＋ｈ≪１）または（ｈ＋ｈ≪３）を中間値として計算し、その中間値を用いて式（４）または式（５）を計算することで、演算量を削減できる。
【００９１】
〔第７実施形態〕
本形態は第４〜６実施形態の変形例である。ｔ＝５、ｎ（４）＝４，ｎ（３）＝３，ｎ（２）＝１，ｎ（１）＝０（例えばｆ０（ｘ）＝ｘ４＋ｘ３＋ｘ＋１）の場合には、列σ＝（ｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１））＋（ｈ’≪ｎ（１）＋・・・＋ｈ’≪ｎ（ｔ−１））∈ＧＦ（ｑｎ）を効率よく計算することができる場合がある。
【００９２】
すなわち、ｔ＝５、ｎ（４）＝４，ｎ（３）＝３，ｎ（２）＝１，ｎ（１）＝０の場合、列σは以下のように変形できる。
σ＝（ｈ＋ｈ≪１＋ｈ≪３＋ｈ≪４）
＋（ｈ’＋ｈ’≪１＋ｈ’≪３＋ｈ’≪４）∈ＧＦ（ｑｎ）
＝｛（ｈ＋ｈ’）＋（ｈ＋ｈ’）≪１｝
＋｛（ｈ＋ｈ’）＋（ｈ＋ｈ’）≪１｝≪３  …(6)
＝｛（ｈ＋ｈ’）＋（ｈ＋ｈ’）≪３｝
＋｛（ｈ＋ｈ’）＋（ｈ＋ｈ’）≪３｝≪１  …(7)
従って、（ｈ＋ｈ’）を第１中間値として計算し、第１中間値を用いて｛（ｈ＋ｈ’）＋（ｈ＋ｈ’）≪１｝または｛（ｈ＋ｈ’）＋（ｈ＋ｈ’）≪３｝を第２中間値として計算し、第２中間値を用いて式（６）または式（７）を計算することで、演算量を削減できる場合がある。
【００９３】
＜構成＞
図１Ａに例示するように、第７実施形態の縮約装置７は、入力部１１、分割部１２、演算部７３（第２〜４演算部）、演算部７４（第１演算部）、出力部１５、制御部１６、および記憶部１７を有する。縮約装置７は、例えば、公知または専用のコンピュータに所定のプログラムが読み込まれることによって構成される特別な装置である。縮約装置７は、制御部１６の制御のもとで各処理を行う。
【００９４】
＜方法＞
図６に例示するように、まず第１実施形態で説明したステップＳ１１およびＳ１２が実行される。
【００９５】
次に演算部７３に列ｈが入力される。演算部７３は、ｈ’＝ｈ≫ｎ−ｎ（２）＋・・・＋ｈ≫ｎ−ｎ（ｔ−１）∈ＧＦ（ｑｎ）を得、列ｈ’を出力する。ただし、ｔ＝５であり、ｎ（４）＝４，ｎ（３）＝３，ｎ（２）＝１，ｎ（１）＝０である（ステップＳ７３−１）。
【００９６】
演算部７３に列ｈおよびｈ’が入力される。演算部７３は、列ν＝ｈ＋ｈ’ ∈ＧＦ（ｑｎ）を得、列νを出力する（ステップＳ７３−２）。
【００９７】
演算部７３に列νが入力される。演算部７３は、列υ＝ν＋ν≪１∈ＧＦ（ｑｎ）または列ι＝ν＋ν≪３∈ＧＦ（ｑｎ）を得、列υまたはιを出力する（ステップＳ７３−３）。
【００９８】
演算部７３に列υまたはιが入力される。演算部７３は、列σ＝υ＋υ≪３∈ＧＦ（ｑｎ）または列σ＝ι＋ι≪１∈ＧＦ（ｑｎ）を得、列σを出力する（ステップＳ７３−４）。
【００９９】
演算部７４に列ｋ，σが入力される。演算部７４は、列σをｈ≪ｎ（１）＋・・・＋ｈ≪ｎ（ｔ−１）＋η∈ＧＦ（ｑｎ）として用いて列Ｒ＝ｋ＋σ∈ＧＦ（ｑｎ）を得、列Ｒを出力する（ステップＳ７４）。
【０１００】
その後、第１実施形態で説明したＳ１５が実行される。
【０１０１】
＜本形態の特徴＞
本形態では、（ｈ＋ｈ’）を第１中間値として計算し、第１中間値を用いて｛（ｈ＋ｈ’）＋（ｈ＋ｈ’）≪１｝または｛（ｈ＋ｈ’）＋（ｈ＋ｈ’）≪３｝を第２中間値として計算し、第２中間値を用いて式（６）または式（７）を計算することで、演算量を削減できる場合がある。
【０１０２】
〔第８実施形態〕
ｔ＝５，ｎ（４）＝７，ｎ（３）＝２，ｎ（２）＝１，ｎ（１）＝０の場合、すなわち、ｆ０（ｘ）がｆ０（ｘ）＝ｘ７＋ｘ２＋ｘ＋１であり、ｈｎ−１＝０である場合には、以下のように演算を効率化できる。なお、ｑ＝２、ｎ＝１２８，１９２の場合、ｆ（ｘ）＝ｘｎ−ｆ０（ｘ）は既約多項式である。
【０１０３】
すなわち、ｈｎ−１＝０、ｎ（４）＝７，ｎ（３）＝２，ｎ（２）＝１，ｎ（１）＝０である場合、列Ｈは以下のように変形できる。ｈｎ−１＝０であり、列ｈ≫ｎ−１の要素がすべて０となるため、列Ｈは以下のように変形できる。
Ｈ＝ｈ＋ｈ≫ｎ−１＋ｈ≫ｎ−２＋ｈ≫ｎ−７∈ＧＦ（ｑｎ）
＝ｈ＋ｈ≫ｎ−１＋ｈ≫ｎ−２＋ｈ≫ｎ−７
＝ｈ＋ｈ≫ｎ−２＋ｈ≫ｎ−７
従って列Ｒは以下のように計算できる。
Ｒ＝ｋ＋Ｈ＋Ｈ≪１＋Ｈ≪２＋Ｈ≪７∈ＧＦ（ｑｎ）
【０１０４】
図１Ａに例示するように、第８実施形態の縮約装置８は、入力部１１、分割部１２、演算部８３（第１演算部）、演算部１４（第２演算部）、出力部１５、制御部１６、および記憶部１７を有する。縮約装置８は、例えば、公知または専用のコンピュータに所定のプログラムが読み込まれることによって構成される特別な装置である。縮約装置８は、制御部１６の制御のもとで各処理を行う。
【０１０５】
＜方法＞
図７に例示するように、まず第１実施形態で説明したステップＳ１１およびＳ１２が実行される。
【０１０６】
次に演算部８３に列ｈが入力される。演算部８３は、列Ｈ＝ｈ＋ｈ≫ｎ−７＋ｈ≫ｎ−２∈ＧＦ（ｑｎ）を得、列Ｈを出力する（ステップＳ８３）。
【０１０７】
その後、第１実施形態で説明したＳ１４およびＳ１５が実行される。
【０１０８】
＜本形態の特徴＞
本形態では、ｈｎ−１＝０，ｎ（４）＝７，ｎ（３）＝２，ｎ（２）＝１，ｎ（１）＝０である場合に、Ｈ＝ｈ＋ｈ≫ｎ−２＋ｈ≫ｎ−７によって列Ｈを得るため、演算量を削減できる。
【０１０９】
〔その他の変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１１０】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【０１１１】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【０１１３】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【０１１４】
縮約装置  １〜８
【図１】
2014021237.tif 000005
【図２】
2014021237.tif 000006
【図３】
2014021237.tif 000007
【図４】
2014021237.tif 000008
【図５】
2014021237.tif 000009
【図６】
2014021237.tif 000010
【図７】
2014021237.tif 000011
【図８】
2014021237.tif 000012
【図９】
2014021237.tif 000013