(57)【要約】      （修正有）【課題】楕円曲線暗号等に必要な種々の多倍長演算を高速に実行することが可能な多倍長演算装置を提供する。【解決手段】演算対象となるｎワード長の整数や演算結果等を一時的に記憶するための２個のデュアルポートメモリ４１、４２からなるメモリ部４０と、ワード単位で加算及び乗算を含む２以上の種類の演算を実行し、１ワード長の演算結果を出力する演算部２０と、メモリ部４０から演算部２０に最大３つの１ワードデータを供給すると同時に、演算部２０からの１ワード長の演算結果をメモリ部４０に格納するメモリ入出力部３０と、演算部２０及びメモリ入出力部３０を制御することにより、演算部２０にｎワード長の加算剰余及びモンゴメリリダクションのいずれかの演算を実行させる制御を行う制御部１０とを備える。【選択図】図１
2010044398.tif 000002
【特許請求の範囲】
【請求項１】
外部装置からの指示に従って、２以上のワード長の整数を対象とする加算剰余とモンゴメリリダクションとを選択的に実行する多倍長演算装置であって、
メモリと、
ワード単位で、加算及び乗算を含む２以上の種類の演算を実行し、１ワード長の演算結果を出力する演算器と、
加算剰余又はモンゴメリリダクションの対象となる少なくとも１つの整数を前記外部装置から前記メモリに第１データ転送と、前記メモリに格納された整数をワード単位で演算器に入力させる第２データ転送と、前記演算器から出力される演算結果を前記メモリに格納する第３データ転送と、前記演算結果を前記メモリから前記外部装置に出力する第４データ転送とを行うメモリ入出力回路と、
前記外部装置からの指示に従って、前記メモリ入出力回路に対して実行すべき前記第２及び第３データ転送の対象を指示して制御し、前記演算器に対して実行すべき演算の種類を指示して制御することにより、前記演算部に前記メモリに格納された整数に対する加算剰余とモンゴメリリダクションとを、選択的に実行させ、前記メモリ入出力回路に前記剰余演算の結果を前記メモリに格納させる制御回路とを備え、
前記演算器は、
２個の１ワード長データを入力とし、入力された２個の１ワード長データを乗じて、２ワード長データを出力する乗算器と、
前記乗算器から出力される２ワード長データを含む３個の２ワード長データ及び直前の算術加算において得られた１個のキャリーデータを入力とし、３個の２ワード長データ及び１個のキャリーデータを算術加算して、１個の２ワード長データ及び１個のキャリーデータとを出力する３入力加算器とを含み、
前記演算器は、前記演算結果として、前記３入力加算器から出力された１個の２ワード長データの下位の１ワード長データ及びキャリーデータを出力し、
（ａ）前記外部装置から加算剰余を実行する旨及び加算剰余の対象となる整数のワード数ｎの指示を受けた場合に、前記制御回路は、前記メモリ入出力回路及び前記演算器が以下の処理（i）〜（iii）を実行するように前記メモリ入出力回路及び前記演算器を制御する。
（i）前記メモリ入出力回路は、加算剰余の対象となる２つのｎワード長の整数Ａ及びＢと法を示すｎワード長の整数Ｐとを前記外部装置から取得して前記メモリに格納し、
（ii）前記メモリ入出力回路は、前記メモリに格納された前記整数Ａ、Ｂ及びＰそれぞれから同一桁の１ワード長のデータａ、ｂ及びｐを同時に読み出して前記演算器に入力させると共に、前記演算器から出力される１ワード長のデータｗを前記メモリに格納することを、最下位ワードから順にｎワード分だけ繰り返すことにより、ｎワード長の整数Ｗを前記メモリに格納し、
（iii）前記演算器は、前記メモリ入出力回路から送られてくるデータａ、ｂ及びｐに対して、キャリーを伝播させながら、ａ＋ｂ−ｐを算出し、その結果ｗを出力することをｎ回繰り返す。
（ｂ）前記モンゴメリリダクションは、１ワードをｋビット、整数Ａを２ｎワード長の
入力データ、整数Ｒを２＾（ｋ×ｎ）としたときに、ｎワード長の整数Ｐを法とするＡ・Ｒ＾（−１）の剰余を算出するための演算であり、前記外部装置からモンゴメリリダクションを実行する旨及びモンゴメリリダクションの対象となる整数Ａのワード数２ｎの指示を受けた場合に、前記制御回路は、前記メモリ入出力回路及び前記演算器が以下の処理（I）〜（V）で示されるモンゴメリリダクションを実行するように前記メモリ入出力回路及び前記演算器を制御する。
（I）前記メモリ入出力回路は、前記整数Ａ、Ｐ、及び、前記整数Ｒを法とする−Ｐ＾（−１）の剰余である整数Ｖとを前記外部装置から取得して前記メモリに格納し、
（II）前記演算器は、前記メモリに格納された前記整数Ａの下位ｎワードと前記整数Ｖとのワードごとの部分積の算出とそれら部分積における同一ワードの累算とを、最下位ワードから順に累算結果が得られるようにｎワードだけ繰り返し、その累算結果をｎワードの中間データＢとして前記メモリに格納し、
（III）前記演算器は、前記メモリに格納された前記中間データＢと整数Ｐとのワードごとの部分積の算出とそれら部分積における同一ワードの累算とを、最下位ワードを第０ワードとしたときの第０ワードから第（ｎ−３）は求めずに、第（ｎ−２）ワードから第（２ｎ−１）ワードまでを求め、その累算結果の上位（ｎ＋１）ワードを中間データＤとして前記メモリに格納し、
（IV）前記演算器は、前記整数Ａの上位（ｎ＋１）ワードを整数ＡＡとしたときに、前記メモリに格納された前記中間データＤ及び前記整数ＡＡそれぞれの最下位ワードを加算したときのキャリーと、その加算結果の１ワードが０の場合に０とし、０でない場合に１とする１ビットの論理値とを生成し、前記中間データＤの上位ｎワードと、前記整数ＡＡの上位ｎワードと、前記論理値とを加算することを、最下位ワードから順にキャリーを伝播させながらワード単位での加算をｎワード分繰り返すことによって実行し、その加算結果をｎワードの出力データＭとして前記メモリに格納し、
（V）前記演算器は、前記メモリに格納された前記出力データＭが前記整数Ｐ以上である場合に、前記出力データＭが０以上で前記整数Ｐより小さい整数となるまで前記出力データＭから整数Ｐを減算することを、最下位ワードから順にキャリーを伝播させながらワード単位での減算をｎワード分繰り返すことによって実行し、その減算結果を新たなｎワードの出力データＭとして前記メモリに格納する
ことを特徴とする多倍長演算装置。
【請求項２】
前記制御回路は、前記処理（i）〜（iii）が完了した直後における前記演算器からのキャリーの発生を検査し、キャリーが発生している場合には、前記メモリ入出力回路及び前記加算器を制御することで、さらに、次の処理（iv）〜（v）を実行させることを特徴とする請求項１記載の多倍長演算装置。
（iv）前記メモリ入出力回路は、前記メモリに格納された前記整数Ｗ及びＰそれぞれから同一桁の１ワード長のデータｗ及びｐを同時に読み出して前記演算器に入力させると共に、前記演算器から出力される１ワード長のデータｃを前記メモリに格納することを、最下位ワードから順にｎワード分だけ繰り返すことにより、ｎワード長の整数Ｃを前記メモリに格納し、（v）前記演算器は、前記メモリ入出力回路から送られてくるデータｗ及びｐに対して、キャリーを伝播させながら、ｗ＋ｐを算出し、その結果ｃを出力することをｎ回繰り返す。
【請求項３】
前記演算器は、前記処理（IV）において、前記中間データＤと前記整数ＡＡそれぞれの全てのワードとオール１の１ワード長のデータとを加算し、得られた加算結果の上位ｎワードを前記出力データＭとして前記メモリに格納することを特徴とする請求項１記載の多倍長演算装置。
【請求項４】
前記演算器は、前記処理（II）及び（III）において、各２ワードの部分積を累算するときに同一桁の部分積を生成するような、全ての１ワードどおしの組み合わせを選んで、乗算器の入力値を設定し、その結果の部分積の累算を下位桁から順に繰り返していくことを特徴とする請求項３記載の多倍長演算装置。
【請求項５】
前記演算器は、前記処理（II）及び（III）において、同一桁の部分積の累算で得られた２ワード長の累算結果のうち、下位１ワードを乗算結果として前記メモリに格納すると共に、上位１ワードを次に算出される１ワードだけ桁の高い部分積に加算させることを特徴とする請求項４記載の多倍長演算装置。
【請求項６】
前記演算器は、前記部分積の累算結果の下位１ワードを前記メモリに格納すること、及び、前記部分積の累算結果の上位１ワードと次に算出される１ワードだけ桁の高い部分積とを加算することを同時に実行することを特徴とする請求項５記載の多倍長演算装置。
【請求項７】
前記演算器は、前記処理（ii）及び（iii）において、部分積を算出し累算するときに、部分積の算出と同時に、累算の対象となる１ワード長の累算値を前記メモリから読み出し、それら部分積と累算値とを桁を合わせて加算し、その加算結果を対応する前記メモリに格納することによって累算値を更新していくことを特徴とする請求項３記載の多倍長演算装置。
【請求項８】
前記メモリ入出力回路は、演算の対象となる少なくとも２個の整数を前記メモリに格納した後に、それら少なくとも２個の整数それぞれから１ワード長のデータを同時に読み出して前記３入力加算器又は前記乗算器に入力させる
ことを特徴とする請求項１記載の多倍長演算装置。
【請求項９】
前記メモリは、異なる２つのアドレスによって特定される２つの記憶領域それぞれに対して、ワード単位で、同時にデータを読み出すこと、及び、データを読み出すと同時にデータを書き込むことが可能なデュアルポートメモリを２個有し、
前記メモリ入出力回路は、２個の前記デュアルポートメモリそれぞれに格納された少なくとも２個の整数それぞれから１ワード長のデータを同時に読み出して前記３入力加算器又は前記乗算器に入力させると同時に、前記３入力加算器から出力される１ワード長のデータを２個の前記デュアルポートメモリのいずれかに格納する
ことを特徴とする請求項８記載の多倍長演算装置。
【請求項１０】
外部装置からの指示に従って、２以上のワード長の整数を対象とする加算剰余とモンゴメリリダクションとを選択的に実行する多倍長演算装置であって、
メモリと、
ワード単位で、加算及び乗算を含む２以上の種類の演算を実行し、１ワード長の演算結果を出力する演算器と、
加算剰余又はモンゴメリリダクションの対象となる少なくとも１つの整数を前記外部装置から前記メモリに第１データ転送と、前記メモリに格納された整数をワード単位で演算器に入力させる第２データ転送と、前記演算器から出力される演算結果を前記メモリに格納する第３データ転送と、前記演算結果を前記メモリから前記外部装置に出力する第４データ転送とを行うメモリ入出力回路と、
前記外部装置からの指示に従って、前記メモリ入出力回路に対して実行すべき前記第２及び第３データ転送の対象を指示して制御し、前記演算器に対して実行すべき演算の種類を指示して制御することにより、前記演算部に前記メモリに格納された整数に対する加算剰余とモンゴメリリダクションとを、選択的に実行させ、前記メモリ入出力回路に前記剰余演算の結果を前記メモリに格納させる制御回路とを備え、
前記演算器は、
２個の１ワード長データを入力とし、入力された２個の１ワード長データを乗じて、２ワード長データを出力する乗算器と、
前記乗算器から出力される２ワード長データを含む３個の２ワード長データ及び直前の算術加算において得られた１個のキャリーデータを入力とし、３個の２ワード長データ及び１個のキャリーデータを算術加算して、１個の２ワード長データ及び１個のキャリーデータとを出力する３入力加算器とを含み、
前記演算器は、前記演算結果として、前記３入力加算器から出力された１個の２ワード長データの下位の１ワード長データ及びキャリーデータを出力し、
前記外部装置から加算剰余を実行する旨及び加算剰余の対象となる整数のワード数ｎの指示を受けた場合に、前記制御回路は、前記メモリ入出力回路及び前記演算器が以下の処理（i）〜（iii）を実行するように前記メモリ入出力回路及び前記演算器を制御する。
（i）前記メモリ入出力回路は、加算剰余の対象となる２つのｎワード長の整数Ａ及びＢと法を示すｎワード長の整数Ｐとを前記外部装置から取得して前記メモリに格納し、
（ii）前記メモリ入出力回路は、前記メモリに格納された前記整数Ａ、Ｂ及びＰそれぞれから同一桁の１ワード長のデータａ、ｂ及びｐを同時に読み出して前記演算器に入力させると共に、前記演算器から出力される１ワード長のデータｗを前記メモリに格納することを、最下位ワードから順にｎワード分だけ繰り返すことにより、ｎワード長の整数Ｗを前記メモリに格納し、
（iii）前記演算器は、前記メモリ入出力回路から送られてくるデータａ、ｂ及びｐに対して、キャリーを伝播させながら、ａ＋ｂ−ｐを算出し、その結果ｗを出力することをｎ回繰り返す
ことを特徴とする多倍長演算装置。
【請求項１１】
外部装置からの指示に従って、２以上のワード長の整数を対象とする加算剰余とモンゴメリリダクションとを選択的に実行する多倍長演算装置であって、
メモリと、
ワード単位で、加算及び乗算を含む２以上の種類の演算を実行し、１ワード長の演算結果を出力する演算器と、
加算剰余又はモンゴメリリダクションの対象となる少なくとも１つの整数を前記外部装置から前記メモリに第１データ転送と、前記メモリに格納された整数をワード単位で演算器に入力させる第２データ転送と、前記演算器から出力される演算結果を前記メモリに格納する第３データ転送と、前記演算結果を前記メモリから前記外部装置に出力する第４データ転送とを行うメモリ入出力回路と、
前記外部装置からの指示に従って、前記メモリ入出力回路に対して実行すべき前記第２及び第３データ転送の対象を指示して制御し、前記演算器に対して実行すべき演算の種類を指示して制御することにより、前記演算部に前記メモリに格納された整数に対する加算剰余とモンゴメリリダクションとを、選択的に実行させ、前記メモリ入出力回路に前記剰余演算の結果を前記メモリに格納させる制御回路とを備え、
前記演算器は、
２個の１ワード長データを入力とし、入力された２個の１ワード長データを乗じて、２ワード長データを出力する乗算器と、
前記乗算器から出力される２ワード長データを含む３個の２ワード長データ及び直前の算術加算において得られた１個のキャリーデータを入力とし、３個の２ワード長データ及び１個のキャリーデータを算術加算して、１個の２ワード長データ及び１個のキャリーデータとを出力する３入力加算器とを含み、
前記演算器は、前記演算結果として、前記３入力加算器から出力された１個の２ワード長データの下位の１ワード長データ及びキャリーデータを出力し、
前記モンゴメリリダクションは、１ワードをｋビット、整数Ａを２ｎワード長の入力データ、整数Ｒを２＾（ｋ×ｎ）としたときに、ｎワード長の整数Ｐを法とするＡ・Ｒ＾（−１）の剰余を算出するための演算であり、前記外部装置からモンゴメリリダクションを実行する旨及びモンゴメリリダクションの対象となる整数Ａのワード数２ｎの指示を受けた場合に、前記制御回路は、前記メモリ入出力回路及び前記演算器が以下の処理（I）〜（V）で示されるモンゴメリリダクションを実行するように前記メモリ入出力回路及び前記演算器を制御する。
（I）前記メモリ入出力回路は、前記整数Ａ、Ｐ、及び、前記整数Ｒを法とする−Ｐ＾（−１）の剰余である整数Ｖとを前記外部装置から取得して前記メモリに格納し、
（II）前記演算器は、前記メモリに格納された前記整数Ａの下位ｎワードと前記整数Ｖとのワードごとの部分積の算出とそれら部分積における同一ワードの累算とを、最下位ワードから順に累算結果が得られるようにｎワードだけ繰り返し、その累算結果をｎワードの中間データＢとして前記メモリに格納し、
（III）前記演算器は、前記メモリに格納された前記中間データＢと整数Ｐとのワードごとの部分積の算出とそれら部分積における同一ワードの累算とを、最下位ワードを第０ワードとしたときの第０ワードから第（ｎ−３）は求めずに、第（ｎ−２）ワードから第（２ｎ−１）ワードまでを求め、その累算結果の上位（ｎ＋１）ワードを中間データＤとして前記メモリに格納し、
（IV）前記演算器は、前記整数Ａの上位（ｎ＋１）ワードを整数ＡＡとしたときに、前記メモリに格納された前記中間データＤ及び前記整数ＡＡそれぞれの最下位ワードを加算したときのキャリーと、その加算結果の１ワードが０の場合に０とし、０でない場合に１とする１ビットの論理値とを生成し、前記中間データＤの上位ｎワードと、前記整数ＡＡの上位ｎワードと、前記論理値とを加算することを、最下位ワードから順にキャリーを伝播させながらワード単位での加算をｎワード分繰り返すことによって実行し、その加算結果をｎワードの出力データＭとして前記メモリに格納し、
（V）前記演算器は、前記メモリに格納された前記出力データＭが前記整数Ｐ以上である場合に、前記出力データＭが０以上で前記整数Ｐより小さい整数となるまで前記出力データＭから整数Ｐを減算することを、最下位ワードから順にキャリーを伝播させながらワード単位での減算をｎワード分繰り返すことによって実行し、その減算結果を新たなｎワードの出力データＭとして前記メモリに格納する
ことを特徴とする多倍長演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多倍長の整数を対象とする剰余演算を実行する装置に関し、特に、２以上の種類の剰余演算を実行する装置に関する。
【背景技術】
【０００２】
多くの暗号方式では、多倍長の整数を対象とした有限体上での演算が利用される。ここで、多倍長の整数とは、一般的なＣＰＵの語長（３２ビット等）を超える語長の整数、例えば、１６０ビット長の整数をいう。このような暗号方式を通信機器等に実装するには、多倍長演算を高速に実行する演算装置が必要とされる。
従来、ＲＳＡ暗号のための演算装置として、乗算器とメモリからなる専用のＬＳＩが製品化されている。この演算装置は、多倍長のべき乗剰余演算だけを対象とする装置であり、短いビット幅の乗算器を繰り返し用いることによって多倍長のべき乗剰余演算を実現するものであり、ＣＰＵと組み合わせてコプロセッサとして用いられる。
【０００３】
これに対し、近年、ＲＳＡ暗号に置き換わる公開鍵暗号として注目を集めている方式の一つに楕円曲線暗号がある。この暗号方式に対しては、ＲＳＡ暗号に対して通用した強力な攻撃法（Index Calculus法）はもはや通用しない。楕円曲線暗号によれば、ＲＳＡ暗号に比べ、非常に短い語長の鍵データを用いるにも拘わらず十分な安全性が確保される。例えば、ＲＳＡ暗号によれば１０２４ビット長の鍵データで達成される安全性が、楕円曲線暗号によれば、わずか１６０ビット長の鍵データで達成される。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】岡本龍明・太田和夫共編「暗号・ゼロ知識証明・数論」共立出版、１９９５年
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところが、このように高い安全性を有する楕円曲線暗号を用いるためには、ＲＳＡ暗号で必要とされたべき乗剰余演算だけでなく、ＲＳＡ暗号では必要とされなかった四則演算や、予め決まってはいるが条件分岐を含む複雑な手順での演算等の種々の演算が必要とされる。
そのために、例えば、上述のＲＳＡ暗号専用のコプロセッサを用いて楕円曲線暗号の演算を行った場合には、そのコプロセッサが実行できる演算の数はわずかとなり、つまり、ほとんどの演算がＣＰＵによる演算となってしまい、ＣＰＵとコプロセッサ間での制御信号のやりとりによるオーバーヘッドが大きくなって高速処理が実現されない。
【０００６】
一方、楕円曲線暗号で必要とされる全ての種類の演算をＣＰＵに実行させるというソフトウェア的な手法をとったのでは、演算対象のデータが多倍長であることから、極めて高い頻度でＣＰＵによるメモリへのアクセスが発生し、ＣＰＵの演算部に効率的にデータが供給されず、高速処理が実現されない。そこで、本発明は、楕円曲線暗号等に必要な種々の多倍長演算を高速に実行することが可能な多倍長演算装置を提供することを目的とする。
【０００７】
また、比較的小さな回路規模で複数の種類の多倍長演算から選択されものを実行することが可能な多倍長演算装置を提供することも目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、本発明は、外部装置からの指示に従って、２以上のワード長の整数を対象とする加算剰余とモンゴメリリダクションとを選択的に実行する多倍長演算装置であって、メモリと、ワード単位で、加算及び乗算を含む２以上の種類の演算を実行し、１ワード長の演算結果を出力する演算器と、加算剰余又はモンゴメリリダクションの対象となる少なくとも１つの整数を前記外部装置から前記メモリに第１データ転送と、前記メモリに格納された整数をワード単位で演算器に入力させる第２データ転送と、前記演算器から出力される演算結果を前記メモリに格納する第３データ転送と、前記演算結果を前記メモリから前記外部装置に出力する第４データ転送とを行うメモリ入出力回路と、前記外部装置からの指示に従って、前記メモリ入出力回路に対して実行すべき前記第２及び第３データ転送の対象を指示して制御し、前記演算器に対して実行すべき演算の種類を指示して制御することにより、前記演算部に前記メモリに格納された整数に対する加算剰余とモンゴメリリダクションとを、選択的に実行させ、前記メモリ入出力回路に前記剰余演算の結果を前記メモリに格納させる制御回路とを備え、前記演算器は、２個の１ワード長データを入力とし、入力された２個の１ワード長データを乗じて、２ワード長データを出力する乗算器と、前記乗算器から出力される２ワード長データを含む３個の２ワード長データ及び直前の算術加算において得られた１個のキャリーデータを入力とし、３個の２ワード長データ及び１個のキャリーデータを算術加算して、１個の２ワード長データ及び１個のキャリーデータとを出力する３入力加算器とを含み、前記演算器は、前記演算結果として、前記３入力加算器から出力された１個の２ワード長データの下位の１ワード長データ及びキャリーデータを出力し、（ａ）前記外部装置から加算剰余を実行する旨及び加算剰余の対象となる整数のワード数ｎの指示を受けた場合に、前記制御回路は、前記メモリ入出力回路及び前記演算器が以下の処理（i）〜（iii）を実行するように前記メモリ入出力回路及び前記演算器を制御する。（i）前記メモリ入出力回路は、加算剰余の対象となる２つのｎワード長の整数Ａ及びＢと法を示すｎワード長の整数Ｐとを前記外部装置から取得して前記メモリに格納し、（ii）前記メモリ入出力回路は、前記メモリに格納された前記整数Ａ、Ｂ及びＰそれぞれから同一桁の１ワード長のデータａ、ｂ及びｐを同時に読み出して前記演算器に入力させると共に、前記演算器から出力される１ワード長のデータｗを前記メモリに格納することを、最下位ワードから順にｎワード分だけ繰り返すことにより、ｎワード長の整数Ｗを前記メモリに格納し、（iii）前記演算器は、前記メモリ入出力回路から送られてくるデータａ、ｂ及びｐに対して、キャリーを伝播させながら、ａ＋ｂ−ｐを算出し、その結果ｗを出力することをｎ回繰り返す。（ｂ）前記モンゴメリリダクションは、１ワードをｋビット、整数Ａを２ｎワード長の入力データ、整数Ｒを２＾（ｋ×ｎ）としたときに、ｎワード長の整数Ｐを法とするＡ・Ｒ＾（−１）の剰余を算出するための演算であり、前記外部装置からモンゴメリリダクションを実行する旨及びモンゴメリリダクションの対象となる整数Ａのワード数２ｎの指示を受けた場合に、前記制御回路は、前記メモリ入出力回路及び前記演算器が以下の処理（I）〜（V）で示されるモンゴメリリダクションを実行するように前記メモリ入出力回路及び前記演算器を制御する。（I）前記メモリ入出力回路は、前記整数Ａ、Ｐ、及び、前記整数Ｒを法とする−Ｐ＾（−１）の剰余である整数Ｖとを前記外部装置から取得して前記メモリに格納し、（II）前記演算器は、前記メモリに格納された前記整数Ａの下位ｎワードと前記整数Ｖとのワードごとの部分積の算出とそれら部分積における同一ワードの累算とを、最下位ワードから順に累算結果が得られるようにｎワードだけ繰り返し、その累算結果をｎワードの中間データＢとして前記メモリに格納し、（III）前記演算器は、前記メモリに格納された前記中間データＢと整数Ｐとのワードごとの部分積の算出とそれら部分積における同一ワードの累算とを、最下位ワードを第０ワードとしたときの第０ワードから第（ｎ−３）は求めずに、第（ｎ−２）ワードから第（２ｎ−１）ワードまでを求め、その累算結果の上位（ｎ＋１）ワードを中間データＤとして前記メモリに格納し、（IV）前記演算器は、前記整数Ａの上位（ｎ＋１）ワードを整数ＡＡとしたときに、前記メモリに格納された前記中間データＤ及び前記整数ＡＡそれぞれの最下位ワードを加算したときのキャリーと、その加算結果の１ワードが０の場合に０とし、０でない場合に１とする１ビットの論理値とを生成し、前記中間データＤの上位ｎワードと、前記整数ＡＡの上位ｎワードと、前記論理値とを加算することを、最下位ワードから順にキャリーを伝播させながらワード単位での加算をｎワード分繰り返すことによって実行し、その加算結果をｎワードの出力データＭとして前記メモリに格納し、（V）前記演算器は、前記メモリに格納された前記出力データＭが前記整数Ｐ以上である場合に、前記出力データＭが０以上で前記整数Ｐより小さい整数となるまで前記出力データＭから整数Ｐを減算することを、最下位ワードから順にキャリーを伝播させながらワード単位での減算をｎワード分繰り返すことによって実行し、その減算結果を新たなｎワードの出力データＭとして前記メモリに格納することを特徴とする。
【発明の効果】
【０００９】
このように構成されているので、この多倍長演算装置は、ロングワードの演算器を備えるのではなく、ワード単位で動作する演算器を備え、これを繰り返し用いることで多倍長演算を完遂することができるので、小さな回路規模で実現され得る。
【図面の簡単な説明】
【００１０】
【図１】本発明の多倍長演算装置の回路構成を示すブロック図である。
【図２】同多倍長演算装置の演算部の詳細な構成を示す回路図である。
【図３】同多倍長演算装置のメモリ入出力部の詳細な構成を示す回路図である。
【図４】同多倍長演算装置の全体的な動作の手順を示すフローチャートである。
【図５】同多倍長演算装置による加算剰余の演算式と外部装置から多倍長演算装置に与えられる入力データの例とを示す図である。
【図６】同多倍長演算装置による加算剰余におけるメモリ部のメモリマップを示す。
【図７】同多倍長演算装置が加算剰余演算を実行する場合の動作手順を示すフローチャートである。
【図８】（ａ）は図７に示された第１の処理（ステップＳ２１０〜Ｓ２１２）、（ｂ）は第２の処理（ステップＳ２１４〜Ｓ２１６）、（ｃ）は第３の処理（ステップＳ２１７〜Ｓ２１９）、における演算部の動作状態（演算機能）と演算部への入力データとを示す模式図である。
【図９】（ａ）は図７に示された第１の処理（ステップＳ２１０〜Ｓ２１２）、（ｂ）は第２の処理（ステップＳ２１４〜Ｓ２１６）、（ｃ）は第３の処理（ステップＳ２１７〜Ｓ２１９）、における演算部のパイプライン動作を示すタイミングチャートである。
【図１０】同多倍長演算装置によるモンゴメリ演算の演算式と外部装置から多倍長演算装置に与えられる入力データの例とを示す図である。
【図１１】多倍長演算装置によるモンゴメリ演算におけるメモリ部のメモリマップを示す。
【図１２】（ａ）はモンゴメリ演算のｓｔｅｐ１において同一桁の部分積を算出・累算する最初、（ｂ）はモンゴメリ演算のｓｔｅｐ１における同一桁の部分積を算出・累算する２回目以降、における演算部の動作状態と演算部への入力データとを示す模式図である。
【図１３】演算部がモンゴメリ演算のｓｔｅｐ１を実行する場合の演算手順を示す図である。
【図１４】（ａ）はモンゴメリ演算のｓｔｅｐ２の前半の処理（Ｂ×Ｐ）において同一桁の部分積を算出・累算する最初、（ｂ）はモンゴメリ演算のｓｔｅｐ２の前半の処理（Ｂ×Ｐ）において同一桁の部分積を算出・累算する２回目以降、（ｃ）はモンゴメリ演算のｓｔｅｐ２における後半の処理（上記前半の処理結果Ｂ×Ｐと整数Ａとの加算）を実行する場合の演算部の動作状態と演算部への入力データとを示す模式図である。
【図１５】演算部がモンゴメリ演算のｓｔｅｐ２を実行する場合の演算手順を示す図である。
【図１６】（ａ）はモンゴメリ演算のｓｔｅｐ３における前半の処理（Ｍ＋Ｑ、又は、Ｎ＋Ｑ）、（ｂ）はモンゴメリ演算のｓｔｅｐ３における後半の処理（Ｍ＋Ｐ、又は、Ｎ＋Ｐ）、における演算部の動作状態と演算部への入力データとを示す模式図である。
【図１７】減算機能を有する変形例に係る演算部の構成を示す回路である。
【図１８】（ａ）は変形例に係る演算部の符号反転部の回路構成を示し、（ｂ）は変形例に係る演算部の符号反転部の動作機能を示す。
【発明を実施するための形態】
【００１１】
本発明の１の実施態様は、外部装置からの指示に従って、２以上のワード長の整数を対象とする剰余演算を実行する多倍長演算装置であって、メモリと、ワード単位で、加算及び乗算を含む２以上の種類の演算を実行し、１ワード長の演算結果を出力する演算器と、剰余演算の対象となる少なくとも１つの整数を前記外部装置から前記メモリに格納する第１データ転送と、前記メモリに格納された整数をワード単位で演算器に入力させる第２データ転送と、前記演算器から出力される演算結果を前記メモリに格納する第３データ転送と、前記演算結果を前記メモリから前記外部装置に出力する第4データ転送とを行うメモリ入出力回路と、前記外部装置からの指示に従って、前記メモリ入出力回路に対して実行すべき前記第２及び第３データ転送の対象を指示して制御し、前記演算器に対して実行すべき演算の種類を指示して制御することにより、前記演算器に前記メモリに格納された整数に対する２以上の種類の剰余演算を選択的に実行させ、前記メモリ入出力回路に前記剰余演算の結果を前記メモリに格納させる制御回路とを備えることを特徴とする。
【００１２】
前記多倍長演算装置は、演算対象となるｎワード長の整数や演算結果等を一時的に記憶するための２個のデュアルポートメモリからなるメモリと、ワード単位で加算及び乗算を含む２以上の種類の演算を実行し、１ワード長の演算結果を出力する演算部と、メモリから演算部に最大３つの１ワードデータを供給すると同時に、演算部からの１ワード長の演算結果をメモリに格納するメモリ入出力部と、演算部及びメモリ入出力部を制御することにより、演算部にｎワード長の加算剰余及びモンゴメリリダクションのいずれかの演算を実行させる制御を行う制御とを備えるとしてもよい。
【００１３】
前記演算器は、少なくとも２つの１ワード長のデータを加算する加算器と、少なくとも２つの１ワード長のデータを乗算する乗算器とを有し、前記メモリ入出力回路は、演算の対象となる２個の整数を前記メモリに格納した後に、それら２個の整数それぞれから１ワード長のデータを同時に読み出して前記加算器又は前記乗算器に入力させるとしてもよい。
【００１４】
前記メモリは、異なる２つのアドレスによって特定される２つの記憶領域それぞれに対して、ワード単位で、同時にデータを読み出すこと、及び、データを読み出すと同時にデータを書き込むことが可能なデュアルポートメモリを２個有し、前記メモリ入出力回路は、２個の前記デュアルポートメモリそれぞれに格納された２個の前記整数それぞれから１ワード長のデータを同時に読み出して前記加算器又は前記乗算器に入力させると同時に、前記加算器又は前記乗算器から出力される１ワード長のデータを２個の前記デュアルポートメモリのいずれかに格納するとしてもよい。
【００１５】
前記演算器は、前記制御回路からの指示に従って、（i）少なくとも２つの１ワード長のデータに対する加算と、（ii）２つの１ワード長のデータに対する乗算と、（iii）２つの１ワード長のデータに対する乗算及びその乗算結果の累算のいすれかを実行するとしてもよい。
前記演算器は、２つの１ワード長のデータを入力とし、２ワード長のデータを出力する乗算器と、前記乗算器から出力される２ワード長のデータを含む少なくとも２つの２ワード長のデータを入力とし、少なくとも２以上のワード長のデータを出力する加算器と、前記制御回路からの指示に従って、前記メモリ入出力回路から送られてくる２つの１ワード長のデータを前記乗算器及び前記加算器のいずれかに入力させると共に、前記加算器から出力されたデータの前記加算器への入力を制御することによって、前記乗算器及び前記加算器に前記３つの演算（i）〜（iii）のいずれかを実行させ、得られた加算結果又は乗算結果における１ワード長のデータを前記演算結果として出力させる選択回路とを有するとしてもよい。
【００１６】
前記２以上の種類の剰余演算には加算剰余が含まれ、前記制御回路は、前記外部装置から加算剰余を実行する旨及び加算剰余の対象となる整数のワード数ｎの指示を受けた場合に、前記メモリ入出力回路及び前記演算器が以下の処理（i）〜（iii）を実行するように前記メモリ入出力回路及び前記演算器を制御する。（i）前記メモリ入出力回路は、加算剰余の対象となる２つのｎワード長の整数Ａ及びＢと法を示すｎワード長の整数Ｐとを前記外部装置から取得して前記メモリに格納し、（ii）前記メモリ入出力回路は、前記メモリに格納された前記整数Ａ、Ｂ及びＰそれぞれから同一桁の１ワード長のデータａ、ｂ及びｐを同時に読み出して前記演算器に入力させると共に、前記演算器から出力される１ワード長のデータｗを前記メモリに格納することを、最下位ワードから順にｎワード分だけ繰り返すことにより、ｎワード長の整数Ｗを前記メモリに格納し、（iii）前記演算器は、前記メモリ入出力回路から送られてくるデータａ、ｂ及びｐに対して、キャリーを伝播させながら、ａ＋ｂ−ｐを算出し、その結果ｗを出力することをｎ回繰り返すとしてもよい。
【００１７】
前記制御回路は、前記処理（i）〜（iii）が完了した直後における前記演算器からのキャリーの発生を検査し、キャリーが発生している場合には、前記メモリ入出力回路及び前記加算器を制御することで、さらに、次の処理（iv）〜（v）を実行させる。（iv）前記メモリ入出力回路は、前記メモリに格納された前記整数Ｗ及びＰそれぞれから同一桁の１ワード長のデータｗ及びｐを同時に読み出して前記演算器に入力させると共に、前記演算器から出力される１ワード長のデータｃを前記メモリに格納することを、最下位ワードから順にｎワード分だけ繰り返すことにより、ｎワード長の整数Ｃを前記メモリに格納し、（v）前記演算器は、前記メモリ入出力回路から送られてくるデータｗ及びｐに対して、キャリーを伝播させながら、ｗ＋ｐを算出し、その結果ｃを出力することをｎ回繰り返すとしてもよい。
【００１８】
前記２以上の種類の剰余演算には、１ワードをｋビット、整数Ａを２ｎワード長の入力データ、整数Ｒを２＾（ｋ×ｎ）としたときに、ｎワード長の整数Ｐを法とするＡ・Ｒ＾（−１）の剰余を算出するためのモンゴメリリダクションが含まれ、前記制御回路は、前記外部装置からモンゴメリリダクションを実行する旨及びモンゴメリリダクションの対象となる整数Ａのワード数２ｎの指示を受けた場合に、前記メモリ入出力回路及び前記演算器がモンゴメリリダクションを実行するように前記メモリ入出力回路及び前記演算器を制御するとしてもよい。
【００１９】
前記制御回路は、前記外部装置からモンゴメリリダクションを実行する旨の指示を受けた場合に、前記メモリ入出力回路及び前記演算器が以下の処理（i）〜（v）を実行するように前記メモリ入出力回路及び前記演算器を制御する。（i）前記メモリ入出力回路は、前記整数Ａ、Ｐ、及び、前記整数Ｒを法とする−Ｐ＾（−１）の剰余である整数Ｖとを前記外部装置から取得して前記メモリに格納し、（ii）前記演算器は、前記メモリに格納された前記整数Ａの下位ｎワードと前記整数Ｖとのワードごとの部分積の算出とそれら部分積における同一ワードの累算とを、最下位ワードから順に累算結果が得られるようにｎワードだけ繰り返し、その累算結果をｎワードの中間データＢとして前記メモリに格納し、（iii）前記演算器は、前記メモリに格納された前記中間データＢと整数Ｐとのワードごとの部分積の算出とそれら部分積における同一ワードの累算とを、最下位ワードを第０ワードとしたときの第０ワードから第（ｎ−３）は求めずに、第（ｎ−２）ワードから第（２ｎ−１）ワードまでを求め、その累算結果の上位（ｎ＋１）ワードを中間データＤとして前記メモリに格納し、（iv）前記演算器は、前記整数Ａの上位（ｎ＋１）ワードを整数ＡＡとしたときに、前記メモリに格納された前記中間データＤ及び前記整数ＡＡそれぞれの最下位ワードを加算したときのキャリーと、その加算結果の１ワードが０の場合に０とし、０でない場合に１とする１ビットの論理値とを生成し、前記中間データＤの上位ｎワードと、前記整数ＡＡの上位ｎワードと、前記キャリーと、前記論理値とを加算することを、最下位ワードから順にキャリーを伝播させながらワード単位での加算をｎワード分繰り返すことによって実行し、その加算結果をｎワードの出力データＭとして前記メモリに格納し、（v）前記演算器は、前記メモリに格納された前記出力データＭが前記整数Ｐ以上である場合に、前記出力データＭが０以上で前記整数Ｐより小さい整数となるまで前記出力データＭから整数Ｐを減算することを、最下位ワードから順にキャリーを伝播させながらワード単位での減算をｎワード分繰り返すことによって実行し、その減算結果を新たなｎワードの出力データＭとして前記メモリに格納するとしてもよい。
【００２０】
前記演算器は、前記処理（iv）において、前記中間データＤと前記整数ＡＡそれぞれの全てのワードとオール１の１ワード長のデータとを加算し、得られた加算結果の上位ｎワードを前記出力データＭとして前記メモリに格納するとしてもよい。
前記演算器は、前記処理（ii）及び（iii）において、各２ワードの部分積を累算するときに同一桁の部分積を生成するような、全ての１ワードどおしの組み合わせを選んで、乗算器の入力値を設定し、その結果の部分積の累算を下位桁から順に繰り返していくとしてもよい。
【００２１】
前記演算器は、前記処理（ii）及び（iii）において、同一桁の部分積の累算で得られた２ワード長の累算結果のうち、下位１ワードを乗算結果として前記メモリに格納すると共に、上位１ワードを次に算出される１ワードだけ桁の高い部分積に加算させるとしてもよい。
前記演算器は、前記部分積の累算結果の下位１ワードを前記メモリに格納すること、及び、前記部分積の累算結果の上位１ワードと次に算出される１ワードだけ桁の高い部分積とを加算することを同時に実行するとしてもよい。
【００２２】
前記演算器は、前記処理（ii）及び（iii）において、部分積を算出し累算するときに、部分積の算出と同時に、累算の対象となる１ワード長の累算値を前記メモリから読み出し、それら部分積と累算値とを桁を合わせて加算し、その加算結果を対応する前記メモリに格納することによって累算値を更新していくとしてもよい。
本発明の他の実施態様は、外部装置からの指示に従って、２以上のワード長の整数を対象とする剰余演算を実行する多倍長演算装置であって、メモリと、ワード単位で、加算及び乗算を含む２以上の種類の演算を実行し、１ワード長の演算結果を出力する演算器と、剰余演算の対象となる少なくとも１つの整数を前記外部装置から前記メモリに格納する第１データ転送と、前記メモリに格納された整数をワード単位で演算器に入力させる第２データ転送と、前記演算器から出力される演算結果を前記メモリに格納する第３データ転送と、前記演算結果を前記メモリから前記外部装置に出力する第4データ転送とを行うメモリ入出力回路と、前記外部装置からの指示に従って、前記メモリ入出力回路に対して実行すべき前記第２及び第３データ転送の対象を指示して制御し、前記演算器に対して実行すべき演算の種類を指示して制御することにより、前記演算器に前記メモリに格納された整数に対する２以上の種類の剰余演算を選択的に実行させ、前記メモリ入出力回路に前記剰余演算の結果を前記メモリに格納させる制御回路とを備え、前記２以上の種類の剰余演算には加算剰余とモンゴメリリダクションとが含まれ、前記制御回路は、前記外部装置から加算剰余を実行する旨の指示を受けた場合に、前記演算器がｎワード長の整数Ｐを法として２つのｎワード長の整数ＡとＢとを加算するように前記メモリ入出力回路及び前記演算器を制御し、前記外部装置からモンゴメリリダクションを実行する旨の指示を受けた場合に、前記演算器が１ワードをｋビット、整数Ａを２ｎワード長の入力データ、整数Ｒを２＾（ｋ×ｎ）としたときに、１ワード長の整数Ｐを法とするＡ・Ｒ＾（−１）の剰余を算出するように前記メモリ入出力回路及び前記演算器を制御することを特徴とする。
【００２３】
前記演算器は、２つの１ワード長のデータを入力とし、２ワード長のデータを出力する乗算器と、前記乗算器から出力される２ワード長のデータを含む少なくとも２つの２ワード長のデータを入力とし、少なくとも２以上のワード長のデータを出力する加算器と、前記制御回路からの指示に従って、前記メモリ入出力回路から送られてくる２つの１ワード長のデータを前記乗算器及び前記加算器のいずれかに入力させると共に、前記加算器から出力されたデータの前記加算器への入力を制御することによって、（i）少なくとも２つの１ワード長のデータに対する加算と、（ii）２つの１ワード長のデータに対する乗算と、（iii）２つの１ワード長のデータに対する乗算及びその乗算結果の累算のいすれかを前記乗算器及び前記加算器に実行させる選択回路とを有するとしてもよい。
【００２４】
前記メモリは、異なる２つのアドレスによって特定される２つの記憶領域それぞれに対して、ワード単位で、同時にデータを読み出すこと、及び、データを読み出すと同時に書き込むことが可能なデュアルポートメモリを２個有し、前記メモリ入出力回路は、２個の前記デュアルポートメモリそれぞれに格納された２個の整数それぞれから１ワード長のデータを同時に読み出して前記加算器又は前記乗算器に入力させると同時に、前記加算器又は前記乗算器から出力される１ワード長のデータを２個の前記デュアルポートメモリのいずれかに格納するとしてもよい。
【００２５】
以下、本発明の実施の形態について、図面を用いて説明する。図１は、本発明の多倍長演算装置１００の回路構成を示すブロック図である。この多倍長演算装置１００は、外部装置（図示されず）からの指示（演算の種類と演算対象となる多倍長整数の長さ等）に基づいて２種類の多倍長演算、例えば、５ワード長の２つの整数の加算剰余と１０ワード長の整数を入力とするモンゴメリリダクションとを選択的に実行するコプロセッサ（ＬＳＩ）であり、内部で生成されるクロック信号に同期して動作する制御部１０、演算部２０、メモリ入出力部３０及びメモリ部４０から構成される。
【００２６】
ここで、１ワードとは、演算部２０が１クロックサイクルで実行する演算の対象となるデータの語長であり、ここでは、３２ビットである。外部装置とは、この多倍長演算装置１００を利用する通信機器等に備えられたＣＰＵ等である。また、加算剰余とは、ある定数Ｐを法とする加算である。モンゴメリリダクションとは、剰余演算を高速に行うアルゴリズムの一つであり、以下のように、ある定数Ｐと定数ＲがＰ＜Ｒ＝２＾ｍとし、Ｐ＾２程度の大きさの入力Ａに対して、Ｍ＝Ａ・Ｒ＾（−１） ｍｏｄ Ｐを求めるための３つのステップからなる演算（以下、この演算を「モンゴメリ演算」という。）である（岡本龍明・太田和夫共編「暗号・ゼロ知識証明・数論」共立出版、１９９５年）。
【００２７】
入力：Ａ（２ｍビット程度の値）
前計算：Ｖ＝−Ｐ＾（−１） ｍｏｄ Ｒ
出力：Ｍ＝Ａ・Ｒ＾（−１） ｍｏｄ Ｐ
処理：
ｓｔｅｐ１： Ｂ＝Ａ×Ｖ ｍｏｄ Ｒ
ｓｔｅｐ２： Ｍ＝（Ｂ×Ｐ＋Ａ）／Ｒ
ｓｔｅｐ３： Ｍ ｍｏｄ Ｐを出力
演算部２０は、制御部１０からの指示に基づいて、１クロックサイクルで２つの１ワード長のデータの乗算及び３つの１ワード長のデータの加算のいずれかを実行する共にその結果又はその結果の一部を示す１ワードのデータと２ビットのキャリー（桁上げ）を含む３４ビットのデータを出力する演算器であり、入力のための３つのデータバス６１〜６３と出力のための１つのデータバス６４によってメモリ入出力部３０と接続されている。
【００２８】
メモリ部４０は、この多倍長演算装置１００による多倍長演算の対象となる整数、その演算過程で生じる中間データ及び演算結果を一時的に格納するメモリであり、ワード単位でアクセスが可能な２つの独立したデュアルポートメモリ（第１メモリ４１及び第２メモリ４２）からなり、４つのデータバス６５〜６８と４つのアドレスバス７１〜７４によってメモリ入出力部３０と接続されている。
【００２９】
第１メモリ４１及び第２メモリ４２それぞれは、２５６ワードの記憶容量を有し、２つの入出力ポートを介して、１クロックサイクルで、最大２つの異なる記憶領域の１ワード長のデータ（部分整数）を同時に読み書きできるメモリである。メモリ入出力部３０は、制御部１０からの指示に基づいて、演算部２０とメモリ部４０間のデータ転送及び外部装置とメモリ部４０間のデータ転送を行うインタフェース回路である。
【００３０】
制御部１０は、制御プログラムが格納されたＲＯＭ、そのプログラムに従って制御信号を出力する論理回路及びＲＡＭ等からなり、外部装置からの指示（演算の種類や演算対象となる多倍長整数のワード数等）に基づいて、演算部２０及びメモリ入出力部３０を制御することにより、例えば、メモリ部４０に格納された２つの５ワード長の整数に対する加算剰余演算及び１つの１０ワード長の整数に対するモンゴメリ演算のいずれかを完遂させる。
【００３１】
図２は、図１に示された演算部２０の詳細な構成を示す回路図である。この演算部２０は、乗算器２１、３入力加算器２２、レジスタ２３及び３つのセレクタ２４〜２６からなる。なお、図中の［ｎ：ｍ］は、着目するビット列の最下位ビットを第０ビットとした場合の第ｎ〜第ｍビット列を意味する。乗算器２１は、２つのデータバス６１、６２を介してメモリ入出力部３０から送られてくる２つの１ワード長のデータを乗算し、その結果を２ワード長のデータで出力する。
【００３２】
３入力加算器２２は、セレクタ２４から第１入力ポートｉｎ１に入力される２ワード長のデータと、データバス６２を介してメモリ入出力部３０から送られてくる１ワード長のデータを下位ワードとし“０”を上位ワードとして第２入力ポートｉｎ２に入力される２ワード長のデータと、セレクタ２５から第３入力ポートｉｎ３に入力される２ワード長のデータと、セレクタ２６からキャリー入力端子（carry in）に入力される２ビットのキャリーとを算術加算し、得られた６６ビット長のデータ（上位２ビットのキャリー及び続く２ワード長のデータ）をレジスタ２３に出力する。
【００３３】
なお、この３入力加算器２２は、負数（２の補数により表現された数）を加算することができるので、オーバーフロー時だけでなく、アンダーフロー時（ボロー時）にもキャリーを出力する。レジスタ２３は、３入力加算器２２から出力される６６ビット長のデータを１クロックサイクルだけ保持する。レジスタ２３に保持された６６ビット長のデータは、次のクロックサイクルにおいて、その上位２ビットのキャリー［６５：６４］及び中位２ビットのキャリー［３３：３２］がセレクタ２６に入力され、下位２ワード長のデータがセレクタ２５に入力され、下位の３４ビットがデータバス６４を介してメモリ入出力部３０に出力される。
【００３４】
セレクタ２４は、制御部１０からの指示に従って、（i）データバス６１を介してメモリ入出力部３０から送られてくる１ワード長のデータを下位ワードとし“０”を上位ワードとする２ワード長のデータ、及び、（ii）乗算器２１から出力される２ワード長のデータのいずれかを選択し、３入力加算器２２の第１入力ポートｉｎ１に出力する。
セレクタ２５は、制御部１０からの指示に従って、（i）データバス６３を介してメモリ入出力部３０から送られてくる１ワード長のデータを下位ワードとし“０”を上位ワードとする２ワード長のデータ、（ii）レジスタ２３から出力される２ワード長のデータ、及び、（iii）レジスタ２３から出力される２ワード長のデータの上位ワードを下位ワードし“０”を上位ワードとする２ワード長のデータのいずれかを選択し、３入力加算器２２の第３入力ポートｉｎ３に出力する。
【００３５】
セレクタ２６は、３入力加算器２２での加算で生じたキャリーを次のクロックサイクルにおける加算に伝播するための回路であり、制御部１０からの指示に従って、（i）レジスタ２３から送られてくる２ビットのキャリー［６５：６４］、及び、（ii）［３３：３２］のいずれかを選択し、３入力加算器２２のキャリー入力端子に出力する。
図３は、図１に示されたメモリ入出力部３０の詳細な構成を示す回路図である。このメモリ入出力部３０は、バススイッチ部３１、入出力制御部３２及びアドレス生成部３３からなる。バススイッチ部３１は、複数のセレクタ回路の集まりであり、入出力制御部３２からの指示に従って、演算部２０に接続されている４つのデータバス６１〜６４それぞれをメモリ部４０に接続されている４つのデータバス６５〜６８のいずれかに接続する。
【００３６】
アドレス生成部３３は、４個の独立したアドレスレジスタ及びインクリメンタ等からなり、入出力制御部３２からの指示に従って、４組のアクセス制御信号（アドレス、読み出し／書き込み信号等）を生成し、４つのアドレスバス７１〜７４に出力する。入出力制御部３２は、制御部１０からの指示に基づいて、演算部２０がメモリ部４０に対して同時かつ独立に最大４つのアクセスを行えるようにバススイッチ部３１及びアドレス生成部３３を制御したり、データバス６９及びアドレスバス７５を介して接続された外部装置とメモリ部４０間のデータ転送を行ったり、演算部２０から送られてきたキャリーに関する情報をキャリー信号として制御部１０に伝えたりする。
【００３７】
次に、以上のように構成された多倍長演算装置１００の動作について説明する。図４は、多倍長演算装置１００の全体的な動作の手順を示すフローチャートである。まず、メモリ入出力部３０は、演算の対象となる整数や予め前計算で算出されている整数等の入力データをデータバス６９及びアドレスバス７５を介して外部装置から受け取り、メモリ部４０の所定位置に格納する（ステップＳ２００）次に、制御部１０は、加算剰余演算及びモンゴメリ演算のいずれを実行すべきかの指示を外部装置から受け取る（ステップＳ２０１）。
【００３８】
その結果、加算剰余を実行すべき指示を受け取った場合には、制御部１０は、予めプログラムされた制御信号を演算部２０及びメモリ入出力部３０に送ることにより、メモリ部４０に格納された５ワード長の２つの整数Ａ及びＢの加算剰余を演算部２０に実行させ、その結果Ｃをメモリ部４０に格納させる（ステップＳ２０２）。
一方、モンゴメリ演算を実行すべき指示を受け取った場合には、制御部１０は、予めプログラムされた制御信号を演算部２０及びメモリ入出力部３０に送ることにより、メモリ部４０に格納された整数Ａ等を用いて上記モンゴメリ演算のｓｔｅｐ１〜ｓｔｅｐ３を演算部２０に順次実行させ、最終的な結果Ｍをメモリ部４０に格納させる（ステップＳ２０３〜５）。
【００３９】
なお、上記加算剰余の結果Ｃやモンゴメリ演算の結果Ｍは、メモリ入出力部３０を介して外部装置によって読み出される。次に、本多倍長演算装置１００による具体的な演算例を説明する。まず、本多倍長演算装置１００が加算剰余（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｐ）を実行する場合について、図５〜図９を用いて説明する。
図５は、加算剰余の演算式と、加算剰余に際して外部装置から本多倍長演算装置１００に与えられる入力データ、即ち、メモリ入出力部３０を経てメモリ部４０に格納される入力データＡ、Ｂ、Ｐ、Ｑの例とを示す図である。整数Ａは、加算剰余の演算対象の一つであり、上位桁から順に５個のワードａ４、ａ３、ａ２、ａ１、ａ０が並べられた５ワード長の整数である（以下、このような多倍長整数を［ａ４、ａ３、ａ２、ａ１、ａ０］と表す）。同様に、整数Ｂは、加算剰余の演算対象の一つであり、５ワード長の整数［ｂ４、ｂ３、ｂ２、ｂ１、ｂ０］である。整数Ｐは、加算剰余における法であり、５ワード長の整数［ｐ４、ｐ３、ｐ２、ｐ１、ｐ０］である。整数Ｑは、整数Ｐの符号を反転した値（−Ｐ）に等しい５ワード長の整数［ｑ４、ｑ３、ｑ２、ｑ１、ｑ０］である。
【００４０】
図６は、本多倍長演算装置１００による加算剰余におけるメモリ部４０のメモリマップを示す。ここには、上記４つの入力データＡ、Ｂ、Ｐ、Ｑに加えて、その演算結果を格納するための５ワード長の整数Ｃ［ｃ４、ｃ３、ｃ２、ｃ１、ｃ０］及びこの加算剰余で発生する中間データＷ［ｗ４、ｗ３、ｗ２、ｗ１、ｗ０］も併せて示されている。
第１メモリ４１には、整数Ａ、Ｐ及びＱが格納され、第２メモリ４２には、整数Ｂ、Ｃ及びＷが格納される。このようなメモリマップによって、演算部２０は、１クロックサイクルで、３つの整数Ａ、Ｐ及びＱから選択した２つのワードと、３つの整数Ｂ、Ｃ及びＷから選択した２つのワードとを同時に読み出し又は書き込みを行うことができる。
【００４１】
図７は、多倍長演算装置１００が加算剰余演算を実行する場合の動作手順、即ち、図４に示されたステップＳ２０２の詳細な手順を示すフローチャートである。多倍長演算装置１００による加算剰余演算は、大別すると、３つの処理からなる。つまり、ワード単位での加算剰余を５回繰り返す第１の処理（ステップＳ２１０〜２１２）と、第１の処理によってキャリーを生じた場合の「引き戻し演算」と呼ばれる、ワード単位での加算を５回繰り返す第２の処理（ステップＳ２１４〜Ｓ２１６）と、第１の処理によってキャリーを生じなかった場合に、中間データＷを演算結果Ｃに代入するためのデータ転送を５回繰り返す第３の処理（ステップＳ２１７〜Ｓ２１９）とからなる。
【００４２】
図８（ａ）〜（ｃ）は、それぞれ、図７に示された第１の処理（ステップＳ２１０〜Ｓ２１２）、第２の処理（ステップＳ２１４〜Ｓ２１６）及び第３の処理（ステップＳ２１７〜Ｓ２１９）における演算部２０の動作状態（演算機能）と演算部２０への入力データとを示す模式図である。演算部２０は、第１の処理においては、３つのデータａｉ、ｂｉ及びｑｉを加算し、その結果をデータｗｉに代入する１ワードの３入力加算器として動作し、第２の処理においては、２つのデータｐｉ及びｗｉを加算し、その結果をデータｃｉに代入する１ワードの２入力加算器として動作し、第３の処理においては、１つのデータｗｉをデータｃｉに代入する１ワードのデータ転送器として動作する。
【００４３】
なお、これら演算部２０の動作状態は、制御部１０から演算部２０に出力される制御信号によって決定され、演算部２０への入力データは、制御部１０からメモリ入出力部３０に出力される制御信号によって決定される。また、３入力加算器２２のいずれかの入力ポートに対して固定的に“０”を入力することは、セレクタ２４、２５を制御することによってオール“０”のデータを出力させたり、メモリ入出力部３０を制御することによってオール“０”のデータを出力させたりすることによって実現される。
【００４４】
図９（ａ）〜（ｃ）は、それぞれ、図７に示された第１の処理（ステップＳ２１０〜Ｓ２１２）、第２の処理（ステップＳ２１４〜Ｓ２１６）及び第３の処理（ステップＳ２１７〜Ｓ２１９）における演算部２０のパイプライン動作を示すタイミングチャートである。演算部２０は、３入力加算器２２の出力を保持するレジスタ２３を有しているので、３入力加算器２２による演算と、３入力加算器２２による直前の演算結果のメモリ部４０への格納という２つのステージを１つのクロックサイクルで同時並列に実行する。
【００４５】
図７に示されるように、第１の処理において、まず、制御部１０は、演算部２０及びメモリ入出力部３０に制御信号を送ることで演算部２０を図８（ａ）に示される動作状態にした後に、演算部２０に対して初期化の制御信号を出力することにより、レジスタ２３の保持値Ｒｅｇ及びキャリーｃａｒｒｙ（Ｒｅｇ［３３：３２］）を“０”に初期化する（ステップＳ２１０）。
【００４６】
そして、演算部２０は、クロックサイクルごとに、メモリ入出力部３０を経て第１メモリ４１から送られてくる２つのデータａｉ及びｑｉと第２メモリ４２から送られてくるデータｂｉと直前の演算で生じたキャリーｃａｒｒｙとを加算すると共に、レジスタ２３の保持値Ｒｅｇの下位１ワードを第２メモリ４２の記憶領域ｗｉに書き込むという並列動作を繰り返す（ステップＳ２１１）。
【００４７】
具体的には、図９（ａ）に示されるように、演算部２０は、第１クロックサイクルにおいて、３つのデータａ０、ｂ０及びｑ０を加算してレジスタ２３Ｒｅｇに格納し、続く第２クロックサイクルにおいて、３つのデータａ１、ｂ１及びｑ１と第１クロックサイクルでの演算で生じたキャリーとを加算してレジスタ２３Ｒｅｇに格納すると共に、レジスタ２３に保持されていた直前の演算結果Ｒｅｇを第２メモリ４２の記憶領域ｗ０に書き込む、というパイプライン動作を繰り返す。
【００４８】
演算部２０は、制御部１０による制御の下で、５ワード分の加算とその結果の第２メモリ４２への格納とを合計５回繰り返す（ステップＳ２１１〜Ｓ２１２）。これによって、Ｗ＝Ａ＋Ｂ＋Ｑ、即ち、Ｗ＝Ａ＋Ｂ−Ｐの演算が完了する。次に、制御部１０は、第５クロックサイクルにおける加算によってキャリーｃａｒｒｙ（ここでは、ボロー）が生じているか否か判断し（ステップＳ２１３）、キャリーｃａｒｒｙが生じている場合には第２の処理（ステップＳ２１４〜Ｓ２１６）を、キャリーｃａｒｒｙが生じていない場合には第３の処理（ステップＳ２１７〜Ｓ２１９）を、演算部２０に実行させる。
【００４９】
これは、第１の処理によって得られた中間データＷが負の値となってしまった場合には、その中間データＷに法Ｐを加算して得られる値（引き戻して得られる値）を最終結果Ｃ（Ａ＋Ｂ ｍｏｄ Ｐ）とし、一方、中間データＷが正の値である場合には、その中間データＷを最終結果Ｃとするためである。第２の処理では、まず、制御部１０は、演算部２０及びメモリ入出力部３０に制御信号を送ることで演算部２０を図８（ｂ）に示される動作状態にした後に、演算部２０に対して初期化の制御信号を出力することにより、レジスタ２３の保持値Ｒｅｇ及びキャリーｃａｒｒｙ（Ｒｅｇ［３３：３２］）を“０”に初期化する（ステップＳ２１４）。
【００５０】
そして、演算部２０は、クロックサイクルごとに、メモリ入出力部３０を経て第１メモリ４１から送られてくるデータｐｉと第２メモリ４２から送られてくるデータｗｉと直前の演算で生じたキャリーｃａｒｒｙとを加算すると共に、レジスタ２３の保持値Ｒｅｇの下位１ワードを第２メモリ４２の記憶領域ｃｉに書き込むという並列動作を繰り返す（ステップＳ２１５）。
【００５１】
具体的には、図９（ｂ）に示されるように、演算部２０は、第１クロックサイクルにおいて、２つのデータｐ０及びｗ０を加算してレジスタ２３Ｒｅｇに格納し、続く第２クロックサイクルにおいて、２つのデータｐ１及びｗ１と第１クロックサイクルでの演算で生じたキャリーとを加算してレジスタ２３Ｒｅｇに格納すると共に、レジスタ２３に保持されていた直前の演算結果Ｒｅｇを第２メモリ４２の記憶領域ｃ０に書き込む、というパイプライン動作を繰り返していく。
【００５２】
演算部２０は、制御部１０による制御の下で、５ワード分の加算とその結果の第２メモリ４２への格納とを合計５回繰り返す（ステップＳ２１５〜Ｓ２１６）。これによって、Ｃ＝Ｗ＋Ｐ、即ち、Ｃ＝Ａ＋Ｂ ｍｏｄ Ｐの演算が完了する。一方、第３の処理では、まず、制御部１０は、演算部２０及びメモリ入出力部３０に制御信号を送ることで演算部２０を図８（ｃ）に示される動作状態に初期化する（ステップＳ２１７）。
【００５３】
そして、演算部２０は、クロックサイクルごとに、メモリ入出力部３０を経て第１メモリ４２から送られてくるデータｗｉを通過させてレジスタ２３に格納すると共に、レジスタ２３の保持値Ｒｅｇの下位１ワードを第２メモリ４２の記憶領域ｃｉに書き込むという並列動作を繰り返す（ステップＳ２１８）。具体的には、図９（ｃ）に示されるように、演算部２０は、第１クロックサイクルにおいて、データｗ０をそのままレジスタ２３Ｒｅｇに格納し、続く第２クロックサイクルにおいて、データｗ１をレジスタ２３Ｒｅｇに格納すると共に、レジスタ２３に保持されていた直前の値Ｒｅｇを第２メモリ４２の記憶領域ｃ０に書き込む、というパイプライン動作を繰り返していく。
【００５４】
演算部２０は、制御部１０による制御の下で、５ワード分のデータ転送を合計５回繰り返す（ステップＳ２１８〜Ｓ２１９）。これによって、Ｃ＝Ｗ、即ち、Ｃ＝Ａ＋Ｂ ｍｏｄ Ｐの演算が完了する。以上のように、本多倍長演算装置１００は、１クロックサイクルで１ワード長の演算を行う回路規模の小さな演算部２０を備えるにも拘らず、わずか１０クロックサイクルで５ワード長の加算剰余演算を完了した。ここで、もし、上記第１の処理が終了した段階においてキャリーが生じていなかった場合には、わずか５クロックサイクルで５ワード長の加算剰余演算の結果Ｗが得られたことになる。
【００５５】
次に、本多倍長演算装置１００がモンゴメリ演算（Ｍ＝Ａ・Ｒ＾（−１） ｍｏｄ Ｐ）を実行する場合について、図１０〜図１６を用いて説明する。図１０は、モンゴメリ演算の式と、モンゴメリ演算に際して外部装置から本多倍長演算装置１００に与えられる入力データ、即ち、メモリ入出力部３０を経てメモリ部４０に格納される入力データＡ、Ｐ、Ｖの例とを示す図である。
【００５６】
整数Ａは、モンゴメリ演算の対象となるデータであり、１０ワード長の整数［ａ９、ａ８、・・、ａ１、ａ０］である。整数Ｐは、剰余演算における法であり、５ワード長の整数［ｐ４、ｐ３、ｐ２、ｐ１、ｐ０］である。整数Ｑは、整数Ｐの符号を反転した値（−Ｐ）に等しい５ワード長の整数［ｑ４、ｑ３、ｑ２、ｑ１、ｑ０］である。整数Ｖは、外部装置による上記前計算の計算結果である５ワード長の整数［ｖ４、ｖ３、ｖ２、ｖ１、ｖ０］である。
【００５７】
図１１は、本多倍長演算装置１００によるモンゴメリ演算におけるメモリ部４０のメモリマップを示す。ここには、上記４つの入力データＡ、Ｐ、Ｑ、Ｖに加えて、演算過程で生じる５ワード長の中間データＢ［ｂ４、ｂ３、ｂ２、ｂ１、ｂ０］、６ワード長の中間データＣ［ｃ５、ｃ４、ｃ３、ｃ２、ｃ１、ｃ０］、演算過程で必要とされる１ワード長の固定値Ｅ［ｅ０］（0xffffffff；１ワードの全ビットがオール“１”）及びこのモンゴメリ演算の最終結果を格納するための５ワード長の整数Ｍ［ｍ４、ｍ３、ｍ２、ｍ１、ｍ０］及びＮ［ｎ４、ｎ３、ｎ２、ｎ１、ｎ０］も併せて示されている。
【００５８】
第１メモリ４１には、整数Ａ、Ｐ、Ｑ及びＭが格納され、第２メモリ４２には、整数Ｖ、中間データＢ、Ｃ、固定値Ｅ及び整数Ｎが格納される。このようなメモリマップによって、演算部２０は、１クロックサイクルで、４つのデータＡ、Ｐ、Ｑ及びＭから選択した２つのワードと、３つのデータＶ、Ｂ、Ｃ及びＥから選択した２つのワードとを同時に読み出し又は書き込みすることができる。
【００５９】
［ｓｔｅｐ１］次に、図１２（ａ）、（ｂ）及び図１３を用いて、本多倍長演算装置１００がモンゴメリ演算のｓｔｅｐ１を実行する場合の動作、即ち、図４に示されたステップＳ２０３の詳細な動作を説明する。
図１２（ａ）、（ｂ）は、いずれも、モンゴメリ演算のｓｔｅｐ１を実行する場合の演算部２０の動作状態と演算部２０への入力データとを示す模式図である。演算部２０は、整数Ａを構成する各ワードａｉと整数Ｖを構成する各ワードｖｊとを乗算するとともに、得られた同一桁の部分積を累積（累算）し、その累積結果を整数Ｂに代入する。
【００６０】
図１２（ａ）は、同一桁の部分積の累積における最初の加算時における演算部２０の動作状態を示す。ここでは、演算部２０のセレクタ２５は、レジスタ２３から出力される２ワード長のデータの上位ワードを下位ワードし“０”を上位ワードとする２ワード長のデータを選択している。これは、同一桁の部分積の累積によって得られた２ワード長の累積値の上位ワードを、その上位の部分積の累積、即ち、１ワードだけ上位にシフトした桁に位置する部分積の累積に加算させるためである。
【００６１】
図１２（ｂ）は、それら同一桁の部分積の累積における２回目以降の加算時における演算部２０の動作状態を示す。ここでは、演算部２０のセレクタ２５は、レジスタ２３から出力される２ワード長のデータを選択している。図１３は、演算部２０がモンゴメリ演算のｓｔｅｐ１を実行する場合の演算手順を示す図である。本図の上部には、乗算の対象となる整数Ａ［ａ４、ａ３、ａ２、ａ１、ａ０］と整数Ｖ［ｖ４、ｖ３、ｖ２、ｖ１、ｖ０］が示され、本図の中央部には、算出順に従って上方から下方に部分積が配置され、本図の下部には、同一桁の部分積の累積結果が整数Ｂ［ｂ４、ｂ３、ｂ２、ｂ１、ｂ０］の各ワードに代入される様子が示されている。
【００６２】
なお、１０ワード長の整数Ａのうち下位５ワードだけが乗算の対象とされているのは、図１０に示されるように、モンゴメリ演算のｓｔｅｐ１では整数Ｒの剰余（ｍｏｄ Ｒ）を求めればよいからである。このｓｔｅｐ１における演算部２０の具体的な動作は次の通りである。まず、制御部１０は、演算部２０及びメモリ入出力部３０に制御信号を送ることで、演算部２０を初期化しておく。
【００６３】
第１クロックサイクルにおいて、演算部２０は、制御部１０からの制御信号により図１２（ａ）に示される動作状態となった後に、メモリ入出力部３０を経て第１メモリ４１から送られてくるデータａ０と第２メモリ４２から送られてくるデータｖ０とを乗算器２１で乗算し、その結果をレジスタ２３に格納する。第２クロックサイクルにおいて、演算部２０は、第１メモリ４１から送られてくるデータａ１と第２メモリ４２から送られてくるデータｖ０とを乗算器２１で乗算し、その結果得られた乗算結果と第１クロックサイクルで得られた乗算結果を１ワードだけシフトダウンした値とを加算し、レジスタ２３に格納すると共に、レジスタ２３に保持されていた第１クロックサイクルでの乗算結果の下位ワードを第２メモリ４２の記憶領域ｂ０に書き込む。
【００６４】
第３クロックサイクルにおいて、演算部２０は、制御部１０からの制御信号により図１２（ｂ）に示される動作状態となった後に、第１メモリ４１から送られてくるデータａ０と第２メモリ４２から送られてくるデータｖ１とを乗算器２１で乗算し、その乗算結果とレジスタ２３に格納されていた２ワード長の累積値とを加算し、レジスタ２３に格納する。
【００６５】
第４クロックサイクルにおいて、演算部２０は、制御部１０からの制御信号により図１２（ａ）に示される動作状態となった後に、第１メモリ４１から送られてくるデータａ２と第２メモリ４２から送られてくるデータｖ０とを乗算器２１で乗算し、その結果得られた乗算結果と第３クロックサイクルで得られた乗算結果を１ワードだけシフトダウンした値とを加算し、レジスタ２３に格納すると共に、レジスタ２３に保持されていた第３クロックサイクルでの乗算結果の下位ワードを第２メモリ４２の記憶領域ｂ１に書き込む。
【００６６】
以下、同様にして、データａｉとデータｖｊそれぞれの添字ｉ及びｊの合計が０、１、２、３及び４となる全ての組み合わせについて、部分積（同一桁の部分積）を算出し、累算し、その結果を記憶領域ｂ０、ｂ１、ｂ２、ｂ３、ｂ４に格納することを繰り返す。このようにして、ｓｔｅｐ１の処理が完了する。なお、第１５クロックサイクルでの乗算及び累算の終了後にレジスタ２３に残った上位５ワードについては、切り捨てる。
【００６７】
［ｓｔｅｐ２］次に、図１４（ａ）、（ｂ）、（ｃ）及び図１５を用いて、本多倍長演算装置１００がモンゴメリ演算のｓｔｅｐ２を実行する場合の動作、即ち、図４に示されたステップＳ２０４の詳細な動作を説明する。
図１４（ａ）、（ｂ）は、いずれも、モンゴメリ演算のｓｔｅｐ２における前半の処理（Ｂ×Ｐ）を実行する場合の演算部２０の動作状態と演算部２０への入力データとを示す模式図である。演算部２０は、ｓｔｅｐ１で得られた整数Ｂを構成する各ワードｂｉと整数Ｐを構成する各ワードｐｊとを乗算するとともに、得られた同一桁の部分積を累積し、その累積結果の上位６ワードを整数Ｃに代入する。
【００６８】
図１４（ａ）は、同一桁の部分積の累積における最初の加算時における演算部２０の動作状態を示し、図１４（ｂ）は、それら同一桁の部分積の累積における２回目以降の加算時における演算部２０の動作状態を示す。図１４（ｃ）は、モンゴメリ演算のｓｔｅｐ２における後半の処理（上記前半の処理結果Ｂ×Ｐと整数Ａとの加算）を実行する場合の演算部２０の動作状態と演算部２０への入力データとを示す模式図である。演算部２０は、上記前半の処理で得られた整数Ｃと１ワード長の固定整数Ｅと整数Ａの上位６ワードとを加算し、その加算結果の上位５ワードを整数Ｍに代入する。
【００６９】
図１５は、演算部２０がモンゴメリ演算のｓｔｅｐ２を実行する場合の演算手順を示す図である。本図の上部には、前半の処理における乗算の対象となる整数Ｂ［ｂ４、ｂ３、ｂ２、ｂ１、ｂ０］と整数Ｐ［ｐ４、ｐ３、ｐ２、ｐ１、ｐ０］が示され、本図の中央部には、算出順に従って上方から下方に部分積が配置されている。そして、本図の下部には、同一桁の部分積の累積結果の上位６ワードが整数Ｃ［ｃ５、ｃ４、ｃ３、ｃ２、ｃ１、ｃ０］の各ワードに代入され、その整数Ｃと整数Ｅと整数Ａの上位６ワードとが加算され、その加算結果の上位５ワードが整数Ｍに代入される様子が示されている。
【００７０】
なお、上記乗算及び加算の結果（Ｂ×Ｐ＋Ａ）における上位５ワードだけが整数Ｍに格納されているのは、Ｂ×Ｐ＋Ａ ｍｏｄ Ｒ ＝ ０ という関係より、上記演算結果（Ｂ×Ｐ＋Ａ）の下半分（下位５ワード）は必ず“０”になることが分かっているからである。
従って、このｓｔｅｐ２では、上記演算結果（Ｂ×Ｐ＋Ａ）の上位５ワードだけに着目して必要な演算を実行している。ただし、演算（Ｂ×Ｐ＋Ａ）における第６ワード（最上位桁より第６番目のワード、以下同様）から第５ワードへのキャリーを考慮するために、整数Ｂと整数Ｐとの乗算及び整数Ａの加算については上位６ワードだけを演算対象としている。
【００７１】
さらに、演算（Ｂ×Ｐ＋Ａ）における第７ワードから第６ワードを経て第５ワードに伝播するキャリーを考慮するために、第６ワードの加算時においてオール“１”をも加算している。これは、上述したように、演算（Ｂ×Ｐ＋Ａ）の第６ワードが必ず“０”になることが判明していることから、もし、データｃ０とデータａ４との加算値が“０”である場合には、第７ワードからのキャリーを考慮する必要がないが、データｃ０とデータａ４との加算値が“０”でない場合には、演算第７ワードからのキャリーを考慮する必要があることに基づく。
【００７２】
なお、データｃ０とデータａ４との加算においてオール“１”のデータｅ０を加算することは、次の処理（１）〜（４）を行うことに等しい。
（１）データｃ０とデータａ４との加算結果が“０”で、かつ、キャリーが“０”である場合には、データｍ０の算出（ｃ１＋ａ５）においてキャリー“０”を加算し、（２）データｃ０とデータａ４との加算結果が“０”で、かつ、キャリーが“１”である場合には、データｍ０の算出（ｃ１＋ａ５）においてキャリー“１”を加算し、（３）データｃ０とデータａ４との加算結果が“０”でなく、かつ、キャリーが“０”である場合には、データｍ０の算出（ｃ１＋ａ５）においてキャリー“１”を加算し、（４）データｃ０とデータａ４との加算結果が“０”でなく、かつ、キャリーが“１”である場合には、データｍ０の算出（ｃ１＋ａ５）においてキャリー“２”を加算する。
【００７３】
このｓｔｅｐ２における演算部２０の具体的な動作は次の通りである。第１クロックサイクルにおいて、演算部２０は、制御部１０からの制御信号により図１４（ａ）に示される動作状態となった後に、メモリ入出力部３０を経て第２メモリ４２から送られてくるデータｂ３と第１メモリ４１から送られてくるデータｐ０とを乗算器２１で乗算し、その結果をレジスタ２３に格納する。
【００７４】
第２クロックサイクルにおいて、演算部２０は、制御部１０からの制御信号により図１４（ｂ）に示される動作状態となった後に、第２メモリ４２から送られてくるデータｂ２と第１メモリ４１から送られてくるデータｐ１とを乗算器２１で乗算し、その結果得られた乗算結果とレジスタ２３に保持されていた値とを累算し、レジスタ２３に格納する。
以下、同様にして、データｂｉとデータｐｊそれぞれの添字ｉ及びｊの合計が３となる全ての組み合わせについて、部分積（同一桁の部分積）を算出し、累積する（第３〜第４クロックサイクル）。第５クロックサイクルにおいて、演算部２０は、制御部１０からの制御信号により図１４（ａ）に示される動作状態となった後に、第２メモリ４２から送られてくるデータｂ４と第１メモリ４１から送られてくるデータｐ０とを乗算器２１で乗算し、その結果得られた乗算結果とレジスタ２３に保持されていた値を１ワードだけシフトダウンした値とを加算し、レジスタ２３に格納すると共に、レジスタ２３に保持されていた第４クロックサイクルでの乗算及び累算の結果の下位ワードを第２メモリ４２の記憶領域ｃ０に書き込む。
【００７５】
第６クロックサイクルにおいて、演算部２０は、制御部１０からの制御信号により図１４（ｂ）に示される動作状態となった後に、第２メモリ４２から送られてくるデータｂ３と第１メモリ４１から送られてくるデータｐ１とを乗算器２１で乗算し、その結果得られた乗算結果とレジスタ２３に保持されていた値とを累算し、レジスタ２３に格納する。
以下、同様にして、データｂｉとデータｐｊそれぞれの添字ｉ及びｊの合計が４〜８となる全ての組み合わせについて、部分積（同一桁の部分積）を算出し、累算し、その結果を記憶領域ｃ１、ｃ２、ｃ３、ｃ４、ｃ５に格納することを繰り返す。 続いて、演算部２０は、制御部１０からの制御信号により図１４（ｃ）に示される動作状態となった後に、メモリ入出力部３０を経て第２メモリ４２から送られてくる整数Ｃ［ｃ５、ｃ４、ｃ３、ｃ２、ｃ１、ｃ０］及び整数Ｅ［−、−、−、−、−、ｅ０］と第１メモリ４１から送られてくる整数Ａ［ａ９、ａ８、ａ７、ａ６、ａ５、ａ４］とをワード単位で桁を揃えて加算し、その結果をそれぞれ第１メモリ４１の整数Ｍ［ｍ４、ｍ３、ｍ２、ｍ１、ｍ０、−］に代入する。
【００７６】
具体的には、演算部２０は、第１クロックサイクルにおいて、データｃ０とデータａ４とデータｅ０とを加算し、第２クロックサイクルにおいて、データｃ１とデータａ５とキャリーとを加算し、その結果をデータｍ０に代入し、第３クロックサイクルにおいて、データｃ２とデータａ６とキャリーとを加算し、その結果をデータｍ１に代入し、以下同様に繰り返していく。
【００７７】
このようにして、ｓｔｅｐ２の処理が完了する。なお、このｓｔｅｐ２では、整数Ｂと整数Ｐとの部分積のうち、例えばｂ０＊ｐ０、ｂ１＊ｐ０などの添字ｉの和が２以下の部分積の算出は行われていないので、全ての部分積を算出する通常の乗算に比べ、処理時間が短縮化されている。［ｓｔｅｐ３］次に、図１６（ａ）、（ｂ）を用いて、本多倍長演算装置１００がモンゴメリ演算のｓｔｅｐ３を実行する場合の動作、即ち、図４に示されたステップＳ２０５の詳細な動作を説明する。
【００７８】
図１６（ａ）、（ｂ）は、いずれも、モンゴメリ演算のｓｔｅｐ３における演算部２０の動作状態と演算部２０への入力データとを示す模式図である。演算部２０は、第１メモリ４１（整数Ｍ）と第２メモリ４２（整数Ｎ）とを一時的な作業領域（バッファ）として交互に用いながら、ｓｔｅｐ２で得られた整数Ｍの整数Ｐを法とする剰余（Ｍ ｍｏｄ 
Ｐ）を算出し、その結果を整数Ｍ又は整数Ｎに格納する。
【００７９】
図１６（ａ）は、ｓｔｅｐ３の前半の処理における演算部２０の動作状態を示す。前半の処理では、演算部２０は、（i）整数Ｍと整数Ｑ（＝−Ｐ）とを加算し、その結果を整数Ｎに代入することと、（ii）整数Ｎと整数Ｑとを加算し、その結果を整数Ｍに代入することとを、得られた整数Ｎ（又は整数Ｍ）が負になるまでそれら加算を交互に繰り返す。
図１６（ｂ）は、ｓｔｅｐ３の後半の処理における演算部２０の動作状態を示す。演算部２０は、上記前半の処理で得られた負の整数Ｍ（又は整数Ｎ）に整数Ｐを加算し、その結果を整数Ｎ（又は整数Ｍ）に代入する。このｓｔｅｐ３における演算部２０の具体的な動作は次の通りである。第１クロックサイクルにおいて、演算部２０は、制御部１０からの制御信号により図１６（ａ）に示される動作状態となった後に、メモリ入出力部３０を経て第１メモリ４１から送られてくるデータｍ０とデータｑ０とを加算し、その結果をレジスタ２３に格納する。
【００８０】
第２クロックサイクルにおいて、演算部２０は、第１メモリ４１から送られてくるデータｍ１とデータｑ１とを加算し、その結果をレジスタ２３に格納すると共に、レジスタ２３に保持されていた値の下位１ワードを第２メモリ４２の記憶領域ｎ０に格納する。以下同様の加算と格納を繰り返すことで、第２メモリ４２の整数Ｎは、Ｍ＋Ｑ、即ち、Ｍ−Ｐの値となる。
【００８１】
次に、制御部１０は、上記加算における最後の演算で生じたキャリーをメモリ入出力部３０から受け取ることで、いま格納された新たな整数Ｎの符号を検査する。その結果、整数Ｎが正である場合には、今度は、その整数Ｎに整数Ｑを加算し整数Ｍに代入するという演算をワード単位で実行し、得られた整数Ｍの符号を検査する。以上の２種類の加算（Ｍ＋Ｑ→Ｎ、Ｎ＋Ｑ→Ｍ）を、整数Ｍ（又は整数Ｎ）が負になるまで、交互に繰り返す。
【００８２】
その結果、整数Ｍ（又は整数Ｎ）が負となった場合には、制御部１０は、演算部２０及びメモリ入出力部３０に制御信号を送ることで、演算部２０の動作状態を図１６（ｂ）に示される状態に設定する。そして、演算部２０は、上記前半の処理での加算と同様にして、ワード単位での加算と格納を繰り返すことにより、整数Ｍ（又は整数Ｎ）と整数Ｐとを加算し、その結果を整数Ｎ（又は整数Ｍ）に代入する。
【００８３】
このようにして、整数Ｍの整数Ｐを法とする剰余（Ｍ ｍｏｄ Ｐ）、即ち、モンゴメリ演算の最終結果は、第１メモリ４１の整数Ｍ又は第２メモリ４２の整数Ｎに格納され、ｓｔｅｐ３の処理が終了する。以上のように、本実施の形態の多倍長演算装置１００によれば、わずか１個の演算部２０を備えるにも拘らず、楕円曲線暗号等に必要とされる加算剰余とモンゴメリ演算という２種類の多倍長演算が実行される。
【００８４】
また、乗算器２１による２ワードの乗算及び３入力加算器２２による３ワードの加算処理と、直前の乗算及び加算結果のメモリ部４０への格納処理とは、パイプラインの異なるステージとして同時並列に実行されるので、高速な多倍長演算が可能となる。以上、本発明の多倍長演算装置について、実施の形態に基づいて説明したが、本発明はこのような実施の形態に限られないのは言うまでもない。
【００８５】
例えば、本実施の形態では、本多倍長演算装置１００は５ワード長の多倍長演算を対象とし、さらに、演算部２０の処理単位（１ワード）は３２ビットであったが、本発明はこのような数値に限定されるものではない。また、本多倍長演算装置１００は、ある整数から法Ｐを減算するために、予め外部装置から取得していた整数Ｑ（＝−Ｐ）を加算する手法をとっていたが、法Ｐで直接減算する手法をとってもよい。
【００８６】
図１７は、法Ｐで直接減算することが可能な変形例に係る演算部５０の構成を示す回路である。この演算部５０は、上記実施の形態における演算部２０において、３入力加算器２２の第２入力ポートｉｎ２の直前に符号反転部５１を追加挿入した構成に等しい。この符号反転部５１は、ｎワード長の整数の符号を反転する機能を有し、図１８（ａ）に示される回路構成と、図１８（ｂ）に示される動作機能を有する。つまり、この符号反転部５１は、ｎワード長の整数の最下位ワードが入力された場合には、その各ビットを反転させた後に“１”を加算した値を出力し、それよりも上位のワードが入力された場合には、その各ビットを反転させて出力する。
【００８７】
このような符号反転部５１に整数Ｐの各ワードを順次入力させることは、３入力加算器２２の第２入力ポートｉｎ２に整数Ｑ（＝−Ｐ）の各ワードを順次入力することに等しくなる。従って、上記演算部２０に代えてこの演算部５０を用いることで、外部装置は、事前に整数Ｑを生成して多倍長演算装置１００に与えておくという処理が不要となる。
また、本多倍長演算装置１００は、演算部２０とメモリ部４０間のデータ転送及び外部装置とメモリ部４０間のデータ転送を実行するメモリ入出力部３０を備えていたが、本発明はこのような構成に限定されるものではない。多倍長演算装置１００にメモリ入出力部３０を含ませるのではなく、これら２種類のデータ転送を外部装置や他のデータ転送制御回路等に実行させる構成としてもよい。また、それとは逆に、これら２種類のデータ転送それぞれを実行する回路を分離し、演算部２０及びメモリ部４０それぞれに含ませて実装してもよい。
【００８８】
また、第１メモリ４１及び第２メモリ４２それぞれは、１クロックサイクルで２つの独立したアクセスを同時に行うことができるデュアルポートメモリであったが、２倍の周波数のクロックの供給を受けて動作する１ポートメモリであってもよい。また、多倍長演算装置１００は、モンゴメリ演算のｓｔｅｐ２において、６ワード長の中間データＣと整数Ａの上位５ワードと１ワード長の整数Ｅとを加算することで５ワード長の整数Ｍを算出したが、これに代えて、整数Ａの上位（ｎ＋１）ワードを整数ＡＡとしたときに、（i）中間データＣ及び整数ＡＡそれぞれの最下位ワードを加算したときのキャリーと、（ii）その加算結果の１ワードが“０”の場合に“０とし、“０”でない場合に“１”とする１ビットの論理値と、（iii）前記中間データＣの上位ｎワードと、（iv）前記整数ＡＡの上位ｎワードとを加算してもよい。これによって、多倍長演算装置１００は、外部装置から整数Ｅを取得することなく、モンゴメリ演算のｓｔｅｐ２を完遂することができる。
【００８９】
また、多倍長演算装置１００は、モンゴメリ演算のｓｔｅｐ３において、モンゴメリ演算の最終結果を第１メモリ４１（整数Ｍ）及び第２メモリ４２（整数Ｎ）のいずれかに格納して終了したが、これに代えて、加算剰余演算における第３の処理のように、最終結果が格納された整数Ｎを整数Ｍに転送する処理を追加してもよい。これによって、モンゴメリ演算の最終結果が必ず整数Ｍに格納されることが保証される。
【００９０】
また、多倍長演算装置１００は、モンゴメリ演算において、部分積を算出し累算するときに、同一桁の部分積を生成するような、全ての１ワードどおしの組み合わせを選んで、乗算器の入力値を設定し、その結果とレジスタ２３に格納された累算値とを加算したが、これに代えて、メモリ部４０を介して部分積の累算値を算出してもよい。
つまり、メモリ部４０に累算値を格納するための領域を予め設けておき、部分積の算出と同時に、累算の対象となる１ワード長の累算値をメモリ部４０から読み出し、それら部分積と累算値とを桁を合わせて加算し、その加算結果を対応するメモリ部４０の領域に格納することによって累算値を更新していってもよい。これによって、乗算の対象となる２つのデータの組み合わせを選択する際の自由度が大きくなる。
【００９１】
また、演算部２０は、乗算器２１による乗算と３入力加算器２２による乗算結果の累算とを１クロックサイクルで実行したが、乗算器２１と３入力加算器２２間にレジスタを介在させることで、これら乗算と累算とを２クロックサイクルで実行してもよい。つまり、演算部２０のパイプライン構成を３ステージ（乗算、加算及びメモリ部４０への書き込み）としてもよい。これによって、１クロックサイクルにおけるパイプライン処理の最大負荷が軽減され、そのクリティカルパスが短縮化されるので、演算部２０の動作周波数を向上させることが可能となる。
【００９２】
（発明の効果）
以上の説明から明らかなように、本発明に係る多倍長演算装置は、外部装置からの指示に従って、２以上のワード長の整数を対象とする剰余演算を実行する多倍長演算装置であって、メモリと、ワード単位で、加算及び乗算を含む２以上の種類の演算を実行し、１ワード長の演算結果を出力する演算器と、剰余演算の対象となる少なくとも１つの整数を前記外部装置から前記メモリに格納する第１データ転送と、前記メモリに格納された整数をワード単位で演算器に入力させる第２データ転送と、前記演算器から出力される演算結果を前記メモリに格納する第３データ転送と、前記演算結果を前記メモリから前記外部装置に出力する第4データ転送とを行うメモリ入出力回路と、前記外部装置からの指示に従って、前記メモリ入出力回路に対して実行すべき前記第２及び第３データ転送の対象を指示して制御し、前記演算器に対して実行すべき演算の種類を指示して制御することにより、前記演算器に前記メモリに格納された整数に対する２以上の種類の剰余演算を選択的に実行させ、前記メモリ入出力回路に前記剰余演算の結果を前記メモリに格納させる制御回路とを備えることを特徴とする。
【００９３】
これによって、ＣＰＵ等の外部装置から指示を受けた多倍長演算装置は、その外部装置とは独立して、楕円曲線暗号等に必要とされる２以上の種類の剰余演算を選択的に実行するので、コプロセッサとして用いられることで、高速な多倍長演算が実現される。また、この多倍長演算装置は、ロングワードの演算器を備えるのではなく、ワード単位で動作する演算器を備え、これを繰り返し用いることで多倍長演算を完遂することができるので、小さな回路規模で実現され得る。
【００９４】
また、演算器及びメモリ入出力回路の具体的な動作内容は、固定化されているのではなく、外部装置からの指示を受けた制御回路によって決定される。従って、演算器による繰り返し回数等を制御することで、ハードウェアを変更することなく、様々なワード長の整数、即ち、様々な安全性に対応した剰余演算を実行することが可能な柔軟な多倍長演算装置が実現される。
【００９５】
ここで、前記演算器は、少なくとも２つの１ワード長のデータを加算する加算器と、少なくとも２つの１ワード長のデータを乗算する乗算器とを有し、前記メモリ入出力回路は、演算の対象となる２個の整数を前記メモリに格納した後に、それら２個の整数それぞれから１ワード長のデータを同時に読み出して前記加算器又は前記乗算器に入力させてもよい。これによって、２つの被演算データは同時に演算器に入力されるので、シーケンシャルに入力される場合に比べ、処理は高速化される。
【００９６】
また、前記メモリは、異なる２つのアドレスによって特定される２つの記憶領域それぞれに対して同時にワード単位での読み書きが可能なデュアルポートメモリを２個有し、前記メモリ入出力回路は、２個の前記デュアルポートメモリそれぞれに格納された２個の前記整数それぞれから１ワード長のデータを同時に読み出して前記加算器又は前記乗算器に入力させると同時に、前記加算器又は前記乗算器から出力される１ワード長のデータを２個の前記デュアルポートメモリのいずれかに格納してもよい。これによって、メモリから演算器へのデータの入力と演算器からメモリへのデータの出力とが同時並列に行われるので、演算器とメモリ間のデータ転送に伴うオーバーヘッドは最小限に抑えられる。つまり、ワード単位で休みなくメモリへの入出力を繰り返すことで、処理の高速化が図られる。
【００９７】
また、また、前記演算器は、前記制御回路からの指示に従って、（i）少なくとも２つの１ワード長のデータに対する加算と、（ii）２つの１ワード長のデータに対する乗算と、（iii）２つの１ワード長のデータに対する乗算及びその乗算結果の累算のいすれかを実行したり、前記演算器は、２つの１ワード長のデータを入力とし、２ワード長のデータを出力する乗算器と、前記乗算器から出力される２ワード長のデータを含む少なくとも２つの２ワード長のデータを入力とし、少なくとも２以上のワード長のデータを出力する加算器と、前記制御回路からの指示に従って、前記メモリ入出力回路から送られてくる２つの１ワード長のデータを前記乗算器及び前記加算器のいずれかに入力させると共に、前記加算器から出力されたデータの前記加算器への入力を制御することによって、前記乗算器及び前記加算器に前記３つの演算（i）〜（iii）のいずれかを実行させる選択回路とを有してもよい。
【００９８】
これによって、演算器は、わずか１個の乗算器と１個の加算器とを備えるにも拘わらず、３種類の演算の中から制御回路によって指定された演算を実行するので、小さな回路規模で多くの種類の剰余演算を実行することができる多倍長演算装置が実現される。また、前記２以上の種類の剰余演算には加算剰余が含まれ、前記制御回路は、前記外部装置から加算剰余を実行する旨及び加算剰余の対象となる整数のワード数ｎの指示を受けた場合に、前記メモリ入出力回路及び前記演算器が以下の処理（i）〜（iii）を実行するように前記メモリ入出力回路及び前記演算器を制御してもよい。つまり、（i）前記メモリ入出力回路は、加算剰余の対象となる２つのｎワード長の整数Ａ及びＢと法を示すｎワード長の整数Ｐとを前記外部装置から取得して前記メモリに格納し、（ii）前記メモリ入出力回路は、前記メモリに格納された前記整数Ａ、Ｂ及びＰそれぞれから同一桁の１ワード長のデータａ、ｂ及びｐを同時に読み出して前記演算器に入力させると共に、前記演算器から出力される１ワード長のデータｗを前記メモリに格納することを、最下位ワードから順にｎワード分だけ繰り返すことにより、ｎワード長の整数Ｗを前記メモリに格納し、（iii）前記演算器は、前記メモリ入出力回路から送られてくるデータａ、ｂ及びｐに対して、キャリーを伝播させながら、ａ＋ｂ−ｐを算出し、その結果ｗを出力することをｎ回繰り返す。
【００９９】
これによって、多倍長演算装置は、Ａ＋Ｂ−Ｐという加算剰余を投機実行するので、整数Ａ及びＢが、Ｐ≦Ａ＋Ｂ＜２Ｐの場合には、上記処理（i）〜（iii）だけで整数Ａと整数Ｂとの加算剰余が完了する。また、前記制御回路は、前記処理（i）〜（iii）が完了した直後における前記演算器からのキャリーの発生を検査し、キャリーが発生している場合には、前記メモリ入出力回路及び前記加算器を制御することで、さらに、次の処理（iv）〜（v）を実行させてもよい。つまり、（iv）前記メモリ入出力回路は、前記メモリに格納された前記整数Ｗ及びＰそれぞれから同一桁の１ワード長のデータｗ及びｐを同時に読み出して前記演算器に入力させると共に、前記演算器から出力される１ワード長のデータｃを前記メモリに格納することを、最下位ワードから順にｎワード分だけ繰り返すことにより、ｎワード長の整数Ｃを前記メモリに格納し、（v）前記演算器は、前記メモリ入出力回路から送られてくるデータｗ及びｐに対して、キャリーを伝播させながら、ｗ＋ｐを算出し、その結果ｃを出力することをｎ回繰り返す。
【０１００】
これによって、上記処理（i）〜（iii）によってＡ＋Ｂが負となってしまったときの手当て(法Ｐの引き戻し)が行われる。また、前記２以上の種類の剰余演算には、１ワードをｋビット、整数Ａを２ｎワード長の入力データ、整数Ｒを２＾（ｋ×ｎ）としたときに、ｎワード長の整数Ｐを法とするＡ・Ｒ＾（−１）の剰余を算出するためのモンゴメリリダクションが含まれ、前記制御回路は、前記外部装置からモンゴメリリダクションを実行する旨及びモンゴメリリダクションの対象となる整数Ａのワード数２ｎの指示を受けた場合に、前記メモリ入出力回路及び前記演算器がモンゴメリリダクションを実行するように前記メモリ入出力回路及び前記演算器を制御してもよい。
【０１０１】
これによって、モンゴメリリダクションという高速処理アルゴリズムに基づく剰余演算を実行する多倍長演算装置が実現される。また、前記制御回路は、前記外部装置からモンゴメリリダクションを実行する旨の指示を受けた場合に、前記メモリ入出力回路及び前記演算器が以下の処理（i）〜（v）を実行するように前記メモリ入出力回路及び前記演算器を制御してもよい。つまり、（i）前記メモリ入出力回路は、前記整数Ａ、Ｐ、及び、前記整数Ｒを法とする−Ｐ＾（−１）の剰余である整数Ｖとを前記外部装置から取得して前記メモリに格納し、（ii）前記演算器は、前記メモリに格納された前記整数Ａの下位ｎワードと前記整数Ｖとのワードごとの部分積の算出とそれら部分積における同一ワードの累算とを、最下位ワードから順に累算結果が得られるようにｎワードだけ繰り返し、その累算結果をｎワードの中間データＢとして前記メモリに格納し、（iii）前記演算器は、前記メモリに格納された前記中間データＢと整数Ｐとのワードごとの部分積の算出とそれら部分積における同一ワードの累算とを、最下位ワードを第０ワードとしたときの第０ワードから第（ｎ−３）は求めずに、第（ｎ−２）ワードから第（２ｎ−１）ワードまでを求め、その累算結果の上位（ｎ＋１）ワードを中間データＤとして前記メモリに格納し、（iv）前記演算器は、前記整数Ａの上位（ｎ＋１）ワードを整数ＡＡとしたときに、前記メモリに格納された前記中間データＤ及び前記整数ＡＡそれぞれの最下位ワードを加算したときのキャリーと、その加算結果の１ワードが０の場合に０とし、０でない場合に１とする１ビットの論理値とを生成し、前記中間データＤの上位ｎワードと、前記整数ＡＡの上位ｎワードと、前記キャリーと、前記論理値とを加算することを、最下位ワードから順にキャリーを伝播させながらワード単位での加算をｎワード分繰り返すことによって実行し、その加算結果をｎワードの出力データＭとして前記メモリに格納し、（v）前記演算器は、前記メモリに格納された前記出力データＭが前記整数Ｐ以上である場合に、前記出力データＭが０以上で前記整数Ｐより小さい整数となるまで前記出力データＭから整数Ｐを減算することを、最下位ワードから順にキャリーを伝播させながらワード単位での減算をｎワード分繰り返すことによって実行し、その減算結果を新たなｎワードの出力データＭとして前記メモリに格納する。
【０１０２】
これによって、処理（ii）及び（iii）での乗算においては、全ての可能な組み合わせについての部分積が算出されるのではなく、必要な部分積だけが算出され累算されるので、乗算処理が短縮化される。また、前記演算器は、前記処理（iv）において、前記中間データＤと前記整数ＡＡそれぞれの全てのワードとオール１の１ワード長のデータとを加算し、得られた加算結果の上位ｎワードを前記出力データＭとして前記メモリに格納してもよい。これによって、処理（iv）における４つのデータの加算は、３つのデータの加算に置き換えられ、例えば、３入力加算器による２回の演算が１回で済む。
【０１０３】
また、前記演算器は、前記処理（ii）及び（iii）において、２つのｎワード長の整数それぞれから選択した１ワードどうしの部分積を算出し累算するときに、同一桁の部分積を生成する全ての１ワードどうしの組み合わせを選んで部分積を算出し累算することを下位桁から順に繰り返していってもよい。これによって、部分積の算出と累算とは効率的な順序で実行され、パイプラインの乱れは生じにくい。
【０１０４】
また、前記演算器は、前記処理（ii）及び（iii）において、同一桁の部分積の累算で得られた２ワード長の累算結果のうち、下位１ワードを乗算結果として前記メモリに格納すると共に、上位１ワードを次に算出される１ワードだけ桁の高い部分積に加算させてもよいし、前記演算器は、前記部分積の累算結果の下位１ワードを前記メモリに格納すること、及び、前記部分積の累算結果の上位１ワードと次に算出される１ワードだけ桁の高い部分積とを加算することを同時に実行してもよい。これによって、部分積の累算と、その累算結果の上位ワードをより高い桁の部分積に伝播させる処理とが同時並列に行われるので、全ての部分積に対する累算が高速化される。
【０１０５】
また、前記演算器は、前記処理（ii）及び（iii）において、部分積を算出し累算するときに、部分積の算出と同時に、累算の対象となる１ワード長の累算値を前記メモリから読み出し、それら部分積と累算値とを桁を合わせて加算し、その加算結果を対応する前記メモリに格納することによって累算値を更新していってもよい。これによって、乗算の対象となる２つのデータの組み合わせを選択する際の自由度が大きくなる。
【産業上の利用可能性】
【０１０６】
本発明の多倍長演算装置は、ロングワードの演算器を備えるのではなく、ワード単位で動作する演算器を備え、これを繰り返し用いることで多倍長演算を完遂することができ、小さな回路規模で実現され得るので、多倍長の整数を対象とする剰余演算を実行する装置、特に、２以上の種類の剰余演算を実行する装置として有用である。
【符号の説明】
【０１０７】
１０    制御部
２０    演算部
２１    乗算器
２２    ３入力加算器
２３    レジスタ
２４〜２６    セレクタ
３０    メモリ入出力部
３１    バススイッチ部
３２    入出力制御部
３３    アドレス生成部
４０    メモリ部
４１    第１メモリ
４２    第２メモリ
５０    変形例に係る演算部
５１    符号反転部
６１〜６９    データバス
７１〜７５    アドレスバス
１００    多倍長演算装置
【図１】
2010044398.tif 000003
【図２】
2010044398.tif 000004
【図３】
2010044398.tif 000005
【図４】
2010044398.tif 000006
【図５】
2010044398.tif 000007
【図６】
2010044398.tif 000008
【図７】
2010044398.tif 000009
【図８】
2010044398.tif 000010
【図９】
2010044398.tif 000011
【図１０】
2010044398.tif 000012
【図１１】
2010044398.tif 000013
【図１２】
2010044398.tif 000014
【図１３】
2010044398.tif 000015
【図１４】
2010044398.tif 000016
【図１５】
2010044398.tif 000017
【図１６】
2010044398.tif 000018
【図１７】
2010044398.tif 000019
【図１８】
2010044398.tif 000020