JPH0720778A - 剰余計算装置、テーブル作成装置および乗算剰余計算装置 - Google Patents
剰余計算装置、テーブル作成装置および乗算剰余計算装置Info
- Publication number
- JPH0720778A JPH0720778A JP5164870A JP16487093A JPH0720778A JP H0720778 A JPH0720778 A JP H0720778A JP 5164870 A JP5164870 A JP 5164870A JP 16487093 A JP16487093 A JP 16487093A JP H0720778 A JPH0720778 A JP H0720778A
- Authority
- JP
- Japan
- Prior art keywords
- remainder
- modulus
- register
- calculation
- lower predetermined
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
- G06F7/728—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic using Montgomery reduction
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
- H04L9/302—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
- H04L2209/12—Details relating to cryptographic hardware or logic circuitry
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Physics & Mathematics (AREA)
- Computing Systems (AREA)
- Mathematical Analysis (AREA)
- Pure & Applied Mathematics (AREA)
- Mathematical Optimization (AREA)
- Computational Mathematics (AREA)
- Mathematical Physics (AREA)
- General Engineering & Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Complex Calculations (AREA)
Abstract
(57)【要約】
【目的】剰余計算の演算処理を簡略化して、高速処理を
実現する。 【構成】入力レジスタ１の下位所定ビットに対応して剰
余の法Ｎの倍数が格納された倍数テーブル５を有し、入
力レジスタ１の被剰余数Ｔの下位所定ビットに基づいて
倍数テーブル５を検索することにより、前記Ｔの下位所
定ビットに対応する剰余の法Ｎの倍数を求める。加算器
３は、倍数テーブル５の索引により求められる剰余の法
Ｎの倍数と入力レジスタ１の内容とを加算する。加算器
３の所定回数ｎの加算について、加算器３の加算結果の
上位所定ビットで入力レジスタ１の内容を更新する。補
正装置４は、加算器３の加算結果として得られるｔに対
して補正処理を施す。
実現する。 【構成】入力レジスタ１の下位所定ビットに対応して剰
余の法Ｎの倍数が格納された倍数テーブル５を有し、入
力レジスタ１の被剰余数Ｔの下位所定ビットに基づいて
倍数テーブル５を検索することにより、前記Ｔの下位所
定ビットに対応する剰余の法Ｎの倍数を求める。加算器
３は、倍数テーブル５の索引により求められる剰余の法
Ｎの倍数と入力レジスタ１の内容とを加算する。加算器
３の所定回数ｎの加算について、加算器３の加算結果の
上位所定ビットで入力レジスタ１の内容を更新する。補
正装置４は、加算器３の加算結果として得られるｔに対
して補正処理を施す。
Description
【０００１】
【産業上の利用分野】本発明は、例えば公開鍵暗号系に
おけるＲＳＡ暗号処理における剰余演算等に好適な剰余
計算装置に係り、特に剰余計算の一手法であるモンゴメ
リのアルゴリズム（Modulo Multiplication Without Tr
ial Division, Peter L. Montgomery,Mathematics of C
omputation, Volume 44, Number 170, April 1985 pp.
519〜528参照）を用いて、高速に剰余計算を行う剰余計
算装置および乗算剰余計算装置ならびに剰余計算に使用
するための倍数テーブルを作成するテーブル作成装置に
関する。
おけるＲＳＡ暗号処理における剰余演算等に好適な剰余
計算装置に係り、特に剰余計算の一手法であるモンゴメ
リのアルゴリズム（Modulo Multiplication Without Tr
ial Division, Peter L. Montgomery,Mathematics of C
omputation, Volume 44, Number 170, April 1985 pp.
519〜528参照）を用いて、高速に剰余計算を行う剰余計
算装置および乗算剰余計算装置ならびに剰余計算に使用
するための倍数テーブルを作成するテーブル作成装置に
関する。
【０００２】
【従来の技術】近年のコンピュータネットワークの発達
により、データベースの検索や電子メール、電子ニュー
スなどの電子化された情報をネットワークを経由して送
受する機会が急速に増加してきている。さらに、これら
を利用して、オンラインショッピングなどのサービスも
提供されつつある。しかし、それにともなって、ネット
ワーク上の電子化されたデータを盗聴する、改ざんす
る、他人になりすましてサービスを受けるなどの問題も
指摘されている。特に無線を利用したネットワークにお
いては、傍受が容易なためにこれらを防止する対策が望
まれている。
により、データベースの検索や電子メール、電子ニュー
スなどの電子化された情報をネットワークを経由して送
受する機会が急速に増加してきている。さらに、これら
を利用して、オンラインショッピングなどのサービスも
提供されつつある。しかし、それにともなって、ネット
ワーク上の電子化されたデータを盗聴する、改ざんす
る、他人になりすましてサービスを受けるなどの問題も
指摘されている。特に無線を利用したネットワークにお
いては、傍受が容易なためにこれらを防止する対策が望
まれている。
【０００３】これらの問題に対して暗号技術(encryptio
n technology)を応用した暗号化電子メールや利用者認
証システムが提案され、種々のネットワークにも導入さ
れつつある。この意味でコンピュータネットワークにお
いては暗号化は必須の技術であるといえる。このような
暗号技術の中の１つにディジタル署名すなわち認証に適
した公開鍵暗号方式(public key cryptosystem)がある
が、暗号化／復号に大量の処理が必要なため高速化が望
まれており、様々な高速化アルゴリズムも発表されてい
る。
n technology)を応用した暗号化電子メールや利用者認
証システムが提案され、種々のネットワークにも導入さ
れつつある。この意味でコンピュータネットワークにお
いては暗号化は必須の技術であるといえる。このような
暗号技術の中の１つにディジタル署名すなわち認証に適
した公開鍵暗号方式(public key cryptosystem)がある
が、暗号化／復号に大量の処理が必要なため高速化が望
まれており、様々な高速化アルゴリズムも発表されてい
る。
【０００４】暗号化方式は、大別すると秘密鍵暗号系と
公開鍵暗号系の２つに分類することができる。秘密鍵暗
号系は、送信者と受信者が同じ暗号鍵を持つことにより
暗号通信を行う方式である。すなわち、秘密暗号系で
は、あるメッセージを秘密の暗号鍵に基づいて暗号化し
て相手に送り、受け手はこの暗号鍵を用いて暗号を復号
しもとのメッセージに戻して情報を入手する。
公開鍵暗号系の２つに分類することができる。秘密鍵暗
号系は、送信者と受信者が同じ暗号鍵を持つことにより
暗号通信を行う方式である。すなわち、秘密暗号系で
は、あるメッセージを秘密の暗号鍵に基づいて暗号化し
て相手に送り、受け手はこの暗号鍵を用いて暗号を復号
しもとのメッセージに戻して情報を入手する。
【０００５】公開鍵暗号系は、送信者は公開されている
受信者の公開鍵でメッセージを暗号化して送信し、受信
者は自分の秘密鍵でその暗号化メッセージを復号するこ
とで通信を行う方式である。すなわち、公開鍵暗号系で
は、公開鍵は暗号化のための鍵、秘密鍵は公開鍵により
暗号化された暗号を復号するための鍵であり、公開鍵で
暗号化した暗号は秘密鍵でのみ復号することができる。
受信者の公開鍵でメッセージを暗号化して送信し、受信
者は自分の秘密鍵でその暗号化メッセージを復号するこ
とで通信を行う方式である。すなわち、公開鍵暗号系で
は、公開鍵は暗号化のための鍵、秘密鍵は公開鍵により
暗号化された暗号を復号するための鍵であり、公開鍵で
暗号化した暗号は秘密鍵でのみ復号することができる。
【０００６】秘密鍵暗号系では、個人が秘密に保管しな
ければならない鍵の数が通信相手の数だけ必要であり、
必要な総鍵数はｎ人のネットワークの場合ｎ（ｎ−１）
／２個である。また、はじめて通信する相手に対して
は、何らかの方法で秘密鍵の配送が必要であるという欠
点がある。この問題を避けるために、大規模なネットワ
ークでは鍵管理センタを設置し、センタとの間の秘密鍵
のみを保管し、暗号通信を行う場合はセンタから送信相
手との秘密鍵を得る方法が用いられる。この場合秘密鍵
の総数はｎとなる。
ければならない鍵の数が通信相手の数だけ必要であり、
必要な総鍵数はｎ人のネットワークの場合ｎ（ｎ−１）
／２個である。また、はじめて通信する相手に対して
は、何らかの方法で秘密鍵の配送が必要であるという欠
点がある。この問題を避けるために、大規模なネットワ
ークでは鍵管理センタを設置し、センタとの間の秘密鍵
のみを保管し、暗号通信を行う場合はセンタから送信相
手との秘密鍵を得る方法が用いられる。この場合秘密鍵
の総数はｎとなる。
【０００７】一方、公開鍵暗号系では、個人が秘密に保
管する鍵は自分の秘密鍵のみであり、必要な総秘密件数
もｎ人のネットワークの場合ｎ個である。また、はじめ
て通信する相手に対しては、公開鍵の配送を行えばよ
く、鍵管理センタを設置して、ユーザの公開鍵をｎ個公
開簿に登録し、センタから送信相手の公開鍵を得る方法
が用いられる。この場合、センタは公開鍵の改ざんを防
ぐだけで、秘密に保管する必要がない。但し、公開鍵方
式は秘密鍵方式に比べて鍵のビット数が大きいため保管
に要するファイルサイズは大きくなる。
管する鍵は自分の秘密鍵のみであり、必要な総秘密件数
もｎ人のネットワークの場合ｎ個である。また、はじめ
て通信する相手に対しては、公開鍵の配送を行えばよ
く、鍵管理センタを設置して、ユーザの公開鍵をｎ個公
開簿に登録し、センタから送信相手の公開鍵を得る方法
が用いられる。この場合、センタは公開鍵の改ざんを防
ぐだけで、秘密に保管する必要がない。但し、公開鍵方
式は秘密鍵方式に比べて鍵のビット数が大きいため保管
に要するファイルサイズは大きくなる。
【０００８】また、認証の場合、秘密暗号系では、例え
ば送信するメッセージを秘密鍵で圧縮変換し、送信文に
付加して送り、受信側では同様に圧縮変換して比較する
方式がとられている。しかし、送受信が同じ鍵であるた
め受信者は認証データを偽造することができる。これに
対して、公開鍵暗号系では、秘密鍵で暗号化することが
できるのは本人だけであるという特徴を利用する。送信
者はメッセージを圧縮変換して秘密鍵で暗号化し、送信
文に付加して送り、受信者は送信者の公開鍵で付加され
たデータを復号し、同様に圧縮変換したものと比較する
方式がとられている。この場合は受信者は不正ができな
い。
ば送信するメッセージを秘密鍵で圧縮変換し、送信文に
付加して送り、受信側では同様に圧縮変換して比較する
方式がとられている。しかし、送受信が同じ鍵であるた
め受信者は認証データを偽造することができる。これに
対して、公開鍵暗号系では、秘密鍵で暗号化することが
できるのは本人だけであるという特徴を利用する。送信
者はメッセージを圧縮変換して秘密鍵で暗号化し、送信
文に付加して送り、受信者は送信者の公開鍵で付加され
たデータを復号し、同様に圧縮変換したものと比較する
方式がとられている。この場合は受信者は不正ができな
い。
【０００９】このように、認証系では公開鍵暗号系の技
術は必要不可欠であるといえる。しかし、公開鍵暗号系
には、暗号化／復号に大量の処理が必要であるという大
きな欠点があるため、一般には処理の速い秘密暗号系を
メッセージの暗号化に、公開鍵暗号系は認証用にという
ように組み合わせて用いられる場合が多い。公開暗号系
の中で、現在最も有力なものが１９７７年にリヴェスト
(Rivest)、シャミア(Shamir)およびエイドルマン(Adlma
n)の３人によって発明されたＲＳＡ暗号である。ＲＳＡ
暗号の基本原理は次のようなものである。
術は必要不可欠であるといえる。しかし、公開鍵暗号系
には、暗号化／復号に大量の処理が必要であるという大
きな欠点があるため、一般には処理の速い秘密暗号系を
メッセージの暗号化に、公開鍵暗号系は認証用にという
ように組み合わせて用いられる場合が多い。公開暗号系
の中で、現在最も有力なものが１９７７年にリヴェスト
(Rivest)、シャミア(Shamir)およびエイドルマン(Adlma
n)の３人によって発明されたＲＳＡ暗号である。ＲＳＡ
暗号の基本原理は次のようなものである。
【００１０】〈ＲＳＡの基本アルゴリズム〉暗号鍵
（ｅ，Ｎ）と対応する復号鍵（ｄ，Ｎ）で、ｅとＮは公
開鍵であり、ｄは秘密鍵である。平文をＭ、暗号文をＣ
とすると、暗号化Ｅと複合化Ｄのアルゴリズムは次のよ
うにあらわされる。 Ｃ＝Ｅ（Ｍ）＝ＭemodＮ Ｍ＝Ｄ（Ｃ）＝ＣdmodＮ 但し、ｄ・ｅ＝１modＬＣＭ｛（ｐ−１），（ｑ−
１）｝ Ｎ＝ｐ・ｑ ＬＣＭ：最小公倍数[lowest common multiple]；ｐ、ｑ
は大きな素数 である。
（ｅ，Ｎ）と対応する復号鍵（ｄ，Ｎ）で、ｅとＮは公
開鍵であり、ｄは秘密鍵である。平文をＭ、暗号文をＣ
とすると、暗号化Ｅと複合化Ｄのアルゴリズムは次のよ
うにあらわされる。 Ｃ＝Ｅ（Ｍ）＝ＭemodＮ Ｍ＝Ｄ（Ｃ）＝ＣdmodＮ 但し、ｄ・ｅ＝１modＬＣＭ｛（ｐ−１），（ｑ−
１）｝ Ｎ＝ｐ・ｑ ＬＣＭ：最小公倍数[lowest common multiple]；ｐ、ｑ
は大きな素数 である。
【００１１】通常、ｅ、ｄ、Ｎ、Ｍなどは５１２ビット
程度の大きな整数が用いられるので、高速指数計算法を
使用しても１回のＲＳＡ演算で平均７７０回程度の乗算
と剰余演算を行わなければならない。特に剰余演算は、
近似法や剰余テーブル方式、モンゴメリのアルゴリズム
等、多くの高速化手法が提案されている。このような、
ＲＳＡ暗号に代表される公開鍵暗号系の多くで利用され
る、べき乗剰余アルゴリズムを高速に処理するために
は、１回あたりの剰余アルゴリズムの高速化が要求され
る。
程度の大きな整数が用いられるので、高速指数計算法を
使用しても１回のＲＳＡ演算で平均７７０回程度の乗算
と剰余演算を行わなければならない。特に剰余演算は、
近似法や剰余テーブル方式、モンゴメリのアルゴリズム
等、多くの高速化手法が提案されている。このような、
ＲＳＡ暗号に代表される公開鍵暗号系の多くで利用され
る、べき乗剰余アルゴリズムを高速に処理するために
は、１回あたりの剰余アルゴリズムの高速化が要求され
る。
【００１２】この剰余演算の高速化の実現の一方法であ
るモンゴメリのアルゴリズムについて説明する。 〈モンゴメリのアルゴリズム〉モンゴメリのアルゴリズ
ムは、剰余の法Ｎ（Ｎ＞１）と、剰余の法Ｎと互いに素
である基数Ｒ（Ｒ＞Ｎ）を用いると、被剰余数ＴからＴ
Ｒ-1modＮの計算が基数Ｒによる除算のみで行えること
を利用して、Ｎによる除算を用いることなく剰余計算を
行うアルゴリズムである。ここで、Ｎ、Ｎ′、Ｒ、Ｒ-1
およびＴは整数であり、被剰余数Ｔは０≦Ｔ＜ＲＮ、Ｒ
-1は剰余の法Ｎの上での基数Ｒの逆数であり、ＲＲ-1−
ＮＮ′＝１（０≦Ｒ-1＜Ｎ，０≦Ｎ′＜Ｒ）の関係を満
たす。
るモンゴメリのアルゴリズムについて説明する。 〈モンゴメリのアルゴリズム〉モンゴメリのアルゴリズ
ムは、剰余の法Ｎ（Ｎ＞１）と、剰余の法Ｎと互いに素
である基数Ｒ（Ｒ＞Ｎ）を用いると、被剰余数ＴからＴ
Ｒ-1modＮの計算が基数Ｒによる除算のみで行えること
を利用して、Ｎによる除算を用いることなく剰余計算を
行うアルゴリズムである。ここで、Ｎ、Ｎ′、Ｒ、Ｒ-1
およびＴは整数であり、被剰余数Ｔは０≦Ｔ＜ＲＮ、Ｒ
-1は剰余の法Ｎの上での基数Ｒの逆数であり、ＲＲ-1−
ＮＮ′＝１（０≦Ｒ-1＜Ｎ，０≦Ｎ′＜Ｒ）の関係を満
たす。
【００１３】さらにこの基数Ｒに２のベキ乗数を使用し
た場合、基数Ｒによる除算をシフト操作に置き換えるこ
とができるため、Ｔ→ＴＲ-1modＮの計算の高速処理が
可能となる。次にアルゴリズム１として、Ｔ→ＴＲ-1mo
dＮのアルゴリズムＲＥＤＣ（Ｔ）を示す。但し、アル
ゴリズム１において（Ｔ＋ｍＮ）／Ｒは必ず割り切れ
る。
た場合、基数Ｒによる除算をシフト操作に置き換えるこ
とができるため、Ｔ→ＴＲ-1modＮの計算の高速処理が
可能となる。次にアルゴリズム１として、Ｔ→ＴＲ-1mo
dＮのアルゴリズムＲＥＤＣ（Ｔ）を示す。但し、アル
ゴリズム１において（Ｔ＋ｍＮ）／Ｒは必ず割り切れ
る。
【００１４】〈アルゴリズム１〉Ｔ→ＴＲ-1modＮのア
ルゴリズムＲＥＤＣ（Ｔ）は次のようにあらわされる。 ｍ＝（ＴmodＲ）Ｎ′modＲ ｔ＝（Ｔ＋ｍＮ）／Ｒ if ｔ＜Ｎ then return ｔ else return ｔ−Ｎ すなわち、 ＲＥＤＣ（Ｔ）＝ｔ （ｔ＜Ｎ） ＝ｔ−Ｎ （ｔ≧Ｎ） である。
ルゴリズムＲＥＤＣ（Ｔ）は次のようにあらわされる。 ｍ＝（ＴmodＲ）Ｎ′modＲ ｔ＝（Ｔ＋ｍＮ）／Ｒ if ｔ＜Ｎ then return ｔ else return ｔ−Ｎ すなわち、 ＲＥＤＣ（Ｔ）＝ｔ （ｔ＜Ｎ） ＝ｔ−Ｎ （ｔ≧Ｎ） である。
【００１５】１回のＲＥＤＣでは、剰余ＴmodＮではな
くＴＲ-1modＮが求められるだけである。そこで、剰余
ＴmodＮを求めるためには、次に示すようにＲＥＤＣ
（Ｔ）と予め求めておいたＲ2modＮとの積で、再びＲＥ
ＤＣを行えばよい。 ＲＥＤＣ（ＲＥＤＣ（Ｔ）＊（Ｒ2modＮ）） ＝（ＴＲ-1modＮ）（Ｒ2modＮ）Ｒ-1modＮ ＝ＴＲ-1＊Ｒ2＊Ｒ-1modＮ ＝ＴmodＮ このようにして、剰余ＴmodＮを求めることができる。
くＴＲ-1modＮが求められるだけである。そこで、剰余
ＴmodＮを求めるためには、次に示すようにＲＥＤＣ
（Ｔ）と予め求めておいたＲ2modＮとの積で、再びＲＥ
ＤＣを行えばよい。 ＲＥＤＣ（ＲＥＤＣ（Ｔ）＊（Ｒ2modＮ）） ＝（ＴＲ-1modＮ）（Ｒ2modＮ）Ｒ-1modＮ ＝ＴＲ-1＊Ｒ2＊Ｒ-1modＮ ＝ＴmodＮ このようにして、剰余ＴmodＮを求めることができる。
【００１６】〈ＲＥＤＣの多重精度計算への拡張〉次
に、剰余の法Ｎあるいは基数Ｒが多倍長すなわち多重精
度の場合について、ＲＥＤＣのアルゴリズムを拡張す
る。剰余の法Ｎや基数Ｒが多重精度の場合、ＲＥＤＣの
（ＴmodＲ）Ｎ′やｍＮの計算は、多重精度×多重精度
の処理となり汎用の計算機では非常に大きな処理量と処
理時間が必要となる。そこで、この部分を多重精度×単
精度の処理で行えるように拡張したアルゴリズム２を示
す。
に、剰余の法Ｎあるいは基数Ｒが多倍長すなわち多重精
度の場合について、ＲＥＤＣのアルゴリズムを拡張す
る。剰余の法Ｎや基数Ｒが多重精度の場合、ＲＥＤＣの
（ＴmodＲ）Ｎ′やｍＮの計算は、多重精度×多重精度
の処理となり汎用の計算機では非常に大きな処理量と処
理時間が必要となる。そこで、この部分を多重精度×単
精度の処理で行えるように拡張したアルゴリズム２を示
す。
【００１７】〈アルゴリズム２〉ＲＥＤＣを多重精度へ
拡張したアルゴリズムは次に示すようになる。被剰余数
Ｔがｂ進数でＴ＝（Ｔ2n-1Ｔ2n-2…Ｔ0）b、Ｒ＝ｂn、
ｂ＝２kとあらわされる場合、次に示すｉ＝０〜ｎ−１
の繰り返し処理によりＴＲ-1modＮを単倍長と同様にし
て求めることができる。
拡張したアルゴリズムは次に示すようになる。被剰余数
Ｔがｂ進数でＴ＝（Ｔ2n-1Ｔ2n-2…Ｔ0）b、Ｒ＝ｂn、
ｂ＝２kとあらわされる場合、次に示すｉ＝０〜ｎ−１
の繰り返し処理によりＴＲ-1modＮを単倍長と同様にし
て求めることができる。
【００１８】 このようにして得られるＴＲ-1modＮと、上述したよう
に予め求めておいたＲ2modＮとの積で再びＲＥＤＣを行
うことにより求める剰余ＴmodＮを求めることができ
る。
に予め求めておいたＲ2modＮとの積で再びＲＥＤＣを行
うことにより求める剰余ＴmodＮを求めることができ
る。
【００１９】
【発明が解決しようとする課題】上述したモンゴメリの
アルゴリズムは、基数Ｒを２のべき乗数にすることによ
り、処理時間のかかる割り算を高速なシフト処理に置き
換えることが可能であるため剰余計算を高速で行うこと
ができる。しかし、このモンゴメリのアルゴリズムを用
いた演算を高速で行おうとすると、多重精度の処理は、
多重精度×単精度の乗算処理が必要となるため、大量の
処理が必要となる。
アルゴリズムは、基数Ｒを２のべき乗数にすることによ
り、処理時間のかかる割り算を高速なシフト処理に置き
換えることが可能であるため剰余計算を高速で行うこと
ができる。しかし、このモンゴメリのアルゴリズムを用
いた演算を高速で行おうとすると、多重精度の処理は、
多重精度×単精度の乗算処理が必要となるため、大量の
処理が必要となる。
【００２０】また、べき乗剰余などの演算をこのアルゴ
リズムを用いて行う場合、剰余演算が何度も繰り返され
ることになるため、剰余演算の処理回数の多い部分をで
きるだけ単純化することで全体の計算量を削減し、処理
速度の向上を図る必要がある。また、モンゴメリ法特有
のＮ′およびＲ2modＮ等の事前に計算しておかなければ
ならないパラメータの計算が前処理として必要である。
特に、Ｎ′は、拡張ユークリッドの互除法を使用するた
め、Ｒ2modＮよりも多くの処理時間を必要とする。
リズムを用いて行う場合、剰余演算が何度も繰り返され
ることになるため、剰余演算の処理回数の多い部分をで
きるだけ単純化することで全体の計算量を削減し、処理
速度の向上を図る必要がある。また、モンゴメリ法特有
のＮ′およびＲ2modＮ等の事前に計算しておかなければ
ならないパラメータの計算が前処理として必要である。
特に、Ｎ′は、拡張ユークリッドの互除法を使用するた
め、Ｒ2modＮよりも多くの処理時間を必要とする。
【００２１】したがって、本発明は、剰余計算に際し多
重の繰り返し演算を必要とする倍数演算部分に着目して
剰余計算の演算処理を簡略化し、高速処理を実現し得る
剰余計算装置および乗算剰余計算装置を提供することを
目的としている。本発明の他の目的は、本発明による剰
余計算装置および乗算剰余計算装置に用いるための倍数
テーブルを容易に作成することのできるテーブル作成装
置を提供することにある。
重の繰り返し演算を必要とする倍数演算部分に着目して
剰余計算の演算処理を簡略化し、高速処理を実現し得る
剰余計算装置および乗算剰余計算装置を提供することを
目的としている。本発明の他の目的は、本発明による剰
余計算装置および乗算剰余計算装置に用いるための倍数
テーブルを容易に作成することのできるテーブル作成装
置を提供することにある。
【００２２】
【課題を解決するための手段】本発明は、上記目的を達
成するために、多重の繰り返し演算を必要とする倍数演
算部分にテーブルを用い、演算結果をテーブル検索によ
り得るようにして、演算処理を簡略化して高速化するこ
とにより、剰余計算を高速処理し得る次のような構成の
剰余計算装置とした。
成するために、多重の繰り返し演算を必要とする倍数演
算部分にテーブルを用い、演算結果をテーブル検索によ
り得るようにして、演算処理を簡略化して高速化するこ
とにより、剰余計算を高速処理し得る次のような構成の
剰余計算装置とした。
【００２３】図１は、本発明の基本となる剰余計算装置
の原理を示している。図１に示す剰余計算装置は、入力
レジスタ１、倍数算定部２、加算器３および補正装置４
を有している。入力レジスタ１は入力される被剰余数Ｔ
を保持する。倍数算定部２は、入力レジスタ１の下位所
定ビットに対応して剰余の法Ｎの倍数が格納された倍数
テーブル５を有し、入力レジスタ１の被剰余数Ｔの下位
所定ビットに基づいて倍数テーブル５を検索することに
より、前記Ｔの下位所定ビットに対応する剰余の法Ｎの
倍数を求める。加算器３は、倍数算定部２で求められる
剰余の法Ｎの倍数と入力レジスタ１の内容とを加算す
る。この加算器３の所定回数ｎの加算について、加算器
３の加算結果の上位所定ビットで入力レジスタ１の内容
を更新する。補正装置４は、加算器３の加算結果として
得られるｔに対して補正処理を施す。
の原理を示している。図１に示す剰余計算装置は、入力
レジスタ１、倍数算定部２、加算器３および補正装置４
を有している。入力レジスタ１は入力される被剰余数Ｔ
を保持する。倍数算定部２は、入力レジスタ１の下位所
定ビットに対応して剰余の法Ｎの倍数が格納された倍数
テーブル５を有し、入力レジスタ１の被剰余数Ｔの下位
所定ビットに基づいて倍数テーブル５を検索することに
より、前記Ｔの下位所定ビットに対応する剰余の法Ｎの
倍数を求める。加算器３は、倍数算定部２で求められる
剰余の法Ｎの倍数と入力レジスタ１の内容とを加算す
る。この加算器３の所定回数ｎの加算について、加算器
３の加算結果の上位所定ビットで入力レジスタ１の内容
を更新する。補正装置４は、加算器３の加算結果として
得られるｔに対して補正処理を施す。
【００２４】このような剰余計算装置は、ｎ回の繰り返
し演算の必要な倍数算定部２に倍数テーブル５を用いて
高速に倍数を求めることができるので、剰余計算を高速
に処理することができる。図１の剰余計算装置において
は、具体的には、先に述べたモンゴメリのアルゴリズム
における被剰余数Ｔが入力レジスタ１に格納され、倍数
算定部２において剰余の法Ｎの倍数ｍ′Ｎ（但し、ｍ′
＝（Ｔmodｂ）Ｎ′modｂ、ここでＮ′およびＲは整数で
あり、Ｒ＝ｂn、ｂ＝２kとする）が格納された倍数テー
ブル５を検索して、前記被剰余数Ｔの下位ｋビットに対
応する剰余の法Ｎの倍数ｍ′Ｎが求められる。この倍数
ｍ′Ｎと前記被剰余数Ｔが加算され、その加算結果によ
り入力レジスタ１の内容が更新される。このような処理
がｎ回繰り返され、加算器３の出力にｔ＝（Ｔ＋ｍＮ）
／Ｒが得られる。この加算器３の出力ｔは、補正装置４
に与えられ、ｔ＜Ｎの場合はそのままｔ＝ＲＥＤＣ
（Ｔ）、ｔ≧Ｎの場合はｔ−Ｎ＝ＲＥＤＣ（Ｔ）とし
て、ＴＲ-1modＮが得られる。
し演算の必要な倍数算定部２に倍数テーブル５を用いて
高速に倍数を求めることができるので、剰余計算を高速
に処理することができる。図１の剰余計算装置において
は、具体的には、先に述べたモンゴメリのアルゴリズム
における被剰余数Ｔが入力レジスタ１に格納され、倍数
算定部２において剰余の法Ｎの倍数ｍ′Ｎ（但し、ｍ′
＝（Ｔmodｂ）Ｎ′modｂ、ここでＮ′およびＲは整数で
あり、Ｒ＝ｂn、ｂ＝２kとする）が格納された倍数テー
ブル５を検索して、前記被剰余数Ｔの下位ｋビットに対
応する剰余の法Ｎの倍数ｍ′Ｎが求められる。この倍数
ｍ′Ｎと前記被剰余数Ｔが加算され、その加算結果によ
り入力レジスタ１の内容が更新される。このような処理
がｎ回繰り返され、加算器３の出力にｔ＝（Ｔ＋ｍＮ）
／Ｒが得られる。この加算器３の出力ｔは、補正装置４
に与えられ、ｔ＜Ｎの場合はそのままｔ＝ＲＥＤＣ
（Ｔ）、ｔ≧Ｎの場合はｔ−Ｎ＝ＲＥＤＣ（Ｔ）とし
て、ＴＲ-1modＮが得られる。
【００２５】上述の倍数テーブル５を作成するテーブル
作成装置は、繰り返し加算部、補数算定部およびテーブ
ル書き込み部を有する。繰り返し加算部は剰余の法Ｎを
繰り返し加算する。補数算定部は前記繰り返し加算部で
求められる各加算結果の値の下位ｂビットの２の補数を
求める。テーブル書き込み部は、テーブルの前記補数算
定部で得られる各補数値に対応するテーブルアドレスに
前記各加算結果をそれぞれ格納する。このテーブル作成
装置は、例えば同様の機能をソフトウェアにより実現す
るコンピュータにより構成することもできる。
作成装置は、繰り返し加算部、補数算定部およびテーブ
ル書き込み部を有する。繰り返し加算部は剰余の法Ｎを
繰り返し加算する。補数算定部は前記繰り返し加算部で
求められる各加算結果の値の下位ｂビットの２の補数を
求める。テーブル書き込み部は、テーブルの前記補数算
定部で得られる各補数値に対応するテーブルアドレスに
前記各加算結果をそれぞれ格納する。このテーブル作成
装置は、例えば同様の機能をソフトウェアにより実現す
るコンピュータにより構成することもできる。
【００２６】このようなテーブル作成装置により、計算
処理に多くの時間を必要とするＮ′を求めることなく記
憶装置上に倍数テーブルを作成することができる。ま
た、上述の倍数テーブル５は、多量のデータにより構成
されることになり、倍数テーブル５を構成する記憶装置
に多くの記憶容量を必要とするので、倍数テーブル５を
用いる倍数算定部２に代えて、被剰余数Ｔの下位所定ビ
ットに対応させて倍数情報ｍ′を格納する倍数情報テー
ブルを用い、この倍数情報テーブルを前記被剰余数Ｔの
下位所定ビットで検索して、それに対応する倍数情報
ｍ′を求める倍数情報算定部と、剰余の法Ｎを格納する
剰余の法レジスタと、前記倍数情報算定部で得られる倍
数情報ｍ′と前記剰余の法レジスタから得られる剰余の
法Ｎとを乗算する乗算器とを有する倍数算定部を設ける
構成としてもよい。この場合、前記倍数算定部により前
記被剰余数の下位所定ビットに対応する前記剰余の法Ｎ
の倍数ｍ′Ｎを求める。この場合、計算速度は、倍数テ
ーブル５を用いる場合よりも遅くなるが、倍数情報テー
ブルは倍数テーブル５に比して少ない記憶容量で済む。
処理に多くの時間を必要とするＮ′を求めることなく記
憶装置上に倍数テーブルを作成することができる。ま
た、上述の倍数テーブル５は、多量のデータにより構成
されることになり、倍数テーブル５を構成する記憶装置
に多くの記憶容量を必要とするので、倍数テーブル５を
用いる倍数算定部２に代えて、被剰余数Ｔの下位所定ビ
ットに対応させて倍数情報ｍ′を格納する倍数情報テー
ブルを用い、この倍数情報テーブルを前記被剰余数Ｔの
下位所定ビットで検索して、それに対応する倍数情報
ｍ′を求める倍数情報算定部と、剰余の法Ｎを格納する
剰余の法レジスタと、前記倍数情報算定部で得られる倍
数情報ｍ′と前記剰余の法レジスタから得られる剰余の
法Ｎとを乗算する乗算器とを有する倍数算定部を設ける
構成としてもよい。この場合、前記倍数算定部により前
記被剰余数の下位所定ビットに対応する前記剰余の法Ｎ
の倍数ｍ′Ｎを求める。この場合、計算速度は、倍数テ
ーブル５を用いる場合よりも遅くなるが、倍数情報テー
ブルは倍数テーブル５に比して少ない記憶容量で済む。
【００２７】さらに、乗算剰余計算装置は、上述した剰
余計算装置と同様の構成に加えて、被乗数に対し所定ビ
ット毎に乗数との乗算を行い行う分割乗算装置を設け、
この分割乗算装置の出力を上述した剰余計算装置の入力
レジスタに与えるとともに、前記剰余計算装置の加算器
の出力を前記分割乗算装置の乗算結果に加算する構成と
して、乗算剰余の計算を高速に行う。
余計算装置と同様の構成に加えて、被乗数に対し所定ビ
ット毎に乗数との乗算を行い行う分割乗算装置を設け、
この分割乗算装置の出力を上述した剰余計算装置の入力
レジスタに与えるとともに、前記剰余計算装置の加算器
の出力を前記分割乗算装置の乗算結果に加算する構成と
して、乗算剰余の計算を高速に行う。
【００２８】
【作用】本発明による剰余計算装置では、剰余計算にお
いて、ループによる多数回の繰り返し演算が必要な倍数
算定部２に、入力レジスタ１の保持値の下位所定ビット
に基づくテーブル検索を用いて高速に処理することによ
り、高速剰余計算が行われる。特に、倍数算定部２に倍
数テーブル５を用いて、倍数算定部２の機能をすべてテ
ーブル検索により処理すれば、処理速度が顕著に向上す
る。
いて、ループによる多数回の繰り返し演算が必要な倍数
算定部２に、入力レジスタ１の保持値の下位所定ビット
に基づくテーブル検索を用いて高速に処理することによ
り、高速剰余計算が行われる。特に、倍数算定部２に倍
数テーブル５を用いて、倍数算定部２の機能をすべてテ
ーブル検索により処理すれば、処理速度が顕著に向上す
る。
【００２９】本発明によるテーブル作成装置では、倍数
算定部２に用いる倍数テーブル５を作成するのに、剰余
の法を繰り返し加算し、加算結果の下位所定ビットの２
の補数を求め、その２の補数値に対応するアドレスに前
記加算結果を格納することにより、煩雑な計算を要する
パラメータＮ′を求めることなく倍数テーブル５を作成
することができる。
算定部２に用いる倍数テーブル５を作成するのに、剰余
の法を繰り返し加算し、加算結果の下位所定ビットの２
の補数を求め、その２の補数値に対応するアドレスに前
記加算結果を格納することにより、煩雑な計算を要する
パラメータＮ′を求めることなく倍数テーブル５を作成
することができる。
【００３０】本発明による乗算剰余計算装置では、剰余
計算における繰り返し処理の部分にテーブルを用いて、
効率よく剰余計算処理を高速化し、乗算剰余計算を処理
速度を向上させる。
計算における繰り返し処理の部分にテーブルを用いて、
効率よく剰余計算処理を高速化し、乗算剰余計算を処理
速度を向上させる。
【００３１】
〈実施例１〉本発明に係る剰余計算装置の第１の実施例
の説明に先立ち、本発明における剰余計算処理の原理を
詳細に説明する。上述したモンゴメリのアルゴリズムを
利用して、ハードウェアにより剰余計算装置を構成する
と、一般的には図８のようになると考えられる。図８の
構成は、先に述べた多重精度のアルゴリズムをそのまま
ハードウェアで実現したものである。
の説明に先立ち、本発明における剰余計算処理の原理を
詳細に説明する。上述したモンゴメリのアルゴリズムを
利用して、ハードウェアにより剰余計算装置を構成する
と、一般的には図８のようになると考えられる。図８の
構成は、先に述べた多重精度のアルゴリズムをそのまま
ハードウェアで実現したものである。
【００３２】図８の剰余計算装置は、先に述べた通り、
Ｒ＝ｂn、ｂ＝２kとして、Ｔ→ＴＲ -1modＮの処理を行
うものとし、Ｔレジスタ１１、Ｎレジスタ１２、Ｎ′レ
ジスタ１３、第１の乗算器１４、第２の乗算器１５、第
１の加算器１６、第１のレジスタ１７、−Ｎレジスタ１
８、第２の加算器１９、第２のレジスタ２０およびセレ
クタ２１を具備する。
Ｒ＝ｂn、ｂ＝２kとして、Ｔ→ＴＲ -1modＮの処理を行
うものとし、Ｔレジスタ１１、Ｎレジスタ１２、Ｎ′レ
ジスタ１３、第１の乗算器１４、第２の乗算器１５、第
１の加算器１６、第１のレジスタ１７、−Ｎレジスタ１
８、第２の加算器１９、第２のレジスタ２０およびセレ
クタ２１を具備する。
【００３３】第１のレジスタ１７、−Ｎレジスタ１８、
第２の加算器１９、第２のレジスタ２０およびセレクタ
２１は、補正装置２２を構成する。Ｎ′レジスタ１３お
よび第２の乗算器１５からなる部分は倍数情報算定部３
１を構成し、この倍数情報算定部３１、Ｎレジスタ１２
および第１の乗算器１４からなる部分は倍数算定部３２
を構成する。
第２の加算器１９、第２のレジスタ２０およびセレクタ
２１は、補正装置２２を構成する。Ｎ′レジスタ１３お
よび第２の乗算器１５からなる部分は倍数情報算定部３
１を構成し、この倍数情報算定部３１、Ｎレジスタ１２
および第１の乗算器１４からなる部分は倍数算定部３２
を構成する。
【００３４】ここで、剰余の法Ｎをａビット、入力値を
ａ＋ｎｋビットと仮定して、上述の剰余計算装置につい
て説明する。Ｔレジスタ１１は、図１における入力レジ
スタ１に相当し、入力される被剰余数Ｔを保持する。Ｎ
レジスタ１２およびＮ′レジスタ１３は、共にａビット
のレジスタであり、与えられる剰余の法Ｎおよび先に述
べたＮ′をそれぞれ保持する。第２の乗算器１５は、Ｔ
レジスタ１１の保持値の下位ｋビットとＮ′レジスタ１
３の下位ｋビットとを乗算する。第１の乗算器１４は、
Ｎレジスタ１２の保持値と第２の乗算器１５の乗算結果
の下位ｋビットとを乗算する。
ａ＋ｎｋビットと仮定して、上述の剰余計算装置につい
て説明する。Ｔレジスタ１１は、図１における入力レジ
スタ１に相当し、入力される被剰余数Ｔを保持する。Ｎ
レジスタ１２およびＮ′レジスタ１３は、共にａビット
のレジスタであり、与えられる剰余の法Ｎおよび先に述
べたＮ′をそれぞれ保持する。第２の乗算器１５は、Ｔ
レジスタ１１の保持値の下位ｋビットとＮ′レジスタ１
３の下位ｋビットとを乗算する。第１の乗算器１４は、
Ｎレジスタ１２の保持値と第２の乗算器１５の乗算結果
の下位ｋビットとを乗算する。
【００３５】第１の加算器１６は、Ｔレジスタ１１の保
持値（ａ＋ｎｋビット）と第１の乗算器１４の乗算結果
（ａ＋ｋビット）とを加算する。第１の加算器１６の加
算結果（ａ＋ｎｋ＋１ビット）の上位ａ＋（ｎ−１）ｋ
＋１ビットはＴレジスタ１１の内容を更新してｎ回のル
ープ処理を行うのに用いられる。第１のレジスタ１７
は、第１の加算器１６の加算結果の下位ｋビットを超え
る部分の下位ａ＋１ビットを保持し、−Ｎレジスタ１８
は、予め与えられる剰余の法Ｎに基づく−Ｎの値（ａ＋
１ビット）を保持する。第２の加算器１９は、第１のレ
ジスタ１７の保持値と−Ｎレジスタ１８の保持値とを加
算して、第２のレジスタ２０に保持させる。セレクタ２
１は、第２のレジスタ２０のａ＋１ビットの保持値の最
上位の１ビット（符号ビットに相当する）の値を条件と
して動作し、該最上位ビットが“１”の場合は第１のレ
ジスタ１７の保持値を出力し、“０”の場合は第２のレ
ジスタ２０の保持値を出力する。
持値（ａ＋ｎｋビット）と第１の乗算器１４の乗算結果
（ａ＋ｋビット）とを加算する。第１の加算器１６の加
算結果（ａ＋ｎｋ＋１ビット）の上位ａ＋（ｎ−１）ｋ
＋１ビットはＴレジスタ１１の内容を更新してｎ回のル
ープ処理を行うのに用いられる。第１のレジスタ１７
は、第１の加算器１６の加算結果の下位ｋビットを超え
る部分の下位ａ＋１ビットを保持し、−Ｎレジスタ１８
は、予め与えられる剰余の法Ｎに基づく−Ｎの値（ａ＋
１ビット）を保持する。第２の加算器１９は、第１のレ
ジスタ１７の保持値と−Ｎレジスタ１８の保持値とを加
算して、第２のレジスタ２０に保持させる。セレクタ２
１は、第２のレジスタ２０のａ＋１ビットの保持値の最
上位の１ビット（符号ビットに相当する）の値を条件と
して動作し、該最上位ビットが“１”の場合は第１のレ
ジスタ１７の保持値を出力し、“０”の場合は第２のレ
ジスタ２０の保持値を出力する。
【００３６】すなわち、剰余計算を行う場合、前処理と
して事前に計算して求めておいたＮ、Ｎ′および−Ｎ
を、Ｎレジスタ、Ｎ′レジスタおよび−Ｎレジスタにそ
れぞれ設定する。入力被剰余数Ｔは、まずＴレジスタ１
１に与えられる。このＴレジスタ１１の保持値の下位ｋ
ビットとＮ′レジスタ１３の保持値の下位ｋビットとを
第２の乗算器１５に入力する。第２の乗算器１５の乗算
結果の下位ｋビットとＮレジスタ１２の保持値を第１の
乗算器１４に入力し、その乗算結果とＴレジスタ１１の
保持値とを第１の加算器１６に入力する。Ｔレジスタ１
１と第１の加算器１６との間のループ処理の回数がｎ未
満の場合は、第１の加算器１６の加算結果の上位ａ＋
（ｎ−１）ｋ＋１ビットを再びＴレジスタ１１に入力す
る。ループ処理の回数がｎに達した場合は、第１の加算
器１６の加算結果の下位ｋ＋１ビット目から下位ａ＋ｋ
＋２ビット目までのａ＋１ビットを取り出し、補正装置
２２の第１のレジスタ１７に入力する。
して事前に計算して求めておいたＮ、Ｎ′および−Ｎ
を、Ｎレジスタ、Ｎ′レジスタおよび−Ｎレジスタにそ
れぞれ設定する。入力被剰余数Ｔは、まずＴレジスタ１
１に与えられる。このＴレジスタ１１の保持値の下位ｋ
ビットとＮ′レジスタ１３の保持値の下位ｋビットとを
第２の乗算器１５に入力する。第２の乗算器１５の乗算
結果の下位ｋビットとＮレジスタ１２の保持値を第１の
乗算器１４に入力し、その乗算結果とＴレジスタ１１の
保持値とを第１の加算器１６に入力する。Ｔレジスタ１
１と第１の加算器１６との間のループ処理の回数がｎ未
満の場合は、第１の加算器１６の加算結果の上位ａ＋
（ｎ−１）ｋ＋１ビットを再びＴレジスタ１１に入力す
る。ループ処理の回数がｎに達した場合は、第１の加算
器１６の加算結果の下位ｋ＋１ビット目から下位ａ＋ｋ
＋２ビット目までのａ＋１ビットを取り出し、補正装置
２２の第１のレジスタ１７に入力する。
【００３７】補正装置２２では、入力を一旦第１のレジ
スタ１７に保持し、その保持値と−Ｎレジスタ１８の保
持値とを第２の加算器１９に入力し、加算結果を第２の
レジスタ２０に与える。第２のレジスタ２０の上位１ビ
ットの値をセレクタ２１の動作条件として、“１”の場
合は第１のレジスタ１７の保持値が、“０”の場合は第
２のレジスタ２０の保持値がセレクタ２１で選択され、
結果として出力される。
スタ１７に保持し、その保持値と−Ｎレジスタ１８の保
持値とを第２の加算器１９に入力し、加算結果を第２の
レジスタ２０に与える。第２のレジスタ２０の上位１ビ
ットの値をセレクタ２１の動作条件として、“１”の場
合は第１のレジスタ１７の保持値が、“０”の場合は第
２のレジスタ２０の保持値がセレクタ２１で選択され、
結果として出力される。
【００３８】ここで、補正装置２２における処理は、モ
ンゴメリのアルゴリズムで最後に計算値ｔがＮ以上の場
合にはＮを引く部分の処理である。この図８のような構
成の場合、倍数算定部３２の部分は何度も同じ処理を繰
り返されることになる。さらにこの構成をべき乗剰余演
算に用いた場合はこれらの処理全体が繰り返されるた
め、倍数算定部３２の部分の処理回数は非常に多くな
る。
ンゴメリのアルゴリズムで最後に計算値ｔがＮ以上の場
合にはＮを引く部分の処理である。この図８のような構
成の場合、倍数算定部３２の部分は何度も同じ処理を繰
り返されることになる。さらにこの構成をべき乗剰余演
算に用いた場合はこれらの処理全体が繰り返されるた
め、倍数算定部３２の部分の処理回数は非常に多くな
る。
【００３９】一方、倍数算定部３２の処理自体は、乗算
という処理量の大きな演算が中心であり、さらに計算内
容がＮという多重精度の定数とｋビットの変数との積で
あるため処理回数の多さとあいまって、長い処理時間が
必要となる。そこで、本発明の第１の実施例では、図８
における倍数情報算定部３１の部分をｋビット×２kの
大きさの倍数情報テーブルとして持っておくことによ
り、無駄な計算を省き、処理を高速化する。
という処理量の大きな演算が中心であり、さらに計算内
容がＮという多重精度の定数とｋビットの変数との積で
あるため処理回数の多さとあいまって、長い処理時間が
必要となる。そこで、本発明の第１の実施例では、図８
における倍数情報算定部３１の部分をｋビット×２kの
大きさの倍数情報テーブルとして持っておくことによ
り、無駄な計算を省き、処理を高速化する。
【００４０】本発明に係る剰余計算装置の第１の実施例
を説明する。なお、以下の各実施例においては、説明の
便宜のためビット数をａ＝５１２、ｋ＝８、ｎ＝６４と
して説明する。図２は、倍数情報テーブル方式を用いた
剰余計算装置の構成を示している。図２において、図８
と共通の部分には同符号を付してその詳細な説明を省略
する。図２の剰余計算装置は、図８と同様の、Ｔレジス
タ１１、Ｎレジスタ１２、第１の乗算器１４、第１の加
算器１６および補正装置２２を具備する。補正装置２２
は、第１のレジスタ１７、−Ｎレジスタ１８、第２の加
算器１９、第２のレジスタ２０およびセレクタ２１を有
する。
を説明する。なお、以下の各実施例においては、説明の
便宜のためビット数をａ＝５１２、ｋ＝８、ｎ＝６４と
して説明する。図２は、倍数情報テーブル方式を用いた
剰余計算装置の構成を示している。図２において、図８
と共通の部分には同符号を付してその詳細な説明を省略
する。図２の剰余計算装置は、図８と同様の、Ｔレジス
タ１１、Ｎレジスタ１２、第１の乗算器１４、第１の加
算器１６および補正装置２２を具備する。補正装置２２
は、第１のレジスタ１７、−Ｎレジスタ１８、第２の加
算器１９、第２のレジスタ２０およびセレクタ２１を有
する。
【００４１】さらに、図２の剰余計算装置においては、
図８における倍数情報算定部３１に代えて、倍数情報テ
ーブル４１を備えた倍数情報算定部４２を設けている。
倍数情報テーブル４１は、被剰余数Ｔの下位所定ビット
に対応して倍数情報ｍ′を格納している。Ｔレジスタ１
１は、１０２４ビットの入力レジスタであり、このＴレ
ジスタ１１には、被剰余数Ｔおよび第１の加算器１６の
出力ループが再び入力される。倍数情報テーブル４１
は、幅８ビット奥行き２５６のテーブルで、Ｔレジスタ
１１の下位８ビットで索引すると８ビットの倍数情報
ｍ′を出力する。Ｎレジスタ１２は、剰余の法Ｎを格納
する５１２ビットのレジスタである。
図８における倍数情報算定部３１に代えて、倍数情報テ
ーブル４１を備えた倍数情報算定部４２を設けている。
倍数情報テーブル４１は、被剰余数Ｔの下位所定ビット
に対応して倍数情報ｍ′を格納している。Ｔレジスタ１
１は、１０２４ビットの入力レジスタであり、このＴレ
ジスタ１１には、被剰余数Ｔおよび第１の加算器１６の
出力ループが再び入力される。倍数情報テーブル４１
は、幅８ビット奥行き２５６のテーブルで、Ｔレジスタ
１１の下位８ビットで索引すると８ビットの倍数情報
ｍ′を出力する。Ｎレジスタ１２は、剰余の法Ｎを格納
する５１２ビットのレジスタである。
【００４２】第１の乗算器１４は、８ビット×５１２ビ
ットの乗算器であり、倍数情報テーブル４１の索引結果
とＮレジスタ１２の保持値との乗算を行う。第１の加算
器１６は、１０２５ビットの加算器であり、Ｔレジスタ
１１の保持値と第１の乗算器１４の乗算結果との加算を
行う。補正装置２２は、図８の補正装置２２と同じもの
で剰余計算結果の補正を行う。
ットの乗算器であり、倍数情報テーブル４１の索引結果
とＮレジスタ１２の保持値との乗算を行う。第１の加算
器１６は、１０２５ビットの加算器であり、Ｔレジスタ
１１の保持値と第１の乗算器１４の乗算結果との加算を
行う。補正装置２２は、図８の補正装置２２と同じもの
で剰余計算結果の補正を行う。
【００４３】倍数情報算定部４２の倍数情報テーブル４
１は、図３に示すように予めＮ′の下位８ビットを加算
器により２５５回順次加算し、結果の下位８ビットを加
算回数をアドレスとしてテーブル化したものである。被
剰余数ＴがＴレジスタ１１に入力されると、その下位８
ビットで倍数情報テーブル４１の索引を行い、その索引
結果（＝ｍ′）とＮレジスタ１２の保持値Ｎを第１の乗
算器１４で乗算し、その積とＴレジスタ１１の保持値と
を第１の加算器１６で加算する。ループの回数ｎが６４
未満の場合は、第１の加算器１６の加算結果の上位１０
１８ビットを、再びＴレジスタ１１にＬＳＢ（leastsig
nificant bit）側からつめて入力し、処理ループを形成
する。ループの回数ｎが６４回目の場合は、第１の加算
器１６の加算結果の下位９ビット目から５１３ビットを
取り出して、補正装置２２の第１のレジスタ１７に入力
する。補正処理は図８の場合と同様である。
１は、図３に示すように予めＮ′の下位８ビットを加算
器により２５５回順次加算し、結果の下位８ビットを加
算回数をアドレスとしてテーブル化したものである。被
剰余数ＴがＴレジスタ１１に入力されると、その下位８
ビットで倍数情報テーブル４１の索引を行い、その索引
結果（＝ｍ′）とＮレジスタ１２の保持値Ｎを第１の乗
算器１４で乗算し、その積とＴレジスタ１１の保持値と
を第１の加算器１６で加算する。ループの回数ｎが６４
未満の場合は、第１の加算器１６の加算結果の上位１０
１８ビットを、再びＴレジスタ１１にＬＳＢ（leastsig
nificant bit）側からつめて入力し、処理ループを形成
する。ループの回数ｎが６４回目の場合は、第１の加算
器１６の加算結果の下位９ビット目から５１３ビットを
取り出して、補正装置２２の第１のレジスタ１７に入力
する。補正処理は図８の場合と同様である。
【００４４】このように、図２の剰余計算装置とすれ
ば、倍数情報の算定を倍数情報算定部４２でテーブル索
引により行うので、倍数情報の算定を高速に行うことが
でき、剰余計算の高速化を実現することができる。な
お、上述のように、図８における倍数情報算定部３１の
部分をテーブル化するよりも、図８における倍数算定部
３２の部分をテーブル化したほうが、当然高速化される
が、テーブルのサイズが大きくなるため、記憶装置に大
きなテーブルをとる余裕がない場合に倍数情報算定部３
１の部分のテーブル化を行うことにより、小規模の装置
構成でも高速化を実現することができる。
ば、倍数情報の算定を倍数情報算定部４２でテーブル索
引により行うので、倍数情報の算定を高速に行うことが
でき、剰余計算の高速化を実現することができる。な
お、上述のように、図８における倍数情報算定部３１の
部分をテーブル化するよりも、図８における倍数算定部
３２の部分をテーブル化したほうが、当然高速化される
が、テーブルのサイズが大きくなるため、記憶装置に大
きなテーブルをとる余裕がない場合に倍数情報算定部３
１の部分のテーブル化を行うことにより、小規模の装置
構成でも高速化を実現することができる。
【００４５】次に、図８における倍数算定部３２の部分
をテーブル化する場合の実施例を説明する。 〈実施例２〉本発明の第２の実施例では、図８における
倍数算定部３２の部分をａ＋ｋビット×２kの大きさの
倍数テーブルとして持っておくことにより、無駄な計算
を省き、処理を高速化する。以下、本発明の第２の実施
例に係る剰余計算装置を、図２または図８と同様の部分
には同符号を付して示す図４を参照して説明する。
をテーブル化する場合の実施例を説明する。 〈実施例２〉本発明の第２の実施例では、図８における
倍数算定部３２の部分をａ＋ｋビット×２kの大きさの
倍数テーブルとして持っておくことにより、無駄な計算
を省き、処理を高速化する。以下、本発明の第２の実施
例に係る剰余計算装置を、図２または図８と同様の部分
には同符号を付して示す図４を参照して説明する。
【００４６】図４に示す倍数テーブル方式を用いた剰余
計算装置は、図２と同様の、Ｔレジスタ１１、第１の加
算器１６および補正装置２２を具備する。さらに、図４
の剰余計算装置においては、図８における倍数算定部３
２に代えて、倍数テーブル５１を備えた倍数算定部５２
を設ける。倍数算定部５２の倍数テーブル５１は、被剰
余数Ｔの下位所定ビットに対応させて剰余の法Ｎの倍数
ｍ′Ｎを格納している。すなわち、倍数テーブル５１
は、図２の倍数情報テーブル４１、Ｎレジスタ１２およ
び第１の乗算器１４からなる部分の処理を一括してテー
ブル化したものであり、Ｔレジスタ１１の保持値の下位
８ビットで検索すると５２０ビットの倍数算定結果が出
力される。この倍数テーブル５１は、例えば後述する第
３の実施例のような倍数テーブル作成方法に従って、予
め幅５２０ビット奥行き２５６のテーブルとして作成す
る。
計算装置は、図２と同様の、Ｔレジスタ１１、第１の加
算器１６および補正装置２２を具備する。さらに、図４
の剰余計算装置においては、図８における倍数算定部３
２に代えて、倍数テーブル５１を備えた倍数算定部５２
を設ける。倍数算定部５２の倍数テーブル５１は、被剰
余数Ｔの下位所定ビットに対応させて剰余の法Ｎの倍数
ｍ′Ｎを格納している。すなわち、倍数テーブル５１
は、図２の倍数情報テーブル４１、Ｎレジスタ１２およ
び第１の乗算器１４からなる部分の処理を一括してテー
ブル化したものであり、Ｔレジスタ１１の保持値の下位
８ビットで検索すると５２０ビットの倍数算定結果が出
力される。この倍数テーブル５１は、例えば後述する第
３の実施例のような倍数テーブル作成方法に従って、予
め幅５２０ビット奥行き２５６のテーブルとして作成す
る。
【００４７】第１の実施例の場合と同様に被剰余数Ｔが
Ｔレジスタ１１に入力されると、Ｔレジスタ１１の下位
８ビットで倍数算定部５２の倍数テーブル５１を索引
し、その結果とＴレジスタ１１の値を第１の加算器１６
で加算する。第１の加算器１６の加算後の処理、つまり
Ｔレジスタ１１と第１の加算器１６との間の加算ループ
処理以後の処理は上述した第１の実施例と同様に行われ
る。
Ｔレジスタ１１に入力されると、Ｔレジスタ１１の下位
８ビットで倍数算定部５２の倍数テーブル５１を索引
し、その結果とＴレジスタ１１の値を第１の加算器１６
で加算する。第１の加算器１６の加算後の処理、つまり
Ｔレジスタ１１と第１の加算器１６との間の加算ループ
処理以後の処理は上述した第１の実施例と同様に行われ
る。
【００４８】このように、図４の剰余計算装置とすれ
ば、倍数算定を倍数算定部５２で、場数テーブル５１の
テーブル索引により行うので、倍数の算定を一層高速に
行うことができる。 〈実施例３〉本発明の第３の実施例は、上述した第２の
実施例による図４に示した剰余計算装置で用いるための
倍数テーブルを作成するためのテーブル作成装置であ
り、倍数テーブルを容易に作成することができる。
ば、倍数算定を倍数算定部５２で、場数テーブル５１の
テーブル索引により行うので、倍数の算定を一層高速に
行うことができる。 〈実施例３〉本発明の第３の実施例は、上述した第２の
実施例による図４に示した剰余計算装置で用いるための
倍数テーブルを作成するためのテーブル作成装置であ
り、倍数テーブルを容易に作成することができる。
【００４９】本発明の第３の実施例のテーブル作成装置
は、モンゴメリのアルゴリズムの剰余の法Ｎの倍数を入
力値Ｔに加えると、下位ｋビットが０となるという性質
を利用し、パラメータＮ′を直接使用することなく倍数
テーブルの作成を行う。図５にテーブル作成装置の構成
および作成される倍数テーブルの構成を模式的に示して
いる。
は、モンゴメリのアルゴリズムの剰余の法Ｎの倍数を入
力値Ｔに加えると、下位ｋビットが０となるという性質
を利用し、パラメータＮ′を直接使用することなく倍数
テーブルの作成を行う。図５にテーブル作成装置の構成
および作成される倍数テーブルの構成を模式的に示して
いる。
【００５０】テーブル作成装置は、Ｎレジスタ６１、加
算器６２、加算結果レジスタ６３および補数演算部６４
を有する。Ｎレジスタ６１は、剰余の法Ｎを保持し、こ
のＮレジスタ６１の保持値を加算器６２で繰り返し加算
する。この加算器６２の加算結果は加算結果レジスタ６
３に保持され、補数演算部６４は、加算結果レジスタ６
３の保持値の下位所定ビットの２の補数を求める。この
ような計算の結果、逐次、補数演算部６４で求められた
値をテーブルのアドレスとして、加算結果レジスタ６３
に保持された値を書き込んで、倍数テーブル５１とす
る。
算器６２、加算結果レジスタ６３および補数演算部６４
を有する。Ｎレジスタ６１は、剰余の法Ｎを保持し、こ
のＮレジスタ６１の保持値を加算器６２で繰り返し加算
する。この加算器６２の加算結果は加算結果レジスタ６
３に保持され、補数演算部６４は、加算結果レジスタ６
３の保持値の下位所定ビットの２の補数を求める。この
ような計算の結果、逐次、補数演算部６４で求められた
値をテーブルのアドレスとして、加算結果レジスタ６３
に保持された値を書き込んで、倍数テーブル５１とす
る。
【００５１】ここでは、説明の便宜のため、剰余の法Ｎ
を１０１１００１１2とし、索引を４ビットで行うもの
とする。図５において、まず、０をテーブルの０番目す
なわちアドレス０にセットする。次に０にＮレジスタ６
１の剰余の法Ｎを加え、加算結果を１０１１００１１2
として、加算結果レジスタ６３に保持する。この加算結
果の下位４ビットを取り出し、補数演算部６４で２の補
数をとると１１０１2になるので、テーブルのアドレス
１１０１2に１０１１００１１2をセットする。このよう
にして、順次、テーブルの求められた２の補数値のアド
レスに加算結果をセットしてゆく。
を１０１１００１１2とし、索引を４ビットで行うもの
とする。図５において、まず、０をテーブルの０番目す
なわちアドレス０にセットする。次に０にＮレジスタ６
１の剰余の法Ｎを加え、加算結果を１０１１００１１2
として、加算結果レジスタ６３に保持する。この加算結
果の下位４ビットを取り出し、補数演算部６４で２の補
数をとると１１０１2になるので、テーブルのアドレス
１１０１2に１０１１００１１2をセットする。このよう
にして、順次、テーブルの求められた２の補数値のアド
レスに加算結果をセットしてゆく。
【００５２】例えば、図５に示された状態では、剰余の
法Ｎを６回加算した値１００００１１００１０2に、Ｎ
を加えて１００１１１００１０１2を得て、下位４ビッ
トの２の補数１０１１2をとる。そして、テーブルのア
ドレス１０１１2に１００１１１００１０１2をセットし
ている。このような操作を１６回繰り返すことにより、
倍数テーブル５１を作成することができる。
法Ｎを６回加算した値１００００１１００１０2に、Ｎ
を加えて１００１１１００１０１2を得て、下位４ビッ
トの２の補数１０１１2をとる。そして、テーブルのア
ドレス１０１１2に１００１１１００１０１2をセットし
ている。このような操作を１６回繰り返すことにより、
倍数テーブル５１を作成することができる。
【００５３】この実施例によるテーブル作成装置は、煩
雑な計算を要するパラメータＮ′を直接使用することな
く、モンゴメリのアルゴリズムの剰余の法Ｎの倍数を入
力値Ｔに加えると、下位ｋビットが０となるという性質
を利用して、倍数テーブルを容易に作成することができ
る。なお、このテーブル作成装置は、単純な繰り返し加
算処理、２の補数を求める処理およびテーブルの書き込
み処理のみで済むので、図５に対応するハードウェア構
成のみならず、ワークステーション、パーソナルコンピ
ュータ等を用いたソフトウェア処理で容易に実現するこ
とができる。
雑な計算を要するパラメータＮ′を直接使用することな
く、モンゴメリのアルゴリズムの剰余の法Ｎの倍数を入
力値Ｔに加えると、下位ｋビットが０となるという性質
を利用して、倍数テーブルを容易に作成することができ
る。なお、このテーブル作成装置は、単純な繰り返し加
算処理、２の補数を求める処理およびテーブルの書き込
み処理のみで済むので、図５に対応するハードウェア構
成のみならず、ワークステーション、パーソナルコンピ
ュータ等を用いたソフトウェア処理で容易に実現するこ
とができる。
【００５４】〈実施例４〉本発明の第４の実施例は、図
２に示したように倍数情報テーブルを用いた剰余計算装
置の構成を、分割乗算処理を行う分割乗算装置と組み合
わせて構成した乗算剰余計算装置の実施例である。以
下、本発明の第４の実施例に係る乗算剰余計算装置を、
図２と同様の部分には同符号を付して示す図６を参照し
て説明する。
２に示したように倍数情報テーブルを用いた剰余計算装
置の構成を、分割乗算処理を行う分割乗算装置と組み合
わせて構成した乗算剰余計算装置の実施例である。以
下、本発明の第４の実施例に係る乗算剰余計算装置を、
図２と同様の部分には同符号を付して示す図６を参照し
て説明する。
【００５５】図６に示す乗算剰余計算装置は、Ｒ＝
ｂn、ｂ＝２kとして、ＡＢ→ＡＢＲ-1modＮの処理を行
うものとし、図２と同様の、Ｔレジスタ１１、Ｎレジス
タ１２、第１の乗算器１４、第１の加算器１６、補正装
置２２および倍数情報テーブル４１を具備する。さら
に、図６の乗算剰余計算装置においては、Ａレジスタ７
１、Ｂレジスタ７２、第３の乗算器７３および第３の加
算器７４を設けている。
ｂn、ｂ＝２kとして、ＡＢ→ＡＢＲ-1modＮの処理を行
うものとし、図２と同様の、Ｔレジスタ１１、Ｎレジス
タ１２、第１の乗算器１４、第１の加算器１６、補正装
置２２および倍数情報テーブル４１を具備する。さら
に、図６の乗算剰余計算装置においては、Ａレジスタ７
１、Ｂレジスタ７２、第３の乗算器７３および第３の加
算器７４を設けている。
【００５６】Ａレジスタ７１、Ｂレジスタ７２、第３の
乗算器７３および第３の加算器７４は分割乗算装置７５
を構成しており、Ｔレジスタ１１、Ｎレジスタ１２、第
１の乗算器１４、第１の加算器１６および倍数情報テー
ブル４１は剰余演算装置７６を構成している。Ａレジス
タ７１は与えられる乗数Ａを保持し、Ｂレジスタ７２は
与えられる被乗数Ｂを保持する。乗算器７３は、Ｂレジ
スタ７２に保持される被乗数をｋビット毎に下位から順
次取り出して、Ａレジスタ７１の乗数Ａに乗算する。加
算器７４は、ｎ回のループ処理の間、剰余演算装置７６
の加算器１６の演算結果を乗算器７３の乗算結果に加算
する。
乗算器７３および第３の加算器７４は分割乗算装置７５
を構成しており、Ｔレジスタ１１、Ｎレジスタ１２、第
１の乗算器１４、第１の加算器１６および倍数情報テー
ブル４１は剰余演算装置７６を構成している。Ａレジス
タ７１は与えられる乗数Ａを保持し、Ｂレジスタ７２は
与えられる被乗数Ｂを保持する。乗算器７３は、Ｂレジ
スタ７２に保持される被乗数をｋビット毎に下位から順
次取り出して、Ａレジスタ７１の乗数Ａに乗算する。加
算器７４は、ｎ回のループ処理の間、剰余演算装置７６
の加算器１６の演算結果を乗算器７３の乗算結果に加算
する。
【００５７】この場合、図２の場合とは異なり、剰余演
算装置７６の加算器１６の加算結果はそのまま加算器７
４に入力されてｎ回の処理ループを形成する。ここで、
図６の乗算剰余計算装置は、図２におけるＴレジスタ１
１と処理ループの部分に、５１２ビット幅のＡレジスタ
７１およびＢレジスタ７２、５２０ビット幅の乗算器７
３、ならびに５２１ビット幅の加算器７４を具備する分
割乗算装置７５を組み込んだ倍数情報テーブル式の乗算
剰余計算装置として、具体的なビット数の例を示して説
明する。図２の剰余計算装置をそのまま乗算剰余計算装
置に使用する場合は、乗算装置を設けて単にその乗算結
果をＴレジスタ１１に代入するようにして実現すること
ができるが、本実施例では、分割乗算装置と組み合わせ
ることにより、剰余演算装置のＴレジスタ１１、加算器
１６およびループ処理部分のビット幅を削減している。
算装置７６の加算器１６の加算結果はそのまま加算器７
４に入力されてｎ回の処理ループを形成する。ここで、
図６の乗算剰余計算装置は、図２におけるＴレジスタ１
１と処理ループの部分に、５１２ビット幅のＡレジスタ
７１およびＢレジスタ７２、５２０ビット幅の乗算器７
３、ならびに５２１ビット幅の加算器７４を具備する分
割乗算装置７５を組み込んだ倍数情報テーブル式の乗算
剰余計算装置として、具体的なビット数の例を示して説
明する。図２の剰余計算装置をそのまま乗算剰余計算装
置に使用する場合は、乗算装置を設けて単にその乗算結
果をＴレジスタ１１に代入するようにして実現すること
ができるが、本実施例では、分割乗算装置と組み合わせ
ることにより、剰余演算装置のＴレジスタ１１、加算器
１６およびループ処理部分のビット幅を削減している。
【００５８】乗算剰余を行う２数すなわち乗数および被
乗数が、ＡおよびＢのレジスタ７１および７２にそれぞ
れ入力されると、Ａレジスタ７１の保持値とＢレジスタ
７２の保持値の下位側から８ビットずつの値が乗算器７
３で乗算される。この乗算器７３の乗算結果と前回の処
理ループの計算値（初回は０とする）が加算器７４で加
算されてＴレジスタ１１に入力される。ここから加算器
１６までは図２の実施例の場合と同様の処理が行われ
る。ループの回数ｎが６４未満の場合、加算器１６の加
算結果の上位５１４ビットをループによりフィードバッ
クして加算器３に入力し、次回のＡレジスタ７１とＢレ
ジスタ７２との分割剰余結果に加算する。ループの回数
ｎが６４の場合、加算器１６の加算結果の下位９ビット
目から５１３ビットを取り出し、補正装置２２に入力す
る。このようにすることにより、５１２ビットのＡＢＲ
-1modＮが補正装置２２から出力される。
乗数が、ＡおよびＢのレジスタ７１および７２にそれぞ
れ入力されると、Ａレジスタ７１の保持値とＢレジスタ
７２の保持値の下位側から８ビットずつの値が乗算器７
３で乗算される。この乗算器７３の乗算結果と前回の処
理ループの計算値（初回は０とする）が加算器７４で加
算されてＴレジスタ１１に入力される。ここから加算器
１６までは図２の実施例の場合と同様の処理が行われ
る。ループの回数ｎが６４未満の場合、加算器１６の加
算結果の上位５１４ビットをループによりフィードバッ
クして加算器３に入力し、次回のＡレジスタ７１とＢレ
ジスタ７２との分割剰余結果に加算する。ループの回数
ｎが６４の場合、加算器１６の加算結果の下位９ビット
目から５１３ビットを取り出し、補正装置２２に入力す
る。このようにすることにより、５１２ビットのＡＢＲ
-1modＮが補正装置２２から出力される。
【００５９】〈実施例５〉本発明の第５の実施例は、図
４に示したように倍数テーブルを用いた剰余計算装置の
構成を、分割乗算処理を行う分割乗算装置と組み合わせ
て構成した乗算剰余計算装置の実施例である。以下、本
発明の第５の実施例に係る乗算剰余計算装置を、図４ま
たは図６と同様の部分には同符号を付して示す図７を参
照して説明する。
４に示したように倍数テーブルを用いた剰余計算装置の
構成を、分割乗算処理を行う分割乗算装置と組み合わせ
て構成した乗算剰余計算装置の実施例である。以下、本
発明の第５の実施例に係る乗算剰余計算装置を、図４ま
たは図６と同様の部分には同符号を付して示す図７を参
照して説明する。
【００６０】図７に示す乗算剰余計算装置は、図４と同
様の、Ｔレジスタ１１、第１の加算器１６、補正装置２
２および倍数テーブル５１を具備する。さらに、図７の
乗算剰余計算装置においては、図６と同様の、Ａレジス
タ７１、Ｂレジスタ７２、第３の乗算器７３および第３
の加算器７４を設けている。Ａレジスタ７１、Ｂレジス
タ７２、第３の乗算器７３および第３の加算器７４は分
割乗算装置７５を構成しており、Ｔレジスタ１１、第１
の加算器１６および倍数テーブル５１は剰余演算装置８
１を構成している。
様の、Ｔレジスタ１１、第１の加算器１６、補正装置２
２および倍数テーブル５１を具備する。さらに、図７の
乗算剰余計算装置においては、図６と同様の、Ａレジス
タ７１、Ｂレジスタ７２、第３の乗算器７３および第３
の加算器７４を設けている。Ａレジスタ７１、Ｂレジス
タ７２、第３の乗算器７３および第３の加算器７４は分
割乗算装置７５を構成しており、Ｔレジスタ１１、第１
の加算器１６および倍数テーブル５１は剰余演算装置８
１を構成している。
【００６１】図６の場合と同様に、Ａレジスタ７１は与
えられる乗数Ａを保持し、Ｂレジスタ７２は与えられる
被乗数Ｂを保持する。乗算器７３は、Ｂレジスタ７２に
保持される被乗数をｋビット毎に下位から順次取り出し
て、Ａレジスタ７１の乗数Ａに乗算する。加算器７４
は、ｎ回のループ処理の間、剰余演算装置８１の加算器
１６の演算結果を乗算器７３の乗算結果に加算する。加
算器１６の加算結果はそのまま加算器７４に入力されて
ｎ回の処理ループを形成する。
えられる乗数Ａを保持し、Ｂレジスタ７２は与えられる
被乗数Ｂを保持する。乗算器７３は、Ｂレジスタ７２に
保持される被乗数をｋビット毎に下位から順次取り出し
て、Ａレジスタ７１の乗数Ａに乗算する。加算器７４
は、ｎ回のループ処理の間、剰余演算装置８１の加算器
１６の演算結果を乗算器７３の乗算結果に加算する。加
算器１６の加算結果はそのまま加算器７４に入力されて
ｎ回の処理ループを形成する。
【００６２】なお、本発明の剰余計算装置および乗算剰
余計算装置はハードウェアに限らず同様の機能構成の少
なくとも一部をソフトウェアで実現することもでき、そ
のような場合にも処理の高速化を達成することができ
る。
余計算装置はハードウェアに限らず同様の機能構成の少
なくとも一部をソフトウェアで実現することもでき、そ
のような場合にも処理の高速化を達成することができ
る。
【００６３】
【発明の効果】以上説明したように、本発明によれば、
モンゴメリ法による剰余計算処理における倍数算定の乗
算処理をテーブル索引で行うため、処理を簡略化するこ
とができ、高速に剰余演算を行うことを可能とする剰余
計算装置および同様に高速に乗算剰余演算を行うことを
可能とする乗算剰余計算装置を提供することができる。
モンゴメリ法による剰余計算処理における倍数算定の乗
算処理をテーブル索引で行うため、処理を簡略化するこ
とができ、高速に剰余演算を行うことを可能とする剰余
計算装置および同様に高速に乗算剰余演算を行うことを
可能とする乗算剰余計算装置を提供することができる。
【００６４】例えば、ソフトウェアで本発明をの剰余計
算装置または乗算剰余計算装置を実現した場合、剰余計
算部分を比較すれば、テーブルを用いない場合の処理時
間を１００とすると、倍数情報テーブル方式が９８、倍
数テーブル方式が３１となり、その効果は明らかであ
る。また、本発明によれば、倍数テーブル方式に用いる
倍数テーブルを作成するのに、剰余の法を繰り返し加算
し、加算結果の下位所定ビットの２の補数を求め、その
２の補数値に対応するアドレスに前記加算結果を格納す
ることにより、煩雑な計算を要するパラメータＮ′を求
めることなくテーブルを作成することが可能なテーブル
作成装置を提供することができる。
算装置または乗算剰余計算装置を実現した場合、剰余計
算部分を比較すれば、テーブルを用いない場合の処理時
間を１００とすると、倍数情報テーブル方式が９８、倍
数テーブル方式が３１となり、その効果は明らかであ
る。また、本発明によれば、倍数テーブル方式に用いる
倍数テーブルを作成するのに、剰余の法を繰り返し加算
し、加算結果の下位所定ビットの２の補数を求め、その
２の補数値に対応するアドレスに前記加算結果を格納す
ることにより、煩雑な計算を要するパラメータＮ′を求
めることなくテーブルを作成することが可能なテーブル
作成装置を提供することができる。
【図１】本発明に係る剰余計算装置の構成を示す原理図
である。
である。
【図２】本発明の第１の実施例に係る剰余計算装置の構
成を示すブロック図である。
成を示すブロック図である。
【図３】図２の剰余計算装置で用いる倍数情報テーブル
を説明するための模式図である。
を説明するための模式図である。
【図４】本発明の第２の実施例に係る剰余計算装置の構
成を示すブロック図である。
成を示すブロック図である。
【図５】図４の剰余計算装置で用いる倍数テーブルを作
成するための本発明の第３の実施例に係るテーブル作成
装置の原理構成を概略的に示す図である。
成するための本発明の第３の実施例に係るテーブル作成
装置の原理構成を概略的に示す図である。
【図６】本発明の第４の実施例に係る乗算剰余計算装置
の構成を示すブロック図である。
の構成を示すブロック図である。
【図７】本発明の第５の実施例に係る乗算剰余計算装置
の構成を示すブロック図である。
の構成を示すブロック図である。
【図８】モンゴメリのアルゴリズムを単純にハードウェ
ア化した場合の一般的に考えられる剰余計算装置の構成
を示すブロック図である。
ア化した場合の一般的に考えられる剰余計算装置の構成
を示すブロック図である。
１，１１…Ｔレジスタ ２，５２…倍数算定部 ３，１６，１９，６２，７４…加算器 ４，２２…補正装置 ５，５１…倍数テーブル １２，６１…Ｎレジスタ １４，７３…乗算器 １７，２０…レジスタ １８…−Ｎレジスタ ２１…セレクタ ４１…倍数情報テーブル ４２…倍数情報算定部 ６３…加算結果レジスタ ６４…補数演算部 ７１…Ａレジスタ ７２…Ｂレジスタ ７５…分割乗算装置 ７６，８１…剰余演算装置
───────────────────────────────────────────────────── フロントページの続き (72)発明者 秋山 良太 神奈川県川崎市中原区上小田中1015番地 富士通株式会社内
Claims (10)
- 【請求項１】 入力される被剰余数を保持する入力レジ
スタ（１）と、 前記入力レジスタ（１）に格納される被剰余数の下位所
定ビットに基づいて、予め演算データを格納したテーブ
ルを用いるテーブル検索により、前記被剰余数の下位所
定ビットに対応する剰余の法の倍数を求めるための倍数
算定手段（２）と、 前記倍数算定手段（２）で求められる剰余の法の倍数と
前記入力レジスタ（１）の内容とを加算するとともに、
所定回数の加算についてその加算結果の上位所定ビット
で前記入力レジスタ（１）の内容を更新するための加算
手段（３）と、 前記加算手段（３）の加算結果に対して剰余結果の補正
処理を施すための補正手段（４）とを具備することを特
徴とする剰余計算装置。 - 【請求項２】 倍数算定手段（２）は、被剰余数の下位
所定ビットに対応させて剰余の法の倍数を格納した倍数
テーブル（５）を有し、この倍数テーブル（５）を前記
被剰余数の下位所定ビットで検索して、それに対応する
前記剰余の法の倍数を直接求める手段であることを特徴
とする請求項１に記載の剰余計算装置。 - 【請求項３】 倍数算定手段（２）は、被剰余数の下位
所定ビットに対応させて倍数情報を格納した倍数情報テ
ーブル（４１）を前記被剰余数の下位所定ビットで検索
して、それに対応する倍数情報を求める倍数情報算定手
段（４２）と、剰余の法を格納する剰余の法レジスタ
（１２）と、前記倍数情報算定手段（４２）で得られる
倍数情報と前記剰余の法レジスタ（１２）から得られる
剰余の法とを乗算する乗算手段（１４）とを有し、前記
倍数算定手段（１０）により前記被剰余数の下位所定ビ
ットに対応する前記剰余の法の倍数を求める手段である
ことを特徴とする請求項１に記載の剰余計算装置。 - 【請求項４】 請求項２の剰余計算装置に用いる倍数テ
ーブルを記憶装置上に作成するテーブル作成装置におい
て、剰余の法を繰り返し加算するための繰り返し加算手
段（６２）と、前記繰り返し加算手段（６２）で求めら
れる各加算結果の値の下位ｂビットの２の補数を求める
ための補数算定手段（６４）と、前記補数算定手段（６
４）で得られる各補数値に対応するテーブルアドレスに
前記各加算結果をそれぞれ格納するためのテーブル書き
込み手段とを具備することを特徴とするテーブル作成装
置。 - 【請求項５】 被乗数の下位から所定ビット毎の値と乗
数を乗算し、その乗算結果に剰余を加算する分割乗算装
置（７５）と、 この分割乗算装置（７５）から出力される被剰余数を保
持する被剰余数レジスタ（１１）と、 前記被剰余数レジスタ（１１）に格納される被剰余数の
下位所定ビットに基づいて、予め演算データを格納した
テーブルを用いるテーブル検索により、前記被剰余数の
下位所定ビットに対応する剰余の法の倍数を求めるため
の倍数算定手段と、 前記倍数算定手段で求められる剰余の法の倍数と前記入
力レジスタの内容とを加算するとともに、所定回数の加
算についてその加算結果を前記剰余として前記分割乗算
装置の前記乗算結果への加算に供するための加算手段
（１６）と、 前記加算手段（１６）の加算結果に対して剰余結果の補
正処理を施すための補正手段（２２）とを有することを
特徴とする乗算剰余計算装置。 - 【請求項６】 倍数算定手段は、被剰余数の下位所定ビ
ットに対応させて剰余の法の倍数を格納した倍数テーブ
ル（５１）を有し、この倍数テーブル（５１）を前記被
剰余数の下位所定ビットで検索して、それに対応する前
記剰余の法の倍数を直接求める手段であることを特徴と
する請求項５に記載の乗算剰余計算装置。 - 【請求項７】 倍数算定手段は、被剰余数の下位所定ビ
ットに対応させて倍数情報を格納した倍数情報テーブル
（４１）を前記被剰余数の下位所定ビットで検索して、
それに対応する倍数情報を求めるための倍数情報算定手
段と、剰余の法を格納する剰余の法レジスタ（１２）
と、前記倍数情報算定手段で得られる倍数情報と前記剰
余の法レジスタ（１２）から得られる剰余の法とを乗算
するための乗算手段（１４）とを有し、この倍数算定手
段により前記被剰余数の下位所定ビットに対応する前記
剰余の法の倍数を求める手段であることを特徴とする請
求項５に記載の乗算剰余計算装置。 - 【請求項８】 整数ＴおよびＮについて、被剰余数Ｔに
対する剰余の法Ｎにおける剰余ＴmodＮ＝ＲＥＤＣ（Ｔ
＊（Ｒ2modＮ）を求めるためＴＲ-1modＮ＝ＲＥＤＣ
（Ｔ）を算出する剰余計算装置において、 入力される被剰余数Ｔを保持する入力レジスタ（１１）
と、 前記入力レジスタ（１１）に格納される被剰余数Ｔの下
位所定ビットに基づいて、予め演算データを格納したテ
ーブルを用いるテーブル検索により、前記被剰余数の下
位所定ビットに対応する剰余の法Ｎの倍数ｍ′Ｎ（但
し、ｍ′＝（Ｔmodｂ）Ｎ′modｂ、ここでＮ′およびＲ
は整数であり、Ｒ＝ｂn、ｂ＝２kとする）を求めるため
の倍数算定手段と、 前記倍数算定手段で求められる剰余の法Ｎの倍数ｍ′Ｎ
と前記入力レジスタの内容とを加算するとともに、所定
回数の加算についてその加算結果の上位所定ビットで前
記入力レジスタの内容を更新することによりｔ＝（Ｔ＋
ｍＮ）／Ｒを出力する加算器（１６）と、 前記加算器（１６）の加算結果ｔに対してｔ＜Ｎの場合
はそのままｔ＝ＲＥＤＣ（Ｔ）、ｔ≧Ｎの場合はｔ−Ｎ
＝ＲＥＤＣ（Ｔ）として補正処理を施しＴＲ-1modＮを
得る補正装置（２２）とを有することを特徴とする剰余
計算装置。 - 【請求項９】 倍数算定手段（５２）は、被剰余数Ｔの
下位所定ビットに対応させて剰余の法Ｎの倍数ｍ′Ｎを
格納した倍数テーブル（５１）を有し、この倍数テーブ
ル（５１）を前記被剰余数Ｔの下位所定ビットで検索し
て、それに対応する前記剰余の法の倍数ｍ′Ｎを直接求
める手段であることを特徴とする請求項８に記載の剰余
計算装置。 - 【請求項１０】 倍数算定手段は、被剰余数Ｔの下位所
定ビットに対応させて倍数情報ｍ′を格納した倍数情報
テーブル（４１）を前記被剰余数Ｔの下位所定ビットで
検索して、それに対応する倍数情報ｍ′を求める倍数情
報算定手段（４２）と、剰余の法Ｎを格納する剰余の法
レジスタ（１２）と、前記倍数情報算定手段（４２）で
得られる倍数情報ｍ′と前記剰余の法レジスタ（１２）
から得られる剰余の法Ｎとを乗算する乗算器（１４）と
を有し、この倍数算定手段により前記被剰余数の下位所
定ビットに対応する前記剰余の法Ｎの倍数ｍ′Ｎを求め
る手段であることを特徴とする請求項８に記載の剰余計
算装置。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5164870A JPH0720778A (ja) | 1993-07-02 | 1993-07-02 | 剰余計算装置、テーブル作成装置および乗算剰余計算装置 |
| US08/268,435 US5499299A (en) | 1993-07-02 | 1994-06-30 | Modular arithmetic operation system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5164870A JPH0720778A (ja) | 1993-07-02 | 1993-07-02 | 剰余計算装置、テーブル作成装置および乗算剰余計算装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0720778A true JPH0720778A (ja) | 1995-01-24 |
Family
ID=15801496
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP5164870A Withdrawn JPH0720778A (ja) | 1993-07-02 | 1993-07-02 | 剰余計算装置、テーブル作成装置および乗算剰余計算装置 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5499299A (ja) |
| JP (1) | JPH0720778A (ja) |
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6415310B1 (en) | 1998-10-27 | 2002-07-02 | Fujitsu Limited | Remainder calculating method, modular-multiplication method, remainder calculating apparatus, modular-multiplication apparatus and recording medium |
| JP2003501698A (ja) * | 1999-06-09 | 2003-01-14 | マイクロソフト コーポレイション | 基本的なレジスタ演算を用いたパラメータの生成 |
| US7171437B2 (en) | 2002-09-30 | 2007-01-30 | Renesas Technology Corp. | Residue calculating unit immune to power analysis |
| US7471789B2 (en) | 2002-10-24 | 2008-12-30 | Renesas Technology Corp. | Encryption circuit achieving higher operation speed |
| JP2010186075A (ja) * | 2009-02-12 | 2010-08-26 | Chugoku Electric Power Co Inc:The | 整数の暗号化及び復号化方法 |
| JP2010186076A (ja) * | 2009-02-12 | 2010-08-26 | Chugoku Electric Power Co Inc:The | 整数の暗号化及び復号化方法 |
| JP2011180390A (ja) * | 2010-03-01 | 2011-09-15 | Chugoku Electric Power Co Inc:The | 整数を暗号化及び復号化する方法、装置及びシステム |
Families Citing this family (48)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5724279A (en) * | 1995-08-25 | 1998-03-03 | Microsoft Corporation | Computer-implemented method and computer for performing modular reduction |
| JP3504050B2 (ja) * | 1996-01-26 | 2004-03-08 | 株式会社東芝 | べき乗剰余演算方法及び装置 |
| JP3525209B2 (ja) * | 1996-04-05 | 2004-05-10 | 株式会社 沖マイクロデザイン | べき乗剰余演算回路及びべき乗剰余演算システム及びべき乗剰余演算のための演算方法 |
| US5793659A (en) * | 1996-10-15 | 1998-08-11 | United Microelectronics Corporation | Method of modular reduction and modular reduction circuit |
| US6088453A (en) * | 1997-01-27 | 2000-07-11 | Kabushiki Kaisha Toshiba | Scheme for computing Montgomery division and Montgomery inverse realizing fast implementation |
| US5987131A (en) * | 1997-08-18 | 1999-11-16 | Picturetel Corporation | Cryptographic key exchange using pre-computation |
| US7197625B1 (en) * | 1997-10-09 | 2007-03-27 | Mips Technologies, Inc. | Alignment and ordering of vector elements for single instruction multiple data processing |
| US5864703A (en) * | 1997-10-09 | 1999-01-26 | Mips Technologies, Inc. | Method for providing extended precision in SIMD vector arithmetic operations |
| EP0947914B1 (en) * | 1998-03-30 | 2004-12-15 | Rainbow Technologies Inc. | Computationally efficient modular multiplication method and apparatus |
| KR100486697B1 (ko) * | 1998-05-26 | 2005-06-16 | 삼성전자주식회사 | 모듈러연산장치및그방법 |
| US6182104B1 (en) * | 1998-07-22 | 2001-01-30 | Motorola, Inc. | Circuit and method of modulo multiplication |
| US6408075B1 (en) * | 1998-11-30 | 2002-06-18 | Hitachi, Ltd. | Information processing equipment and IC card |
| TW429344B (en) * | 1999-04-28 | 2001-04-11 | Via Tech Inc | Matching table method of element product in Galois field |
| WO2001089129A2 (en) * | 2000-05-15 | 2001-11-22 | M-Systems Flash Disk Pioneers Ltd. | Extending the range of computational fields of integers |
| US7080109B2 (en) * | 2000-06-29 | 2006-07-18 | State Of Oregon Acting By And Through The State Board Of Higher Education On Behalf Of Oregon State University | Methods and apparatus for incomplete modular arithmetic |
| US7620832B2 (en) * | 2000-09-20 | 2009-11-17 | Mips Technologies, Inc. | Method and apparatus for masking a microprocessor execution signature |
| SE0003757L (sv) * | 2000-10-17 | 2002-04-09 | Novacatus Invest Ab | Metod och anordning vid modulomultiplikation samt användning av metoden vid asymmetrisk kryptering/dekryptering |
| US6963977B2 (en) * | 2000-12-19 | 2005-11-08 | International Business Machines Corporation | Circuits and methods for modular exponentiation |
| US7162621B2 (en) * | 2001-02-21 | 2007-01-09 | Mips Technologies, Inc. | Virtual instruction expansion based on template and parameter selector information specifying sign-extension or concentration |
| US7181484B2 (en) * | 2001-02-21 | 2007-02-20 | Mips Technologies, Inc. | Extended-precision accumulation of multiplier output |
| US7599981B2 (en) * | 2001-02-21 | 2009-10-06 | Mips Technologies, Inc. | Binary polynomial multiplier |
| US7237097B2 (en) | 2001-02-21 | 2007-06-26 | Mips Technologies, Inc. | Partial bitwise permutations |
| US7711763B2 (en) * | 2001-02-21 | 2010-05-04 | Mips Technologies, Inc. | Microprocessor instructions for performing polynomial arithmetic operations |
| US7017064B2 (en) * | 2001-05-09 | 2006-03-21 | Mosaid Technologies, Inc. | Calculating apparatus having a plurality of stages |
| US7318145B1 (en) | 2001-06-01 | 2008-01-08 | Mips Technologies, Inc. | Random slip generator |
| US20030065697A1 (en) * | 2001-08-29 | 2003-04-03 | Shimman Patel | Fast, iterative system and method for evaluating a modulo operation without using division |
| US20030065699A1 (en) * | 2001-10-01 | 2003-04-03 | Koninklijke Philips Electronics N.V. | Split multiplier for efficient mixed-precision DSP |
| DE10200133B4 (de) * | 2002-01-04 | 2005-12-22 | Infineon Technologies Ag | Verfahren und Vorrichtung zur Berechnung von Modulo-Operationen |
| DE10205713C1 (de) * | 2002-02-12 | 2003-08-07 | Infineon Technologies Ag | Vorrichtung und Verfahren zum Berechnen eines Ergebnisses aus einer Division |
| FR2843211B1 (fr) * | 2002-08-05 | 2005-05-20 | Everbee Networks | Procede pour accelerer des calculs en arithmetique modulaire |
| US7451326B2 (en) * | 2002-08-26 | 2008-11-11 | Mosaid Technologies, Inc. | Method and apparatus for processing arbitrary key bit length encryption operations with similar efficiencies |
| US7386705B2 (en) | 2002-08-27 | 2008-06-10 | Mosaid Technologies Inc. | Method for allocating processor resources and system for encrypting data |
| GB0221837D0 (en) * | 2002-09-20 | 2002-10-30 | Koninkl Philips Electronics Nv | Improved quisquater reduction |
| US7243118B2 (en) * | 2003-07-30 | 2007-07-10 | Broadcom Corporation | Method and apparatus for efficient derivation of modulo arithmetic for frequency selection |
| JP4170267B2 (ja) * | 2004-07-09 | 2008-10-22 | Ｎｅｃエレクトロニクス株式会社 | 乗算剰余演算器及び情報処理装置 |
| JP4180024B2 (ja) * | 2004-07-09 | 2008-11-12 | Ｎｅｃエレクトロニクス株式会社 | 乗算剰余演算器及び情報処理装置 |
| US8024391B2 (en) * | 2006-11-06 | 2011-09-20 | Atmel Rousset S.A.S. | Modular multiplication method with precomputation using one known operand |
| EP2208165A4 (en) * | 2007-11-02 | 2010-11-24 | Certicom Corp | MONTGOMERY ARITHMETIC SIGNED |
| US8417756B2 (en) * | 2007-11-29 | 2013-04-09 | Samsung Electronics Co., Ltd. | Method and apparatus for efficient modulo multiplication |
| US8626811B2 (en) * | 2010-04-30 | 2014-01-07 | Certicom Corp. | Method and apparatus for providing flexible bit-length moduli on a block Montgomery machine |
| DE102010051853A1 (de) * | 2010-11-18 | 2012-05-24 | Giesecke & Devrient Gmbh | Verfahren zur Langzahldivision |
| DE102011117219A1 (de) * | 2011-10-28 | 2013-05-02 | Giesecke & Devrient Gmbh | Bestimmen eines Divisionsrests und Ermitteln von Primzahlkandidaten für eine kryptographische Anwendung |
| US9513870B2 (en) * | 2014-04-22 | 2016-12-06 | Dialog Semiconductor (Uk) Limited | Modulo9 and modulo7 operation on unsigned binary numbers |
| US9543963B2 (en) | 2015-01-30 | 2017-01-10 | International Business Machines Corporation | Modulo-m binary counter |
| US10255462B2 (en) | 2016-06-17 | 2019-04-09 | Arm Limited | Apparatus and method for obfuscating power consumption of a processor |
| US11249726B2 (en) * | 2019-09-10 | 2022-02-15 | Intel Corporation | Integrated circuits with modular multiplication circuitry |
| CN118095459B (zh) * | 2022-11-21 | 2026-01-06 | 本源量子计算科技（合肥）股份有限公司 | 变量二倍模乘运算器、运算方法及相关装置 |
| CN116166219B (zh) * | 2022-12-19 | 2026-03-31 | 成都三零嘉微电子有限公司 | 一种可配置模乘法器 |
Family Cites Families (21)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3980874A (en) * | 1975-05-09 | 1976-09-14 | Burroughs Corporation | Binary to modulo M translation |
| US4037093A (en) * | 1975-12-29 | 1977-07-19 | Honeywell Information Systems, Inc. | Matrix multiplier in GF(2m) |
| JPS6034131A (ja) * | 1983-08-04 | 1985-02-21 | Tokiwadou Seika Kk | アロエ入りかりんとう製造法 |
| US4658094A (en) * | 1985-03-28 | 1987-04-14 | Itt Corporation | Encryption apparatus and methods for raising a large unsigned integer to a large unsigned integer power modulo a large unsigned integer |
| ATE55033T1 (de) * | 1986-03-05 | 1990-08-15 | Holger Sedlak | Kryptographie-verfahren und kryptographieprozessor zur durchfuehrung des verfahrens. |
| JPS6329784A (ja) * | 1986-07-23 | 1988-02-08 | 株式会社日立製作所 | 剰余計算方式 |
| JPH0778726B2 (ja) * | 1986-08-21 | 1995-08-23 | 富士通株式会社 | 分割整数剰余計算機 |
| JPS63200233A (ja) * | 1987-02-16 | 1988-08-18 | Fujitsu Ltd | 高速並列乗除計算機 |
| JPS63200183A (ja) * | 1987-02-17 | 1988-08-18 | 富士通株式会社 | 分割整数剰余計算機 |
| EP0308963A3 (en) * | 1987-09-25 | 1990-04-25 | Kabushiki Kaisha Toshiba | Remainder computing system and method |
| GB2217882B (en) * | 1988-04-29 | 1992-06-10 | Philips Electronic Associated | Arithmetic apparatus |
| BE1003932A6 (fr) * | 1989-04-28 | 1992-07-22 | Musyck Emile | Systeme cryptographique par bloc de donnees binaires. |
| FR2658932A1 (fr) * | 1990-02-23 | 1991-08-30 | Koninkl Philips Electronics Nv | Procede de codage selon la methode dite rsa, par un microcontroleur et dispositif utilisant ce procede. |
| JPH03250314A (ja) * | 1990-02-28 | 1991-11-08 | Fujitsu Ltd | 乗算剰余演算装置 |
| US5121431A (en) * | 1990-07-02 | 1992-06-09 | Northern Telecom Limited | Processor method of multiplying large numbers |
| EP0504996B1 (en) * | 1991-03-22 | 1998-07-08 | Koninklijke Philips Electronics N.V. | Arithmetic unit for multiplying long integers modulo M and R.S.A. converter provided with such multiplication device |
| US5289397A (en) * | 1991-07-22 | 1994-02-22 | Itt Corporation | High-speed modulo exponentiator device |
| DE69229766T2 (de) * | 1991-09-05 | 2000-03-23 | Canon K.K., Tokio/Tokyo | Verfahren und Gerät zum Verschlüsseln und Entschlüsseln von Kommunikationsdaten |
| US5274707A (en) * | 1991-12-06 | 1993-12-28 | Roger Schlafly | Modular exponentiation and reduction device and method |
| US5373560A (en) * | 1991-12-06 | 1994-12-13 | Schlafly; Roger | Partial modular reduction method |
| US5349551A (en) * | 1993-07-30 | 1994-09-20 | The United States Of America As Represented By The Director Of National Security Agency | Device for and method of preforming an N-bit modular multiplication in approximately N/2 steps |
-
1993
- 1993-07-02 JP JP5164870A patent/JPH0720778A/ja not_active Withdrawn
-
1994
- 1994-06-30 US US08/268,435 patent/US5499299A/en not_active Expired - Fee Related
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6415310B1 (en) | 1998-10-27 | 2002-07-02 | Fujitsu Limited | Remainder calculating method, modular-multiplication method, remainder calculating apparatus, modular-multiplication apparatus and recording medium |
| JP2003501698A (ja) * | 1999-06-09 | 2003-01-14 | マイクロソフト コーポレイション | 基本的なレジスタ演算を用いたパラメータの生成 |
| US7171437B2 (en) | 2002-09-30 | 2007-01-30 | Renesas Technology Corp. | Residue calculating unit immune to power analysis |
| US7471789B2 (en) | 2002-10-24 | 2008-12-30 | Renesas Technology Corp. | Encryption circuit achieving higher operation speed |
| JP2010186075A (ja) * | 2009-02-12 | 2010-08-26 | Chugoku Electric Power Co Inc:The | 整数の暗号化及び復号化方法 |
| JP2010186076A (ja) * | 2009-02-12 | 2010-08-26 | Chugoku Electric Power Co Inc:The | 整数の暗号化及び復号化方法 |
| JP2011180390A (ja) * | 2010-03-01 | 2011-09-15 | Chugoku Electric Power Co Inc:The | 整数を暗号化及び復号化する方法、装置及びシステム |
Also Published As
| Publication number | Publication date |
|---|---|
| US5499299A (en) | 1996-03-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0720778A (ja) | 剰余計算装置、テーブル作成装置および乗算剰余計算装置 | |
| US6396926B1 (en) | Scheme for fast realization of encrytion, decryption and authentication | |
| US6259790B1 (en) | Secret communication and authentication scheme based on public key cryptosystem using N-adic expansion | |
| US8352529B2 (en) | Modular multiplication calculation apparatus used for montgomery method | |
| US20020021803A1 (en) | Cryptographic identification and digital signature method using efficient elliptic curve | |
| US7248692B2 (en) | Method of and apparatus for determining a key pair and for generating RSA keys | |
| JP2000132376A (ja) | 剰余演算方法，乗算剰余演算方法，剰余演算装置，乗算剰余演算装置及び記録媒体 | |
| US7050579B1 (en) | Cryptographic methods and apparatus using word-wise montgomery multiplication | |
| WO2005099150A2 (en) | Public key cryptographic methods and systems | |
| JP3402441B2 (ja) | 公開鍵暗号化装置、公開鍵暗号復号装置及び復号プログラム記録媒体 | |
| JP3616897B2 (ja) | モンゴメリ法による乗算剰余計算装置 | |
| JP4177526B2 (ja) | 乗算剰余演算方法および乗算剰余回路 | |
| US6337909B1 (en) | Generation of session keys for El Gamal-like protocols from low hamming weight integers | |
| US20040174995A1 (en) | Cryptosystems | |
| JP3797808B2 (ja) | スカラー倍算方法およびその装置 | |
| US20020025034A1 (en) | Cryptographic encryption method using efficient elliptic curve | |
| JP3615405B2 (ja) | 素体上楕円曲線上の点の演算方法およびその装置 | |
| JP2000137436A (ja) | 素体上楕円曲線上の点の演算方法およびその装置 | |
| JPH11143688A (ja) | 演算装置並びにこれを利用したｒｓａ暗号演算装置及び楕円暗号演算装置 | |
| JP3123820B2 (ja) | 有限可換群における演算器 | |
| KR20010000048A (ko) | ｍ진법 방식을 이용한 타원곡선상 다중 점의 상수고속연산 방법 | |
| US20030072442A1 (en) | Cisponentiation method, software, and device for exponentiation | |
| JP3233605B2 (ja) | 鍵更新方法 | |
| JP4676071B2 (ja) | べき乗剰余演算方法、逆数演算方法およびそれらの装置 | |
| JP3278790B2 (ja) | 公開鍵暗号方法及び公開鍵暗号システム |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Application deemed to be withdrawn because no request for examination was validly filed |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 20000905 |