(57)【特許請求の範囲】
【請求項１】
剰余演算系の基底を｛ａ１，ａ２，…，ａｎ｝（ｎは整数）とし且つＡ＝ａ１ａ２…ａｎとした際に、｛ａ１，ａ２，…，ａｎ｝から任意に１つの基底要素ａｉ（１≦ｉ≦ｎ）を選択し、このａｉの選択情報及びＡ未満の正の整数ｘが入力されたとき、前記ｘをａｉで除した商ｚを出力可能な、剰余演算機能を有する複数の演算ユニットを備えた剰余演算装置において、
前記選択情報に基づいて、前記ｘの剰余演算系表現の各値ｘ１，…，ｘｎから前記基底要素ａｉに対応する値ｘｉを減じるように、前記各演算ユニットを制御する減算制御手段と、
前記減算制御手段により得られた各値（ｘ１−ｘｉ），…，（ｘｎ−ｘｉ）（但し、（ｘｉ−ｘｉ）を除く）に対し、前記基底要素ａｉの乗法逆元ａｉ-1を乗じるように、前記各演算ユニットを制御する乗算制御手段と、
前記乗算制御手段により得られた乗算結果を商ｚとして出力する出力手段と、
を備えたことを特徴とする剰余演算装置。
【請求項２】
剰余演算系の基底を｛ａ１，ａ２，…，ａｎ｝（ｎは整数）とし且つＡ＝ａ１ａ２…ａｎとした際に、｛ａ１，ａ２，…，ａｎ｝から任意にｋ個（２≦ｋ≦ｎ）の基底要素ａｉ，ａｊ，…を選択し、これらの基底要素ａｉ，ａｊ，…の選択情報及びＡ未満の正の整数ｘが入力されたとき、前記ｘをａｉ・ａｊ・…で除した商ｚを出力可能な、剰余演算機能を有する複数の演算ユニットを備えた剰余演算装置において、
前記選択された基底要素ａｉ，ａｊ，…のうち、いずれか１個の基底要素ａｈを再選択する再選択手段と、
前記再選択手段により再選択された基底要素ａｈに対応する値ｘｈを、前記ｘの剰余演算系表現の各値ｘ１，…，ｘｎから減じるように、前記各演算ユニットを制御する減算制御手段と、
前記減算制御手段により得られた各値（ｘ１−ｘｉ），…，（ｘｎ−ｘｉ）（但し、（ｘｈ−ｘｈ）を除く）に対し、前記再選択された基底要素ａｈの乗法逆元ａｈ-1を乗じるように、前記各演算ユニットを制御する乗算制御手段と、
前記選択された基底要素ａｉ，ａｊ，…の全てが前記再選択手段、前記減算制御手段及び前記乗算制御手段により順次処理されたとき、最後に再選択された基底要素に関して前記乗算制御手段の制御により得られた乗算結果を商ｚとして出力する出力手段と、
を備えたことを特徴とする剰余演算装置。
【請求項３】
請求項１又は請求項２に記載の剰余演算装置において、
前記基底は、２のべき又は２のべきに近接する値を用いることを特徴とする剰余演算装置。
【請求項４】
請求項１乃至請求項３のいずれか１項に記載の剰余演算装置において、
前記商を、基底拡張によりｎ個の基底で表現するための基底拡張手段を備えたことを特徴とする剰余演算装置。
【請求項５】
請求項１乃至請求項４のいずれか１項に記載の剰余演算装置において、
正の整数Ｎ及びｘ＜Ｎ２を満たす整数ｘを入力としたとき、ｘ ｍｏｄ Ｎを出力するバレット・リダクションを行うように、前記各演算ユニットを制御するバレット・リダクション制御手段を備えたことを特徴とする剰余演算装置。
【請求項６】
請求項１乃至請求項４のいずれか１項に記載の剰余演算装置において、
正の整数Ｎ及びｘ＜９Ｎ２を満たす整数ｘを入力としたとき、ｘ ｍｏｄ Ｎ、ｘ ｍｏｄ Ｎ＋Ｎ、またはｘ ｍｏｄ Ｎ＋２Ｎを出力するバレット・リダクションを行うように、前記各演算ユニットを制御するバレット・リダクション制御手段を備えたことを特徴とする剰余演算装置。
【請求項７】
請求項６に記載の剰余演算装置において、
前記バレット・リダクション制御手段は、前記バレット・リダクションのアルゴリズムが含まれる剰余乗算を行うときに前記減算制御手段及び前記乗算制御手段を用いて前記各演算ユニットを制御することを特徴とする剰余演算装置。
【請求項８】
請求項６に記載の剰余演算装置において、
前記バレット・リダクション制御手段は、前記バレット・リダクションのアルゴリズムが含まれる,べき乗剰余算を行うときに前記減算制御手段及び前記乗算制御手段を用いて前記各演算ユニットを制御することを特徴とする剰余演算装置。
【請求項９】
剰余演算系の基底を｛ａ１，ａ２，…，ａｎ｝（ｎは整数）とし且つＡ＝ａ１ａ２…ａｎとした際に、｛ａ１，ａ２，…，ａｎ｝から任意に１つの基底要素ａｉ（１≦ｉ≦ｎ）を選択し、このａｉの選択情報及びＡ未満の正の整数ｘが入力されたとき、前記ｘをａｉで除した商ｚを出力可能な、剰余演算機能を有する複数の演算ユニット、減算制御手段、乗算制御手段及び出力手段を備えた剰余演算装置が実行する剰余演算方法において、
前記減算制御手段が、前記選択情報に基づいて、前記ｘの剰余演算系表現の各値ｘ１，…，ｘｎから前記基底要素ａｉに対応する値ｘｉを減じるように、前記各演算ユニットを制御する減算制御工程と、
前記乗算制御手段が、前記減算制御工程により得られた各値（ｘ１−ｘｉ），…，（ｘｎ−ｘｉ）（但し、（ｘｉ−ｘｉ）を除く）に対し、前記基底要素ａｉの乗法逆元ａｉ-1を乗じるように、前記各演算ユニットを制御する乗算制御工程と、
前記出力手段が、前記乗算制御工程により得られた乗算結果を商ｚとして出力する出力工程と、
を含んでいることを特徴とする剰余演算方法。
【請求項１０】
剰余演算系の基底を｛ａ１，ａ２，…，ａｎ｝（ｎは整数）とし且つＡ＝ａ１ａ２…ａｎとした際に、｛ａ１，ａ２，…，ａｎ｝から任意にｋ個（２≦ｋ≦ｎ）の基底要素ａｉ，ａｊ，…を選択し、これらの基底要素ａｉ，ａｊ，…の選択情報及びＡ未満の正の整数ｘが入力されたとき、前記ｘをａｉ・ａｊ・…で除した商ｚを出力可能な、剰余演算機能を有する複数の演算ユニット、再選択手段、減算制御手段、乗算制御手段及び出力手段を備えた剰余演算装置が実行する剰余演算方法において、
前記再選択手段が、前記選択された基底要素ａｉ，ａｊ，…のうち、いずれか１個の基底要素ａｈを再選択する再選択工程と、
前記減算制御手段が、前記再選択工程により再選択された基底要素ａｈに対応する値ｘｈを、前記ｘの剰余演算系表現の各値ｘ１，…，ｘｎから減じるように、前記各演算ユニットを制御する減算制御工程と、
前記出力手段が、前記減算制御工程により得られた各値（ｘ１−ｘｉ），…，（ｘｎ−ｘｉ）（但し、（ｘｈ−ｘｈ）を除く）に対し、前記再選択された基底要素ａｈの乗法逆元ａｈ-1を乗じるように、前記各演算ユニットを制御する乗算制御工程と、
前記選択された基底要素ａｉ，ａｊ，…の全てが前記再選択工程、前記減算制御工程及び前記乗算制御工程により順次処理されたとき、最後に再選択された基底要素に関して前記乗算制御工程の制御により得られた乗算結果を商ｚとして出力する出力工程と、
を含んでいることを特徴とする剰余演算方法。
【請求項１１】
請求項９又は請求項１０に記載の剰余演算方法において、前記基底は、２のべき又は２のべきに近接する値を用いることを特徴とする剰余演算方法。
【請求項１２】
請求項９乃至請求項１１のいずれか１項に記載の剰余演算方法において、
前記剰余演算装置は基底拡張手段を備えており、
前記基底拡張手段が、前記商を、基底拡張によりｎ個の基底で表現するための基底拡張工程を含んでいることを特徴とする剰余演算方法。
【請求項１３】
請求項９乃至請求項１２のいずれか１項に記載の剰余演算方法において、
前記剰余演算装置はバレット・リダクション制御手段を備えており、
前記バレット・リダクション制御手段が、正の整数Ｎ及びｘ＜Ｎ２を満たす整数ｘを入力としたとき、ｘ ｍｏｄ Ｎを出力するバレット・リダクションを行うように、前記各演算ユニットを制御するバレット・リダクション制御工程を含んでいることを特徴とする剰余演算方法。
【請求項１４】
請求項９乃至請求項１２のいずれか１項に記載の剰余演算方法において、
前記剰余演算装置はバレット・リダクション制御手段を備えており、
前記バレット・リダクション制御手段が、正の整数Ｎ及びｘ＜９Ｎ２を満たす整数ｘを入力としたとき、ｘ ｍｏｄ Ｎ、ｘ ｍｏｄ Ｎ＋Ｎ、またはｘ ｍｏｄ Ｎ＋２Ｎを出力するバレット・リダクションを行うように、前記各演算ユニットを制御するバレット・リダクション制御工程を含んでいることを特徴とする剰余演算方法。
【請求項１５】
請求項１４に記載の剰余演算方法において、
前記バレット・リダクション制御工程は、前記バレット・リダクションのアルゴリズムが含まれる剰余乗算を行うときに前記減算制御工程及び前記乗算制御工程を用いて前記各演算ユニットを制御することを特徴とする剰余演算方法。
【請求項１６】
請求項１４に記載の剰余演算方法において、
前記バレット・リダクション制御工程は、前記バレット・リダクションのアルゴリズムが含まれる,べき乗剰余算を行うときに前記減算制御工程及び前記乗算制御工程を用いて前記各演算ユニットを制御することを特徴とする剰余演算方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、剰余演算系に基づき、大きな整数の演算を並列処理により高速に計算する剰余演算装置及び方法に関する。
【０００２】
【従来の技術】
公開鍵暗号の重要性が増すにつれて、大きな整数の剰余演算を効率よく行うための方法及び装置への要望が高まっている。例えば現在事実上の標準（デファクトスタンダード）であるＲＳＡ（Rivest−Shamir−Adleman）方式では、1,024ビットの整数による剰余演算を高速に行う必要がある。
【０００３】
このための高速演算方法の一つとして、剰余演算系（Residue Number Systems）が知られている。この剰余演算系は、互いに素な比較的小さな整数の組｛ａ１，ａ２，…，ａｎ｝を用意し、演算対象の大きな整数をこれらの整数で割った余りの組で表現する手法である。以後、この余りの組｛ａ１，ａ２，…，ａｎ｝を剰余演算系の基底と呼び、基底を構成する要素の個数ｎを基底のサイズと呼ぶ。また、基底の集合をａ＝｛ａ１，ａ２，…，ａｎ｝で表す。
【０００４】
例えば、整数ｘと基底｛ａ１，ａ２，…，ａｎ｝が与えられたとき、整数ｘを基底要素ａｉ（ｉ＝１，２，…，ｎ）で割った余りｘｉの組（ｘ１，ｘ２，…，ｘｎ）がｘの剰余演算系表現である。なお、ｘｉ＝ｘ ｍｏｄ ａｉである。ここで、整数ｘは、基底の全要素の積Ａ＝ａ１ａ２…ａｎを法として一意的に表現できる。すなわち、ｘがＡ未満の正整数のとき、ｘとその剰余演算系表現（ｘ１，ｘ２，…，ｘｎ）は一対一に対応する。なお、この一対一の対応関係は、中国剰余定理により保証されている。
【０００５】
係る剰余演算系表現では、２つの整数ｘ，ｙの積を計算する際に、各要素毎の積（ｘ１・ｙ１，…，ｘｎ・ｙｎ）を求め、得られた積を、対応する基底ａｉで除した余り（ｘ１・ｙ１ ｍｏｄ ａ１，…，ｘｎ・ｙｎ ｍｏｄ ａｎ）を求める。
【０００６】
この演算は、一般的に言い換えると、各要素毎に、対応する基底ａｉを法とする積を計算することにより、基底要素の積Ａを法とする積が求められることと表現される。加算及び減算についても同様であり、基底ａｉに対応する要素ｘｉ，ｙｉについて、ａｉを法とする加算あるいは減算をすればよい。
【０００７】
このような剰余演算系における乗算、加算、減算は、各要素毎に独立に対応する基底を法とする演算を行えばよいので、例えば基底として計算機のワード長以内の値を採用することにより、非常に大きな整数の演算を単精度の演算の繰り返しによって実現できる。
【０００８】
また、それらの単精度演算は、基底毎に独立して実行可能なので、複数の演算器による並列処理が可能になる。例えば、基底サイズがｎの場合、剰余演算機能付のｎ個の乗算器を並列に動作させることにより、１回の単精度剰余付き乗算と同じ時間内で基底要素の積Ａを法とする乗算を終了できる。
【０００９】
現在の計算機内では、通常、２進数表現が用いられている。２進数表現に基づく大きな整数の演算では、ＬＳＢ(Least Significanｔ Bit)からＭＳＢ(Most Significant Bit)に向けて桁上がりが伝播し、大きな整数の全桁数（あるいはビット長）に比例した処理時間がかかる。従って、２進数表現による演算は、剰余演算系による並列処理に比べ、処理速度の点で不利である。
【００１０】
一方、剰余演算系による演算は、ワード間の桁上がりが生じないので、２進数表現に代表される基数法に比べ、大きい整数の乗算、加算、減算を効率よく行う方式として古くから知られてきている。
【００１１】
しかしながら、剰余演算系では、除算や２数の大小比較については基数法に比べ、効率よく行う手段が知られていない。このため、剰余演算系は、公開鍵暗号のような大きな整数の演算を高速に行う応用に適していると考えられながら、剰余算への適用の仕方が知られていない。
【００１２】
一方、剰余演算系表現した数値同士による剰余乗算の方法がポッシュ（Posch）ら（IEEE Transaction on Parallel and Distributed Systems, Vol.６, No.5, May 1995, pp.449-454に掲載された“Modulo Reduction in Residue Number Systems”、及びComputer & Security誌Vol.17, pp.637-650, 1998に掲載された“RNS−Modulo Reduction Upon a Restricted Base Value Set and its Applicability to RSA Cryptography”）、川村（特開２００１−１９４９９３）によって提案されている。
【００１３】
これらの方法は、剰余演算系表現での演算において不利な除算を避けるために、モンゴメリ（Montgomery）がMathematics of Computation， Vol.44, No.170, pp.519-521， April, 1985に掲載された“Modular Multiplication without Trial Division”で提案した剰余乗算方法（以下、モンゴメリ乗算と呼ぶ）を利用することで、剰余演算系における除算を行わずに剰余乗算を実現している。
【００１４】
しかし、モンゴメリ乗算は、整数にモンゴメリ定数と呼ばれる定数を乗じる必要があるが、このモンゴメリ定数の計算には除算が必要であり、この除算を剰余演算系で行う効率的な方法が知られていないため、モンゴメリ定数を基数表現で計算している。
【００１５】
ここでは、モンゴメリ乗算を例に挙げたが、モンゴメリ乗算に限らず、剰余算を行うアルゴリズムにおいては除算を行う必要性が生じる。
【００１６】
【発明が解決しようとする課題】
以上説明したように、剰余演算系における除算の効率的なアルゴリズムが要望されるものの、未だにその要望を満たせない状況にある。
【００１７】
本発明は上記実情を考慮してなされたもので、剰余演算系で除算を効率的に実行し得る剰余演算装置及び方法を提供することを目的とする。
【００１８】
また、本発明の他の目的は、特に、剰余演算系の基底の幾つかの要素の積が除算の法の場合に、剰余演算系で除算を効率的に実行し得ることにある。
【００１９】
【課題を解決するための手段】
第１の発明は、剰余演算系の基底を｛ａ１，ａ２，…，ａｎ｝（ｎは整数）とし且つＡ＝ａ１ａ２…ａｎとした際に、｛ａ１，ａ２，…，ａｎ｝から任意に１つの基底要素ａｉ（１≦ｉ≦ｎ）を選択し、このａｉの選択情報及びＡ未満の正の整数ｘが入力されたとき、前記ｘをａｉで除した商ｚを出力可能な、剰余演算機能を有する複数の演算ユニットを備えた剰余演算装置において、前記選択情報に基づいて、前記ｘの剰余演算系表現の各値ｘ１，…，ｘｎから前記基底要素ａｉに対応する値ｘｉを減じるように、前記各演算ユニットを制御する減算制御手段と、前記減算制御手段により得られた各値（ｘ１−ｘｉ），…，（ｘｎ−ｘｉ）（但し、（ｘｉ−ｘｉ）を除く）に対し、前記基底要素ａｉの乗法逆元ａｉ-1を乗じるように、前記各演算ユニットを制御する乗算制御手段と、前記乗算制御手段により得られた乗算結果を商ｚとして出力する出力手段と、を備えた剰余演算装置である。
【００２０】
このように、減算制御手段の制御により、各演算ユニットがｘの剰余演算系表現の各値からｘｉ（＝ｘ ｍｏｄ ａｉ）を減じてａｉの倍数としておき、乗算制御手段の制御により、各演算ユニットが減算結果に乗法逆元を乗算して除算結果を得るので、剰余演算系で除算を効率的に実行することができる。
【００２１】
なお、第１の発明は、「装置」として表現したが、「システム」、「方法」、「プログラム」又は「記憶媒体」等として表現してもよいことは言うまでもない。
【００２２】
【発明の実施の形態】
以下、本発明の各実施形態について図面を参照して説明する。
（第１の実施形態）
図１は本発明の第１の実施形態に係る剰余演算装置の主要部分の構成を示す模式図である。この剰余演算装置１０は、ｎ個の演算ユニット２０１〜２０ｎが制御装置３０に接続されている。
【００２３】
ここで、各演算ユニット２０１〜２０ｎは、それぞれ対応する添字のＲＯＭ２１１〜２１ｎ、ＲＡＭ２２１〜２２ｎ及び積和回路２３１〜２３ｎを備えている。
【００２４】
ＲＯＭ２１１〜２１ｎは、制御装置３０により読出制御される読出専用メモリであり、対応する積和回路２３１〜２３ｎで用いる剰余演算系の基底要素ａ１，…，ａｎ、及び他の基底要素ａｊ（ｊ≠１，…，ｎ）の乗法逆元値ａｊ-1を保持し、保持内容を制御装置３０からの制御により、対応する積和回路２３１〜２３ｎに転送可能となっている。
【００２５】
なお、剰余演算系のｎ個の基底要素ａ１，…，ａｎは、どの２つ同士も互いに素な正の整数が使用されている。また、一般には剰余演算系の基底要素ａ１，…，ａｎの個数と、積和回路２３１〜２３ｎの個数とは一致しなくてよいが、ここでは簡単のため、共にｎ個とする。また、基底としては、２のべき又は２のべきに近接する値が用いられる。
【００２６】
乗法逆元値ａｊ-1は、剰余演算系の基底が定まれば決まる値なので、事前計算して格納するが、ＲＯＭ２１１〜２１ｎに限らず、ＲＡＭ２２１〜２２ｎや図示しない他のメモリ（例えばＥＥＰＲＯＭ）に格納されていてもよい。
【００２７】
ＲＡＭ２２１〜２２ｎは、制御装置３０により読出／書込制御される随時書込読出メモリであり、積和回路２３１〜２３ｎへの入力データや、積和回路２３１〜２３ｎからの演算の中間結果データ、及び演算ユニット２０１〜２０ｎ外部への出力データ、といった各データを保持するために用いられる。
【００２８】
制御装置３０は、図２に示す除算アルゴリズムに基づいて、各演算ユニット２０１〜２０ｎや入出力データを制御することにより、所定の演算を実行させる機能をもっている。
【００２９】
なお、以上のような各ユニット２０１〜２０ｎ及び装置３０はそれぞれハードウェア、ソフトウェア又はその組合せにより構成可能となっている。ここで、各ユニット２０１〜２０ｎ及び装置３０がソフトウェアにより構成される場合、後述する各機能を実現させるための剰余演算プログラムが予め剰余演算装置１０のコンピュータにインストールされている。なお、ハードウェア及び／又はソフトウェアにより各ユニット２０１〜２０ｎ及び装置３０を個別に構成可能な旨の説明は、以下の各実施形態にも適用される。
【００３０】
次に、以上のように構成された剰余演算装置の除算動作を図２及び図３を用いて説明する。始めに、図２を用いて原理的に述べ、その後、図３を用いて計算例を述べる。
【００３１】
剰余演算装置１０は、図２の左側に示すように、剰余演算系での除算を行う。なお、図２の右側は、説明の便宜上、対応する基数表現を示している。例えばStep１では、剰余演算系の表現が（ｘ１，ｘ２，…，ｘｉ，…，ｘn-1，ｘｎ）であり、これに対応する基数表現がｘであることを示している。なお、従来の技術で述べたように、ｘｊ＝ｘ ｍｏｄ ａｊ（ｊ＝１，２，…，ｎ）の関係がある。この関係は、基数表現の正の整数ｘが剰余演算系の全ての基底要素の積Ａ＝ａ１ａ２…ａｎより小さいとき（ｘ＜Ａ）、一対一の対応関係となる。
【００３２】
続いて、入力（ｘ＜Ａ）と、任意に選んだ１つの基底要素ａｉからｘ／ａｉの商を求める方法を図２の各ステップＳＴ１〜ＳＴ５に沿って述べる。
【００３３】
（ＳＴ１）  制御装置３０は、入力データｘ１〜ｘｎを対応する各ＲＡＭ２２１〜２２ｎに書込む。
【００３４】
（ＳＴ２）  制御装置３０は、選択した基底要素ａｉに基づいて、対応するＲＡＭ２２ｉ内の値ｘｉを調べ、各積和回路２３１〜２３ｎに対応するＲＡＭ２２１〜２３ｎ内の値ｘ１〜ｘｎからｘｉを減じるように命令する。
【００３５】
（ＳＴ３）  各積和回路２３ｊ（ｊ＝１，２，…，ｎ）は、ｙｊ＝ｘｊ−ｘｉｍｏｄ ａｊを実行し、結果ｙｊを各ＲＡＭ２２ｊに格納する。基数表現での対応する演算はｙ＝ｘ−ｘｉである。
【００３６】
（ＳＴ４）  制御装置３０は、ｎ−１個の積和回路２３ｊ（ｊ＝１，２，…，ｎ、ｊ≠ｉ）に対して、ＲＡＭ２２ｊ内の値ｙｊにａｉの乗法逆元ａｉ-1 ｍｏｄ ａｊを乗じるように命令する。但し、この命令は、ｘｉに対応する積和回路２３ｉには与えない。なお、剰余演算系における乗法逆元の乗算は、基数表現における除算に相当する。
【００３７】
（ＳＴ５）  各積和回路２３ｊ（ｊ＝１，２，…，ｎ、ｊ≠ｉ）は、ｚｊ＝ｙｊ×ａｉ-1 ｍｏｄ ａｊを実行し、結果ｚｊを各ＲＡＭ１２ｊに格納する。なお、ｙは、前述した通り、ｘからｘｉ（＝ｘ ｍｏｄ ａｉ）を減じた値であるのでａｉの倍数である。このため、除算の商ｙ／ａｉは整数となる。従って、ｚ＝ｙ／ａｉが対応する基数表現での演算となる。
【００３８】
この５ステップの結果、ＲＡＭ２２ｊ（ｊ＝１，２，…，ｎ、ｊ≠ｉ）に格納された計算結果ｚｊが商ｚの剰余演算系表現となっている。但し、基底要素ａｉに対応するｚの成分（ｚｉ）が未計算のため（図２のステップＳＴ５では未計算を示すため、ｚｉの箇所に×という印をつけている）、ｚｊで表現できる最大の数はＡ／ａｉとなる。しかしながら、商ｚ＝ｙ／ａｉ≦ｘ／ａｉ＜Ａ／ａｉであるので、この計算結果ｚｊは、商ｚの正しい値を表現している。
【００３９】
以上により、ｘ／ａｉを剰余演算装置１０で計算することができる。
【００４０】
次に、選ばれた基底要素が２個以上の場合について説明する。この場合も上述した５つのステップを選ばれた基底要素の個数分だけ繰り返すことで実現できる。以下、図３を用いて具体例で説明する。
図３に示すように、剰余演算系の基底の要素数ｎ＝４とし、各要素ａ１，ａ２，ａ３，ａ４の値をそれぞれ７、１１、１３、１７としている。
この例は、入力ｘ＝４５６７＜ａ１ａ２ａ３ａ４＝１７０１７であり、基底要素からａ１，ａ４を選んで商４５６７／（７×１７）＝３８を剰余演算系で求める手順を表している。
【００４１】
（ＳＴ１’）  制御装置３０は、入力データ３，２，４，１１を各ＲＡＭ２２１〜２２４に書込む。なお、各入力データ３，２，４，１１は、入力ｘ＝４５６７を剰余演算系で表したものである。例えばｘ１＝４５６７ ｍｏｄ７＝３なので、ａ１＝７の下に３と記述されている。
【００４２】
（ＳＴ２’）  制御装置３０は、選択した基底要素ａ１，ａ４のうち、まず、一方の基底要素ａ１に基づき、対応するＲＡＭ２２１内の値ｘ１＝３を読出し、各積和回路２３１〜２３４に、対応するＲＡＭ２２１〜２２４内の値３，２，４，１１から３を減じるように命令する。
【００４３】
（ＳＴ３’）  その結果、各成分の値はステップＳＴ３’に示した値０，１０，１，８になる。対応する基数表現での値は、４５６７−３＝４５６４である。
【００４４】
（ＳＴ４’）  制御装置３０は、３個の積和回路２３２〜２３４に対し、ＲＡＭ２２２〜２２４の値１０，１，８にその基底要素を法とするａ１の乗法逆元７-1を乗じるように命令する。例えばａ１-1 ｍｏｄ ａ２＝８であるから、ａ２の成分は１０×８ ｍｏｄ １１＝３となる。但し基底要素ａ１に対してはａ１の乗法逆元が存在しないので、ａ１の成分に対応する積和回路２３１には命令を出さない。
【００４５】
（ＳＴ５’）  ａ１の乗法逆元ａ１-1の乗算の結果、各成分の値はステップＳＴ５’で表示した値×，３，２，６になる。但しａ１の成分×は無視する。この場合、剰余演算系で一意的に表示できる数はａ２ａ３ａ４＝２４３１までという制約がつくが、元の入力ｘ＜ａ１ａ２ａ３ａ４であったので、ａ１＝７での除算結果ｘ／ａ１＜ａ２ａ３ａ４となり、正しく表現できている。対応する基数表現での値は４５６４／７＝６５２である。無視したａ１の成分は、以下では演算を行わない。
【００４６】
さて図２の説明では選択した基底要素が１個だけだったのでこれで除算が終了したが、図３の例では基底要素を２個選択しているので、２個目の選択した基底要素ａ４に対しても図２と同じ演算を行う。但し１個目で選択した基底要素ａ１で表現している値は、ステップＳＴ５’終了時では計算されていないので、以下ではこの基底要素ａ１に対応する演算を行わない。
【００４７】
（ＳＴ２”）  次に選んだ基底要素ａ４＝１７に注目する。ａ４の成分は６であるから、各成分から６を減じる。
【００４８】
（ＳＴ３”）その結果、各成分の値はステップＳＴ３”に表示した値になる。対応する基数表現での値は、６５２−６＝６４６である。
【００４９】
（ＳＴ４”）  ステップＳＴ３”の値に対し、ａ４＝１７の乗法逆元１７-1を乗算する。但し基底要素ａ４に対してはａ４の乗法逆元が存在しないのでａ４の成分に対する演算を行わない。
【００５０】
（ＳＴ５”）  ａ４の乗法逆元１７-1の乗算の結果、各成分の値はステップＳＴ５”で表示した値になる。但しａ４の値は無視する。剰余演算系で一意的に表示できる数はａ２ａ３までだが、ステップＳＴ５’で述べた理由と同じ理由により、この２つの基底での表現で正しく表現できている。対応する基数表現での値は６４６／１７＝３８である。
【００５１】
以上で選んだ基底要素ａ１，ａ４について全て演算が終わったので、基底要素ａ２とａ３に保持している値（５及び１２）が求めたい商の基底｛ａ２，ａ３｝の下での剰余演算系表現となる。
【００５２】
上述したように本実施形態によれば、剰余演算系の基底のいくつかの要素の積が除算の法の場合に、剰余演算系で除算を効率的に行うことができる。
【００５３】
また、剰余演算系表現で演算を行う場合、途中で除算処理が生じても基数表現に変更することなく、そのまま剰余演算系表現で処理を行えるため、処理の高速化を期待することができる。
【００５４】
（第２の実施形態）
図４は本発明の第２の実施形態に係る剰余演算装置の主要部分の構成を示す模式図であり、図１と同一部分には同一符号を付し、変形した部分には記号（’）を付して重複した説明を省略し、ここでは異なる部分について主に述べる。なお、以下の各実施形態も同様にして重複した説明を省略する。
【００５５】
すなわち、本実施形態は、第１の実施形態の変形例であり、バレット・リダクションアルゴリズムへの適用を図るものであって、具体的には、図４に示すように、制御装置３０に代えて、バレット・リダクションアルゴリズム及び川村の手法（特開２００１−１９４９９３）を利用可能な制御装置３０’を設け、また川村の手法に述べられるビット選択部４１及び補正項演算ユニット４２を備えている。また、各積和回路２３１’〜２３ｎ’は、補正項演算ユニット４２から制御可能なものとなっている。
【００５６】
まず、基数表現（ｂ進数、ｂは正の整数）におけるバレット・リダクションアルゴリズムを説明する（P. D. Barrett, “Implementing the Rivest, Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor”, Advances in Cryptology, Proc. Crypto ’86, pp.311-323, 1987.）。
【００５７】
なお、以下の説明では、正の整数ｓのｂ進数での表現をｓ＝（ｓk-1 …ｓ１ｓ０）ｂと表す。これはｓ＝ｓk-1ｂk-1＋…＋ｓ１ｂ＋ｓ０である旨を意味している。
【００５８】
バレット・リダクションは、剰余算を、試行割算を用いずに加算と乗算のみで行なうアルゴリズムであり、ｘ ｍｏｄ Ｎの計算において、Ｎの倍数でｘを近似する際に、上位桁で近似するという特色がある。
具体的にはバレット・リダクションは、ｘ＝（ｘ2k-1…ｘ１ｘ０）ｂ、Ｎ＝（Ｎk-1…Ｎ１Ｎ０）ｂ、Ｎk-1≠０を入力としたとき、ｚ＝ｘ ｍｏｄ Ｎを出力するもので、次の８ステップＳＴ１１〜ＳＴ１８からなる。
【００５９】
事前計算：μ＝ Quot（ｂ2k／Ｎ）
（ＳＴ１１）  ｑ１← Quot（ｘ／ｂk-1）
（ＳＴ１２）  ｑ２←ｑ１・μ
（ＳＴ１３）  ｑ３← Quot（ｑ２／ｂk+1）
（ＳＴ１４）  ｒ１← ｘ ｍｏｄ ｂk+1
（ＳＴ１５）  ｒ２ ← ｑ３・ｍ ｍｏｄ ｂk+1
（ＳＴ１６）  ｚ ← ｒ１−ｒ２
（ＳＴ１７）  もしｚ＜０ならｚ←ｚ＋ｂk+1
（ＳＴ１８）  ｚ≧Ｎである間、ｚ←ｚ−Ｎ
ここで、Quot（ｓ／ｔ）はｓをｔで割ったときの商を表す。
【００６０】
これを剰余演算系で行うために、以下のように若干変更する。
【００６１】
まず｛ｂ１，ｂ２，…，ｂｋ，ｂk+1，…，ｂ2k，ｂ2k+1｝を剰余演算系の基底とし、ｂｋ＜ｂ2k+1とする。Ｎをｂ１ｂ２…ｂk-1＜Ｎ＜ｂ１ｂ２…ｂｋを満たす整数とする。このときｘ＜Ｎ２なるｘに対して、ｚ＝ｘ ｍｏｄ Ｎは次の６ステップＳＴ２１〜ＳＴ２６で計算される。
【００６２】
事前計算：μ＝ Quot（ｂ１ｂ２…ｂ2k／Ｎ）
（ＳＴ２１）  ｑ１← Quot（ｘ／ｂ１ｂ２…ｂk-1）
（ＳＴ２２）  ｑ２←ｑ１・μ
（ＳＴ２３）  ｑ３← Quot（ｑ２／ｂｋｂk+1…ｂ2k）
（ＳＴ２４）  ｒ２← ｑ３・Ｎ
（ＳＴ２５）  ｚ ← ｘ−ｒ２
（ＳＴ２６）  ｚ≧Ｎである間、ｚ←ｚ−Ｎ
基数表現でのバレット・リダクションと比較すると、基数ｂを剰余演算系の基底要素に置き換えているのが大きな違いである。基数表現では、基数ｂが一定であるためステップＳＴ１１などではｂのべき乗が使われていたが、剰余演算系では基底の要素が互いに異なるため、ステップＳＴ２１のように基底要素の積に置き換わっている。
【００６３】
その点を考慮すると、上のアルゴリズムの事前計算、ステップＳＴ２１〜ＳＴ２３は、基数表現でのバレット・リダクションに対応した演算となっている。ステップＳＴ２４，ＳＴ２５は、基数表現でのステップＳＴ１４〜ＳＴ１６に対応しているが、剰余演算系では大小関係の比較が困難なため、基数表現におけるｍｏｄ ｂk+1に対応する演算を省略している。
【００６４】
本実施形態は、このような演算により、基数表現でのステップＳＴ１７での比較操作を回避できる。なぜなら、ｑ３は本来の商をＱ＝ Quot（ｘ／Ｎ）としたとき、Ｑ−２≦ｑ３≦Ｑの範囲にあるので、ステップＳＴ２５の減算結果の出力ｚが必ず正になるからである。
【００６５】
またｑ３のこの評価式より、ステップＳＴ２５の出力は、本来のｘ ｍｏｄ ＮをＲとしたとき、Ｒ、Ｒ＋Ｎ、Ｒ＋２Ｎのいずれかとなる。Ｒ＋Ｎ、Ｒ＋２Ｎだったときの場合のため、ステップＳＴ２６で正しいＲの値に調節する。
【００６６】
また、演算の途中結果は全て基底の積ｂ１ｂ２…ｂ2kｂ2k+1以下になっている必要があるが、ｂｋ＜ｂ2k+1となるようにｂ2k+1を選んであるので、これを満たしていることも確認できる。
【００６７】
上で説明した剰余演算系でのバレット・リダクションを剰余演算装置１０’を用いて行う手法について説明する。ここで図４における積和回路２３１’〜２３ｎ’の個数ｎと、剰余演算系の基底要素の個数２ｋ＋１とは、一般には一致しなくてよいが、ここでは簡単のためｎ＝２ｋ＋１とする。
【００６８】
また、整数ｘ＜Ｎ２の剰余演算系の表現をｘ＝（ｘ１，ｘ２，…，ｘ2k，ｘ2k+1）とする。ここでｘｉ＝ｘ ｍｏｄ ｂｉであるのは前述の通りである。
【００６９】
（事前計算）  μ＝ Quot（ｂ１ｂ２…ｂ2k／Ｎ）は、基数表現の下での除算を行うことで実現する。この結果を剰余演算系表現した（μ１，μ２，…，μ2k，μ2k+1）をそれぞれ図４の対応するＲＡＭ２２ｉに格納する。
【００７０】
（ＳＴ２１）  商ｑ１を求める計算は、第１の実施形態で説明した手法により行う。入力は、ｘ及び、基底要素としてｂ１，ｂ２，…，ｂk-1のｋ−１個を選んだという情報である。この商計算の結果ｑ１として、各ＲＡＭ２２ｉに格納された値ｑ１を図５のＳＴ２１に示す。
【００７１】
選択した基底要素がｂ１，ｂ２，…，ｂk-1であったので、前述同様に、対応する剰余演算系表現の値が未計算となる。換言すると、ｑ１の剰余演算系表示は、基底｛ｂｋ，ｂk+1，…，ｂ2k+1 ｝の下で（ｑ１_ｋ，ｑ１_(k+1)，…，ｑ１_(2k+1)）と表現され、基底要素ｂ１，ｂ２，…，ｂk-1にはｑ１の剰余演算系表現の値が格納されない。
【００７２】
そこで、川村の基底拡張の手法により、（ｑ１_ｋ，ｑ１_(k+1)，…，ｑ１_(2k+1)）から図５のＳＴ２１−２に示すように、ｑ１を全ての基底｛ｂ１，ｂ２，…，ｂｋ，ｂk+1，…，ｂ2k，ｂ2k+1｝に拡張した剰余演算系表現を求める。
【００７３】
（ＳＴ２２）  このようにして拡張された商ｑ１にμを乗じる。この乗算は各積和回路２３１’〜２３ｎ’での並列乗算で実現できる。
【００７４】
（ＳＴ２３）  再び第１の実施形態で説明した手法により、入力ｑ２及び基底要素としてｂｋ，ｂk+1，…，ｂ2kのｋ＋１個を選んだという選択情報で商ｑ３を求める。求められた商ｑ３は、図６のＳＴ２３に示すように、基底｛ｂ１，ｂ２，…，ｂｋ-1，ｂ2k+1｝の下での表現なので、ＳＴ２１と同様に基底拡張を用いて全ての基底｛ｂ１，ｂ２，…，ｂｋ，ｂk+1，…，ｂ2k，ｂ2k+1｝を用いた剰余演算系表現にする（図６：ＳＴ２３−２）。
【００７５】
（ＳＴ２４）  このように拡張されたｑ３にＮを乗じる。この乗算は各積和回路２３１’〜２３ｎ’での並列乗算で実現できる。
【００７６】
（ＳＴ２５）  各積和回路２３１’〜２３ｎ’での並列減算で実現できる。
【００７７】
（ＳＴ２６）  この演算は大小比較があるので、ステップＳＴ２５で得られたｚを基数表現に戻してから行う。
【００７８】
上述したように本実施形態によれば、ｘ ｍｏｄ Ｎを求めるバレット・リダクションを剰余演算系表現で並列処理することができ、基数表現で行う場合よりも処理の高速化を期待することができる。
【００７９】
（第３の実施形態）
次に、本発明の第３の実施形態に係る剰余演算装置について図４を参照しながら図７を用いて説明する。この剰余演算装置は、図４と同一要素からなる装置であって、バレット・リダクションを用いてＲＳＡ暗号などに用いられる,べき乗剰余算を行うものである。
【００８０】
べき乗剰余算は、Ｃ＝ＭE ｍｏｄ Ｎ という式で表される。この演算は一般に次の５つのステップＳＴ３１〜ＳＴ３５のように行われる。
【００８１】
Ｅの２進数での表現をＥ＝（Ｅm-1Ｅ１Ｅ０）２、Ｅm-1≠０とするとき、
（ＳＴ３１）  Ｃ ← １
（ＳＴ３２）  ｉ＝ｍ−１から０まで以下のＳＴ３３とＳＴ３４をループ
（ＳＴ３３）  Ｃ ← Ｃ２ ｍｏｄ Ｎ
（ＳＴ３４）  もしＥｉ＝１ならＣ ← Ｃ×Ｍ ｍｏｄ Ｎ
（ＳＴ３５）  Ｃを出力
本実施形態は、ステップＳＴ３３，ＳＴ３４の演算を剰余演算系で行うものである。ステップＳＴ３３，ＳＴ３４の剰余乗算は、乗算後にＮでの剰余を求めるという手法を用いる。乗算は、剰余演算系で並列乗算で実現できる。Ｎでの剰余を求める際に、第２の実施形態で説明したバレット・リダクションアルゴリズムＳＴ２１〜ＳＴ２６を利用する。
【００８２】
（ＳＴ３０）  図７ではまず、べき指数Ｅと剰余演算系表示したＭ＝（Ｍ１，Ｍ２，…，Ｍ2k+1）を入力する。
【００８３】
（ＳＴ３１）  次に（Ｃ１，Ｃ２，…，Ｃ2k+1）を全て１に初期化する。
【００８４】
（ＳＴ３２）  ステップＳＴ３１の初期設定のもと、ｉ＝ｍ−１から０までループを行う。
【００８５】
（ＳＴ３３−１）  ２乗算（Ｃ１，Ｃ２，…，Ｃ2k+1）←（Ｃ１，Ｃ２，…，Ｃ2k+1）×（Ｃ１，Ｃ２，…，Ｃ2k+1）を行なう。これは剰余演算系で並列乗算で実現できる。２乗算の結果をｍｏｄ Ｎするためにバレット・リダクションＢＲを行なう（ＳＴ３３−２）。
【００８６】
（ＳＴ３４−０）  Ｅｉ＝１である場合に演算を行なう。
【００８７】
（ＳＴ３４−１）  乗算（Ｃ１，Ｃ２，…，Ｃ2k+1）←（Ｃ１，Ｃ２，…，Ｃ2k+1）×（Ｍ１，Ｍ２，…，Ｍ2k+1）は、剰余演算系で並列乗算で実現できる。乗算結果をバレット・リダクションでｍｏｄ Ｎする（ＳＴ３４−２）。
【００８８】
（ＳＴ３５）  ループが終了したら、そのときの（Ｃ１，Ｃ２，…，Ｃ2k+1）を出力する。
【００８９】
但し、べき乗剰余算で第２の実施例で説明したバレット・リダクションを用いると、バレット・リダクションの最後のステップＳＴ２６で一旦基数表現に戻して大小比較を行い、剰余を決定するため、剰余演算系での並列計算による処理速度向上の長所を生かしきれていない。
【００９０】
そのため、第２の実施形態で説明した剰余演算系でのバレット・リダクションアルゴリズムのＳＴ２５で終了するようにする。この場合、出力ｚがＮより大きい可能性があるので、バレット・リダクションアルゴリズムを次のように行うことにする。
【００９１】
すなわち、｛ｂ１，ｂ２，…，ｂｋ，ｂk+1，…，ｂ2k，ｂ2k+1｝を剰余演算系の基底とする。法Ｎは、ｂ１ｂ２…ｂk-1＜Ｎ、９Ｎ＜ｂ１ｂ２…ｂｋを満たす整数とする。
【００９２】
このとき、入力ｘが０＜ｘ＜９Ｎ２＜ｂ１ｂ２…ｂ2kを満たせば、下のアルゴリズムで出力されるｚは、ｚ＝ｘ ｍｏｄ Ｎ、０≦ｚ＜３Ｎを満たす。
【００９３】
事前計算：μ＝ Quot（ｂ１ｂ２…ｂ2k／Ｎ）
（ＳＴ２１）  ｑ１← Quot（ｘ／ｂ１ｂ２…ｂk-1）
（ＳＴ２２）  ｑ２←ｑ１・μ
（ＳＴ２３）  ｑ３← Quot（ｑ２／ｂｋｂk+1…ｂ2k）
（ＳＴ２４）  ｒ２← ｑ３・Ｎ
（ＳＴ２５）  ｚ ← ｘ−ｒ２
このアルゴリズムにより、剰余乗算ｚ＝ｘｙ ｍｏｄ Ｎを剰余演算系の乗算とバレット・リダクションを組合せて実行すると、ｘ＜３Ｎ，ｙ＜３Ｎであればｘｙ＜９Ｎ２であるのでｚ＜３Ｎという出力が得られる。ここで、入力と出力の範囲が同じであるので、べき乗剰余算において繰り返し剰余乗算を行うことができる。
【００９４】
また、べき乗剰余算アルゴリズムのステップＳＴ３５で最終的なＣを出力するとき、最後のバレット・リダクションではＣ＜３Ｎにしかサイズが抑えられていないので、基数表現に変換して必要な回数だけＮを減じることにより、Ｃ＜Ｎなる出力を得ることができる。
【００９５】
上述したように本実施形態によれば、ＳＴ３０〜ＳＴ３５に示すように、バレット・リダクションを利用したべき乗剰余算を、剰余演算系で並列処理することができ、基数表現で行う場合よりも処理の高速化が期待できる。
【００９６】
また、基数表現で行っていたバレット・リダクションを、剰余演算系で並列計算することによる効果は、次のように見積られる。
【００９７】
まず、剰余乗算１回あたりの演算量を考える。最初の乗算で、１回の並列乗算が必要である。その後のバレット・リダクションにより剰余を求める。
【００９８】
（ＳＴ２１）  商を求めるのに、並列乗算がｋ−１回、並列加算がｋ−１回必要である。また、基底拡張に並列乗算がｋ＋２回、並列加算が２（ｋ＋１）回必要である。
【００９９】
（ＳＴ２２）  並列乗算が１回必要である。
【０１００】
（ＳＴ２３）  商を求めるのに、並列乗算がｋ＋１回、並列加算がｋ＋１回必要であり、さらに基底拡張に並列乗算がｋ回、並列加算が２（ｋ−１）回必要である。
【０１０１】
（ＳＴ２４）  並列乗算が１回必要である。
【０１０２】
（ＳＴ２５）  並列加算が１回必要である。
【０１０３】
以上をまとめると、剰余乗算１回あたり、並列乗算が４ｋ＋４回、並列加算が６ｋ＋１回必要である。
【０１０４】
ここで、Ｎのビット数を、現在のＲＳＡ暗号で用いられている1,024とし、剰余演算系の基底要素の大きさを３２ビットとする。このとき、ｋ＝３３と取れば1,024ビットの数が表現でき、また表現するための最小のｋであることが分かる。この値を上の式に代入すると、１回の剰余乗算あたり、並列乗算が１３７回、並列加算が１９９回必要であることが分かる。
【０１０５】
一般に乗算は、オペランドのビット長の２乗に比例する時間がかかるので、３２ビットの乗算は1,024ビットの乗算の１／３２２＝１／1,024の時間で処理できる。そのため、1,024ビットの乗算に比べて剰余演算系でのバレット・リダクションを用いた剰余乗算は約１３７／1,024＝０.１３の時間で処理できる。
【０１０６】
ここで、加算は、乗算に比べて処理量が少ないので無視した。また、この比較には1,024ビットでの剰余算の時間は含まれていないので、ここで見積もった０.１３よりさらに小さな割合の時間で処理できることが期待できる。
【０１０７】
なお、上記各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１０８】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１０９】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行しても良い。
【０１１０】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１１１】
また、記憶媒体は１つに限らず、複数の媒体から本実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１１２】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１１３】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１１４】
なお、本願発明は、上記各実施形態に限定されるものでなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。また、各実施形態は可能な限り適宜組み合わせて実施してもよく、その場合、組み合わされた効果が得られる。さらに、上記各実施形態には種々の段階の発明が含まれており、開示される複数の構成用件における適宜な組み合わせにより種々の発明が抽出され得る。例えば実施形態に示される全構成要件から幾つかの構成要件が省略されることで発明が抽出された場合には、その抽出された発明を実施する場合には省略部分が周知慣用技術で適宜補われるものである。
【０１１５】
その他、本発明はその要旨を逸脱しない範囲で種々変形して実施できる。
【０１１６】
【発明の効果】
以上説明したように本発明によれば、剰余演算系の基底の幾つかの要素の積が除算対象の場合に、剰余演算系で除算を効率的に実行できる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態に係る剰余演算装置の主要部分の構成を示す模式図。
【図２】同実施形態における動作を説明するための模式図。
【図３】同実施形態における動作の具体例を説明するための模式図。
【図４】本発明の第２の実施形態に係る剰余演算装置の主要部分の構成を示す模式図。
【図５】同実施形態における基底拡張の適用を示す模式図。
【図６】同実施形態における基底拡張の適用を示す模式図。
【図７】本発明の第３の実施形態に係る剰余演算装置の動作を説明するためのフローチャート。
【符号の説明】
１０，１０’…剰余演算装置
２０１〜２０ｎ…演算ユニット
２１１〜２１ｎ…ＲＯＭ
２２１〜２２ｎ…ＲＡＭ
２３１〜２３ｎ，２３１’〜２３ｎ’…積和回路
３０，３０’…制御装置
【図１】
0004080754.tif 000002
【図２】
0004080754.tif 000003
【図３】
0004080754.tif 000004
【図４】
0004080754.tif 000005
【図５】
0004080754.tif 000006
【図６】
0004080754.tif 000007
【図７】
0004080754.tif 000008