データ処理装置

【課題】剰余乗算器の演算ビット数の２倍を超えるビット数のデータに対する剰余乗算の演算効率を向上させることができるデータ処理装置を提供する。
【解決手段】演算部（３１０）により剰余乗算の演算処理を再帰的に複数回繰り返してｗビットの剰余乗算の剰余と商から、２ｗビットの剰余乗算の商と剰余を計算するとき、先の剰余乗算の演算処理で求めたｗビットの剰余乗算の剰余と商を、次の剰余乗算の演算処理に振り分ける制御を制御部（３２０）が行う。これにより、先の剰余乗算の演算処理がｗビットの剰余乗算の剰余だけを求める演算アルゴリズムに比べ、再帰的に行われる後の演算に必要な前の演算処理の商を新たに演算することを要しない。剰余乗算ユニットの演算ビット数の２の倍数のビット数のデータに対する剰余乗算の演算効率を向上させることができる。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ分野における、剰余乗算機能を備えたデータ処理装置に関し、例えば、剰余乗算を用いた暗号技術を適用したＩＣカード用マイクロコンピュータ、さらには当該マイクロコンピュータを備えたＩＣカードに関する。
【背景技術】
【０００２】
公開鍵暗号の事実上標準であるＲＳＡ暗号に代表されるように、剰余乗算は、暗号技術における最も基本的な演算の一つである。重い計算処理である剰余乗算を高速に実行するため、ＩＣカード等の多くの暗号機器が剰余乗算を処理できる専用のハードウェアとして剰余乗算ユニット(以降、剰余乗算専用器とも呼ぶ）を搭載している。
【０００３】
一方、剰余乗算を採用する暗号アルゴリズムでは、安全性の観点から、年々、長い鍵長を推奨する傾向がある。特に、公開鍵暗号の代表的な暗号アルゴリズムである、ＲＳＡ暗号や楕円曲線暗号に対しては、近年の計算機器の性能向上や解読アルゴリズムの改善により、より長い鍵長が要求されている。長い鍵長に対応するには、回路規模が大きな前記の剰余乗算専用器を必要とするが、回路規模の増加は、生産コストの増加を招いてしまう。また、近年はＲＦＩＤに代表される小型機器に対しても、利用者のプライバシー保護などを目的に、暗号装置の採用に対する要望が強い。従って、前記の剰余乗算専用器に対する回路の小規模化の要望が強い。そこで、計算できる最大ビット長が短い演算器を用いて長いビット長の剰余乗算を演算できるデータ処理装置が提供されている。計算できる最大ビット長を抑制して、回路全体の小規模化に貢献できる技術として、剰余乗算専用器で計算できる最大ビット長の２倍の剰余乗算を実現する技術を記載した非特許文献１、非特許文献２、及び非特許文献３がある。また、上記の非特許文献１乃至３の一般的な計算手順を整理し、汎用化した文献として、非特許文献４がある。
【０００４】
非特許文献４では、最大ｗビットの剰余乗算が計算可能な前記の剰余乗算専用器を用いて、剰余乗算の商を計算するアルゴリズム１と、その商を用いて、最大２ｗビットの剰余乗算（の剰余）を計算するアルゴリズム２を紹介している。ただし、剰余乗算の商ｑと剰余ｒでは、
ｒ＝xy2^-m mod (z)…（式ａ）
xy＝qz＋r2^ｍ…（式ｂ）
の式が成り立つ。
【０００５】
［アルゴリズム１］
入力：x、y、z、ただし0≦x、y<z、gcd(z, 2^m) = 1、かつ0≦m<ｗ
出力：xy/z、xy mod (z)
ステップ1. r ←xy2^-m mod (z)
ステップ2. r'←xy2^-m mod(z + 2^m)
ステップ3. q ← r - r'
ステップ4. q ≦-2^m, q ← q + z + 2^m
ステップ5. Return (q、r)
上記アルゴリズム１では、2種類の剰余乗算の剰余（ステップ１の剰余ｒとステップ２の剰余ｒ’）から、剰余乗算の商（q）を計算する。従って、上記アルゴリズム１は、最低でも２つの剰余乗算の剰余を演算することが必要になる。gcd(z, 2^m) = 1はzと2^mの最大公約数が１であること、即ちzと2^mが相互に素数であることを意味する。
【０００６】
［アルゴリズム２］
入力：X = x1 c + x0 2^m、Y = y1 c + y0 2^m、Z = z1 c + z0 2^m、ただし0≦m<ｗ
出力：XY mod Z
ステップ1. r1 ← x1 y1 2^-m mod(z1) and q1 ← x1 y1 -r1 z1 2^m
ステップ2. r2 ← q1 z0 2^-m mod(c) and q2 ← q1 z0 -r2 c 2^m
ステップ3. r3 ← (x0+x1)(y0+y1) 2^-m mod(c) and q3 ← (x0+x1)(y0+y1)-r3c2^m
ステップ4. r4 ←x0 y0 2^-m mod(c) and q4 ← x0 y0 -r4c2^m
ステップ5. r5 ← c(-q2+q3-q4+r1) 2^-m mod(z1) and q5 ← c(-q2+q3-q4+r1)-r5 z1 2^m
ステップ6. r6← q5 z0 2^-m mod(c) and q6 ← q5 z0 -r6 c 2^m
ステップ7. Return (q2 + q4 - q6 - r1 - r2 + r3 - r4 + r5)c + (r2 + r4 - r6)2^m
上記アルゴリズム２の入力において、最大ビット長２ｗのデータＸ、データＹ、データＺをより小さなビット長のデータx1、x0、y1、y0、z1、z0、c、2^mで表す。ただし、ｍは前記の剰余乗算専用器が実装する剰余乗算から定まるため、ｃの値を設定すれば他の値が定まる。例えば、ｍの値に応じて、c=1(m=wのとき)、c=2^m(m=0)、c=2^w-1(ｍは任意)などの値をcに設定する。このアルゴリズム２では、上記小さいビット長のデータに対してアルゴリズム１で求めた商を用いて余りを求める演算を繰り返して最後にXYmodZで表されるXYをZで割った余りが求められる。このアルゴリズム２では、６組の剰余乗算の商と剰余(ステップ1からステップ６)を要する。相対的に計算量の軽い加算や減算を無視した場合、上記アルゴリズム２は、６組の剰余乗算の商と剰余の計算コストの総和とほぼ等しい計算コストを有する。
【０００７】
【非特許文献１】Ｗ．Ｆｉｓｃｈｅｒ，Ｊ．−Ｐ．Ｓｅｉｆｅｒｔ： “Ｉｎｃｒｅａｓｉｎｇｔｈｅｂｉｔｌｅｎｇｔｈｏｆｃｒｙｐｔｏ−ｃｏｐｒｏｃｅｓｓｏｒｓ” ＣＨＥＳ２００２，ｖｏｌ．２５２３ｏｆＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．７１−−８１（２００３）．
【非特許文献２】ＢｅｎｏｉｔＣｈｅｖａｌｌｉｅｒ−Ｍａｍｅｓ，ＭａｒｃＪｏｙｅ，ａｎｄＰａｓｃａｌＰａｉｌｌｉｅｒ： “ＦａｓｔｅｒＤｏｕｂｌｅ−ＳｉｚｅＭｏｄｕｌａｒＭｕｌｔｉｐｌｉｃａｔｉｏｎＦｒｏｍＥｕｃｌｉｄｅａｎＭｕｌｔｉｐｌｉｅｒｓ” ＣＨＥＳ２００３，ｖｏｌ．２７７９ｏｆＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．２１４−２２７（２００３）．
【非特許文献３】ＭａｓａｙｕｋｉＹｏｓｈｉｎｏ，ＫａｔｓｕｙｕｋｉＯｋｅｙａ，ａｎｄＣａｍｉｌｌｅＶｕｉｌｌａｕｍｅ．ＵｎｂｒｉｄｌｅｔｈｅＢｉｔ−ＬｅｎｇｔｈｏｆａＣｒｙｐｔｏ−ＣｏｐｒｏｃｅｓｓｏｒｗｉｔｈＭｏｎｔｇｏｍｅｒｙＭｕｌｔｉｐｌｉｃａｔｉｏｎ．ＩｎＰｒｅｐｒｏｃｅｅｄｉｎｇｓｏｆＳＡＣ２００６ｐｐ．１８４−１９８（２００６）
【非特許文献４】ＭａｓａｙｕｋｉＹｏｓｈｉｎｏ，ＫａｔｓｕｙｕｋｉＯｋｅｙａ，ａｎｄＣａｍｉｌｌｅＶｕｉｌｌａｕｍｅ． “Ｄｏｕｂｌｅ−ＳｉｚｅＢｉｐａｒｔｉｔｅＭｕｌｔｉｐｌｉｃａｔｉｏｎ” ＡＣＩＳＰ２００７，ｖｏｌ．４５８６ｏｆＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．２３０−２４４（２００７）
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記の非特許文献４に紹介された実現手法(以下、従来技術と呼ぶ）では、１回で計算できる最大ビット長（ｗ）に制限がある前記の剰余乗算専用器に、上記アルゴリズム１と上記アルゴリズム２用い、最大２倍のビット長（２ｗ）の剰余乗算を計算する。即ち、上記アルゴリズム１及び２を用いて最大ビット長ｗの剰余乗算の商と余りを逐次的に計算して、最大ビット長の２倍である２ｗの剰余乗算の剰余を求めることができる。本発明者は更にこれを発展させ、上記アルゴリズムによる２倍のビット長の剰余乗算を再帰的に繰り返すことによって４倍、さらには８倍のビット長の剰余乗算を行うことについて検討した。しかしながら、２倍のビット長の剰余乗算を再帰的に繰り返して４倍のビット長の剰余乗算を行うには、４倍のビット長の剰余乗算を行うには、２倍のビット長の剰余乗算で使用した商が必要に成る。しかしながら、非特許文献に記載された技術は２倍化に特化した技術であるため、その演算に使用した商を再帰的演算に使用可能なように出力することが考慮されていなかった。そのため、単純に上記アルゴリズムを４倍化にも適用する場合には、４倍のビット長の剰余乗算を行うときは、新たに２倍のビット長の剰余乗算のアルゴリズムに従って逐次商を特別に求める操作を追加しなければならない。しかもそのような操作の追加はアルゴリズム２の各ステップで行わなければならないから、全体としての演算処理時間が著しく増大する。以下に、剰余乗算器の最大ビット長の複数倍の剰余乗算演算に関する課題を整理して示す。
【０００９】
課題１：効率性
(a)：従来技術では、前記の剰余乗算専用器が１回で計算可能な最大ビット長（ｗ）を越える剰余乗算の商の計算コストが大きい。例えば、上記アルゴリズム１と上記アルゴリズム２に従い、前記の剰余乗算専用器の最大４倍のビット長（４ｗ）の剰余剰算の計算する例を示す。４ｗビットの剰余乗算の計算では、上記アルゴリズム２に従い、各６個の２ｗビットの剰余乗算の剰余（r1、r2、r3、r4、r5、r6）と商（q1、q2、q3、q4、q5、q6）が必要である。２ｗビットのそれぞれの剰余乗算の剰余を計算するには、再度、上記アルゴリズム２に従い、各６個のｗビットの剰余乗算の剰余（r1、r2、r3、r4、r5、r6）と商（q1、q2、q3、q4、q5、q6）が必要である。一方、２ｗビットの剰余乗算の商の計算においては、上記アルゴリズム１から、前記で得た２ｗビットの剰余乗算の剰余と、別の値を持つ剰余乗算の剰余の、2種類の剰余乗算の剰余が必要である。従って、２ｗビットの6個の剰余乗算の商（q1、q2、q3、q4、q5、q6）の計算には、異なる6個の２ｗビットの剰余乗算の剰余（r1'、r2'、r3'、r4'、r5'、r6'）が必要であり、これらは上記アルゴリズム２に従い、各6個のｗビットの剰余乗算の商と剰余を必要とする。
【００１０】
従って、計算する剰余乗算のビット長が増加すると、計算に必要なｗビットの剰余乗算の剰余と商の個数（即ち、ｗビットの剰余乗算の計算回数）が指数関数的に増加する。例えば、最大ｗビットの剰余乗算の剰余を計算する前記剰余乗算器を用い、２ｗビットの剰余乗算を計算する場合にはｗビットの剰余乗算を１２回、４ｗビットの剰余乗算を計算する場合にはｗビットの剰余乗算を12²回、８ｗビットの剰余乗算を計算するには、12³回の計算が必要である。これにより、指数関数的に増加する計算量を抑制するこが必要であるという課題が見出された。
(b)：上記アルゴリズム１と上記アルゴリズム２では、剰余乗算だけでなく、四則演算（加算、減算、乗算、割算）を処理する必要がある。そこで、剰余乗算の計算機能に加え、実装環境に四則演算（加算、減算、乗算、割算）の一部または全ての計算機能を備えた方が、性能が向上する場合がある。これにより、剰余乗算に加え、四則演算を利用して、前記の剰余乗算専用器の１回で計算できる最大ビット長の２倍を越える剰余乗算を計算することが得策であるという課題が見出された。
【００１１】
課題２：柔軟なビット長の拡張
(a)：上記アルゴリズム１と上記アルゴリズム２を用いた従来技術では、前記の剰余乗算専用器が１回で最大ｗビットの剰余乗算を計算する場合、２ｗビットの剰余乗算が計算できる。この方法を再帰的に利用し、４ｗビット、８ｗビット、１６ｗビット等、ｗビットの２のべき乗倍の剰余乗算が計算できる。しかし、常に倍数は２のべき乗倍に限定される。そのため、前記の剰余乗算専用器で計算可能なビット長が変更できない（最大ビット長の剰余乗算しか計算できない等）場合、長いビット長の剰余乗算で短いビット長の剰余乗算を代用する必要がある。例えば最大1024ビット、ただし512ビットの剰余乗算も前記の剰余乗算専用器が計算可能な場合、1536(=512×3)ビットの剰余乗算を処理する代わりに、2048(=512×2²)ビットの剰余乗算を計算する必要がある。剰余乗算のビット長が長い場合、計算に必要な時間や、データの一時保存に必要なメモリが増加してしまう。これにより、２の倍数だけでなく、前記の剰余乗算専用器のビット長の整数倍の剰余乗算を計算できることが望ましいと言う課題が見出された。
(b)：計算する剰余乗算のビット長が長い場合、データの一時保存のために、より大きな領域（メモリ等）が必要である。これにより、剰余乗算器のワークメモリを容易に大きくすることが望ましいと言うことが見出された。
【００１２】
本発明の目的は、剰余乗算器の演算ビット数の２倍を超えるビット数のデータに対する剰余乗算の演算効率を向上させることができるデータ処理装置を提供することにある。
【００１３】
本発明の別の目的は、剰余乗算器の演算ビット数の２倍を超える整数倍のビット数のデータに対する剰余乗算の演算効率を向上させることができるデータ処理装置を提供することにある。
【００１４】
本発明の更に別の目的は、剰余乗算器の演算ビット数の２倍を超えるビット数のデータに対する剰余乗算のためのワークメモリを容易に大きくすることができるデータ処理装置を提供することにある。
【００１５】
本発明の前記並びにその他の目的と新規な特徴は本明細書の記述及び添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１６】
本願において開示される発明のうち代表的なものの概要を簡単に説明すれば下記の通りである。
【００１７】
〔１〕剰余乗算の演算処理を再帰的に複数回繰り返してｗビットの剰余乗算の剰余と商から、２ｗビットの剰余乗算の商と剰余を計算するとき、先の剰余乗算の演算処理で求めたｗビットの剰余乗算の剰余と商を、次の剰余乗算の演算処理に振り分ける制御を行う。これにより、先の剰余乗算の演算処理がｗビットの剰余乗算の剰余だけを求める演算アルゴリズムに比べ、再帰的に行われる後の演算に必要な前の演算処理の商を新たに演算することを要しない。剰余乗算器の演算ビット数の２の倍数のビット数のデータに対する剰余乗算の演算効率を向上させることができる。
【００１８】
〔２〕ｗビットの剰余乗算の剰余乗算の剰余と商から、ｋｗビット（ｋ＞２）の剰余乗算の商と剰余を計算するとき、kｗビットの乗算をｗビットの乗算に分割する分割演算処理と、分割処理された乗算の積から剰余乗算を計算するためのリダクション処理を前記演算部に実行させる。これにより、剰余乗算器の演算ビット数の２倍を超える整数倍のビット数のデータに対する剰余乗算の演算効率を向上させることができる。
【００１９】
〔３〕剰余乗算を行う演算部の制御部は、中央処理装置のアドレス空間に配置されたＲＡＭを、前記演算部のワークメモリとして用いことが可能とされる。剰余乗算を行う演算部内部のワークメモリを大きくすることなく剰余乗算のワークメモリを増やすことができる。
【発明の効果】
【００２０】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば下記のとおりである。
【００２１】
〔１〕剰余乗算器の演算ビット数の２倍を超えるビット数のデータに対する剰余乗算の演算効率を向上させることができる。
【００２２】
〔２〕剰余乗算器の演算ビット数の２倍を超える整数倍のビット数のデータに対する剰余乗算の演算効率を向上させることができる。
【００２３】
〔３〕剰余乗算器の演算ビット数の２倍を超えるビット数のデータに対する剰余乗算のためのワークメモリを容易に大きくすることができる。
【発明を実施するための最良の形態】
【００２４】
１．実施の形態の概要
先ず、本願において開示される発明の代表的な実施の形態について概要を説明する。代表的な実施の形態についての概要説明で括弧を付して参照する図面中の参照符号はそれが付された構成要素の概念に含まれるものを例示するに過ぎない。
【００２５】
〔１〕本発明に係るデータ処理装置（６０１）は、剰余乗算のための演算部（３１０）と制御部（３２０）を有する。前記演算部は剰余乗算の演算処理を行う。前記制御部は前記剰余乗算の演算処理を再帰的に複数回繰り返してｗビットの剰余乗算の剰余と商から、２ｗビットの剰余乗算の商と剰余を計算するとき、先の剰余乗算の演算処理で求めたｗビットの剰余乗算の剰余と商を、次の剰余乗算の演算処理に振り分ける制御を行う（アルゴリズム３）。
【００２６】
〔２〕更に具体的には、本発明に係るデータ処理装置（６０１）は、剰余乗算のための演算部（３１０）と制御部（３２０）を有する。前記演算部は、wを演算値のビット数を表す正の整数、x、y、zを0≦x、y、z<2^wを満たすwビットの非負の整数、X、Y、Zを0≦X、Y、Z<2^2wを満たす2wビットの非負の整数、m、nを非負の整数とするとき、剰余乗算の演算式xy = qz+r2ⁿを満たす整数ｑと整数ｒを出力するための演算処理を行なう。前記制御部は、前記演算処理を再帰的に繰り返すとき、前記剰余乗算専用器が出力する前記整数ｑと前記整数ｒを、乗算の演算式XY = QZ + R2^2mを満たす整数Qと整数Rを得るための次の演算処理に振り分ける処理を制御する（アルゴリズム３）。
【００２７】
〔３〕項２のデータ処理装置において、前記演算部は、剰余乗算器（１０１）、加算器（１０２）、及び減算器（１０３）を有する。
【００２８】
〔４〕項３のデータ処理装置は更に、前記演算部は、データメモリ（３０６）と、アキュムレータ（３１２）と、前記データメモリ又は前記アキュムレータから前記剰余乗算器、前記加算器、又は前記減算器へのデータ経路を選択するセレクタとを有する。前記アキュムレータは、前記剰余乗算器、前記加算器、又は前記減算器の出力を累積し、累積されたデータをセレクタ又はデータメモリに出力する。
【００２９】
〔５〕項２のデータ処理装置において、前記制御部は、前記処理の手順を記述した演算制御プログラムを保持するプログラムメモリ（３０５）と、前記プログラムメモリから読み出される演算命令を解読して前記演算部に前記演算処理を実行させるための制御信号を生成する制御回路（３０３）と、を有する。
【００３０】
〔６〕項２のデータ処理装置において、前記制御部に暗号化又は復号のための剰余乗算処理の指示を与える中央処理装置（６０３）とを更に備え、１個の半導体基板に形成されている。
【００３１】
〔７〕項２のデータ処理装置は更に、前記中央処理装置のアドレス空間に配置されたＲＡＭ（６０６）を有し、前記制御部は前記ＲＡＭを前記演算部のワークメモリとして用いことが可能とされる。
【００３２】
〔８〕本発明の別の観点によるデータ処理装置（６０１）は、剰余乗算のための演算部（３１０）と制御部（３２０）を有する。前記演算部は剰余乗算の演算処理を行う。前記制御部は、ｗビットの剰余乗算の剰余乗算の剰余と商から、ｋｗビット（ｋ＞２）の剰余乗算の商と剰余を計算するとき、kｗビットの乗算をｗビットの乗算に分割する分割演算処理と、分割処理された乗算の積から剰余乗算を計算するためのリダクション処理を前記演算部に実行させる（アルゴリズム１０）。
【００３３】
〔９〕更に具体的な観点によるデータ処理装置（６０１）は、剰余乗算のための演算部（３１０）と制御部（３２０）を有する。前記演算部は剰余乗算の演算処理を行う。前記制御部は、Ｘ、Ｙ、Ｚを0≦Ｘ、Ｙ、Ｚ<2^kwを満たすkwビットの非負の整数とし、剰余乗算の演算式Ｒ＝ＸＹ2^-kw mod Ｚを満たす非負の整数Ｒを得るとき、kwビットの整数同士の乗算の積ＸＹを小さいビット数の乗算の積に分割する分割演算処理と、前記の整数Ｚに基づいて前記分割処理された前記乗算の積ＸＹに対して次数を低くするリダクション処理と、を前記演算部に実行させる（アルゴリズム１０）。
【００３４】
〔１０〕項９のデータ処理装置において、前記リダクション処理は、前記分割処理された前記乗算の積ＸＹに対して、最終的に０以上Ｚ未満の値を求める処理である。
【００３５】
〔１１〕項１０のデータ処理装置において、前記演算部は、剰余乗算器（１０１）、加算器（１０２）、及び減算器（１０３）を有する。
【００３６】
〔１２〕項１１のデータ処理装置は更に、前記演算部は、データメモリ（３０６）と、アキュムレータ（３１２）と、前記データメモリ又は前記アキュムレータから前記剰余乗算器、前記加算器、又は前記減算器へのデータ経路を選択するセレクタ（３０８）とを有する。前記アキュムレータは、前記剰余乗算器、前記加算器、又は前記減算器の出力を累積し、累積されたデータをセレクタ又はデータメモリに出力する。
【００３７】
〔１３〕項９のデータ処理装置において、前記制御部は、前記処理の手順を記述した演算制御プログラムを保持するプログラムメモリ（３０５）と、前記プログラムメモリから読み出される演算命令を解読して前記演算部に前記分割演算処理及びリダクション処理を実行させるための制御信号を生成する制御回路（３０３）とを有する。
【００３８】
〔１４〕項９のデータ処理装置は更に、前記制御部に暗号化又は復号のための剰余乗算処理の指示を与える中央処理装置（６０３）を有し、１個の半導体基板に形成されている。
【００３９】
〔１５〕項１４のデータ処理装置は更に、前記中央処理装置のアドレス空間に配置されたＲＡＭ（６０６）を有し、前記制御部は前記ＲＡＭを前記演算部のワークメモリとして用いことが可能とされる。
【００４０】
２．実施の形態の詳細
実施の形態について更に詳述する。
【００４１】
《実施に形態１》
非特許文献４の上記アルゴリズム１と上記アルゴリズム２では、前記の剰余乗算専用器が1回で計算できる剰余乗算の最大ビット長の２倍を越える剰余乗算を計算する場合、剰余乗算の商の計算コストが大きいという前記課題１があった。剰余乗算の商の計算に、２種類の剰余乗算の剰余を要するからである。
【００４２】
そこで、剰余乗算の剰余から商を計算する方式（即ち、上記アルゴリズム１と上記アルゴリズム２に沿った方式）ではなく、乗算を計算し、剰余乗算の商と剰余を効率的に計算するアルゴリズム３を以下に示す。
【００４３】
［アルゴリズム３］
入力：X = x1 c + x0 2^m、Y = y1 c + y0 2^m、Z = z1 c + z0 2^m、ただし0≦m<ｗ
出力：XY2^-2m / Z、XY2^-2m mod Z
ステップ1. r1 ← x0 y0 2^-m mod(2^w) and q1 ← x0 y0 -r1 2^w 2^m
ステップ2. r2 ← (x0+x1)(y0+y1)2^-m mod(z1) and q2 ← (x0+x1)(y0+y1) -r2 z1 2^m
ステップ3. r3 ← x1y1 2^-m mod(z1) and q3 ← x1y1 -r3 z1 2^m
ステップ4. r4 ← (r3-q1)c 2^-m mod(z1) and q4 ← (r3-q1)c -r4 z1 2^m
ステップ5. r5 ← q3 z0 2^-m mod(z1) and q5 ← q3 z0 -r5 z1 2^m
ステップ6. r6← (q2-q3+q4-q5) z0 2^-m mod(2^w) and q6 ← (q2-q3+q4-q5) z0 -r6 2^w 2^m
ステップ7. Return q3 2^w-m+(q2-q3+q4-q5)2^m and (q1-q6-r1+r2-r3+r4-r5)2^w-m+ (r1-r6)2^m
ただし、出力値 (XY2^-2m / Z)は、XY2^-2mをZで割り、小数点以下を切捨てた値である。上記アルゴリズム３における入出力データは、以下の恒等式を満たす。
XY = (XY2^-2m / Z)Z + (XY2^-2m mod Z)2^2m
即ち、(XY2^-2m / Z)の値をもつ剰余乗算の商をＱ、(XY2^-2m mod Z)の値をもつ剰余をＲとすると、(式ａ)、（式ｂ）同様、以下の式が成り立つ。
Ｒ＝XY2^-2m mod Z・・・（式Ａ）
XY＝QZ＋Ｒ2^2m ・・・(式Ｂ)
上記アルゴリズム３の各ステップは、剰余乗算の商と剰余を求める計算と、加算と減算から構成される。剰余乗算の商を計算する毎に、上記アルゴリズム２を２回（再帰的に）呼び出す必要があった従来技術と比べ、剰余乗算の商と剰余をまとめて計算する上記アルゴリズム３は、計算量が少なく、全体の処理時間を短縮できる。
【００４４】
例えば、最大ｗビットの剰余乗算の剰余を計算する前記剰余乗算器を用い、２ｗビットの剰余乗算を計算する場合にはｗビットの剰余乗算の回数は１２回であり、上記アルゴリズム２を用いた従来技術と同様の計算量である。しかし、４ｗビットの剰余乗算を計算する場合にはｗビットの剰余乗算は6*12(=72)回、８ｗビットの剰余乗算を計算するには6²*12(=432)回である。上記アルゴリズム１と上記アルゴリズム２を用いた従来技術では、４ｗビットの場合は12²(=144)回、8ｗビットの場合は12³(=1728)回であり、提案手法は計算量が50%（４ｗビットの場合）、25％(8wビットの場合)と少なくて済む。一般に、最大ｗビットの剰余乗算の剰余を計算する前記剰余乗算器を用い、２^ｘｗビットの剰余乗算を計算する場合、従来技術に比べ、計算量は僅か(1/2^x-１)*100%で済む（ただし、理論的に計算量の少ない、加減算等の他の演算は無視している）。
【００４５】
従って、本発明では、指数関数的に増加する計算量を抑制し、より効率的に剰余乗算の剰余と商の双方を計算する処理フローと、前記処理フローを用いて剰余乗算を計算する剰余乗算器が提供できる。
【００４６】
上記アルゴリズム３の実装機器は、前記の剰余乗算専用器における剰余乗算の計算機能と、加算や減算の計算機能を実装すればよい。
【００４７】
なお、上記のアルゴリズム３は、前記の剰余乗算専用器が1回で計算可能な最大ビット長以上の剰余乗算の商と剰余を計算する他のアルゴリズムと、本質的に同様である。例えば、下記のアルゴリズム４においても、同様に商と剰余が計算できる。従って、上記アルゴリズム３と下記アルゴリズム４の処理は、本質的に同じである。アルゴリズム4は、
[アルゴリズム４]
入力：X = x1 c + x0 2^m、Y = y1 c + y0 2^m、Z = z1 c + z0 2^m、ただし0≦m<ｗ
出力：XY2^-2m / Z、XY2^-2m mod Z
ステップ1. r1 ← x0 y0 2^-m mod(2^w) and q1 ← x0 y0 -r1 2^w 2^m
ステップ2. r2 ← x1 y0 2^-m mod(z1) and q2 ← x1 y0 -r2 z1 2^m
ステップ3. r3 ← x0 y1 2^-m mod(z1) and q3 ← x0 y1 -r3 z1 2^m
ステップ4. r4 ← x1 y1 2^-m mod(z1) and q4 ← x1 y1 -r4 z1 2^m
ステップ5. r5 ← r4 c 2^-m mod(z1) and q5 ← r4 c -r5 z1 2^m
ステップ6. r6 ← q4 z0 2^-m mod(z1) and q6 ← q4 z0 -r6 z1 2^m
ステップ7. r7← (-q2-q3-q5+q6) z0 2^-m mod(2^w) and q7 ← (-q2-q3-q5+q6) z0 -r7 2^w 2^m
ステップ8. Return q4 2^w-m + (q2+q3+q5-q6)2^m and (r2+r3+r5-r6+q1+q7)2^w-m +(r1+r7)2^m
である。
【００４８】
また、下記のアルゴリズム５においても、同様に商と剰余が計算できる。アルゴリズム５は、
[アルゴリズム５]
入力：X = x1 s + x0 2^m、Y = y1 s + y0 2^m、Z = z1 s + z0 2^m、ただし0≦m<ｗかつs^２＝Z＋a
出力：XY2^-2m / Z、XY2^-2m mod Z
ステップ1. r1 ← x0 y0 2^-m mod(s) and q1 ← x0 y0 -r1 s 2^m
ステップ2. r2 ← (x1+x0)(y1+y0) 2^-m mod(s) and q2 ← (x1+x0) (y1+y0) -r2 s 2^m
ステップ3. r3 ← x1 y1 2^-m mod(s) and q3 ← x1 y1 -r3 s 2^m
ステップ4. r4 ← a q3 2^-m mod(s) and q4 ← a q3 -r4 s 2^m
ステップ5. r5 ← a(-q1+q2-q3+q4+r3) 2^-m mod(s) and q5 ← a(-q1+q2-q3+q4+r3)-r5 s 2^m
ステップ6. Return q3 2^w-m+(q1-q3+q4-q5)2^m and (r1+r4-r6)2^w-m+(q2-q6+r1-r2-r3+r4-r5)2^m
である。
【００４９】
また、前記の剰余乗算専用器が実装する剰余乗算の種類によらず、任意の種類の剰余乗算の商と剰余が計算できる。例えば、前記の剰余乗算専用器における変数ｍがｍ＝１を満たすとき(一般に、モンゴメリ乗算と呼ばれる)に、変数ｍがｍ＝0.5となる剰余乗算(一般に、二分割剰余乗算と呼ばれる)の商と剰余も、下記のアルゴリズム６に従い、計算できる。アルゴリズム６は、
［アルゴリズム６］
入力：X = x1 c + x0 2^m、Y = y1 c + y0 2^m、Z = z1 c + z0 2^m、ただし0≦m<ｗ
出力：XY2^-m /Z and XY2^-m mod(Z)
ステップ1. r1 ← x1 y1 2^-m mod(2^w) and q1 ← x1 y1 -r1 2^w 2^m
ステップ2. r2 ← (x1+x0) (y1+y0) 2^-m mod(2^w) and q2 ← (x1+x0)(y1+y0) -r2 2^w 2^m
ステップ3. r3 ← x0 y0 2^-m mod(2^w) and q3 ← x0 y0 -r3 2^w 2^m
ステップ4. r4 ← q3 2^w 2^-m mod(z1) and q4 ← q3 2^w -r4 z1 2^m
ステップ5. r5 ← r1 1 2^-m mod(z0) and q5 ← r1 1 -r5 z0 2^m
ステップ6. r6 ← q4 z0 2^-m mod(2^w) and q6 ← q4 z0 -r6 2^w 2^m
ステップ7. r7 ← q5 z1 2^-m mod(2^w) and q7 ← q5 z1 -r7 2^w 2^m
ステップ8. Return q4 2^w + q5 and (r4-q1+q2-q3-q6-q7)2^w +(q1-r1+r2+r5-r6-r7)
である。
【００５０】
また、法Zと変数ｍにおいて、Ｚ＝２^2ｗかつｍ＝０、またはＺ＝２^2ｗかつｍ＝１が成り立つ場合、剰余乗算の商と剰余を計算する上記アルゴリズム３に代えて、乗算を計算する下記アルゴリズム７を実施してもよい。ただし、下記アルゴリズム７では、乗算結果の上位２ｗビットを剰余乗算の商（ｍ＝０のとき）または剰余乗算の剰余（ｍ＝１）、下位２ｗビットを剰余乗算の剰余（ｍ＝１のとき）または剰余乗算の商（ｍ＝０）とみなす。アルゴリズム７は、
［アルゴリズム７］
入力：X = x1 c + x0 2^m、Y = y1 c + y0 2^m、Z = z1 c + z0 2^m、ただし0≦m<ｗ
出力：XY2^-2m /Z and XY2^-2m mod(Z)
ステップ1. r1 ← x0 y0 2^-m mod(2^w) and q1 ← x0 y0 -r1 2^w 2^m
ステップ2. r2 ← x0 y1 2^-m mod(2^w) and q2 ← x0 y1 -r2 2^w 2^m
ステップ3. r3 ← x1 y0 2^-m mod(2^w) and q3 ← x1 y0 -r3 2^w 2^m
ステップ4. r4 ← x1 y1 2^-m mod(2^w) and q4 ← x1 y1 -r3 2^w 2^m
ステップ5. sum = x1y12^2w + (x1y0+x0y1)2^w + x0y0
ステップ6. Return sum/2^2w and sum mod(2^2w)
である。
【００５１】
なお、上記のアルゴリズム３と同様に、上記アルゴリズム７も計算方式の一例であり、乗算を用いて、前記の剰余乗算専用器が1回で計算可能な最大ビット長以上の剰余乗算の商と剰余を計算する他のアルゴリズムと、本質的に同様である。例えば、他の計算方式として、下記のアルゴリズム８がある。アルゴリズム８は、
［アルゴリズム８］
入力：X = x1 c + x0 2^m、Y = y1 c + y0 2^m、Z = z1 c + z0 2^m、ただし0≦m<ｗ
出力：XY2^-2m /Z and XY2^-2m mod(Z)
ステップ1. r1 ← x0 y0 2^-m mod(2^w) and q1 ← x0 y0 -r1 2^w 2^m
ステップ2. r2 ← (x0+x1)(y1+y0) 2^-m mod(2^w) and q2 ← (x0+x1)(y0+y1) -r2 2^w 2^m
ステップ3. r3 ← x1 y1 2^-m mod(2^w) and q3 ← x1 y1 -r3 2^w 2^m
ステップ4. sum = x1y12^w(2^w-1) + (x1+x0)(y1+y0)2^w - x0y0(2^w-1)
ステップ5. Return sum/2^2w and sum mod(2^2w)
である。
【００５２】
次に、剰余乗算ユニットにおいて、上記アルゴリズム３を実現する場合の処理フローを説明する。ただし、その処理フローは特に制限されず、上記アルゴリズム４、上記アルゴリズム６、上記アルゴリズム７、上記アルゴリズム８やその他のアルゴリズムを処理する場合でも同様に実現できる。
【００５３】
先ず、その処理に用いる演算ユニットに付ついて説明する。特に制限されないが、図１中の（Ａ）に、与えられた所定の入力値から、各演算器固有の演算を計算し、計算結果を出力する演算器を示す。以下においては、剰余乗算の商と剰余を計算する剰余乗算器としてのＭＭ演算器１０１、加算を計算する加算器としてのＡＤＤ演算器１０２、減算を計算する減算器としてのＳＵＢ演算器１０３の３種類の演算器を用いて、上記のアルゴリズム３を処理する場合を以下で説明する。ただし、剰余乗算ユニットが上記アルゴリズム３を処理するには、剰余乗算と加算と減算が処理できればよく、それらは別々の演算器である必要は無い。例えば、剰余乗算と加算と減算の計算機能をもつ一つの演算器を用いても良い。また、２の補数表現で表したデータとＡＤＤ演算器１０２を用いて、減算を処理するように変更しても良い。
【００５４】
さらに、剰余乗算の商と剰余の計算では、別の演算器を用いても良い。上記アルゴリズム２に従い、例えば、図１中の（Ｂ）に示す剰余乗算の剰余を計算するＭＭ２演算器１５１を用いても良い。また、乗算と割算を用いて、剰余乗算が計算できる。そのため、図１中の（Ｂ）に示す乗算を計算するＭＵ演算器１５２や、割算を計算するＤＩＶ演算器１５３を用いても良い。
【００５５】
図２には上記アルゴリズム３に関する処理フローが例示される。ここでは、図1の（Ａ）で定義したＭＭ演算器１０１、ＡＤＤ演算器１０２、ＳＵＢ演算器１０３を用いた、上記アルゴリズム３に関する処理フローを示す。ただし、図２の演算器内の()内の番号は、演算器を用いるステップ番号としての参照番号である。また、図２中で線が交差する場合、黒丸印が無い場合は互いに影響がなく、黒丸印がある場合は同一の値をもつデータの分岐処理を指す。従って、図２中の処理フローは、各演算器への入力順と、黒丸印の有無、結線処理により、２ｗビットの剰余乗算の商と剰余それぞれに必要な計算ｗビットの演算結果を振り分け処理を有する。また、この振り分け処理により、図２の処理フローは、最終的には、上記アルゴリズム３の出力値であるq3と(q2-q3+q4-q5)を結合した２ｗビットの剰余乗算の商であるq3c+(q2-q3+q4-q5)と、(q1-q6-r1+r2-r3+r4-r5)と(r1-r6)を結合した２ｗビットの剰余乗算の剰余である(q1-q6-r1+r2-r3+r4- r5)c+(r1-r6)を得る。
【００５６】
例えば、ＭＭ演算器（ｍ１）は、x0、y0、cを入力値として受け付け、剰余乗算の商q1と剰余r1を出力する。ＭＭ演算器(ｍ１)から出力された商ｑ１は結線されたＳＵＢ演算器(ｓ２)とＳＵＢ演算器(ｓ３)に入力値として受け付けられ、同様に、剰余ｒ１はＳＵＢ演算器(ｓ３)とＳＵＢ演算器(ｓ７)に入力値として受け付けられる。ｑ１とｒ１を入力値として受け付けたＳＵＢ演算器は、減算(q1-r1)を計算し、その結果をＡＤＤ演算器(ａ３)へ出力する。同様の処理を他の演算器でも実施し、結果的に、図２中の最下部に記した出力値として、Ｐ１＝q3、Ｐ２＝(q2-q3+q4-q5)、Ｐ３＝(q1-q6-r1+r2-r3+r4-r5)、Ｐ４＝(r1-r6)を得る。
【００５７】
図３には図２の処理フローを実行可能な剰余乗算ユニット３の構成が例示される。なお、図３に示される全ての機能ブロックは、単結晶シリコン基板のような、一個の半導体基板に形成されている。
【００５８】
図３において、３００は、剰余乗算ユニットと他の機器の接続に用いるシステムバスを示す。３０１はクロック発生器、３０２は入出力ポート（単にＩ／Ｆと称する）、３０３はプログラムメモリとしてのプログラム用メモリ３０５に従って他の機器を制御する制御回路、３０４は制御回路３０３における各機器の状態管理用のレジスタ（管理レジスタと称する）、３０５は制御回路３０３から読み出されるプログラムやデータが格納されるプログラム用メモリ（読み込み可能であればよく、ＲＯＭ等の不揮発性媒体でもよい）、３０６はデータメモリとしてのデータの格納用メモリ（プログラムを格納してもよく、ＲＡＭ等の揮発性媒体が望ましい）、３０７は制御レジスタ、３０８はセレクタである。１０１は剰余乗算の商と剰余を計算するＭＭ演算器、１０２は加算を計算するＡＤＤ演算器、１０３は減算を計算するＳＵＢ演算器、３１２は各演算器から出力されたデータを格納するアキュムレータである。
【００５９】
特に制限されないが、上記アルゴリズム３を実現するための処理手順が記述されたプログラムをプログラム用メモリ３０５、処理中の入出力や演算で用いるデータをデータ用メモリ３０６に格納する。また、プログラム用メモリ３０５や、データ用メモリ３０６を着脱可能にし、他のメモリと交換または追加して、利用量する記憶容量の調整をしてもよい。また、剰余乗算ユニット３は、クロック発生器３０１を備えず、外部から供給されるクロック信号に基づいて動作してもよい。
【００６０】
尚、剰余乗算ユニット３において、剰余乗算器（ＭＭ演算器）１０１、加算器（ＡＤＤ演算器）１０２、減算器（ＳＵＢ演算器）１０３、セレクタ３０８、アキュムレータ２１３及びデータ用メモリ３０６は演算部３１０の一例とされ、制御回路３０３及びプログラム用メモリ３０５は制御部３２０の一例とされる。
【００６１】
剰余乗算ユニット３において、図２の処理フローを実行するための、処理フローの概略を図４に示す。図４の処理フローにおいて、剰余乗算の商と剰余の計算はＭＭ演算器１０１、加算はＡＤＤ演算器１０２、減算はＳＵＢ演算器１０３が負担すべき演算処理とされる。
【００６２】
まず、制御回路３０３がプログラム用メモリ３０５から上記アルゴリズム３を記載したプログラムを読み込む（Ｓ４０１）。制御回路３０３は、読み込んだプログラムや管理レジスタ３０４の状態に従って、データ用メモリ３０６とアキュムレータ３１２におけるデータを転送する必要があるか否かを判断する（Ｓ４０２）。転送を必要と判断した場合、データ用メモリ３０６またはアキュムレータ３１２内から、または相互間で、データを転送する。例えば、アキュムレータ３１２に格納されたデータが次の演算処理で出力されるデータに上書きされないよう、アキュムレータ３１２内のデータをデータ用メモリ３０６に転送する（Ｓ４０３）。制御回路３０３は、制御信号を送信し、制御レジスタ３０７内のレジスタ値を設定する（Ｓ４０４）。制御レジスタ３０７内のレジスタ値は、図５中の（Ａ）に示すように、利用する演算器を決定する演算コード（５０１）と、演算器に入力するデータの居場所を示すアドレスコード（５０２）からなる。制御レジスタ３０７内のレジスタ値に従い、セレクタ３０８は、演算器にデータを送信する（Ｓ４０５）。データを送信された演算器は演算（剰余乗算の商と剰余の計算、加算または減算）を処理し、演算結果をアキュムレータ３１２に出力する（Ｓ４０６）。図５中の（Ｂ）に示すように、アキュムレータ３１２は出力値のキャリー(繰上げ)またはボロウ(繰下げ)の有無を、管理レジスタ３０４に伝達する（Ｓ４０７）。制御回路３０３は、読み込んだプログラムや管理レジスタ３０４の状態に従って、処理を終了するかを判断する（Ｓ４０８）。
【００６３】
上記では、剰余乗算の商と剰余を計算できるＭＭ演算器１０１を仮定した。ＭＭ演算器１０１における剰余乗算の計算方法は問わず、例えば、古典的な剰余乗算やモンゴメリ乗算を実装するＭＭ演算器１０１であってもよい。また、ＭＭ演算器１０１の代わりに、他の演算器を用いても、同様に計算できる。例えば、図１中の（Ｂ）に示すような剰余乗算の剰余を出力するＭＭ２演算器１５１を用いてもよい。さらに、ＭＭ演算器１０１が剰余乗算だけでなく、加算や減算も計算できる場合、ＡＤＤ演算器１０２やＳＵＢ演算器１０３を用いなくても良く、剰余乗算ユニットの回路規模を削減できる。また、ＭＭ演算器１０１の代わりに、乗算を計算するＭＵ演算器１５２と割算を計算するＤＩＶ演算器１５３を用いてもよい。また、入力として、データXとデータYとデータZとデータTを受け付け、(XY＋T2^k)/ZとXY+T2^k(mod Z)を出力する演算器を用いても良い。この場合、下記のアルゴリズム９がある。アルゴリズム９は、
［アルゴリズム９］
入力：X = x1 c + x0 2^m、Y = y1 c + y0 2^m、Z = z1 c + z0 2^m、ただし0≦m<ｗ
出力：XY2^-2m /Z and XY2^-2m mod(Z)
ステップ1. r1 ← x1 y1 2^-m mod(z1) and q1 ← x1 y1 -r1 z1 2^m
ステップ2. r2 ← (x0+x1)(y1+y0) 2^-m mod(2^w-1) and q2 ← (x0+x1)(y0+y1) -r2 (2^w-1) 2^m
ステップ3. r3 ← x0 y0 2^-m mod(2^w) and q3 ← x0 y0 -r3 2^w 2^m
ステップ4. r4 ← q2 z0 2^-m + (r2-q3)2^w mod(2^w) and q4 ← q2 z0+(r2-q3)2^w-r4 2^w 2^m
ステップ5. r5 ← (q1-q2-q4) z0 2^-m mod(2^w) and q5 ← (q1-q2-q4) z0 -r5 2^w 2^m
ステップ6. Return q3 2^w + (q1-q2-q4) and (r1-r2-r3-r4+q3-q5)2^w+r3-r4-r5
である。
【００６４】
特に、剰余乗算に加え、乗算を計算できる場合は、上記アルゴリズム３において、剰余乗算に代えて乗算を計算してもよい。図５中の（Ｃ）に示すように、上記アルゴリズム３のステップ１において、c=2^ｗのとき、ｗビット整数x0とy0の積の上位ｗビットは、剰余乗算の商q1と等しく（５５１）、下位ｗビットは剰余乗算の剰余r1と等しい。ステップ6も同様の原理で商q6と剰余r6が求まる（５５２）。
【００６５】
さらに、演算器を利用する代わりに、各演算結果を予めメモリに書き込み、入力値から、適切にメモリの値を参照し、演算結果を得るように変更しても良い。この場合、演算器が必要とする回路規模を削減できるが、代わりにメモリの使用量が多くなる。
【００６６】
図６は、剰余乗算ユニットの商と剰余を計算する上記アルゴリズム３を実行可能なマイクロコンピュータ６０１のブロック図の概略の一例を示している。図６において、６０２はクロック発生器、６０３はＣＰＵ、６０４は入出力ポート（Ｉ／Ｏポートと称する）、６０５はプログラムやデータが格納された読み出し専用のメモリであるＲＯＭ、６０６はＣＰＵ６０３の作業領域を提供するメモリであるＲＡＭ、６０７はプログラムやデータを格納するメモリであるＥＥＰＲＯＭ、３は剰余乗算ユニットを示している。ＣＰＵ６０３、Ｉ／Ｏポート６０４、ＲＯＭ６０５、ＲＡＭ６０６、ＥＥＰＲＯＭ６０７、及び剰余乗算ユニット３は、アドレスバスとコントロールバスの総称であるバス６１１と、データバスの総称であるバス６１２に接続されている。クロック発生器６０２は、クロック端子ＣＬＫから供給されるクロック信号に基づき、または内部の動作基準クロック信号を生成して、ＣＰＵ６０３に供給する。Ｉ／Ｏポート６０４は、データ入出力外部端子Ｉ／Ｏに接続する。Ｖｃｃ、Ｖｓｓはマイクロコンピュータ６０１の電源用外部端子、ＲＥＳはマイクロコンピュータのリセット用外部端子である。
【００６７】
図６に示すマイクロコンピュータ６０１は、単結晶シリコン基板のような、一個の半導体基板に例えば相補型ＭＯＳ集積回路製造技術によって形成される。図６に示すマイクロコンピュータ６０１は一つの実装例であり、他の機器でも、同様に実装できる。例えば、ＲＦＩＤや、ＰＤＡ、携帯電話等の小型機器にも実装可能である。
【００６８】
《実施の形態２》
非特許文献４の上記アルゴリズム２は、前記の剰余乗算専用器のビット長の２のべき乗の倍数(＝2^x倍)が計算可能なビット長であるため、ビット長の微調整がきかず、計算量の増加や消費メモリの増加を招く、という課題２があった。上記課題２に対して有効な、前記の剰余乗算専用器のビット長の整数倍の剰余乗算を計算するアルゴリズムと処理フローを以下に説明する。
【００６９】
まず、前記の剰余乗算専用器が1回で計算できるビット長の最大３倍の剰余乗算を計算するアルゴリズム１０を以下に例示する。アルゴリズム１０は、
[アルゴリズム１０]
入力：X = x2 c² + x1 c + x0、Y = y2 c² +y1 c + y0、Z = z2 c² + z1 c + z0
出力：XY mod Z
ステップ1. q1 ← x2 y2 / z2 and r1 ← x2 y2 mod(z2)
ステップ2. q2 ← q1 z1 / z2 and r2 ← q1 z1 mod(z2)
ステップ3. q3 ← r1 c /z2 and r3 ← r1 c mod(z2)
ステップ4. q4 ← x2 y1 /z2 and r4 ← x2 y1 mod(z2)
ステップ5. q5 ← x1 y2 /z2 and r5 ← x1 y2 mod(z2)
ステップ6. q6 ← q1 z0/ z2 and r6← q1 z0 mod(z2)
ステップ7. q7 ← (-q2+q3+q4+q5) z1 / z2 and r7 ← (-q2+q3+q4+q5) z1 mod(z2)
ステップ8. q8 ← (-r2+r3+r4+r5)c / z2 and r8 ←(-r2+r3+r4+r5) c mod(z2)
ステップ9. q9 ← x2 y0 / z2 and r9 ← x2 y0 mod(z2)
ステップ10. q10 ← x1 y1 / z2 and r10 ← x1 y1 mod(z2)
ステップ11. q11 ← x0 y2 / z2 and r11 ← x0 y2 mod(z2)
ステップ12. q12 ← (-q2+q3+q4+q5) z0 / c and r12 ← (-q2+q3+q4+q5) z0 mod(c)
ステップ13. q13 ← (-q6-q7+q8+q9+q10+q11) z1 / c and r13 ← (-q6-q7+q8+q9+q10+q11) z1 mod(c)
ステップ14. q14 ← x1 y0 / c and r14 ← x1 y0 mod(c)
ステップ15. q15 ← x0 y1 / c and r15 ← x0 y1 mod(c)
ステップ16. q16 ← (-q6-q7+q8+q9+q10+q11) z0 / c and r16 ← (-q6-q7+q8+q9+q10+q11) z0 mod(c)
ステップ17. q17 ← x0 y0 / c and r17 ← x0 y0 mod(c)
ステップ18. Return ((-q12-q13+q14+q15-r6-r7+r8+r9+r10+r11)c² + (-r12-r13+r14+r15- q16+q17)c + (-r16+r17))(mod Z)
である。
【００７０】
上記アルゴリズム１０も、実施の形態１における前記剰余乗算ユニットを用い、同様に実現できる。従って、実施の形態１と実施の形態２において、実装できる装置はプログラムを除いて変わらない。要するに、プログラムメモリ３０５にはアルゴリズム１０を実現するデータ処理手順が記述されたプログラムが格納され、そのプログラムによって規定されるデータを処理行なうための制御回路３０３や演算器１０１，１０２，１０３等は図３の構成をそのまま用いればよい。
【００７１】
上記のアルゴリズム１０の各ステップは、剰余乗算の商と剰余を求める計算と、加算と減算から構成される。前記の剰余乗算専用器のビット長の２倍の剰余乗算を計算する上記アルゴリズム３を再帰的に２回呼び出す場合に比べると、ステップ数が圧倒的に少ない。例えば、上記アルゴリズム１０における、１７回の剰余乗算の商と剰余の計算に対し、上記アルゴリズム３の計算は、３６回である。従って、剰余乗算の計算量が半分以下（＝１７／３６）で済み、全体の処理時間を短縮できる。
【００７２】
上記アルゴリズム１０が、正しく剰余乗算(XY mod Z)を計算できることを以下に示す。
【００７３】
c=2^ｗとすると、整数cと式(X=x2c²+x1c+x0)を用い、3ｗビットの整数Xを、前記の剰余乗算専用器のビット長(ｗビット)の整数x2, x1, x0に分割できる。他の整数Y、Zも同様にｗビット整数y2,y1,y0,z2,z1,z0であらわせる(Y=y2c²+y1c+y0, Z=z2c²+z1c+z0)。従って、乗算XYをｗビット整数で展開すると、(式0)から(式1)のように展開できる。
XY = (x2 c² + x1c + x0)(y2 c² + y1c + y0)…(式0)
= x2y2c⁴+(x2y1+x1y2)c³ + (x2y0+x1y1+x0y2)c² + (x1y0+x0y1)c + x0y0…(式1)
なお、展開方法としては、(式1)のような単純な展開式の他、効率的な乗算式への変換が知られているKaratsubaアルゴリズムや、Tom-Cook乗算アルゴリズム、高速フーリエ変換アルゴリズム等の計算手法を用いても良い。
【００７４】
以降では、(式1)の値が法Z未満になるよう、(式1)の各項目を変換、整理していく。この要が、次式
z2c² = -z1c - z0 (mod Z)
である。以下のその変換と整理の内容を示す。
【００７５】
(式1の第一項)x2y2c⁴
= (q1z2+r1)c⁴ （式(x2 y2 = q1 z2 + r1)、即ち、r1=x2y2 modz2とq1=x2y2/z2を利用)
= -q1(z1c + z0)c² + r1c⁴ (式(z2c² = -z1c -z0 (mod Z))を利用)
= (-q1z1+r1c)c³ - q1z0c² …(式2)
上記展開式の第一式と第二式において、x2 y2 = q1 z2+r1が成り立つ。上記の式を満たすq1とr1は、(式ａ)と（式ｂ）の関係式から、(x2 y2 / z2)の値を持つ整数をq1、(x2 y2 mod(z2))の値を持つ整数をr1とすればよい。従って、上記アルゴリズム10のステップ１
q1←x2 y2 / z2
r1←x2 y2 mod(z2)
が導けた。
【００７６】
（式１）の第一項を展開した（式2）と、式１の他の項の共通項を探す。すると、(式2)の第一項と(式1)の第二項が共通項c³でまとめられる。すなわち、
(式2)の第一項+ (式1)の第二項
= (-q1z1+r1c)c³ +(x2y1+x1y2)c³
= ((-q2+q3+q4+q5)z2+(-r2+r3+r4+r5))c³
= (q' z2+r')c³ （q'=-q2+q3+q4+q5 かつ r'=-r2+r3+r4+r5 と整理)
= - q' z1c² - q'z0c+r'c³ …(式3) (式(z2c² = -z1c -z0 (mod Z))を利用)
となる。
【００７７】
ステップ１を導いた場合と同様、(式a)と（式b）の関係式から、上記展開式の第一式と第二式において、q1z1=q2z2+r2、r1c=q3z2+r3、x2y1=q4z2+r4、x1y2=q5z2+r5が成り立つ。
従って、
ステップ2. q2 ← q1 z1 / z2 and r2 ← q1 z1 mod(z2)
ステップ3. q3 ← r1 c /z2 and r3 ← r1 c mod(z2)
ステップ4. q4 ← x2 y1 /z2 and r4 ← x2 y1 mod(z2)
ステップ5. q5 ← x1 y2 /z2 and r5 ← x1 y2 mod(z2)
のように、上記アルゴリズム10のステップ2からステップ5が導けた。
【００７８】
（式１）の第一項を展開した（式2）の第一項を含む展開式である(式3)と、(式2)の他の項と、(式１)の残りの項の共通項を探す。そうすると、(式1)の第三項と(式2)の第二項と(式3)の第一項と第三項が共通項c²でまとめられる。すなわち、
(式1)の第三項＋(式2)の第二項＋(式3)の第一項＋(式3)の第三項
= (x2y0+x1y1+x0y2)c² - q1z0c² - q'z1c²+r'c³
= ((-q6-q7+q8+q9+q10+q11)z2+(-r6-r7+r8+r9+r10+r11))c²
= q''z2c² + r''c²
（q''=-q6-q7+q8+q9+q10+q11かつ r''=-r6-r7+r8+r9+r10+r11と整理)
= - q''z1c - q''z0+ r''c²…(式4) (式(z2c²=-z1c-z0(mod Z))を利用)
である。
【００７９】
ステップ１からステップ5を導いた場合と同様、(式a)と（式b）の関係式から、上記展開式の第一式と第二式において、q1z0=q6z2+r6、(-q2+q3+q4+q5)z1=q7z2+r7、(-r2+r3+r4+r5)c=q8z2+r8、x2y0=q9z2+r9、x1y1=q10z2+r10、x0y2=q11z2+r11が成り立つ。従って、
ステップ6. q6 ← q1 z0/ z2 and r6← q1 z0 mod(z2)
ステップ7. q7 ← (-q2+q3+q4+q5) z1 / z2 and r7 ← (-q2+q3+q4+q5) z1 mod(z2)
ステップ8. q8 ← (-r2+r3+r4+r5)c / z2 and r8 ←(-r2+r3+r4+r5) c mod(z2)
ステップ9. q9 ← x2 y0 / z2 and r9 ← x2 y0 mod(z2)
ステップ10. q10 ← x1 y1 / z2 and r10 ← x1 y1 mod(z2)
ステップ11. q11 ← x0 y2 / z2 and r11 ← x0 y2 mod(z2)
のように、上記アルゴリズム10のステップ6からステップ11が導けた。
【００８０】
共通項c²および共通項cでまとめるよう、共通項でくくれない各式の項に対し、cを法とする乗算を計算する。従って、下記の式が導ける。すなわち、
(式1)の第四項＋(式3)の第二項＋(式4)の第一項
= (x1y0+x0y1)c - q'z0c - q' z1c
= (-q12-q13+q14+q15)c² + (-r12-r13+r14+r15)c…(式5)
(式１)の第五項＋(式4)の第二項
= -q''z0 + x0y0
= (-q16+q17)c + (-r16+r17) …(式6)
である。
【００８１】
ステップ１からステップ11を導いた場合と同様、(式a)と（式b）の関係式から、 (-q2+q3+q4+q5)z0=q12c+r12、(-q6-q7+q8+q9+q10+q11)z1=q13c+r13、x1y0=q14c+r14、x0y1=q15c+r15、(-q6-q7+q8+q9+q10+q11)c=q16c+r16、x0y0=q17c+r17が成り立つ。従って、
ステップ12. q12 ← (-q2+q3+q4+q5) z0 / c and r12 ← (-q2+q3+q4+q5) z0 mod(c)
ステップ13. q13 ← (-q6-q7+q8+q9+q10+q11) z1 / c and r13 ← (-q6-q7+q8+q9+q10+q11) z1 mod(c)
ステップ14. q14 ← x1 y0 / c and r14 ← x1 y0 mod(c)
ステップ15. q15 ← x0 y1 / c and r15 ← x0 y1 mod(c)
ステップ16. q16 ← (-q6-q7+q8+q9+q10+q11) z0 / c and r16 ← (-q6-q7+q8+q9+q10+q11) z0 mod(c)
ステップ17. q17 ← x0 y0 / c and r17 ← x0 y0 mod(c)
のように、上記アルゴリズム10のステップ12からステップ17が導けた。
【００８２】
以上の式を全て整理すると、(式1)は、(式4)の第三項と(式5)の第一項と(式5)の第二項と(式6)の第一項と(式6)の第二項の和で表せる。従って、以下の式
(式１)
= (式4)の第三項＋(式5)の第一項＋(式5)の第二項＋(式6)の第一項＋(式6)の第二項
= (-q12-q13+q14+q15+r'')c²+(-r12-r13+r14+r15-q16+q17)c+(-r16+r17)・・・(式7)
が成り立つ。(式7)の値は0未満または法Z以上の値となり得る。そこで、0未満の場合は法Zを加算し、法Z以上の場合は法Zの減算を繰返して、0以上法Z未満の値を得る。これによって上記アルゴリズムのステップ18が導けた。
【００８３】
なお、上記の（式０）の展開方法を記載したプログラムをプログラム用メモリ３０５で管理し、剰余乗算ユニットにおける制御回路３０３が、前記プログラムに従って、上記展開式を計算しても良い。また、ＲＯＭ６０５やＲＡＭ６０６、またはＥＥＰＲＯＭ６０７で前記プログラムを管理し、マイクロコンピュータにおける、ＣＰＵ６０３が前記プログラムに従って、展開式を計算してもよい。
【００８４】
上記アルゴリズム１０は、前記の剰余乗算専用器のビット長の最大３倍の剰余乗算を計算する場合に利用できる。上記アルゴリズム１０を汎用化した、前記の剰余乗算専用器のビット長の整数倍（２倍、３倍、４倍、５倍、６倍・・・）の剰余乗算を計算する処理フローを図７に示す。図７の処理フローに従い、前記コプロのビット長の整数倍の剰余乗算が計算できる。
【００８５】
まず、前記の剰余乗算専用器のビット長にあわせ、剰余乗算に必要なパラメータ（乗数Ｘ、被乗数Ｙ、法Ｚ）を分解する。分解式は、特に制限されないが、例えば次式で表せる。
Ｘ＝Σ_(i=0)^[k/ｗ]xicⁱ、Ｙ＝Σ_(i=0)^[k/ｗ]yicⁱ、Ｚ＝Σ_(i=0)^[k/ｗ]zicⁱ・・・(式8)
ただし、ｋは各整数のビット長とし、[k/ｗ]はビット長kを前記の剰余乗算専用器のビット長ｗで割った値を切り下げた整数とする。
【００８６】
例えば、上記アルゴリズム１０の(式０)も(式８)と同様の分解ステップにあたる（Ｓ７０１）。分解したパラメータを展開し、各パラメータ毎の乗算を構成する。この展開ステップでは、単純な展開式や、Karatsubaアルゴリズム、Tom-Cook乗算アルゴリズム、高速フーリエ変換アルゴリズム等の計算手法が利用できる。例えば、上記アルゴリズム１０の(式１)が上記の展開ステップにあたる（Ｓ７０２）。展開された方程式において、最高次ビットまたは最低次ビットの項目から処理を始める。(式1)で最高次ビットから始める場合、第一項が６ｗビット、第二項が５ｗビット、第三項が４ｗビット、第四項が３ｗビット、第五項が２ｗビットである。従って、(式１)では第一項x2y2c⁴が最高ビット長である（Ｓ７０３）。上記項目に対して、剰余乗算を計算する。このとき、(式８)の法Ｚにおける最高次の整数ｚ[k/ｗ]を剰余乗算の法とする。例えば、上記アルゴリズム１０では、最高次の項目であるx2y2c⁴に対し、整数ｚ2が剰余乗算の法である（Ｓ７０４）。各項目を一括して計算できないか、整理するために、共通項をまとめる。上記アルゴリズム１０の場合では、(式２)の第一項と(式１)の第二項の計算において、z2c²を被乗数とする各整数q2、q3、q4、q5と、c³を被乗数とする各整数r2、r3、r4、r5をそれぞれq'とｒ'にまとめている（Ｓ７０５)。
(式8)を変形すると、次式が得られる。
z[k/ｗ] ＝ -Σ_(i=0)^[k/ｗ]-1 zicⁱ (mod Z)・・・(式9)
(式9)を用い、Ｓ７０４で計算した剰余乗算の商に関わる項目の次数を減らす、リダクション処理を行う。例えば、上記アルゴリズム１０の場合では、(式1の第一項)x2y2c⁴の変形式の第二式から、6ｗビットの整数q1z2c⁴を5ｗビットの整数q1z1c³と4ｗビットの整数q1z0c²に、(式9)を用いて変形している（Ｓ７０６）。
【００８７】
各項目の最高ビット長が法Ｚのビット用とほぼ等しいかそれ以下ならば、Ｓ７０８へ進み、そうでなければ、Ｓ７０２に戻る（Ｓ７０７）。
【００８８】
各項目の値を合計する。合計値が負または法Ｚ以上の場合、0以上法Z未満となるよう、法Zの加減算を行う。例えば、上記アルゴリズム１０では、(式７)以降の処理がこれにあたる（Ｓ７０８）。
【００８９】
実施の形態１と同様に、剰余乗算の商と剰余を計算するＭＭ演算器１０１、加算を計算するＡＤＤ演算器１０２、減算を計算するＳＵＢ演算器１０３の3種類の演算器を用いて、図７に記す処理フロー（上記のアルゴリズム１０を含む）を処理できる。
【００９０】
実施の形態１と同様に、図３で概略を記したブロック図における剰余乗算ユニット３は、図７の処理フローが実行可能である。また、図３に示される全ての機能ブロックは、単結晶シリコン基板のような、一個の半導体基板で形成できる。
【００９１】
実施の形態１と同様に、図４に概略を示した処理フローを用い、図７の処理フローが実行できる。また、図４における処理フローにて、ＭＭ演算器１０１における剰余乗算の計算方法は問わず、剰余乗算の商と剰余を計算できる仮定したＭＭ演算器１０１の代わりに、例えば、古典的な剰余乗算やモンゴメリ乗算を実装するＭＭ演算器１０１であってもよい。また、ＭＭ演算器１０１の代わりに、他の演算器を用いても、同様に計算できる。例えば、図１中の（Ｂ）に示すような剰余乗算の剰余を出力するＭＭ２演算器１５１を用いてもよい。さらに、ＭＭ演算器１０１が剰余乗算だけでなく、加算や減算も計算できる場合、ＡＤＤ演算器１０２やＳＵＢ演算器１０３を用いなくても良く、剰余乗算ユニットの回路規模を削減できる。また、ＭＭ演算器１０１の代わりに、乗算を計算するＭＵ演算器１５２と割算を計算するＤＩＶ演算器１５３を用いてもよい。特に、実施の形態１と同様に、剰余乗算に加え、乗算を計算できる場合は、剰余乗算に代えて乗算を計算してもよい。また、演算器を利用する代わりに、各演算結果を予めメモリに書き込み、入力値から、適切にメモリの値を参照し、演算結果を得るように変更しても良い。
【００９２】
実施の形態１と同様に、図６に概略を記したブロック図に示されるマイクロコンピュータにおいて、図４における処理フローは実行可能である。また、図６に示すマイクロコンピュータ６０１は、単結晶シリコン基板のような、一個の半導体基板で形成できる。さらに、図６に示すマイクロコンピュータ６０１は一つの実装例であり、例えば、ＲＦＩＤや、ＰＤＡ、携帯電話等の、他の機器でも実装可能である。
【００９３】
暗号アルゴリズムでは、べき乗の剰余乗算を要求するＲＳＡ暗号など、繰り返しの剰余乗算を処理する場合がある。図８において、剰余乗算ユニットを備えたマイクロコンピュータ６０１の処理フローの概略を示す。剰余乗算ユニットが備える演算機能を繰り返し用い、それらの剰余乗算に対応できる。なお、剰余乗算の計算手順は、特に図８の処理フローに制限されない。例えば、図８におけるＳ８０１からＳ８０５の処理はＣＰＵ６０３が、Ｓ８５１からＳ８５４の処理は剰余乗算ユニットが担当するが、担当区分を変更しても良い。例えば、全ての処理を剰余乗算ユニットが担当しても良い。
【００９４】
まず、ＣＰＵ６０３は剰余乗算ユニットに入力するデータＸ、データＹ、データＺを指定する（Ｓ８０１）。既に入力データが剰余乗算ユニットに設定される場合は、既に設定済みのデータを省いても良く、また、剰余乗算ユニットにより、剰余乗算の演算に必要な変数、剰余乗算のビット長等を入力するデータに指定しても良い。指定したデータの値またはアドレス（直接アドレス、または間接的にデータを参照できるアドレスでもよい）はＣＰＵ６０３から剰余乗算ユニットに通知される（Ｄ８０１）。剰余乗算ユニットは指定されたデータを用い、剰余乗算の入力値を設定する（Ｓ８５１）ＣＰＵ６０３は、剰余乗算ユニットに演算開始を指示する制御信号を送信する（Ｓ８０２）。剰余乗算の演算開始に必要な変数がある場合、Ｓ８０２にて剰余乗算ユニットに送信してもよい。演算開始を意味する前記制御信号がＣＰＵ６０３から剰余乗算ユニットに通知される（Ｄ８０２）。剰余乗算ユニットは前記制御信号を受信すると、剰余乗算を計算する（Ｓ８５２）。剰余乗算ユニットが剰余乗算を計算中、ＣＰＵ６０３は剰余乗算ユニットの演算終了を待つ、または他の演算を実行する（Ｓ８０３）。剰余乗算ユニットは剰余乗算を出力する（Ｓ８５３）。剰余乗算ユニットは、ＣＰＵ６０３に演算終了を通知する（Ｓ８５４）。剰余乗算ユニットの演算過程または出力過程等でエラーが発生した場合、エラーを意味する信号をＳ８５４にてＣＰＵ６０３に送信してもよい（Ｄ８０３）。ＣＰＵ６０３は、上記信号を受信し、演算終了を確認する（Ｓ８０４）。エラーを意味する信号が受信された場合は、ＣＰＵ６０３は演算過程でのエラー発生を確認する。以上の過程で、ＣＰＵ６０３と剰余乗算ユニットは、剰余乗算の商と剰余、または剰余乗算の剰余が計算できた。べき乗の剰余乗算を実行するアルゴリズムなどに従い、ＣＰＵ６０３は処理の繰り返しの是非を判断する（Ｓ８０６）。上記の処理を繰り返す場合は、Ｓ８０１へ戻り、繰り返さない場合は終了する。
【００９５】
なお、上記手順は、剰余乗算の剰余、または剰余乗算の商と剰余を計算する場合であったが、加算や減算等の他の演算を実施する場合でも同様である。また、制御信号の送受信は、システムバス３００を経由しても良い。
【００９６】
以上本発明者によってなされた発明を実施形態に基づいて具体的に説明したが、本発明はそれに限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。本発明は、ＩＣカードだけではなく、暗号機能を備えた種々の組込機器、情報セキュリティ技術に用いる演算器に、広く適用することができる。
【図面の簡単な説明】
【００９７】
【図１】図１は本発明の実施の形態の形態１における、剰余乗算ユニットが備える、または備えてもよい演算器を示す説明図である。
【図２】図２は本発明の実施の形態１における、処理フローの概略を示すフローチャートである。
【図３】図３は本発明の実施の形態１において、図２に示した処理フローを実行可能な剰余乗算ユニットの構成を例示するブロック図である。
【図４】図４は本発明の実施の形態１において、図２に示した処理フローを実行するためのデータ処理手順を例示するフローチャートである。
【図５】図５は、本発明の実施の形態２において、剰余乗算ユニットにおける制御レジスタ３０７内のレジスタ値の一例、剰余乗算ユニットにおける管理レジスタ３０４とアキュムレータ３１２の伝達手続きの一例、アルゴリズム３のステップ１とステップ６において剰余乗算の代わりに乗算を実行する場合に乗算の結果から剰余乗算の商と剰余の相当箇所、の夫々を示した説明図である。
【図６】図６は剰余乗算ユニットの商と剰余を計算する上記アルゴリズム３を実行可能なマイクロコンピュータ６０１の構成を例示するブロック図である。
【図７】図７は剰余乗算を計算できる演算器が1回当たりに計算できるビット長の整数倍のビット長の剰余乗算を計算する処理フローを例示するフローチャートである。
【図８】図８は剰余乗算ユニットを備えたマイクロコンピュータ６０１のデータ処理フローを概略的に示すフローチャートである。
【符号の説明】
【００９８】
１０１ＭＭ演算器
１０２ＡＤＤ演算器
１０３ＳＵＢ演算器
１５２ＭＭ２演算器
１５２ＭＵ演算器
１５３ＤＩＶ演算器
３０１クロック発生器
３０２入出力ポート
３０３制御回路
３０５プログラム用メモリ３０５
３０４管理レジスタ
３０６データの格納用メモリ
３０７制御レジスタ
３０８セレクタ
６０１マイクロコンピュータ
６０２クロック発生器
６０３ＣＰＵ
６０４入出力ポート
６０５ＲＯＭ
６０６ＲＡＭ
６０７ＥＥＰＲＯＭ

【特許請求の範囲】
【請求項１】
剰余乗算のための演算部と制御部を有し、
前記演算部は剰余乗算の演算処理を行い、
前記制御部は前記剰余乗算の演算処理を再帰的に複数回繰り返してｗビットの剰余乗算の剰余と商から、２ｗビットの剰余乗算の商と剰余を計算するとき、先の剰余乗算の演算処理で求めたｗビットの剰余乗算の剰余と商を、次の剰余乗算の演算処理に振り分ける制御を行う、データ処理装置。
【請求項２】
剰余乗算のための演算部と制御部を有し、
前記演算部は、wを演算値のビット数を表す正の整数、
x、y、zを0≦x、y、z<2^wを満たすwビットの非負の整数、
X、Y、Zを0≦X、Y、Z<2^2wを満たす2wビットの非負の整数、
m、nを非負の整数とするとき、
剰余乗算の演算式xy = qz+r2ⁿを満たす整数ｑと整数ｒを出力するための演算処理を行ない、
前記制御部は、前記演算処理を再帰的に繰り返すとき、前記剰余乗算専用器が出力する前記整数ｑと前記整数ｒを、乗算の演算式XY = QZ + R2^2mを満たす整数Qと整数Rを得るための次の演算処理に振り分ける処理を制御する、データ処理装置。
【請求項３】
前記演算部は、剰余乗算器、加算器、及び減算器を有する、請求項２記載のデータ処理装置。
【請求項４】
前記演算部は、データメモリと、
アキュムレータと、
前記データメモリ又は前記アキュムレータから前記剰余乗算器、前記加算器、又は前記減算器へのデータ経路を選択するセレクタと、を更に有し、
前記アキュムレータは、前記剰余乗算器、前記加算器、又は前記減算器の出力を累積し、累積されたデータをセレクタ又はデータメモリに出力する、請求項３記載のデータ処理装置。
【請求項５】
前記制御部は、前記処理の手順を記述した演算制御プログラムを保持するプログラムメモリと、
前記プログラムメモリから読み出される演算命令を解読して前記演算部に前記演算処理を実行させるための制御信号を生成する制御回路と、を有する請求項２記載のデータ処理装置。
【請求項６】
前記制御部に暗号化又は復号のための剰余乗算処理の指示を与える中央処理装置とを更に備え、１個の半導体基板に形成された、請求項２記載のデータ処理装置。
【請求項７】
前記中央処理装置のアドレス空間に配置されたＲＡＭを更に有し、
前記制御部は前記ＲＡＭを前記演算部のワークメモリとして用いことが可能とされる、請求項６記載のデータ処理装置。
【請求項８】
剰余乗算のための演算部と制御部を有し、
前記演算部は剰余乗算の演算処理を行い、
前記制御部は、ｗビットの剰余乗算の剰余乗算の剰余と商から、ｋｗビット（ｋ＞２）の剰余乗算の商と剰余を計算するとき、kｗビットの乗算をｗビットの乗算に分割する分割演算処理と、分割処理された乗算の積から剰余乗算を計算するためのリダクション処理を前記演算部に実行させる、データ処理装置。
【請求項９】
剰余乗算のための演算部と制御部を有し、
前記演算部は剰余乗算の演算処理を行い、
前記制御部は、Ｘ、Ｙ、Ｚを0≦Ｘ、Ｙ、Ｚ<2^kwを満たすkwビットの非負の整数とし、剰余乗算の演算式Ｒ＝ＸＹ2^-kw mod Ｚを満たす非負の整数Ｒを得るとき、
kwビットの整数同士の乗算の積ＸＹを小さいビット数の乗算の積に分割する分割演算処理と、
前記の整数Ｚに基づいて前記分割処理された前記乗算の積ＸＹに対して次数を低くするリダクション処理と、を前記演算部に実行させる、データ処理装置。
【請求項１０】
前記リダクション処理は、前記分割処理された前記乗算の積ＸＹに対して、最終的に０以上Ｚ未満の値を求める処理である、請求項９記載のデータ処理装置。
【請求項１１】
前記演算部は、剰余乗算器、加算器、及び減算器を有する、請求項１０記載のデータ処理装置。
【請求項１２】
前記演算部は、データメモリと、
アキュムレータと、
前記データメモリ又は前記アキュムレータから前記剰余乗算器、前記加算器、又は前記減算器へのデータ経路を選択するセレクタと、を更に有し、
前記アキュムレータは、前記剰余乗算器、前記加算器、又は前記減算器の出力を累積し、累積されたデータをセレクタ又はデータメモリに出力する、請求項１１記載のデータ処理装置。
【請求項１３】
前記制御部は、前記処理の手順を記述した演算制御プログラムを保持するプログラムメモリと、
前記プログラムメモリから読み出される演算命令を解読して前記演算部に前記分割演算処理及びリダクション処理を実行させるための制御信号を生成する制御回路と、を有する請求項９記載のデータ処理装置。
【請求項１４】
前記制御部に暗号化又は復号のための剰余乗算処理の指示を与える中央処理装置を更に備え、１個の半導体基板に形成された、請求項９記載のデータ処理装置。
【請求項１５】
前記中央処理装置のアドレス空間に配置されたＲＡＭを更に有し、
前記制御部は前記ＲＡＭを前記演算部のワークメモリとして用いことが可能とされる、請求項１４記載のデータ処理装置。

【図１】