(57)【要約】 【課題】  ＬＳＢから０が多数連続しているような変数を奇数になるまで１／２する際の処理を高速化することを主たる課題とし、特に、Montgomery逆元の算出の高速化を図る。【解決手段】  ｐを法とする整数ａの逆元ｒを算出する場合に、中間変数ｕ、ｖが偶数か否かを判別し（Ｓ１０３、Ｓ１０６）、中間変数ｕ、ｖが偶数であれば、当該中間変数ｕ、ｖの最下位ビットから連続する０の個数ｋ０を計数し（Ｓ２１１）、この計数によって計数された中間変数ｕ、ｖの下位側ビットの０を削除して新たな中間変数ｕ、ｖを設定する（Ｓ２１０）。また、前記計数によって計数された個数分だけ中間変数ｓの下位側に０を加えて新たな中間変数ｓを設定する（Ｓ２１２）。そして、前記計数によって計数されたｋ０をＰｈａｓｅ１のループカウント値ｋに加算し、当該中間変数ｕ、ｖに対する奇数化処理を終了する。【選択図】    図２
2005221830.tif 000002
【特許請求の範囲】
【請求項１】
ｐを法とする整数ａの逆元を算出するMontgomery逆元演算装置であって、
中間変数ｕ、ｖが偶数か否かを判別する判別手段と、
前記中間変数ｕ、ｖが偶数であるとき、当該中間変数ｕ、ｖの最下位ビットから連続する０の個数ｋ０を計数する計数手段と、
前記計数手段によって計数された中間変数ｕ、ｖの下位側ビットの０を削除することによって新たな中間変数ｕ、ｖを設定するとともに、前記計数手段によって計数された個数分だけ中間変数ｓの下位側に０を加えることによって新たな中間変数ｓを設定する中間変数設定手段と、
前記計数手段によって計数されたｋ０をＰｈａｓｅ１のループカウント値ｋに加算する加算手段と、
を有することを特徴とする逆元演算装置。
【請求項２】
ｐを法とする整数ａの逆元を算出するMontgomery逆元演算装置であって、
中間変数ｒが偶数か否かを判別する判別手段と、
前記中間変数ｒが偶数であるとき、当該中間変数ｒの最下位ビットから連続する０の個数ｋ０を計数する計数手段と、
前記計数手段によって計数された中間変数ｒの下位側ビットの０を削除することによって新たな中間変数ｒを設定する中間変数設定手段と、
前記計数手段によって計数されたｋ０をＰｈａｓｅ２のループカウント値ｉに加算する加算手段と、
を有することを特徴とする逆元演算装置。
【請求項３】
変数データの値が奇数になるまで当該変数データに１／２演算処理を施すとともに、この際に繰り返される前記１／２演算処理の回数を出力する演算処理装置であって、
前記変数が偶数か否かを判別する判別手段と、
前記変数が偶数であるとき、当該変数の最下位ビットから連続する０の個数ｋ０を計数する計数手段と、
前記計数ステップによって計数された当該変数の下位側ビットの０を削除することによって新たな変数を設定する変数設定手段と、
前記計数ステップによって計数されたｋ０を前記１／２演算処理の繰り返し回数として出力するループカウント出力手段と、
を有することを特徴とする演算処理装置。
【請求項４】
変数データの値が奇数になるまで演算回路によって当該変数データに１／２演算処理を施すとともに、この際に繰り返される前記１／２演算処理の回数を出力する演算処理方法であって、
前記変数が偶数か否かを判別する判別ステップと、
前記変数が偶数であるとき、当該変数の最下位ビットから連続する０の個数ｋ０を計数する計数ステップと、
前記計数ステップによって計数された当該変数の下位側ビットの０を削除することによって新たな変数を設定する変数設定ステップと、
前記計数ステップによって計数されたｋ０を前記１／２演算処理の繰り返し回数として出力するループカウント出力ステップと、
を有することを特徴とする演算処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算装置に関し、特に、所定のデータを暗号鍵により暗号化する際に用いて好適なものである。
【背景技術】
【０００２】
近年のコンピュータネットワークの発達により、電子メール、電子ニュース等の電子化された情報をネットワーク経由で送受信する機会が急速に増加してきている。さらに、かかるネットワークを利用して、オンラインショッピング等のサービスも提供されつつある。しかし、その一方で、ネットワーク上の電子化されたデータを盗聴・改竄し、あるいは、他人になりすまして不正にサービスの提供を受ける等の違法行為の問題が浮上してきている。
【０００３】
これらの問題に対し、暗号化技術を応用した暗号化電子メールや利用者認証システムが提案され、種々のネットワークに導入されつつある。コンピュータネットワークにおいて、暗号化技術は必須の技術になりつつある。
【０００４】
かかる暗号化技術は、大別すると、秘密鍵暗号系と公開鍵暗号系の２つに分類できる。「秘密鍵暗号系」は、送信者と受信者が同じ鍵を持つことにより、暗号通信を行う暗号化方式である。すなわち、あるデータを秘密鍵に基づいて暗号化して送信し、受け手側は、この秘密鍵を用いて暗号化データを復号し、暗号化のない元のデータを取得する。
【０００５】
また、「公開鍵暗号系」は、受信者側から公開されている公開鍵でデータを暗号化して送信し、受け手側は、この公開鍵とペアになっている秘密鍵で暗号化データを復号し、暗号化のない元のデータを取得するものである。すなわち、公開鍵で暗号化された暗号化データは、これとペアになっている秘密鍵でのみ復号でき、これにより、データの秘匿性を保持するものである。
【０００６】
公開鍵暗号系の中では、現在、ＲＳＡ（Rivest Shamir Adlman）暗号が広く知られている。この暗号化方式は、１９９７年に、Rivest Shamir Adlmanによって提案されたものである。暗号鍵（ｅ，Ｎ）とこれに対応する復号鍵（ｄ，Ｎ）を用い、ｅとＮを公開鍵、ｄを秘密鍵とし、平文をＭ、暗号文をＣとすると、ＲＳＡ暗号による暗号化Ｅと復号化Ｄのアルゴリズムは、以下のようになる。
【０００７】
Ｃ＝Ｅ（Ｍ）＝ＭｅｍｏｄＮ  …（１）
Ｅ＝Ｄ（Ｃ）＝ＣｄｍｏｄＮ  …（２）
ただし、ｄ・ｅ＝１ｍｏｄＬＣＭ（ｐ−１，ｑ−１）を満たす。なお、ＬＣＭは、最小公倍数（Lowest Common Multiple）、Ｐ、Ｑは大きな素数である。
【０００８】
通常、ｅ、ｄ、Ｎ、Ｍは５１２ビット以上の大きな整数が用いられるので、暗号化および復号化に必要となる剰余演算の高速化には様々な手法が提案されており、その中の一つに、Montgomeryにより提案されたMontgomery乗算（非特許文献１参照）を利用するものがある。
【０００９】
剰余の法をｐ、剰余の法と互いに素である基数をＲ（Ｒ＞ｐ）としたとき、［０、ｐ−１］を満たす２つの整数ａ、ｂのMontgomery乗算ＭｏｎＰｒｏ（ａ、ｂ）は、
ＭｏｎＰｒｏ（ａ、ｂ）＝ａｂＲ−１ｍｏｄ ｐ  …（３）
と定義される。
【００１０】
ここで、基数Ｒとして２のべき乗数を使用すると、Montgomery乗算を実行する際に必要となる基数Ｒの除算をシフト操作に置き換えることができるため、Montgomery乗算を高速化することができ、通常、
ＭｏｎＰｒｏ（ａ、ｂ）＝ａｂ２−ｎｍｏｄ ｐ  …（４）
として定義されることが多い。
【００１１】
ところで、「公開鍵暗号系」の中で、現在標準化が進んでいるものに、楕円曲線暗号（Elliptic Curve Cryptography）がある。これは、楕円曲線の離散対数問題に基づくもので、N.Koblitz（非特許文献２参照）と、V.Miller（非特許文献３参照）により提案された。
【００１２】
この楕円曲線暗号では、除算剰余演算が必要となるため、除算剰余演算の高速化が必要となる。除算剰余演算の高速化を図る手法として、Kaliskiにより提案されたMontgomery逆元（非特許文献４参照）を利用するものがあり、このMontgomery逆元は、
ＭｏｎＩｎｖ（ａ）＝ａ―１２ｎｍｏｄ ｐ  …（５）
と定義される。
【００１３】
上記（４）式に示すMontgomery乗算における被乗数ｂをｂ＝１とし、上記（５）式に示すMontgomery逆元と、かかるMontgomery乗算を連続して作用させると、
ＭｏｎＰｒｏ（ＭｏｎＩｎｖ（ａ）、１）＝ＭｏｎＰｒｏ（ａ−１２ｎｍｏｄｐ、１）
＝ａ−１２ｎ２−ｎｍｏｄｐ
＝ａ―１ｍｏｄｐ      …（６）
となり、ｐを法とする整数ａの逆元を求めることができる。ここで、Montgomery逆元は、後述の如く除算を必要としないため、ｐを法とする整数ａの逆元を除算なしに求めることができ、除算剰余演算を必要とする公開鍵暗号系、たとえば、上述の楕円曲線暗号の演算処理コストを削減することが可能となる。
【００１４】
かかるMontgomery逆元の導出アルゴリズムを図４および図５に示す。
【００１５】
Montgomery逆元の導出アルゴリズムは、図４に示すＰｈａｓｅ１と、図５に示すＰｈａｓｅ２からなる。ｐを法とする整数ａの逆元ｒを求める場合、中間変数ｕ、ｖにそれぞれ初期値としてｐ、ａを設定し、Ｐｈａｓｅ１、２の演算を実行する。これにより、変数ｒの値として逆元が求められる。
【００１６】
Ｐｈａｓｅ１では、中間演算を行うための変数ｕ、ｖ、ｒ、ｓと、ループカウントを行うための変数ｋを用いた演算が行われる。すなわち、これらの変数に初期値を設定した後（Ｓ１０１）、変数ｖがｖ＝０になるまで（Ｓ１０２：ＹＥＳ）、ｕが偶数であれば（Ｓ１０３：ＹＥＳ）、ｕ＝ｕ／２、ｓ＝２ｓを実行し（Ｓ１０４）、ｕが奇数で（Ｓ１０３：ＮＯ）かつｖが偶数であれば（Ｓ１０６：ＹＥＳ）、ｖ＝ｖ／２、ｒ＝２ｒを実行し（Ｓ１０７）、ｕとｖがともに奇数であり（Ｓ１０３：ＮＯ、Ｓ１０６：ＮＯ）かつｕ＞ｖであれば（Ｓ１０８：ＹＥＳ）、ｕ＝（ｕ−ｖ）／２、ｒ＝ｒ＋ｓ、ｓ＝２ｓを実行し（Ｓ１０９）、それ以外の場合（Ｓ１０８：ＮＯ）は、ｖ＝（ｖ−ｕ）／２、ｓ＝ｒ＋ｓ、ｒ＝２ｒを実行しながら（Ｓ１１０）、ループカウント値ｋを加算していく（Ｓ１０５）。そして、変数ｖがｖ＝０になると、変数ｒの補正を行い（Ｓ１１１〜Ｓ１１３）、ｒとｋをＰｈａｓｅ２に出力してＰｈａｓｅ１の演算を終了する。
【００１７】
なお、Ｐｈａｓｅ１の演算が終了したとき、変数ｒは、ｒ＝ａ―１２ｋｍｏｄ ｐとなっている。ここで、ｒ＝［０、ｐ−１］、ｎ≦ｋ≦２ｎ（ｎ：ｐを２進で表現したときの桁数）である。
【００１８】
Ｐｈａｓｅ２では、Ｐｈａｓｅ１の出力であるｒ、ｋと、ループカウントを行うための変数ｉを用いる。すなわち、変数ｉを１に初期化した後（Ｓ１１４）、ｉ＝ｋ−ｎになるまで（Ｓ１１５：ＹＥＳ）、ｒが偶数であれば（Ｓ１１６：ＹＥＳ）、ｒ＝ｒ／２を実行し（Ｓ１１７）、また、ｒが奇数であれば（Ｓ１１６：ＮＯ）、ｒ＝（ｒ＋ｐ）／２を実行しながら（Ｓ１１８）、ループカウント値ｉを加算していく（Ｓ１１９）。そして、ループカウント値ｉがｉ＝ｋ−ｎ（Ｓ１１５：ＹＥＳ）になると、変数ｒを出力してＰｈａｓｅ２の演算を終了する。
【非特許文献１】“Modular multiplication without trial division”, Mathematics of Computation, 44(170): 519-521, April 1985
【非特許文献２】“A course in number theory and cryptography”,Spring-Verlag,1997
【非特許文献３】“Use of elliptic curves in cryptography”,Advances in Cryptology-Proceedings of Crypto '85, Lecture Notes in Computer Science, 218 (1986), Spring-Verlag, pp417-426
【非特許文献４】“The Montgomery inverse and its application”,IEEE Transactions on Computers, 44(8): 1064-1065, August 1995
【発明の開示】
【発明が解決しようとする課題】
【００１９】
上述のMontgomery逆元の算出アルゴリズムにおいて、Ｐｈａｓｅ１の演算処理（Ｓ１０４、Ｓ１０７）と、Ｐｈａｓｅ２の演算処理（Ｓ１１７）は、変数ｕ、ｖまたは変数ｒが奇数になるまで繰り返し実行されるものであるため、これら変数ｕ、ｖ、ｒのＬＳＢから０が多数連続しているような場合には、０の個数分だけ、これらのステップの演算処理が繰り返し実行される。ここで、これらの変数をメモリから読み出す時間をＴｒ、１／２演算を行う処理時間をＴｃ、１／２演算処理した変数をメモリに書き戻す時間をＴｗとすると、ＬＳＢから０がＮ個連続する場合、これらのステップを繰り返すことに要される処理時間Ｔは、Ｔ＝Ｎ＊（Ｔｒ＋Ｔｃ＋Ｔｗ）となる。
【００２０】
そこで、本発明はＬＳＢから０が多数連続しているような変数を奇数になるまで１／２する際の処理を高速化することを主たる課題とし、特に、Montgomery逆元の算出の高速化を図ることを企図するものである。
【課題を解決するための手段】
【００２１】
請求項１の発明は、ｐを法とする整数ａの逆元を算出するMontgomery逆元演算装置であって、中間変数ｕ、ｖが偶数か否かを判別する判別手段と、前記中間変数ｕ、ｖが偶数であるとき、当該中間変数ｕ、ｖの最下位ビットから連続する０の個数ｋ０を計数する計数手段と、前記計数手段によって計数された中間変数ｕ、ｖの下位側ビットの０を削除することによって新たな中間変数ｕ、ｖを設定するとともに、前記計数手段によって計数された個数分だけ中間変数ｓの下位側に０を加えることによって新たな中間変数ｓを設定する中間変数設定手段と、前記計数手段によって計数されたｋ０をＰｈａｓｅ１のループカウント値ｋに加算する加算手段とを有することを特徴とする。
【００２２】
請求項２の発明は、ｐを法とする整数ａの逆元を算出するMontgomery逆元演算装置であって、中間変数ｒが偶数か否かを判別する判別手段と、前記中間変数ｒが偶数であるとき、当該中間変数ｒの最下位ビットから連続する０の個数ｋ０を計数する計数手段と、前記計数手段によって計数された中間変数ｒの下位側ビットの０を削除することによって新たな中間変数ｒを設定する中間変数設定手段と、前記計数手段によって計数されたｋ０をＰｈａｓｅ２のループカウント値ｉに加算する加算手段とを有することを特徴とする。
【００２３】
請求項３の発明は、変数データの値が奇数になるまで当該変数データに１／２演算処理を施すとともに、この際に繰り返される前記１／２演算処理の回数を出力する演算処理装置であって、前記変数が偶数か否かを判別する判別手段と、前記変数が偶数であるとき、当該変数の最下位ビットから連続する０の個数ｋ０を計数する計数手段と、前記計数ステップによって計数された当該変数の下位側ビットの０を削除することによって新たな変数を設定する変数設定手段と、前記計数ステップによって計数されたｋ０を前記１／２演算処理の繰り返し回数として出力するループカウント出力手段とを有することを特徴とする。
【００２４】
請求項４の発明は、変数データの値が奇数になるまで演算回路によって当該変数データに１／２演算処理を施すとともに、この際に繰り返される前記１／２演算処理の回数を出力する演算処理方法であって、前記変数が偶数か否かを判別する判別ステップと、前記変数が偶数であるとき、当該変数の最下位ビットから連続する０の個数ｋ０を計数する計数ステップと、前記計数ステップによって計数された当該変数の下位側ビットの０を削除することによって新たな変数を設定する変数設定ステップと、前記計数ステップによって計数されたｋ０を前記１／２演算処理の繰り返し回数として出力するループカウント出力ステップとを有することを特徴とする。
【００２５】
本発明の特徴は、以下に示す実施の形態の説明により更に明らかとなろう。但し、以下の実施の形態は、あくまでも、本発明の一つの実施形態であって、本発明ないし各構成要件の用語の意義は、以下の実施の形態に記載されたものに制限されるものではない。
【発明の効果】
【００２６】
本発明によれば、最下位ビットから連続する０の個数をカウントすることによって、当該変数が奇数化するまでに繰り返されるべき１／２演算処理の回数（ループカウント値）を検出し、且つ、最下位ビットから連続する０を取り除いた上位側ビットによって奇数化後のデータを取得するものであるから、実際に１／２演算処理を繰り返さなくとも、奇数化後のデータと、１／２演算処理の繰り返し回数を一度に算出することができ、もって、これらのデータを取得するに要する時間を著しく短縮化することができ、特に、請求項１または２の発明によれば、Montgomery逆元の算出処理を著しく高速化することができる。
【００２７】
なお、請求項１および２の発明は、それぞれ、Montgomery逆元演算処理アルゴリズムのＰｈａｓｅ１およびＰｈａｓｅ２に係るものである。実施化においては、これらの発明を、Montgomery逆元演算のＰｈａｓｅ１およびＰｈａｓｅ２の演算処理に同時に適用する形態の他、何れか一方のみを対応するＰｈａｓｅ処理に適用する形態とすることもできる。演算処理の高速化においては、前者の形態とするのが望ましいが、後者の形態によっても、１／２演算処理を実際に繰り返して奇数化する場合に比べ、数段の高速化を図ることができる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の実施の形態につき図面を参照して説明する。
【００２９】
まず、図１に実施の形態に係るMontgomery逆元演算装置の構成を示す。
【００３０】
図示の如く、本実施の形態に係るMontgomery逆元演算装置は、制御部１０１と、メモリ１０２と、メモリ制御部１０３と、演算処理部１０４と、ゼロ検出部１０５と、ゼロカウンタ１０６と、ループカウンタ１０７から構成されている。
【００３１】
制御部１０１は、予め設定された処理フローに従って各部を制御する。メモリ１０２は、中間変数ｕ、ｖ、ｒ、ｓを逐次更新記憶する。メモリ制御部１０３は、制御部１０１からの指令に応じてメモリ１０２を制御する。演算処理部１０４は、制御部１０１からの指令に応じて、メモリ１０２に記憶されている中間変数データ（ｕ、ｖ、ｒ、ｓ）に演算処理を施し、処理結果をメモリ１０２に書き戻す。
【００３２】
ゼロ検出部１０５は、メモリ１０２に記憶されている中間変数データ（ｕ、ｖ、ｒ、ｓ）を参照し、これら中間変数データ（ｕ、ｖ、ｒ、ｓ）のＬＳＢから連続するゼロを検出する。ゼロカウンタ１０６は、ゼロ検出部１０５によって検出されたゼロの個数ｋ０を計数する。ループカウンタ１０７は、Ｐｈａｓｅ１のループカウント値ｋおよびＰｈａｓｅ２のループカウント値ｉを計数する。
【００３３】
図２に、Montgomery逆元演算におけるＰｈａｓｅ１の処理アルゴリズムを示す。
【００３４】
本処理アルゴリズムは、上記図４のアルゴリズム中のＳ１０４→Ｓ１０５とＳ１０６→Ｓ１０７が、それぞれ、Ｓ２１０〜Ｓ２１３とＳ２１４〜Ｓ２１３に変更されている。
【００３５】
すなわち、ｐを法とする整数ａの逆元ｒを求めるために、制御部１０１にｐとａが入力されると、制御部１０１は、変数ｕ、ｖ、ｒ、ｓに初期値（ｕ＝ｐ、ｖ＝ａ、ｒ＝０、ｓ＝１）を設定し、メモリ１０２に格納する（Ｓ１０１）。このとき同時に、ループカウンタ１０７のカウント値ｋをリセットする。
【００３６】
ここで、変数ｕが偶数であれば（Ｓ１０３：ＹＥＳ）、メモリ制御部１０３は、ゼロ検出部１０５による検出値をもとに、変数ｕのＬＳＢから連続する０を除いて新たに変数ｕをメモリ１０２上に設定する（Ｓ２１０）。また、メモリ制御部１０３は、ゼロカウンタ１０６によるカウント値ｋ０（変数ｕのゼロカウント値）を（Ｓ２１１）、変数ｓのＬＳＢに追加すべきゼロの数、すなわち、変数ｕの奇数化にともなって実行されるべき変数ｓの２倍算の繰り返し処理の回数として保持する（Ｓ２１２）。さらに、ループカウンタ１０７は、ゼロカウンタ１０６のカウント値ｋ０（変数ｕのゼロカウント値）をもとに、ｋ＝ｋ＋ｋ０を実行し、ループカウント値ｋを更新する（Ｓ２１３）。以上の処理により、変数ｕの奇数化と、これに伴う変数ｓの２倍算の繰り返し処理およびループカウント値ｋの更新が終了する。
【００３７】
なお、変数ｓの２倍算は、実際には、後段のＳ１０９とＳ１１０において、変数ｓによる演算を行う際に、メモリ１０２に格納した変数ｓのＬＳＢに、Ｓ２１２で保持したカウント値ｋ０個のゼロを追加することにより行われる。すなわち、制御部１０１は、Ｋ０ビットだけ上位にシフトしたデータとして出力されるようにメモリにアクセスすることで変数ｓに対する２倍算の繰り返し処理を実行し、その後、演算処理部１０４にＳ１０９とＳ１１０における変数ｓの演算を行わしめる。
【００３８】
次に、変数ｕが偶数であれば（Ｓ１０６：ＹＥＳ）、メモリ制御部１０３は、ゼロ検出部１０５による検出値をもとに、変数ｖのＬＳＢから連続する０を除いて新たに変数ｖをメモリ１０２上に設定する（Ｓ２１４）。また、メモリ制御部１０３は、ゼロカウンタ１０６によるカウント値ｋ０（変数ｖのゼロカウント値）を（Ｓ２１５）、変数ｒのＬＳＢに追加すべきゼロの数、すなわち、変数ｖの奇数化にともなって実行されるべき変数ｒの２倍算の繰り返し処理の回数として保持する（Ｓ２１６）。さらに、ループカウンタ１０７は、ゼロカウンタ１０６のカウント値ｋ０（変数ｖのゼロカウント値）をもとに、ｋ＝ｋ＋ｋ０を実行し、ループカウント値ｋを更新する（Ｓ２１３）。以上の処理により、変数ｖの奇数化と、これに伴う変数ｒの２倍算およびループカウント値ｋの更新が終了する。
【００３９】
なお、変数ｒの２倍算は、実際には、後段のＳ１０９とＳ１１０において、変数ｒによる演算を行う際に、メモリ１０２に格納した変数ｒのＬＳＢに、Ｓ２１６で保持したカウント値ｋ０個のゼロを追加することにより行われる。すなわち、制御部１０１は、Ｋ０ビットだけ上位にシフトしたデータとして出力されるようにメモリにアクセスすることで変数ｒに対する２倍算の繰り返し処理を実行し、その後、演算処理部１０４にＳ１０９とＳ１１０における変数ｓの演算が行わしめる。
【００４０】
以上にようにして新たに設定された変数ｕ、ｖが、ｕ＞ｖの関係にあれば（Ｓ１０８：ＹＥＳ）、演算処理部１０４は、ｕ＝（ｕ−ｖ）／２、ｒ＝ｒ＋ｓ、ｓ＝２ｓを実行（Ｓ１０９）し、メモリ１０２に書き戻す。このとき、ループカウンタ１０７は、ｋ＝ｋ＋１を実行し、ループカウント値ｋを更新する（Ｓ１０５）。また、ｕ≦ｖの関係にあれば（Ｓ１０８：ＮＯ）、演算処理部１０４は、ｕ＝（ｖ−ｕ）／２、ｓ＝ｒ＋ｓ、ｒ＝２ｒを実行（Ｓ１０９）し、メモリ１０２に書き戻す。このとき、ループカウンタ１０７は、ｋ＝ｋ＋１を実行し、ループカウント値ｋを更新する（Ｓ１０５）。
【００４１】
かかる処理により、変数ｕまたはｖの何れかが偶数となると、上記Ｓ２１１〜２１３またはＳ２１５〜Ｓ２１３の奇数化処理がメモリ処理部１０３により実行され、さらに、Ｓ１０８以降の演算処理が演算処理部１０４により実行される。かかる処理は、変数ｖがｖ＝０になるまで（Ｓ１０２：ＹＥＳ）、繰り返される。そして、ｖ＝０になると、演算処理部１０４は、変数ｒの補正演算（Ｓ１１１〜Ｓ１１３）を行い、これにより求められた変数ｒをメモリ１０２に書き戻す。そして、この変数ｒと、このときのループカウンタ１０７のカウント値ｋをもとに、Ｐｈａｓｅ２の演算処理が開始される。
【００４２】
すなわち、Ｐｈａｓｅ２の演算処理が開始されると、制御部１０１は、ループカウンタ１０７のカウント値ｉをリセットする。ここで、変数ｒが偶数であれば（Ｓ１１６：ＹＥＳ）、メモリ制御部１０３は、ゼロ検出部１０５による検出値をもとに、変数ｒのＬＳＢから連続する０を除いて新たに変数ｒをメモリ１０２上に設定する（Ｓ２２０）。また、ループカウンタ１０７は、ゼロカウンタ１０６のカウント値ｋ０（変数ｒのゼロカウント値）をもとに、ｉ＝ｉ＋ｋ０を実行し、ループカウント値ｉを更新する（Ｓ２２１）。以上の処理により、変数ｒの奇数化と、これに伴うループカウント値ｉの更新が終了する。
【００４３】
また、変数ｒが偶数でなければ（Ｓ１１６：ＮＯ）、演算処理部１０４は、ｒ＝（ｒ＋ｐ）／２を実行し（Ｓ１１８）、これをメモリ１０２に書き戻す。このとき、ループカウンタ１０７は、ｉ＝ｉ＋１を実行し、ループカウント値ｉを更新する（Ｓ１１９）。
【００４４】
以上の処理は、ループカウンタ１０７のカウント値ｉがｉ＝ｋ−ｎになるまで繰り返される。そして、ｉ＝ｋ−ｎになると、制御部１０１は、そのときメモリ１０２に格納されている変数ｒを、ｐを法とする整数ａの逆元値として出力する。
【００４５】
以上の如く、本実施の形態によれば、変数ｕ、ｖ、ｒの奇数化処理において、実際に１／２演算処理を繰り返さなくとも、奇数化後のデータと、１／２演算処理の繰り返し回数（ループカウント値）を一度に算出することができ、もって、Montgomery逆元の演算処理を著しく高速化することができる。
【００４６】
なお、本発明は、上記実施の形態に限定されるものではなく、他に種々の変更が可能であることは言うまでもない。
【００４７】
本発明は、変数データの値が奇数になるまで当該変数データに１／２演算処理を施すとともに、この際に繰り返される前記１／２演算処理の回数を出力する演算処理装置や演算処理方法であれば、Montgomery逆元の算出処理に限らず、他の算出処理に対しても適宜、適用可能なものである。
【００４８】
本発明の実施の形態は、特許請求の範囲に示された技術的思想の範囲内において、適宜、種々の変更が可能である。
【図面の簡単な説明】
【００４９】
【図１】実施の形態に係るMontgomery逆元演算装置の構成を示す図
【図２】実施の形態に係る逆元演算処理アルゴリズム（Phase1）を示す図
【図３】実施の形態に係る逆元演算処理アルゴリズム（Phase2）を示す図
【図４】従来の形態に係る逆元演算処理アルゴリズム（Phase1）を示す図
【図５】従来の形態に係る逆元演算処理アルゴリズム（Phase2）を示す図
【符号の説明】
【００５０】
１０１  制御部
１０２  メモリ
１０３  メモリ制御部
１０４  演算処理部
１０５  ゼロ検出部
１０６  ゼロカウンタ
１０７  ループカウンタ
【図１】
2005221830.tif 000003
【図２】
2005221830.tif 000004
【図３】
2005221830.tif 000005
【図４】
2005221830.tif 000006
【図５】
2005221830.tif 000007