(57)【特許請求の範囲】
【請求項１】
メッセージにアクセスする段階と、
複数のサブセグメントを含む複数のメッセージセグメントに前記メッセージを分割する段階と、
前記複数のメッセージセグメントをそれぞれ表す複数の多項式のうち、類似順序のサブセグメントの予め定められた係数多項式に対するモジュラ剰余を同時に決定し、前記モジュラ剰余を用いて次の類似順序のサブセグメントの前記係数多項式に対するモジュラ剰余を同時に決定し、前記複数のメッセージセグメントのモジュラ剰余のセットを決定する段階と、
前記モジュラ剰余の前記セットと、前記メッセージへのアクセス前に決定された前記複数のメッセージセグメントごとの定数のセットとに基づいて、前記メッセージを表す多項式に対するメッセージモジュラ剰余を決定する段階と、
前記メッセージの前記多項式に対する前記メッセージモジュラ剰余を格納する段階とを含む、コンピュータに実装された方法。
【請求項２】
前記モジュラ剰余の前記セットと、前記メッセージへのアクセス前に決定された前記定数の前記セットとに基づいて、前記メッセージの前記多項式に対する前記メッセージモジュラ剰余を決定する段階は、
【数１】
0005384492.tif 000004
に基づいて決定する段階を含み、
Ｓは前記複数のメッセージセグメントの数であり、
Ｒ０は前記メッセージの０番目のメッセージセグメントであるメッセージセグメント０に関連したモジュラ剰余であり、
Ｒｉは前記メッセージのｉ番目のメッセージセグメントであるメッセージセグメントｉに関連したモジュラ剰余であり、
ＫｉはＸｓｅｇｍｅｎｔａｔｉｏｎ−ｐｏｉｎｔ  ｉ  ｍｏｄ  ｐｏｌｙに基づく定数であり、
Ｘｓｅｇｍｅｎｔａｔｉｏｎ−ｐｏｉｎｔ  ｉは、メッセージセグメントｉの前記メッセージにおける位置（ｓｅｇｍｅｎｔａｔｉｏｎ−ｐｏｉｎｔ  ｉ）により定まる定数であり、
ｐｏｌｙは、前記係数多項式であり、
・は前記多項式に対するモジュラ多項式乗算を表し、
＋は多項式加算を表す、請求項１に記載の方法。
【請求項３】
Ｒｉ・Ｋｉを決定する段階は、Ｒｉのサブセグメントをルックアップキーとして用いて、前記Ｒｉのサブセグメントの複数テーブルルックアップを実行する段階を含む、請求項２に記載の方法。
【請求項４】
前記メッセージモジュラ剰余をランダムアクセスメモリに格納されたパケットに含める段階および前記メッセージモジュラ剰余を受信したパケットに含まれるメッセージモジュラ剰余と比較する段階のうち少なくとも１つを実行する段階をさらに含む、請求項１から請求項３のいずれか１つに記載の方法。
【請求項５】
メッセージにアクセスする段階と、
複数のサブセグメントを含む複数のメッセージセグメントに前記メッセージを分割する段階と、
前記複数のメッセージセグメントをそれぞれ表す複数の多項式のうち、類似順序のサブセグメントの予め定められた係数多項式に対するモジュラ剰余を同時に決定し、前記モジュラ剰余を用いて次の類似順序のサブセグメントの前記係数多項式に対するモジュラ剰余を同時に決定し、前記複数のメッセージセグメントのモジュラ剰余のセットを決定する段階と、
前記モジュラ剰余の前記セットと、前記メッセージへのアクセス前に決定された前記複数のメッセージセグメントごとの定数のセットとに基づいて、前記メッセージを表す多項式に対するメッセージモジュラ剰余を決定する段階と、
前記メッセージの前記多項式に対する前記メッセージモジュラ剰余を格納する段階と
をコンピュータに実行させるためのプログラム。
【請求項６】
前記モジュラ剰余の前記セットと、前記メッセージへのアクセス前に決定された前記定数の前記セットとに基づいて、前記メッセージの前記多項式に対する前記メッセージモジュラ剰余を決定する段階は、
【数１】
0005384492.tif 000005
に基づいて決定する段階を含み、
Ｓは前記複数のメッセージセグメントの数であり、
Ｒ０は前記メッセージの０番目のメッセージセグメントであるメッセージセグメント０に関連したモジュラ剰余であり、
Ｒｉは前記メッセージのｉ番目のメッセージセグメントであるメッセージセグメントｉに関連したモジュラ剰余であり、
ＫｉはＸｓｅｇｍｅｎｔａｔｉｏｎ−ｐｏｉｎｔ  ｉ  ｍｏｄ  ｐｏｌｙに基づく定数であり、
Ｘｓｅｇｍｅｎｔａｔｉｏｎ−ｐｏｉｎｔ  ｉは、メッセージセグメントｉの前記メッセージにおける位置（ｓｅｇｍｅｎｔａｔｉｏｎ−ｐｏｉｎｔ  ｉ）により定まる定数であり、
ｐｏｌｙは、前記係数多項式であり、
・は前記多項式に対するモジュラ多項式乗算を表し、
＋は多項式加算を表す、
請求項５に記載のプログラム。
【請求項７】
Ｒｉ・Ｋｉを決定する段階は、Ｒｉのサブセグメントをルックアップキーとして用いて、前記Ｒｉのサブセグメントの複数テーブルルックアップを実行する段階を含む、請求項６に記載のプログラム。
【請求項８】
前記メッセージモジュラ剰余をランダムアクセスメモリに格納されたパケットに含める段階および前記メッセージモジュラ剰余を受信したパケットに含まれるメッセージモジュラ剰余と比較する段階のうち少なくとも１つを前記コンピュータに実行させる段階をさらに含む、請求項５から請求項７のいずれか１つに記載のプログラム。
【発明の詳細な説明】
【背景技術】
【０００１】
様々なコンピュータアプリケーションがメッセージを操作し、メッセージ剰余を作成する。-メッセージ剰余は、メッセージの内容をより簡潔に表現することができる。メッセージ剰余は、複数の用途の中でも特にネットワーク接続上で送信あるいは記憶装置から取得したデータが破損しているかどうかを決定するべく利用される。例えば、ノイズを有する送信線は、信号「１」を「０」に、またはこの逆に変更する場合がある。破損を検出するべく、メッセージはメッセージ剰余を伴う場合が多い。後にデータの受信側は、メッセージの剰余を独自に決定し、決定した剰余と受信した剰余とを比較してよい。
【０００２】
一般的なメッセージ剰余は、巡回冗長検査（ＣＲＣ）として知られている。ＣＲＣの計算は、メッセージビットのストリームを多項式の係数として解釈することに基づく。例えば、メッセージ「１０１０」は、多項式（１ｘ３）＋（０ｘ２）＋（１ｘ１）＋（０ｘ０）あるいは、より単純にｘ３＋ｘ１に相当する。メッセージ多項式は、係数と呼ばれる他の多項式で除算される。例えば、他の多項式は、「１１」またはｘ＋１であってよい。ＣＲＣは、メッセージを多項式で除算した余りである。しかしながら、ＣＲＣ多項式除算は、有限体ＧＦ（２）（例えば、整数モジュロＴのセット）で算出されるという点において、通常の除算とは異なる。より単純には、偶数の係数は０となり、奇数の係数は１となる。
【図面の簡単な説明】
【０００３】
【図１】メッセージ剰余の決定を示す図である。
【０００４】
【図２】メッセージ剰余を決定する動作を示す図である。
【０００５】
【図３】メッセージ剰余の決定に使用可能なテーブルルックアップを示す図である。
【発明を実施するための形態】
【０００６】
メッセージ剰余の決定は、様々なアプリケーションの中で頻発する。例えば、送信時あるいは受信後のメッセージ処理において、この計算が多大なオーバーヘッドとなる場合が多い。メッセージの異なる部分に対する同時処理を許容することでこの計算を促進するテクニックを以下に説明する。
【０００７】
図解を目的に３Ｎビット長のメッセージＭ１００のＣＲＣ計算を図１に示す。メッセージＭのビットは、多項式Ｍ（ｘ）の係数を表す。上述のように、ＣＲＣは、メッセージＭ（ｘ）の多項式Ｐ（ｘ）係数（「ｐｏｌｙ」）によるモジュロ演算の余りである。
ＣＲＣ  Ｍ（ｘ）＝Ｍ（ｘ）ｍｏｄ  Ｐ  （ｘ）          ［１］
上記の式では、Ｐ（ｘ）はビットストリングで表現された他の多項式である。実際には、Ｐ（ｘ）はアプリケーション毎に定義される。例えば、エンドツーエンドのデータ保護にＣＲＣを用いるｉＳＣＳＩ  （Ｉｎｔｅｒｎｅｔ  Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅ）は、多項式Ｐ（ｘ）として１１ＥＤＣ６Ｆ４１Ｈ１６の値を用いる。異なるアプリケーションは、異なる多項式のサイズと値を選択している。一般的なｋビットのＣＲＣ剰余では、Ｐ（ｘ）はｋビット多項式（例えば、３２ビット）であり、Ｍはｋビットシフトしたメッセージｍ（ｘ）である。通常、ｋビットＣＲＣ値は、Ｍ（ｘ）の空白の最下位ｋビットに格納される。
【０００８】
ＣＲＣ値は、メッセージＭの各ビットの値および位置を示す。しかしながら、図１のようにメッセージのセグメントを個別処理した後に、正確なＣＲＣ計算を保存する形で結果を合計することによって、ＣＲＣ値を並列に計算してよい。より正確には、Ｍ（ｘ）のＣＲＣは、メッセージの異なるセグメント（Ａ、Ｂ、Ｃ）のＣＲＣの計算に分けることができる。例えば、
ＣＲＣ  Ｍ（ｘ）＝（ＣＲＣ（Ｃ）・Ｋ２）＋（ＣＲＣ（Ｂ）・Ｋ１）＋（ＣＲＣ（Ａ））                ［２］
上記の式では、「＋」は多項式の加算（例えば、ビット毎のＸＯＲ）を表し、「・」は多項式の乗算（例えば、ｍｏｄ  Ｐ（ｘ）の桁上げのない乗算）を表す。ＣＲＣ（Ｃ）、ＣＲＣ（Ｂ）およびＣＲＣ（Ａ）の値は、独自かつ同時に計算され、全体のＣＲＣ値の計算を速めてよい。その後、各セグメントのＣＲＣ値は、メッセージＭの例えば定数Ｋによる多項式乗算の全体のＣＲＣ値として合計されてよい。例えば、サイズＮビットの均一なセグメントを有する図１の例では、Ｋ２＝ｘ２Ｎ  ｍｏｄ  ｐｏｌｙおよびＫ１＝ｘＮ  ｍｏｄ  ｐｏｌｙにおいて、ｘ２ＮおよびｘＮはメッセージ内のセグメントの重みに相当する。ｘ２ＮおよびｘＮは定数であることから、係数多項式ｐｏｌｙは定数であり、従ってＫ２およびＫ１の値もまた、メッセージＭの値がアクセスされる前に予め計算可能な定数である。つまり、定数Ｋの値は、メッセージＭのビット値ではなく、セグメンテーションポイントおよびｐｏｌｙの既知値による。言い換えれば、与えられた多項式について決定された定数の与えられたセットを異なるメッセージに用いることができる。定数セットは予め計算されていてよく、実際に用いられる異なる多項式に提供されてよい。定数の値は、ＣＲＣ演算を用いて決定されてよい。例えば、上記の例では、特定の多項式においてＫ２はＣＲＣ（ｘ２Ｎ）であると計算できる。
【０００９】
図１では３つのセグメントを説明したが、他の実装では、異なるセグメント数、サイズが均一でないセグメントなど、異なるセグメンテーションスキームを用いてもよい。さらに、これらの定数の値は予め計算しておくことができるが、これらは、例えば第１のメッセージの初期の処理期間中あるいは効率は悪いが処理されるメッセージ毎に、セグメントのＣＲＣ値と同時に計算されてもよい。
【００１０】
このようなスキームの潜在的な利点は、異なる環境および実装で数量化することができる。例えば、プロセッサが専用のＣＲＣ命令（例えば、ＣＲＣまたは他のメッセージ剰余プロセッサのｍａｃｒｏ−ｏｐ）機能を有してよい。このような命令は次の構文であってよい。
ＣＲＣ（ｉｎｐｕｔ−ｂｉｔ−ｓｔｒｉｎｇ，  ｍｅｓｓａｇｅ−ｒｅｓｉｄｕｅ）
上記のｉｎｐｕｔ−ｂｉｔ−ｓｔｒｉｎｇ（例えば、６４、３２、１６、８または他の指定あるいは固定のストリング長）は、メッセージの一部を表してよい。あるいは、命令またはコンパニオン命令が多項式あるいはビットストリング幅を指定してよい。命令は、ＣＲＣメッセージ剰余の値を更新し、新たな入力ビットストリングによる増分の寄与を反映してよい。このような命令を用いてメッセージＭのＣＲＣの計算を累積的に行うことができる。これには、ＣＲＣ値を増分して更新するＣＲＣ命令の呼び出し毎に入力ビットストリングサイズのチャンクでメッセージを消費するＣＲＣ命令へのコールシーケンスを用いてよい。すべてのデータチャンクが消費された後に残されたメッセージ剰余が、メッセージ全体としてのＣＲＣ値を示す。
【００１１】
このような命令は、３２ビットＣＲＣ演算を実装する次のプロセッサｍｉｃｒｏ−ｏｐで実装することができる。
ＴＥＭＰ１［６３−０］  <-  ＢＩＴ＿ＲＥＦＬＥＣＴ６４（ＳＲＣ［６３−０］）
ＴＥＭＰ２［３１−０］  <-  ＢＩＴ＿ＲＥＦＬＥＣＴ３２（ＤＥＳＴ［３１−０］）
ＴＥＭＰ３［９５−０］  <-  ＴＥＭＰ１［６３−０］＜＜３２
ＴＥＭＰ４［９５−０］  <-  ＴＥＭＰ２［３１−０］＜＜６４
ＴＥＭＰ５［９５−０］  <-  ＴＥＭＰ３［９５−０］ＸＯＲ  ＴＥＭＰ４［９５−０］
ＴＥＭＰ６［３１−０］  <-  ＴＥＭＰ５［９５−０］ＭＯＤＵＬＯ  ＰＯＬＹ
ＤＥＳＴ［３１−０］  <-  ＢＩＴ＿ＲＥＦＬＥＣＴ（ＴＥＭＰ６［３１−０］）
ＤＥＳＴ［６３−３２］  <-  ００００００００Ｈ
上記では、必要に応じてＢＩＴ＿ＲＥＦＬＥＣＴがストリングのエンディアンを変更する。
【００１２】
上述したＣＲＣ値を決定する例示的な実装では、各ＣＲＣ命令が前のＣＲＣ命令の出力を入力とする必要がある。しかしながら、このシリアルなアプローチでは、ＴがＣＲＣ命令サイクルのレイテンシーでＬがチャンク数である場合に、少なくともＴ×Ｌのプロセッササイクル数を消費する。対照的に、セグメントを並行して計算すると、およそ（Ｔ×Ｌ／ＮｕｍＳｅｇｍｅｎｔｓ）のレイテンシーに比較的僅かな再結合演算のレイテンシーを加えた結果をもたらす。通常、後者のアプローチはＣＲＣの決定に必要な時間を顕著に短縮する。
【００１３】
図２は、プロセッサが提供するＣＲＣ命令を用いた例示的な実装を図示する。示された例では、特定のＣＲＣ命令が３サイクルで完了する。タイミング図は、プロセッサによる複数の命令実行パイプラインの実装を図示する。
【００１４】
図のとおり、ＣＲＣ命令は各セグメントのサブセグメント（例えば、ｉ＝１から３である、Ａ［ｉ］、Ｂ［ｉ］およびＣ［ｉ］）で連続して演算する。各セグメントの剰余は、増分して更新された剰余変数に格納される。例えば、剰余値Ｘは、セグメントＣのサブセグメントチャンク（例えば、Ｃ［１］、Ｃ［２］およびＣ［３］）毎に更新される。剰余の値は、与えられたアプリケーションに適切な値（例えば、ｉＳＣＳＩではすべて１）に初期化されてよい。
【００１５】
ＣＲＣ命令のレイテンシーおよびパイプラインアーキテクチャにより、あるセグメントのチャンクに対する動作は、他のセグメントのチャンクに対する動作と交互的となる。例えば、図のように位置が類似のセグメントのチャンクＡ、ＢおよびＣ（例えば、Ａ［１］、Ｂ［１］およびＣ［１］）は、１０４ａから１０４ｃでパイプラインへ順に挿入される。与えられたチャンクのセグメント剰余が更新されると、そのセグメントの次のチャンクを処理することができる。例えば、チャンクＣ［１］のＣＲＣ命令１０４ａの完了後、ＣＲＣ命令１０４ｄはチャンクＣ［２］を処理することができる。図示されたＣＲＣ命令間の重複は、上述のテクニックに起因する全体的なレイテンシーの短縮を示す。
【００１６】
図のように、Ｘ、ＹおよびＺの決定後に再結合１０６が進行する。再結合１０６は、潜在的にＣＲＣ計算に重複することができる。例えば、Ｘ・Ｋ２の決定は、ＹおよびＺの値を待つことなく、Ｘの値の決定後即時に開始されてよい。また潜在的に、Ｘ、ＹおよびＺのメッセージ剰余の値は、メッセージそのもの（例えば、Ｘの値はＣ［３］、Ｙの値はＢ［３］、Ｚの値はＡ［３］）に格納されてよく、メッセージ剰余のわずかな格納へとメッセージを変化させてよい。
【００１７】
図２は、与えられた環境における特定の実施を図示したが、多くの変形が可能である。例えば、セグメントＣＲＣ値の計算は、パイプライン処理に加えて、あるいはその代わりに、異なるプロセッサ要素（例えば、単一ダイに集積されたプロセッサのプログラム可能なプロセッサコア）によって決定されてよい。さらに、ＣＲＣ命令のサイクル数は、説明した実施の３サイクルより少なくても多くてもよい。潜在的に、メッセージセグメントの数はＣＲＣ命令が用いるサイクル数に基づいて（例えば、その数に等しくて）よい。例えば、４サイクルの命令は、メッセージを４つのセグメントに分け、それらを同時に処理する実施と組み合わされてよい。またさらに、説明では専用のＣＲＣ命令を用いたが、明確な専用のＣＲＣ命令がプロセッサによって提供されない状況にテクニックを適用してもよい。さらには、図２ではＣＲＣ計算を説明したが、異なるメッセージ剰余の決定に上述のテクニックを用いてもよい。
【００１８】
さらなる変形によって、メッセージ剰余の計算をさらにあるいは独立して速めることができる。例えば、上述のアプローチは（ＣＲＣ（ｓｅｇｍｅｎｔ）・Ｋ）を計算した。直接的な実施では、セグメントのＣＲＣ値を決定した後にこの多項式乗算およびモジュラ還元を実行してよい。しかしながら、Ｋおよびｐｏｌｙは定数であることから、この演算はルックアップテーブルのセットを用いて実施可能である。例えば、図３のように、セグメントのＣＲＣ値（Ｙで示す）１０８の定数Ｋによるモジュラ多項式乗算は、次の式で表すことができる。
Ｙ・Ｋ＝Ｙ３（Ｄ３・Ｋ）ｍｏｄ  ｐｏｌｙ＋Ｙ２（Ｄ２・Ｋ）ｍｏｄ  ｐｏｌｙ＋Ｙ１（Ｄ１・Ｋ）ｍｏｄ  ｐｏｌｙ＋Ｙ０ｍｏｄ  ｐｏｌｙ          ［４］
上記の式では、ＹｉはＹのｎビットセグメントを表し、ＤｉはｘＤｉの定数を表す。（Ｄｉ・Ｋ）の値は２つの定数のモジュラ多項式乗算を表すのでこれらも定数である。従って、Ｙｉ（Ｄｉ・Ｋ）ｍｏｄ  ｐｏｌｙを実際に計算することなく、Ｙｉ（Ｄｉ・Ｋ）ｍｏｄ  ｐｏｌｙの予め計算された可能値を格納したテーブル１１０ａ、１１０ｂおよび１１０ｃに対するｎビットルックアップキーとしてＹｉの各値を用いてよい。例えば、Ｙが３２ビットの数の場合、Ｙ３の８ビットの値でルックアップするべく、Ｙ３（Ｄ３・Ｋ）ｍｏｄ  ｐｏｌｙの予め計算された値をテーブル１１０ａが格納してよい。このようなテーブルは、過量のデータ容量を消費することなく、これらの計算を顕著に速めることが可能である。さらに、このようなルックアップは、並行して実行されてよい。結果のルックアップ値は、多項式の加算を用いて迅速に合計することが可能である。
【００１９】
以上、ＣＲＣメッセージ剰余について説明した。このような剰余は、例えばＲＡＭあるいはメモリのパケットに格納され、受信したパケットに格納された剰余と比較されることで、例えばデータ破損が起こり得たかどうかが判断されてよい。上述したテクニックはＣＲＣに限定されたものではなく、モジュラ剰余で動作する、例えばＧＦ（２）における多項式の有限体など、他のコーディング／エラー修正スキームなどその他のスキームで用いられてよい。さらには、上述のテクニックでは中間値に対してモジュラ還元を繰り返し実行したが、このようなモジュラ還元は延期または異なる時点で実行されてよい。
【００２０】
上述したテクニックは、ハードウェア、ソフトウェア、および／またはファームウェアあるいはこれらの組み合わせを含む多様なロジックで実装されてよい。例えば、上述のテクニックは、コンピュータで読み取り可能な媒体に配されたコンピュータプログラムの命令であって、上述したメッセージ剰余の決定をプロセッサに実行させる命令であってよい。
【００２１】
その他の実施形態が以下の請求の範囲に含まれる。
［項目１］
メッセージにアクセスする段階と、
前記メッセージの異なるセグメントのそれぞれの多項式に対するモジュラ剰余のセットを同時に決定する段階と、
前記モジュラ剰余のセットと、前記メッセージへのアクセス前に決定された定数のセットとに基づいて、前記メッセージの前記多項式に対するモジュラ剰余を決定する段階と、
前記メッセージの前記多項式に対する前記モジュラ剰余を格納する段階と、
を含む、コンピュータに実装された方法。
［項目２］
前記モジュラ剰余のセットと、前記メッセージへのアクセス前に決定された定数のセットとに基づいて、前記メッセージの前記多項式に対するモジュラ剰余を決定する段階は、
【数１】
0005384492.tif 000002
に基づいて決定する段階を含み、
Ｓは前記メッセージのセグメントの数であり、
Ｒｉは前記メッセージのセグメントｉに関連した剰余であり、
ＫｉはＸｓｅｇｍｅｎｔａｔｉｏｎ−ｐｏｉｎｔ ｉ ｍｏｄ ｐｏｌｙに基づく定数であり、
・は前記多項式に対するモジュラ多項式乗算を表し、
＋は多項式加算を表す、項目１に記載の方法。
［項目３］
Ｒｉ・Ｋｉを決定する段階は、Ｒｉのサブセグメントをルックアップキーとして用いて、前記Ｒｉのサブセグメントの複数テーブルルックアップを実行する段階を含む、項目２に記載の方法。
［項目４］
前記メッセージの異なるセグメントのそれぞれの多項式に対するモジュラ剰余のセットを同時に決定する段階は、それぞれの前記セグメントのサブセグメントの前記剰余を決定する段階を含む、項目１に記載の方法。
［項目５］
前記メッセージの異なるセグメントのそれぞれの多項式に対するモジュラ剰余のセットを同時に決定する段階は、それぞれの前記セグメントの類似順序のサブセグメントの前記剰余を同時に決定する段階を含む、項目４に記載の方法。
［項目６］
それぞれの前記セグメントの類似順序のサブセグメントの前記剰余を同時に決定する段階は、マルチサイクルパイプラインで同時に前記剰余を決定する段階を含む、項目５に記載の方法。
［項目７］
前記モジュラ剰余をパケットに含む段階をさらに含む、項目１に記載の方法。
［項目８］
前記モジュラ剰余をパケットに含まれたメッセージ剰余と比較する段階をさらに含む、項目１に記載の方法。
［項目９］
命令セットを備えるコンピュータで読み取り可能な媒体であって、
前記命令セットはプロセッサに、
メッセージにアクセスする段階と、
メッセージの異なるセグメントのそれぞれの多項式に対するモジュラ剰余のセットを同時に決定する段階と、
前記モジュラ剰余のセットと、前記メッセージへのアクセス前に決定された定数のセットとに基づいて、前記メッセージの前記多項式に対するモジュラ剰余を決定する段階と、
前記メッセージの前記多項式に対する前記モジュラ剰余を格納する段階と、
を実行させる、コンピュータで読み取り可能な媒体。
[項目１０］
前記モジュラ剰余のセットと、前記メッセージへのアクセス前に決定された定数のセットとに基づいて、前記メッセージの前記多項式に対するモジュラ剰余を決定する段階を前記プロセッサに実行させる前記命令は、
【数１】
0005384492.tif 000003
に基づいて決定させ、
Ｓは前記メッセージのセグメントの数であり、
Ｒｉは前記メッセージのセグメントｉに関連した剰余であり、
ＫｉはＸｓｅｇｍｅｎｔａｔｉｏｎ−ｐｏｉｎｔ ｉ ｍｏｄ ｐｏｌｙに基づく定数であり、
・は前記多項式に対するモジュラ多項式乗算を表し、
＋は多項式加算を表す、
項目９に記載の媒体。
[項目１１］
Ｒｉ・Ｋｉを決定する段階を前記プロセッサに実行させる前記命令は、Ｒｉのサブセグメントをルックアップキーとして用いて、前記Ｒｉのサブセグメントの複数テーブルルックアップを実行する段階を前記プロセッサに実行させる命令を含む、項目９に記載の媒体。
[項目１２］
前記メッセージの異なるセグメントのそれぞれの多項式に対するモジュラ剰余のセットを同時に決定する段階を前記プロセッサに実行させる前記命令は、それぞれの前記セグメントのサブセグメントの前記剰余を決定する段階を前記プロセッサに実行させる命令を含む、項目９に記載の媒体。
[項目１３］
前記メッセージの異なるセグメントのそれぞれの多項式に対するモジュラ剰余のセットを同時に決定する段階を前記プロセッサに実行させる前記命令は、それぞれの前記セグメントの類似順序のサブセグメントの前記剰余を同時に決定する段階を前記プロセッサに実行させる命令を含む、項目１２に記載の媒体。
[項目１４］
それぞれの前記セグメントの類似順序のサブセグメントの前記剰余を同時に決定する段階を前記プロセッサに実行させる前記命令は、マルチサイクルパイプラインで同時に前記剰余を決定する段階を前記プロセッサに実行させる命令を含む、項目１３に記載の媒体。
[項目１５］
前記命令は、（１）前記モジュラ剰余をパケットに含む段階および（２）前記モジュラ剰余をパケットに含まれたモジュラ剰余と比較する段階のうち少なくとも１つを前記プロセッサに実行させる命令をさらに含む、項目９に記載の媒体。
【図１】
0005384492.tif 000006
【図２】
0005384492.tif 000007
【図３】
0005384492.tif 000008