(57)【要約】【課題】ｘｉ×ｇ（ｘ） ｍｏｄ ｆ（ｘ）の係数からなる列を効率よく求める。【解決手段】列ＦＬ，０に含まれるｋ個の元ｂｎ−１，．．．，ｂｎ−ｋからなる列ｈを得、ｉ＝１，．．．，ｋについて、ｂｎ−ｉ＝Ｉ１であるｉについて列ＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）＋Ｆ∈ＧＦ（２ｎ）を得、ｂｎ−ｉ＝Ｉ０であるｉについて列ＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）を得る。Ｉ０がガロア体ＧＦ（２）の加法単位元、Ｉ１がＩ１≠Ｉ０であるガロア体ＧＦ（２）の元、ｆ（ｘ）がｎ次既約多項式ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０、Ｆがｎ個の元ｅｎ−１，．．．，ｅ０からなる列、ｅｎ−１＝．．．＝ｅｎ−κ＝Ｉ０であり、ｇ（ｘ）がｎ−１次多項式ｇ（ｘ）＝ｂｎ−１×ｘｎ−１＋．．．＋ｂ０、ＦＬ，０がｎ個の元ｂｎ−１，．．．，ｂ０からなる列である。【選択図】図１
2014029358.tif 000002
【特許請求の範囲】
【請求項１】
ｎが２以上の整数、ιが１以上の整数、κが１以上ｎ未満の整数、ｋが１以上κ以下の整数、ＧＦ（２）が位数２のガロア体、ＧＦ（２ｎ）がガロア体ＧＦ（２）をｎ次拡大したガロア体、Ｉ０が前記ガロア体ＧＦ（２）の加法単位元、Ｉ１がＩ１≠Ｉ０である前記ガロア体ＧＦ（２）の元、α≪ιが前記ガロア体ＧＦ（２）のｎ個の元αｎ−１，．．．，α０からなる列αに対する前記ガロア体ＧＦ（２）のｎ個の元αｎ−１−ι，．．．，α０，Ｉ０，．．．，Ｉ０からなる列、ｘが不定元、ｆ（ｘ）がｎ次既約多項式ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０、ｅｎ，．．．，ｅ０が前記ガロア体ＧＦ（２）のｎ＋１個の元である係数、Ｆがｎ個の元ｅｎ−１，．．．，ｅ０からなる列、ｅｎ−１＝．．．＝ｅｎ−κ＝Ｉ０であり、ｇ（ｘ）がｎ−１次多項式ｇ（ｘ）＝ｂｎ−１×ｘｎ−１＋．．．＋ｂ０、ｂｎ−１，．．．，ｂ０が前記ガロア体ＧＦ（２）のｎ個の元である係数、ＦＬ，０がｎ個の元ｂｎ−１，．．．，ｂ０からなる列であり、
前記列ＦＬ，０に含まれるｋ個の元ｂｎ−１，．．．，ｂｎ−ｋからなる列ｈを得る生成部と、
ｉ＝１，．．．，ｋについて、ｂｎ−ｉ＝Ｉ１であるｉについて列ＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）＋Ｆ∈ＧＦ（２ｎ）を得、ｂｎ−ｉ＝Ｉ０であるｉについて列ＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）を得る演算部と、
を有する演算装置。
【請求項２】
請求項１の演算装置であって、
前記ガロア体ＧＦ（２）のｋ個の元βｎ−１，．．．，βｎ−ｋからなる任意の列βのそれぞれに対し、ｋ個の列γ（βｎ−１），．．．，γ（βｎ−ｋ）の組み合わせを格納したテーブル記憶部をさらに有し、
βｎ−ｉ＝Ｉ０に対する前記列γ（βｎ−ｉ）はｎ個のＩ０からなる列であり、βｎ−ｉ＝Ｉ１に対する前記列γ（βｎ−ｉ）は列Ｆであり、
前記演算部は、前記テーブル記憶部から抽出した、前記列ｈに対応するｋ個の列γ（ｂｎ−１），．．．，γ（ｂｎ−ｋ）からなる組み合わせを用い、ｉ＝１，．．．，ｋについて、列ＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）＋γ（ｂｎ−ｉ）∈ＧＦ（２ｎ）を得る、演算装置。
【請求項３】
請求項１の演算装置であって、
前記ガロア体ＧＦ（２）のｋ個の元βｎ−１，．．．，βｎ−ｋからなる任意の列βのそれぞれに対し、ｋ個の列δ（βｎ−１），．．．，δ（βｎ−ｋ）の組み合わせを格納したテーブル記憶部をさらに有し、
βｎ−ｉ＝Ｉ０に対する前記列δ（βｎ−ｉ）はｎ個のＩ０からなる列であり、βｎ−ｉ＝Ｉ１に対する前記列δ（βｎ−ｉ）は列Ｆ≪ｉ−１であり、Ｆ≪０＝Ｆであり、
前記演算部は、前記テーブル記憶部から抽出した、前記列ｈに対応するｋ個の列δ（ｂｎ−１），．．．，δ（ｂｎ−ｋ）からなる組み合わせを用い、ｉ＝１，．．．，ｋについて、ＦＬ，０＝Ｌ０およびＬｉ＝（Ｌｉ−１≪１）∈ＧＦ（２ｎ）に対する列ＦＬ，ｉ＝Ｌｉ＋δ（ｂｎ−ｉ）∈ＧＦ（２ｎ）を得る、演算装置。
【請求項４】
ｗが２以上の整数、ｄが２以上の整数、ｎ＝ｗ×ｄ、κが１以上ｗ未満の整数、ｋが１以上κ以下の整数、ＧＦ（２）が位数２のガロア体、ＧＦ（２ｎ）がガロア体ＧＦ（２）をｎ次拡大したガロア体、Ｉ０が前記ガロア体ＧＦ（２）の加法単位元、Ｉ１がＩ１≠Ｉ０である前記ガロア体ＧＦ（２）の元、ｘが不定元、ｆ（ｘ）がｎ次既約多項式ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０、ｅｎ，．．．，ｅ０が前記ガロア体ＧＦ（２）のｎ＋１個の元である係数、Ｆがｎ個の元ｅｎ−１，．．．，ｅ０からなる列、ｔ＝ｄ−１，．．．，０についてｅｗ×（ｔ+１）−１＝．．．＝ｅｗ×（ｔ+１）−κ＝Ｉ０であり、ｇ（ｘ）がｎ−１次多項式ｇ（ｘ）＝ｂｎ−１，０×ｘｎ−１＋．．．＋ｂ０，０、ｂｎ−１，０，．．．，ｂ０，０が前記ガロア体ＧＦ（２）のｎ個の元である係数、ＦＬ，０がｎ個の元ｂｎ−１，０，．．．，ｂ０，０からなる列であり、
ｔ＝ｄ−１，．．．，０について、ｗ個の元ｂｗ×（ｔ+１）−１，０，．．．，ｂｗ×ｔ，０からなるワードＸｔ，０に含まれるｋ個の元ｂｗ×（ｔ+１）−１，０，．．．，ｂｗ×（ｔ+１）−ｋ，０からなる列ｈｔを得る生成部と、
ｔ＝ｄ−１，．．．，０について、前記ガロア体ＧＦ（２）のｎ個の元ｂｎ−１，ｉ−１，．．．，ｂ０，ｉ−１からなる列ＦＬ，ｉ−１に含まれるｗ個の元ｂｗ×（ｔ+１）−１，ｉ−１，．．．，ｂｗ×ｔ，ｉ−１からなるワードＸｔ，ｉ−１ごとに、ｗ個の元ｂｗ×（ｔ+１）−２，ｉ−１，．．．，ｂｗ×ｔ，ｉ−１，Ｉ０からなるシフトワードＳｔ，ｉを得、ｄ個の前記シフトワードＳｄ−１，ｉ，．．．，Ｓ０，ｉからなるシフト列Ｓｉを得る第１演算部と、
抽出値ｃｔ，ｉが前記列ｈｔに含まれる元ｂｗ×（ｔ+１）−ｉ，０であり、ｊ＝ｄ−２，．．．，０であり、Ｋｊ，ｉが前記ガロア体ＧＦ（２）のｎ個の元ｋｊ，ｎ−１，ｉ，．．．，ｋｊ，０，ｉからなる列、前記列Ｋｊ，ｉに含まれる元ｋｊ，ｗ×（ｊ＋１），ｉが前記抽出値ｃｊ，ｉ、前記列Ｋｊ，ｉに含まれる元ｋｊ，ｗ×（ｊ＋１），ｉ以外の元が前記加法単位元Ｉ０、前記抽出値ｃｄ−１，ｉが前記加法単位元Ｉ０である場合のＨｉがｎ個の前記加法単位元Ｉ０からなる列、前記抽出値ｃｄ−１，ｉが前記元Ｉ１である場合のＨｉが前記列Ｆ、フィードバック列が
【数３】
2014029358.tif 000005
を満たす列であり、前記シフト列Ｓｉと前記フィードバック列Ｍ［ｃｄ−１,ｉ，．．．，ｃ０,ｉ］とに対する列Ｓｉ＋Ｍ［ｃｄ−１,ｉ，．．．，ｃ０,ｉ］∈ＧＦ（２ｎ）を前記列ＦＬ，ｉとして得る第２演算部と、を有し
前記第１演算部の処理と前記第２演算部の処理とがｉ＝１，．．．，ｋについて実行される、演算装置。
【請求項５】
請求項４の演算装置であって、
予め得られた前記フィードバック列Ｍ［ｃｄ−１,ｉ，．．．，ｃ０,ｉ］を格納したテーブル記憶部をさらに有し、
前記第２演算部は、前記テーブル記憶部に格納された前記フィードバック列Ｍ［ｃｄ−１,ｉ，．．．，ｃ０,ｉ］を用いて前記列ＦＬ，ｉを得る、演算装置。
【請求項６】
ｎが２以上の整数、ιが１以上の整数、κが１以上ｎ未満の整数、ｋが１以上κ以下の整数、ＧＦ（２）が位数２のガロア体、ＧＦ（２ｎ）がガロア体ＧＦ（２）をｎ次拡大したガロア体、Ｉ０が前記ガロア体ＧＦ（２）の加法単位元、Ｉ１がＩ１≠Ｉ０である前記ガロア体ＧＦ（２）の元、α≪ιが前記ガロア体ＧＦ（２）のｎ個の元αｎ−１，．．．，α０からなる列αに対する前記ガロア体ＧＦ（２）のｎ個の元αｎ−１−ι，．．．，α０，Ｉ０，．．．，Ｉ０からなる列、ｘが不定元、ｆ（ｘ）がｎ次既約多項式ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０、ｅｎ，．．．，ｅ０が前記ガロア体ＧＦ（２）のｎ＋１個の元である係数、Ｆがｎ個の元ｅｎ−１，．．．，ｅ０からなる列、ｅｎ−１＝．．．＝ｅｎ−κ＝Ｉ０であり、ｇ（ｘ）がｎ−１次多項式ｇ（ｘ）＝ｂｎ−１×ｘｎ−１＋．．．＋ｂ０、ｂｎ−１，．．．，ｂ０が前記ガロア体ＧＦ（２）のｎ個の元である係数、ＦＬ，０がｎ個の元ｂｎ−１，．．．，ｂ０からなる列であり、
生成部で、前記列ＦＬ，０に含まれるｋ個の元ｂｎ−１，．．．，ｂｎ−ｋからなる列ｈを得るステップと、
演算部で、ｉ＝１，．．．，ｋについて、ｂｎ−ｉ＝Ｉ１であるｉについて列ＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）＋Ｆ∈ＧＦ（２ｎ）を得、ｂｎ−ｉ＝Ｉ０であるｉについて列ＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）を得るステップと、
を有する演算方法。
【請求項７】
ｗが２以上の整数、ｄが２以上の整数、ｎ＝ｗ×ｄ、κが１以上ｗ未満の整数、ｋが１以上κ以下の整数、ＧＦ（２）が位数２のガロア体、ＧＦ（２ｎ）がガロア体ＧＦ（２）をｎ次拡大したガロア体、Ｉ０が前記ガロア体ＧＦ（２）の加法単位元、Ｉ１がＩ１≠Ｉ０である前記ガロア体ＧＦ（２）の元、ｘが不定元、ｆ（ｘ）がｎ次既約多項式ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０、ｅｎ，．．．，ｅ０が前記ガロア体ＧＦ（２）のｎ＋１個の元である係数、Ｆがｎ個の元ｅｎ−１，．．．，ｅ０からなる列、ｔ＝ｄ−１，．．．，０についてｅｗ×（ｔ+１）−１＝．．．＝ｅｗ×（ｔ+１）−κ＝Ｉ０であり、ｇ（ｘ）がｎ−１次多項式ｇ（ｘ）＝ｂｎ−１，０×ｘｎ−１＋．．．＋ｂ０，０、ｂｎ−１，０，．．．，ｂ０，０が前記ガロア体ＧＦ（２）のｎ個の元である係数、ＦＬ，０がｎ個の元ｂｎ−１，０，．．．，ｂ０，０からなる列であり、
生成部で、ｔ＝ｄ−１，．．．，０について、ｗ個の元ｂｗ×（ｔ+１）−１，０，．．．，ｂｗ×ｔ，０からなるワードＸｔ，０に含まれるｋ個の元ｂｗ×（ｔ+１）−１，０，．．．，ｂｗ×（ｔ+１）−ｋ，０からなる列ｈｔを得る生成ステップと、
第１演算部で、ｔ＝ｄ−１，．．．，０について、前記ガロア体ＧＦ（２）のｎ個の元ｂｎ−１，ｉ−１，．．．，ｂ０，ｉ−１からなる列ＦＬ，ｉ−１に含まれるｗ個の元ｂｗ×（ｔ+１）−１，ｉ−１，．．．，ｂｗ×ｔ，ｉ−１からなるワードＸｔ，ｉ−１ごとに、ｗ個の元ｂｗ×（ｔ+１）−２，ｉ−１，．．．，ｂｗ×ｔ，ｉ−１，Ｉ０からなるシフトワードＳｔ，ｉを得、ｄ個の前記シフトワードＳｄ−１，ｉ，．．．，Ｓ０，ｉからなるシフト列Ｓｉを得る第１演算ステップと、
抽出値ｃｔ，ｉが前記列ｈｔに含まれる元ｂｗ×（ｔ+１）−ｉ，０であり、ｊ＝ｄ−２，．．．，０であり、Ｋｊ，ｉが前記ガロア体ＧＦ（２）のｎ個の元ｋｊ，ｎ−１，ｉ，．．．，ｋｊ，０，ｉからなる列、前記列Ｋｊ，ｉに含まれる元ｋｊ，ｗ×（ｊ＋１），ｉが前記抽出値ｃｊ，ｉ、前記列Ｋｊ，ｉに含まれる元ｋｊ，ｗ×（ｊ＋１），ｉ以外の元が前記加法単位元Ｉ０、前記抽出値ｃｄ−１，ｉが前記加法単位元Ｉ０である場合のＨｉがｎ個の前記加法単位元Ｉ０からなる列、前記抽出値ｃｄ−１，ｉが前記元Ｉ１である場合のＨｉが前記列Ｆ、フィードバック列が
【数４】
2014029358.tif 000006
を満たす列であり、第２演算部で、前記シフト列Ｓｉと前記フィードバック列Ｍ［ｃｄ−１,ｉ，．．．，ｃ０,ｉ］とに対する列Ｓｉ＋Ｍ［ｃｄ−１,ｉ，．．．，ｃ０,ｉ］∈ＧＦ（２ｎ）を前記列ＦＬ，ｉとして得る第２演算ステップと、を有し
前記第１演算ステップと前記第２演算ステップとがｉ＝１，．．．，ｋについて実行される、演算方法。
【請求項８】
請求項１から５の何れかの演算装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、線形フィードバックシフトを行う演算技術に関する。
【背景技術】
【０００２】
データを秘匿また改竄検知のためには暗号技術が有効である。暗号技術にはいわゆるＲＳＡ暗号を利用した非対称鍵技術およびＡＥＳなどをはじめとする共通鍵暗号を利用した対称鍵技術がある。非対称鍵技術は鍵の取扱が容易である利点があるものの、速度の面からは圧倒的に対称鍵技術が有利である。実際、大量のデータの秘匿や改竄検知を目的としてＡＥＳを利用した暗号利用モードが多く利用されており、ＳＳＬなどで実用化されている。
【０００３】
暗号利用モードは共通鍵ブロック暗号を単純な演算で組み合わせて、もともと共通鍵ブロック暗号では１ブロック（ＡＥＳでは１２８ビット）の暗号化しか出来なかったものを、多ブロックの暗号化処理や改竄検知（メッセージ認証）などの機能を追加する方法である。従来、守秘機能を実現するＣＦＢモードや、メッセージ認証を実現するＣＢＣ−ＭＡＣといった方法が知られていたが、高い安全性を示せないという問題があった。
【０００４】
その後、認証暗号モードＯＣＢ、ＭＡＣモードＰＭＡＣ、ディスク暗号ＸＴＳといった方法が提案され、高い安全性が示されるようになった。これらの暗号利用モードではガロア体ＧＦ（２ｎ）上の演算が使われている。ただしｎは１以上の整数である。ガロア体ＧＦ（２ｎ）の元は、例えば以下のｎ−１次多項式で表現でき（最高次数が加法単位元（零元）であるｎ−１次多項式も含む）、さらには当該ｎ−１次多項式のｎ個の係数からなるガロア体ＧＦ（２）の元の列（ベクトル）でも表現できる。
ＧＦ（２）［ｘ］／（ｆ（ｘ））      (1)
ただし、ＧＦ（２）［ｘ］はガロア体ＧＦ（２）の元を係数とする多項式の集合、ｘは不定元、ｆ（ｘ）はガロア体ＧＦ（２）上のｎ次既約多項式、ρ／（ε）はεを法としたρの剰余の集合を表す。
【０００５】
ここで式(1)のように表現されるガロア体ＧＦ（２ｎ）の元をｘ倍する演算を「２倍算」と呼ぶ。すなわち、以下を「２倍算」と呼ぶ。
ｘ×γ∈ＧＦ（２）［ｘ］／（ｆ（ｘ））      (2)
ただし、ｘ，γ∈ＧＦ（２）［ｘ］／（ｆ（ｘ））である。
これを「２倍算」と呼ぶのは、ガロア体ＧＦ（２）の元の集合を整数集合｛０，１｝とみなし、ｘをｎ−１次多項式とみなした場合、ｎ−１次多項式ｘの係数からなる列は００...０１０となり、これを二進数表記された「１０」とみなし、それを十進数表記に変換すると「２」になることに基づく。このような「２倍算」は上記モードなど多くのモードで使用されている。
【０００６】
以下に「２倍算」を行うための従来のアルゴリズム（Ａｌｇｏｒｉｔｈｍ１）を例示する（例えば、非特許文献１等参照）。このアルゴリズムでは、２を法とした剰余演算上で四則演算が定義された有限集合でガロア体ＧＦ（２）を実装（以下「ビット実装」）し、ｎ−１次多項式ｇ（ｘ）＝ｂｎ−１×ｘｎ−１＋．．．＋ｂ０、ｂｎ−１，．．．，ｂ０（ただしｂｎ−１，...，ｂ０∈ＧＦ（２））に対するｘ×ｇ（ｘ） ｍｏｄ ｆ（ｘ）の係数からなる列Ｙを求める。ここで、ｎ次既約多項式ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０の係数ｅｎ，．．．，ｅ０∈ＧＦ（２）のうち、係数ｅｎ−１，．．．，ｅ０からなる列をＦとする。また、ｎ−１次多項式ｇ（ｘ）の係数ｂｎ−１，．．．，ｂ０からなる列をＬとする。
【０００７】
［Ａｌｇｏｒｉｔｈｍ］
入力：Ｌ
出力：Ｙ
１：ｉｆ  ｂｎ−１＝１  ｔｈｅｎ
２：Ｙ←（Ｌ≪１）＋Ｆ∈ＧＦ（２ｎ）
３：ｅｌｓｅ
４：Ｙ←（Ｌ≪１）∈ＧＦ（２ｎ）
５：ｅｎｄ  ｉｆ
ただし、α≪ρはαに対する左ρシフト演算を表し、ρ←εはεをρに代入することを表す。「２倍算」をｉ（ｉ＝１，．．．，ｋ）回実行してｘｉ×ｇ（ｘ） ｍｏｄ ｆ（ｘ）の係数からなる列を順次求める場合には、列Ｙを新たな列Ｌとして［Ａｌｇｏｒｉｔｈｍ］をｉ回実行すればよい。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Ted Krovetz and Phillip Rogaway, “The Software Performance of Authenticated Encryption Modes,” Fast Software Encryption 2011 (FSE 2011).
【発明の概要】
【発明が解決しようとする課題】
【０００９】
一般に、列Ｙを新たな列Ｌとして［Ａｌｇｏｒｉｔｈｍ］を繰り返す場合、ｉ−１回目に［Ａｌｇｏｒｉｔｈｍ］を実行して列Ｙを得た後でないと、ｉ回目に［Ａｌｇｏｒｉｔｈｍ］を実行するための条件分岐処理に必要なｂｎ−１を得ることができない。そのため、列Ｙを新たな列Ｌとして［Ａｌｇｏｒｉｔｈｍ］をｉ回実行するためには、［Ａｌｇｏｒｉｔｈｍ］を１回実行するたびに、次の［Ａｌｇｏｒｉｔｈｍ］での条件分岐処理に必要なｂｎ−１を記憶部に格納しなければならず、効率が悪い。
【００１０】
本発明はこのような点に鑑みてなされたものであり、ｘｉ×ｇ（ｘ） ｍｏｄ ｆ（ｘ）の係数からなる列を効率よく求めることが可能な技術を提供する。
【課題を解決するための手段】
【００１１】
入力列ＦＬ，０に含まれるｋ個の元ｂｎ−１，．．．，ｂｎ−ｋからなる列ｈを得、ｉ＝１，．．．，ｋについて、ｂｎ−ｉ＝Ｉ１であるｉについて列ＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）＋Ｆ∈ＧＦ（２ｎ）を得、ｂｎ−ｉ＝Ｉ０であるｉについて列ＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）を得る。ただし、ｎが２以上の整数、ιが１以上の整数、κが１以上ｎ未満の整数、ｋが１以上κ以下の整数、ＧＦ（２）が位数２のガロア体、ＧＦ（２ｎ）がガロア体ＧＦ（２）をｎ次拡大したガロア体、Ｉ０がガロア体ＧＦ（２）の加法単位元、Ｉ１がＩ１≠Ｉ０であるガロア体ＧＦ（２）の元、α≪ιがガロア体ＧＦ（２）のｎ個の元αｎ−１，．．．，α０からなる列αに対するガロア体ＧＦ（２）のｎ個の元αｎ−１−ι，．．．，α０，Ｉ０，．．．，Ｉ０からなる列、ｘが不定元、ｆ（ｘ）がｎ次既約多項式ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０、ｅｎ，．．．，ｅ０がガロア体ＧＦ（２）のｎ＋１個の元である係数、Ｆがｎ個の元ｅｎ−１，．．．，ｅ０からなる列、ｅｎ−１＝．．．＝ｅｎ−κ＝Ｉ０であり、ｇ（ｘ）がｎ−１次多項式ｇ（ｘ）＝ｂｎ−１×ｘｎ−１＋．．．＋ｂ０、ｂｎ−１，．．．，ｂ０がガロア体ＧＦ（２）のｎ個の元である係数、ＦＬ，０がｎ個の元ｂｎ−１，．．．，ｂ０からなる列である。
【発明の効果】
【００１２】
ｂｎ−ｉに応じてＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）＋ＦであるかＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）であるかが異なるが、ｅｎ−１＝．．．＝ｅｎ−κ＝Ｉ０であるため、すべてのｂｎ−ｉ（ｉ＝１，．．．，ｋ）は初期の列ＦＬ，０に含まれる。そのため、記憶部へのｂｎ−ｉの格納回数を削減でき、ｘｉ×ｇ（ｘ） ｍｏｄ ｆ（ｘ）の係数からなる列を効率よく求めることができる。
【図面の簡単な説明】
【００１３】
【図１】第１実施形態の演算装置を例示するためのブロック図。
【図２】第１実施形態の演算方法を例示するためのフロー図。
【図３】第２実施形態の演算装置を例示するためのブロック図。
【図４】第２実施形態の演算方法を例示するためのフロー図。
【図５】第３実施形態の演算装置を例示するためのブロック図。
【図６】第３実施形態の演算方法を例示するためのフロー図。
【図７】第４実施形態の演算装置を例示するためのブロック図。
【図８】第４実施形態の演算方法を例示するためのフロー図。
【発明を実施するための形態】
【００１４】
以下、図面を参照して実施形態を説明する。
〔定義〕
用語および記号を定義する。
ＧＦ（２）は位数２のガロア体（有限体）を表し、ＧＦ（２ｎ）はガロア体ＧＦ（２）をｎ次拡大したガロア体（拡大体）を表す。例えばビット実装の場合には、ＧＦ（２）がビット集合｛０，１｝であり、ＧＦ（２ｎ）がｎビットのビット列の集合｛０，１｝ｎである。ただしｎは２以上の整数であり、ｎの例はｎ＝８，６４，１２８などである。
【００１５】
Ｉ０はガロア体ＧＦ（２）の加法単位元であり、Ｉ１はＩ１≠Ｉ０であるガロア体ＧＦ（２）の元である。例えばビット実装の場合には、Ｉ０＝０，Ｉ１＝１である。
【００１６】
α≪ιはｎ個の元αｎ−１，．．．，α０∈ＧＦ（２）からなる列α∈ＧＦ（２ｎ）に対する左ιシフト演算を表す。ただし、ιが１以上の整数である。すなわち、α≪ιはガロア体ＧＦ（２）のｎ個の元αｎ−１，．．．，α０からなる列αに対し、ガロア体ＧＦ（２）のｎ個の元αｎ−１−ι，．．．，α０，Ｉ０，．．．，Ｉ０からなる列を得る操作を表す。列αに対する左ιシフト演算結果もα≪ιと表す。なお、左ιシフト演算は、シフト命令によって実行されてもよいし、ｎ個のガロア体ＧＦ（２）の元からなる列を整数とみた場合の加算命令（自分自身への繰り上がりがある加算演算命令）の組み合わせによって実行されてもよい。またα≪０は無操作を表し、α≪０のための処理や構成は不要である。
【００１７】
ν＋η∈ＧＦ（２ｎ）は、列ν，η∈ＧＦ（２ｎ）のガロア体ＧＦ（２ｎ）上での加算を表す。ビット実装の場合、ν＋η∈ＧＦ（２ｎ）はν（＋）η∈｛０，１｝ｎとなる。ただし、ν（＋）ηは、ｎ個のビットνｎ−１，．．．，ν０∈｛０，１｝からなるビット列νとｎ個のビットηｎ−１，．．．，η０∈｛０，１｝からなるビット列η∈｛０，１｝ｎとのビットごとの排他的論理和演算
【数１】
2014029358.tif 000003
を表す。
【００１８】
ｆ（ｘ）はｎ次既約多項式ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０を表す。ただし、ｘは不定元であり、ｅｎ，．．．，ｅ０はガロア体ＧＦ（２）のｎ＋１個の元であり、ｎ次既約多項式ｆ（ｘ）の係数である。Ｆはｎ次既約多項式ｆ（ｘ）の最高次数を除いた多項式のｎ個の係数からなる列である。言い換えると、Ｆはｎ個の元ｅｎ−１，．．．，ｅ０からなる列である。本形態ではｅｎ−１＝．．．＝ｅｎ−κ＝Ｉ０を満たすｎ次既約多項式ｆ（ｘ）を用いる。ただし、κは１以上ｎ未満の整数である。このようなｎ次既約多項式ｆ（ｘ）は多用されており、このようなｎ次既約多項式ｆ（ｘ）の選択は容易である。例えば、ｎ＝１２８の場合、ビット実装されたｎ次既約多項式としてｆ（ｘ）＝ｘ１２８＋ｘ７＋ｘ２＋ｘ＋１を選ぶことができ、この場合、Ｆ＝０...０１００００１１１（２）であり、Ｆの上位１２０ビットは０である。
【００１９】
ｇ（ｘ）はｎ−１次多項式ｇ（ｘ）＝ｂｎ−１×ｘｎ−１＋．．．＋ｂ０である。ただし、ｂｎ−１，．．．，ｂ０はガロア体ＧＦ（２）のｎ個の元であり、ｎ−１次多項式ｇ（ｘ）の係数である。
【００２０】
〔第１実施形態〕
＜構成＞
図１に例示するように、本形態の演算装置１は、入力部１１、出力部１２、記憶部１３、制御部１４、生成部１５、判定部１６、および演算部１７を有する。演算装置１は、例えば、公知または専用のコンピュータに所定のプログラムが読み込まれることで構成される特別な装置である。例えば、生成部１５および判定部１６は汎用演算器を含み、演算部１７はＳＩＭＤ（Single instruction, multiple data）演算器を含み、記憶部１３はＳＩＭＤレジスタおよび汎用レジスタを含む。演算装置１の各部は、制御部１４の制御に基づいて各処理を実行する。入力部１１に入力されたデータおよび各部から出力されたデータは記憶部１３に格納される。各部には記憶部１３から読み出されたデータが入力される。各部は入力されたデータを用いて各処理を実行する。
【００２１】
＜方法＞
本形態の演算装置１は、ｎ個の元ｂｎ−１，．．．，ｂ０からなる列ＦＬ，０を入力とし、各ｉ＝１，．．．，ｋに対するｘｉ×ｇ（ｘ） ｍｏｄ ｆ（ｘ）の係数からなる列ＦＬ，ｉを得て出力する。
【００２２】
図２に例示するように、まず、入力部１１にｎ個の元ｂｎ−１，．．．，ｂ０からなる列ＦＬ，０、および１以上κ以下の整数ｋが入力される。元ｂｎ−１，．．．，ｂ０および整数ｋは記憶部１３に格納される。例えば、元ｂｎ−１，．．．，ｂ０は記憶部１３のＳＩＭＤレジスタに格納され、整数ｋは汎用レジスタに格納される（ステップＳ１１）。
【００２３】
生成部１５は、整数ｋを入力とし、記憶部１３から列ＦＬ，０に含まれるｋ個の元ｂｎ−１，．．．，ｂｎ−ｋを抽出し、それらの元ｂｎ−１，．．．，ｂｎ−ｋからなる列ｈを得て出力する。例えばビット実装の場合、生成部１５は列ＦＬ，０の上位ｋビットからなる列ｈを得て出力する。列ｈは記憶部１３に格納される。例えば、列ｈは記憶部１３の汎用レジスタに格納される（ステップＳ１２）。
【００２４】
制御部１４はｉ＝１に設定する（ステップＳ１３）。
【００２５】
判定部１６は、ｉを入力とし、記憶部１３に格納された列ｈから元ｂｎ−ｉを抽出し、元ｂｎ−ｉ＝Ｉ１であるかを判定する（ステップＳ１４）。
ｂｎ−ｉ＝Ｉ１である場合、判定部１６は演算部１７にステップＳ１５の処理を行う旨の指示を与え、演算部１７は列ＦＬ，ｉ−１を入力とし、列ＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）＋Ｆ∈ＧＦ（２ｎ）を得て出力する。得られた列ＦＬ，ｉは記憶部１３に格納される。例えば、列ＦＬ，ｉは記憶部１３のＳＩＭＤレジスタに格納される（ステップＳ１５）。
ｂｎ−ｉ≠Ｉ１である場合、すなわちｂｎ−ｉ＝Ｉ０である場合、判定部１６は演算部１７にステップＳ１６の処理を行う旨の指示を与え、演算部１７は列ＦＬ，ｉ−１を入力とし、列ＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）∈ＧＦ（２ｎ）を得て出力する。得られた列ＦＬ，ｉは記憶部１３に格納される。例えば、列ＦＬ，ｉは記憶部１３のＳＩＭＤレジスタに格納される（ステップＳ１６）。
【００２６】
次に制御部１４はｉ＝ｋであるかを判定する（ステップＳ１７）。制御部１４がｉ＝ｋでないと判定した場合、制御部１４はｉを１増加させた値を新たなｉとし（ステップＳ１８）、処理をステップＳ１４に戻す。制御部１４がｉ＝ｋであると判定した場合、出力部１２は記憶部１３に格納された列ＦＬ，ｉ（ｉ＝１，．．．，ｋ）を出力する（ステップＳ１９）。
【００２７】
＜本形態の特徴＞
本形態では、条件分岐処理の指標であるｂｎ−ｉに応じてＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）＋ＦまたはＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）が実行される。ここでｅｎ−１＝．．．＝ｅｎ−κ＝Ｉ０であるため、すべてのｂｎ−ｉ（ｉ＝１，．．．，ｋ）はステップＳ１２で一度に得られる。そのため、ｂｎ−ｉ（ｉ＝１，．．．，ｋ）の記憶部１３への格納回数はステップＳ１２での１回のみである。これに対し、前述のように従来の［Ａｌｇｏｒｉｔｈｍ］をｋ回繰り返し実行して各ｉ＝１，．．．，ｋに対する列ＦＬ，ｉを得る場合には、条件分岐処理の指標となる最高次数の元（［Ａｌｇｏｒｉｔｈｍ］でのｂｎ−１）の記憶部への格納回数はｋ回となる。このように、本形態では条件分岐処理の指標の記憶部への格納回数を従来の１／ｋにすることができる。
【００２８】
〔第２実施形態〕
前述のように、ｂｎ−ｉ＝Ｉ１であるｉでの列ＦＬ，ｉはＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）＋Ｆ∈ＧＦ（２ｎ）を満たし、ｂｎ−ｉ＝Ｉ０であるｉでの列ＦＬ，ｉはＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）∈ＧＦ（２ｎ）を満たす。そのため、ｂｎ−ｉの値に応じ、列ＦＬ，ｉを得るために（ＦＬ，ｉ−１≪１）に加算（ガロア体ＧＦ（２ｎ）上での加算）される列（加算列）が異なる（Ｆまたはｎ個のＩ０からなる列）。第２実施形態では、ｋ個の元ｂｎ−１，．．．，ｂｎ−ｋからなる列ｈに対応するｋ個の加算列の組み合わせを事前に得ておき、さらなる演算の効率化を図る。以下では第１実施形態の相違点を説明し、第１実施形態と共通する部分については第１実施形態で用いた参照記号を用い、説明を省略する。
【００２９】
＜構成＞
図３に例示するように、本形態の演算装置２は、入力部１１、出力部１２、記憶部１３、制御部１４、生成部１５、演算部２７、およびテーブル記憶部２８を有する。演算装置２は、例えば、公知または専用のコンピュータに所定のプログラムが読み込まれることで構成される特別な装置である。例えば、演算部２７はＳＩＭＤ演算器を含み、テーブル記憶部２８はＲＡＭ（Random Access Memory）やハードディスクなどを含む。演算装置２の各部は、制御部１４の制御に基づいて各処理を実行する。
【００３０】
図３に例示するように、テーブル記憶部２８は、ガロア体ＧＦ（２）のｋ個の元βｎ−１，．．．，βｎ−ｋからなる任意の列βのそれぞれに対し、ｋ個の列γ（βｎ−１），．．．，γ（βｎ−ｋ）の組み合わせγからなるテーブルを格納する。ただし、βｎ−ｉ＝Ｉ０に対する列γ（βｎ−ｉ）はｎ個のＩ０からなる列であり、βｎ−ｉ＝Ｉ１に対する列γ（βｎ−ｉ）は列Ｆである。ｋ個の元βｎ−１，．．．，βｎ−ｋからなる列βは２ｋ種類存在する。テーブル記憶部２８は、２ｋ種類の列βにそれぞれ対応する組み合わせγを格納し、指定された特定の列βに対応する組み合わせγを返す。
【００３１】
＜方法＞
本形態の演算装置２は、テーブル記憶部２８から抽出した、列ｈに対応するｋ個の列γ（ｂｎ−１），．．．，γ（ｂｎ−ｋ）からなる組み合わせを用い、ｉ＝１，．．．，ｋについて、列ＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）＋γ（ｂｎ−ｉ）∈ＧＦ（２ｎ）を得る点で第１実施形態と相違する。
【００３２】
図４に例示するように、本形態では、まず第１実施形態で説明したステップＳ１１およびＳ１３が実行される。
【００３３】
次に演算部２７は、記憶部１３から抽出した列ｈを入力とし、テーブル記憶部２８から列ｈに対応するｋ個の列γ（ｂｎ−１），．．．，γ（ｂｎ−ｋ）からなる組み合わせを抽出する。列γ（ｂｎ−１），．．．，γ（ｂｎ−ｋ）は記憶部１３に格納される。例えば、列γ（ｂｎ−１），．．．，γ（ｂｎ−ｋ）は記憶部１３のＳＩＭＤレジスタに格納される。演算部２７は、記憶部１３から抽出した列ＦＬ，ｉ−１および列γ（ｂｎ−ｉ）を入力とし、列ＦＬ，ｉ＝（ＦＬ，ｉ−１≪１）＋γ（ｂｎ−ｉ）∈ＧＦ（２ｎ）を得て出力する。列ＦＬ，ｉは記憶部１３に格納される。例えば、列ＦＬ，ｉは記憶部１３のＳＩＭＤレジスタに格納される（ステップＳ２５）。
【００３４】
次に制御部１４はｉ＝ｋであるかを判定する（ステップＳ１７）。制御部１４がｉ＝ｋでないと判定した場合、制御部１４はｉを１増加させた値を新たなｉとし（ステップＳ１８）、処理をステップＳ２５に戻す。制御部１４がｉ＝ｋであると判定した場合、出力部１２は記憶部１３に格納された列ＦＬ，ｉ（ｉ＝１，...，ｋ）を出力する（ステップＳ１９）。
【００３５】
＜本形態の特徴＞
本形態では、各列ｈに対してそれぞれ対応するｋ個の加算列の組み合わせを事前に得ておき、それを用いて列ＦＬ，ｉを得るため、条件分岐処理が不要である。ＳＩＭＤ演算では、処理対象のビット列に対して複数個のビットからなるワードごとに独立に同じ演算を施すため一般に高速であるが、条件分岐処理には適していない。本形態では条件分岐処理が不要であるため、高速なＳＩＭＤ演算を用いて「２倍算」の計算が可能である。
【００３６】
〔第３実施形態〕
本形態では前述の加算列を左シフトして得られる列（シフト加算列）を事前に得ておき、シフト加算列を用いて列ＦＬ，ｉを得る。これにより、さらなる演算の効率化を図る。以下では第１実施形態の相違点を説明し、第１実施形態と共通する部分については第１実施形態で用いた参照記号を用い、説明を省略する。
【００３７】
＜構成＞
図５に例示するように、本形態の演算装置３は、入力部１１、出力部１２、記憶部１３、制御部１４、生成部１５、演算部３６，３７、およびテーブル記憶部３８を有する。演算装置３は、例えば、公知または専用のコンピュータに所定のプログラムが読み込まれることで構成される特別な装置である。例えば、演算部３６，３７はＳＩＭＤ演算器を含み、テーブル記憶部３８はＲＡＭやハードディスクなどを含む。演算装置３の各部は、制御部１４の制御に基づいて各処理を実行する。
【００３８】
図５に例示するように、テーブル記憶部３８は、ガロア体ＧＦ（２）のｋ個の元βｎ−１，．．．，βｎ−ｋからなる任意の列βのそれぞれに対し、ｋ個の列δ（βｎ−１），．．．，δ（βｎ−ｋ）の組み合わせδからなるテーブルを格納する。ただし、βｎ−ｉ＝Ｉ０に対する列δ（βｎ−ｉ）はｎ個のＩ０からなる列であり、βｎ−ｉ＝Ｉ１に対する列δ（βｎ−ｉ）は列Ｆ≪ｉ−１であり、Ｆ≪０＝Ｆである。テーブル記憶部３８は、２ｋ種類の列βにそれぞれ対応する組み合わせγを格納し、指定された特定の列βに対応する組み合わせδを返す。
【００３９】
＜方法＞
本形態の演算装置３は、テーブル記憶部３８から抽出した、列ｈに対応するｋ個の列δ（ｂｎ−１），．．．，δ（ｂｎ−ｋ）からなる組み合わせを用い、ｉ＝１，．．．，ｋについて、ＦＬ，０＝Ｌ０およびＬｉ＝（Ｌｉ−１≪１）∈ＧＦ（２ｎ）に対する列ＦＬ，ｉ＝Ｌｉ＋δ（ｂｎ−ｉ）∈ＧＦ（２ｎ）を得る点で第１実施形態と相違する。
【００４０】
図４に例示するように、本形態では、まず第１実施形態で説明したステップＳ１１およびＳ１３が実行される。
【００４１】
次に演算部３６は、記憶部１３から抽出した列Ｌｉ−１を入力とし、列Ｌｉ＝（Ｌｉ−１≪１）∈ＧＦ（２ｎ）を得て出力する。列Ｌｉは記憶部１３に格納される。例えば、列Ｌｉは記憶部１３のＳＩＭＤレジスタに格納される。ただしＦＬ，０＝Ｌ０である（ステップＳ３１）。
【００４２】
次に制御部１４はｉ＝ｋであるかを判定する（ステップＳ１７）。制御部１４がｉ＝ｋでないと判定した場合、制御部１４はｉを１増加させた値を新たなｉとし（ステップＳ１８）、処理をステップＳ３１に戻す。制御部１４がｉ＝ｋであると判定した場合、制御部１４はｉ＝１に設定し（ステップＳ３２）、ステップＳ３３の処理を実行させる。
【００４３】
ステップＳ３３では、演算部３７が記憶部１３から抽出した列ｈを入力とし、テーブル記憶部３８から列ｈに対応するｋ個の列δ（ｂｎ−１），．．．，δ（ｂｎ−ｋ）からなる組み合わせを抽出する。列δ（ｂｎ−１），．．．，δ（ｂｎ−ｋ）は記憶部１３に格納される。例えば、列δ（ｂｎ−１），．．．，δ（ｂｎ−ｋ）は記憶部１３のＳＩＭＤレジスタに格納される。演算部３７は、記憶部１３から抽出した列Ｌｉおよび列δ（ｂｎ−ｉ）を入力とし、列ＦＬ，ｉ＝Ｌｉ＋δ（ｂｎ−ｉ）∈ＧＦ（２ｎ）を得て出力する。列ＦＬ，ｉは記憶部１３に格納される。例えば、列ＦＬ，ｉは記憶部１３のＳＩＭＤレジスタに格納される（ステップＳ３３）。
【００４４】
次に制御部１４はｉ＝ｋであるかを判定する（ステップＳ３４）。制御部１４がｉ＝ｋでないと判定した場合、制御部１４はｉを１増加させた値を新たなｉとし（ステップＳ３５）、処理をステップＳ３３に戻す。制御部１４がｉ＝ｋであると判定した場合、出力部１２は記憶部１３に格納された列ＦＬ，ｉ（ｉ＝１，...，ｋ）を出力する（ステップＳ３６）。
【００４５】
＜本形態の特徴＞
各列ｈに対してそれぞれ対応するｋ個のシフト加算列の組み合わせを事前に得ておき、それを用いて列ＦＬ，ｉを得るため、条件分岐処理が不要である。よって本形態でも、高速なＳＩＭＤ演算を用いて「２倍算」の計算が可能である。さらに本形態ではシフト加算列を用いることにより、列Ｌｉの演算と列ＦＬ，ｉの演算とを独立させることができ、さらなる演算の効率化を図ることができる。例えば、本形態では説明の便宜上、ステップＳ１７でｉ＝ｋであると判定された後にステップＳ３３〜Ｓ３５の繰り返し処理を実行することとしたが、ステップＳ３１，Ｓ１７およびＳ１８の繰り返し処理とステップＳ３３〜Ｓ３５の繰り返し処理とを並列に行うことも可能である。これにより、より高速な演算が可能となる。
【００４６】
〔第４実施形態〕
本形態でも、ｎ次既約多項式ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０の一部の係数がＩ０であることを利用し、初期の列ＦＬ，０から抽出した列を用いて「２倍算」の繰り返し処理を行うことで演算を効率化する。
【００４７】
さらに本形態では、以下のようなＳＩＭＤ演算の問題点をも解決する。ＳＩＭＤ演算器にとって、同じレジスタ内の２つのデータ間の扱いは非常に苦手である。例えば、ＳＩＭＤ演算による単純なシフト演算は、処理対象のビット列に含まれるワードごとに独立に実行される。そのため、ワード長がｎ未満である場合にＳＩＭＤ演算によってビット列全体に対する左シフト演算を行うためには、各ワードでのシフト演算の他にワード間でのビットの移動処理が必要となる。例えば、６４ビットごとに処理を行うＳＩＭＤ演算器によって１２８ビットの列に対する左シフト演算を行う場合には、６４ビットごとの左シフト演算に加え、６３ビット目から６４ビット目へのビット（ただし最下位は０ビット目）の移動処理が必要となる。しかしながら、一般的に、ＳＩＭＤ演算にはワード間でビットを直接移動させる命令は存在しない。本形態では、このようなＳＩＭＤ演算の問題点にかかわらず、効率的に「２倍算」の計算を行うことができる。
【００４８】
＜構成＞
図７に例示するように、本形態の演算装置４は、入力部１１、出力部１２、記憶部１３、制御部１４、生成部４５、および演算部４６，４７を有する。演算装置４は、例えば、公知または専用のコンピュータに所定のプログラムが読み込まれることで構成される特別な装置である。例えば、生成部４５は汎用演算器を含み、演算部４６，４７はＳＩＭＤ演算器を含む。演算装置４の各部は、制御部１４の制御に基づいて各処理を実行する。
【００４９】
なお本形態では、ｗが２以上の整数、ｄが２以上の整数、ｎ＝ｗ×ｄ、κが１以上ｗ未満の整数、ｋが１以上κ以下の整数である。また、ｆ（ｘ）がｎ次既約多項式ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０、ｅｎ，．．．，ｅ０がガロア体ＧＦ（２）のｎ＋１個の元である係数であり、Ｆがｎ個の元ｅｎ−１，．．．，ｅ０からなる列であり、ｔ＝ｄ−１，．．．，０についてｅｗ×（ｔ+１）−１＝．．．＝ｅｗ×（ｔ+１）−κ＝Ｉ０である。また、ｇ（ｘ）がｎ−１次多項式ｇ（ｘ）＝ｂｎ−１，０×ｘｎ−１＋．．．＋ｂ０，０であり、ｂｎ−１，０，．．．，ｂ０，０がガロア体ＧＦ（２）のｎ個の元である係数であり、ＦＬ，０がｎ個の元ｂｎ−１，０，．．．，ｂ０，０からなる列である。
【００５０】
＜方法＞
本形態の演算装置４は、ｎ個の元ｂｎ−１，０，．．．，ｂ０，０からなる列ＦＬ，０を入力とし、各ｉ＝１，．．．，ｋに対するｘｉ×ｇ（ｘ） ｍｏｄ ｆ（ｘ）の係数からなる列ＦＬ，ｉを得て出力する。
【００５１】
図８に例示するように、まず第１実施形態で説明したステップＳ１１が実行される。次に生成部４５が、整数ｋを入力とし、ｔ＝ｄ−１，．．．，０について、記憶部１３から列ＦＬ，０に含まれるｗ個の元ｂｗ×（ｔ+１）−１，０，．．．，ｂｗ×ｔ，０からなるワードＸｔ，０に含まれるｋ個の元ｂｗ×（ｔ+１）−１，０，．．．，ｂｗ×（ｔ+１）−ｋ，０からなる各列ｈｔを得て出力する。各列ｈｔ（ただしｔ＝ｄ−１，．．．，０）は記憶部１３に格納される。例えば、各列ｈｔは記憶部１３の汎用レジスタに格納される（ステップＳ４２）。
【００５２】
制御部１４はｉ＝１に設定する（ステップＳ１３）。
【００５３】
演算部４６は、記憶部１３に格納された列ＦＬ，ｉ−１を入力とし、ｔ＝ｄ−１，．．．，０について、ガロア体ＧＦ（２）のｎ個の元ｂｎ−１，ｉ−１，．．．，ｂ０，ｉ−１からなる列ＦＬ，ｉ−１に含まれるｗ個の元ｂｗ×（ｔ+１）−１，ｉ−１，．．．，ｂｗ×ｔ，ｉ−１からなるワードＸｔ，ｉ−１ごとに、ｗ個の元ｂｗ×（ｔ+１）−２，ｉ−１，．．．，ｂｗ×ｔ，ｉ−１，Ｉ０からなるシフトワードＳｔ，ｉを得、ｄ個のシフトワードＳｄ−１，ｉ，．．．，Ｓ０，ｉからなるシフト列Ｓｉを得る。すなわち、演算部４６は、ｔ＝ｄ−１，．．．，０について、元ｂｗ×（ｔ+１）−１，ｉ−１，．．．，ｂｗ×ｔ，ｉ−１からなるワードＸｔ，ｉ−１ごとに左１シフト演算を行い、元ｂｗ×（ｔ+１）−２，ｉ−１，．．．，ｂｗ×ｔ，ｉ−１，Ｉ０からなるシフトワードＳｔ，ｉを得、シフト列Ｓｉを得る。シフト列Ｓｉは記憶部１３に格納される。例えば、シフト列Ｓｉは記憶部１３のＳＩＭＤレジスタに格納される（ステップＳ４４）。
【００５４】
次に演算部４７は、記憶部１３から抽出した列ｈｔを入力とし、シフト列Ｓｉとフィードバック列Ｍ［ｃｄ−１,ｉ，．．．，ｃ０,ｉ］とに対する列Ｓｉ＋Ｍ［ｃｄ−１,ｉ，．．．，ｃ０,ｉ］∈ＧＦ（２ｎ）を列ＦＬ，ｉとして得て出力する。ただし、抽出値ｃｔ，ｉが列ｈｔに含まれる元ｂｗ×（ｔ+１）−ｉ，０であり、Ｋｊ，ｉがガロア体ＧＦ（２）のｎ個の元ｋｊ，ｎ−１，ｉ，．．．，ｋｊ，０，ｉからなる列であり、列Ｋｊ，ｉに含まれる元ｋｊ，ｗ×（ｊ＋１），ｉが抽出値ｃｊ，ｉであり、列Ｋｊ，ｉに含まれる元ｋｊ，ｗ×（ｊ＋１），ｉ以外の元が加法単位元Ｉ０であり、ｊ＝ｄ−２，．．．，０である。また、抽出値ｃｄ−１，ｉが加法単位元Ｉ０である場合のＨｉがｎ個の加法単位元Ｉ０からなる列であり、抽出値ｃｄ−１，ｉが元Ｉ１である場合のＨｉが列Ｆであり、フィードバック列が
【数２】
2014029358.tif 000004
を満たす列である。列ＦＬ，ｉは記憶部１３に格納される。例えば列ＦＬ，ｉは記憶部１３のＳＩＭＤレジスタに格納される（ステップＳ４５）。
【００５５】
次に制御部１４はｉ＝ｋであるかを判定する（ステップＳ１７）。制御部１４がｉ＝ｋでないと判定した場合、制御部１４はｉを１増加させた値を新たなｉとし（ステップＳ１８）、処理をステップＳ４４に戻す。制御部１４がｉ＝ｋであると判定した場合、出力部１２は記憶部１３に格納された列ＦＬ，ｉ（ｉ＝１，．．．，ｋ）を出力する（ステップＳ１９）。
【００５６】
＜本形態の特徴＞
本形態でも第１実施形態と同様な効果を得ることができる。さらに本形態では、ＳＩＭＤ演算でのワード長がｎ未満である場合であっても効率的に「２倍算」を計算できる。
【００５７】
〔第４実施形態の変形例〕
なお、第４実施形態において、とり得るすべてのｃｄ−１,ｉ，．．．，ｃ０,ｉの組について、事前にフィードバック列Ｍ［ｃｄ−１,ｉ，．．．，ｃ０,ｉ］を得ておき、それらをテーブル記憶部（図示せず）に格納しておいてもよい。この場合、演算部４７は、生成部４５で得られた各列ｈｔ（ただしｔ＝ｄ−１，．．．，０）に対応するフィードバック列Ｍ［ｃｄ−１,ｉ，．．．，ｃ０,ｉ］をテーブル記憶部から抽出し、それを用いて列ＦＬ，ｉを得てもよい。これにより、演算効率が向上する。
【００５８】
〔その他の変形例等〕
本発明は上述の実施の形態に限定されるものではない。上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００５９】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００６０】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。
【００６２】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００６３】
１〜４  演算装置
【図１】
2014029358.tif 000007
【図２】
2014029358.tif 000008
【図３】
2014029358.tif 000009
【図４】
2014029358.tif 000010
【図５】
2014029358.tif 000011
【図６】
2014029358.tif 000012
【図７】
2014029358.tif 000013
【図８】
2014029358.tif 000014