JPH0212290A - べき乗剰余演算回路 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明はべき乗剰余演算回路に係り、特に公開鍵暗号化
方式で用いるべき乗剰余演算回路に関する。

（従来の技術） 周知のように、データ通信システムや計算機システムで
は、扱う情報の安全確保の手段が種々検討されているが
、その１つの手段として情報を暗号化する方式がある。

暗号化方式には、趣の管理法や使用法の観点から、暗号
化鍵と復号化鍵に同一のものを用いる慣用暗号化方式と
、公開された暗号化鍵と秘密の復号鍵を用いる公開鍵暗
号化方式とがある。公開鍵暗号化方式は慣用暗号化方式
の欠点を解消したもので、代表的なアルゴリズムにはＲ
ｉｖｅｓｔ、Ｓｈａｍｉｒ。

Ａｄｌｅ＋ｓｉｎらによって提案されたＲＡＳ方式があ
る。

ＲＡＳ暗号方式は０　＜　Ｍ　＜　ｎおよびＯ＜ｅ＜ｎ
なる関係にあり、かつそれぞれ等しいビット長で示され
る整数Ｍ、同ｅおよび同ｎを用いてＭ＠ｍｏｄｎ＝Ｃ（
１） なる「べき乗剰余演算」を行い剰余Ｃを求め暗号化する
方式であり、十分な安全性を確保するためには整数Ｍ、
同ｅおよび同ｎはそれぞれ５１２ビット程度必要である
とされる。

このＲＡＳ暗号方式で用いる「べき乗剰余演算回路」と
しては、従来、例えば加納等の提案に係る「高次の拡張
Ｂｏｏｔｈアルゴリズムを用いたべき乗剰余演算ＬＳＩ
Ｊ（暗号と情報セキュリティワークショップ講演論文集
、１９８７年７月、ｐｐ、１３３−１４２）が知られて
いる。このものは、前記式（１）の演算が、 ａＸｂｍｏｄｎ　　　　　　　　　　　　　（２）なる
剰余乗算の繰り返しに帰着することに鑑み剰余テーブル
を設け、被乗数が除数のビット長を越える部分における
剰余計算を剰余テーブルで行い、その結果と除数のビッ
ト長を越えなかった部分の被乗数の値との加算を行い、
その加算結果に乗数を掛けて積を求めそれを次の被乗数
とする操作を繰り返し行うことによって所望の剰余Ｃを
得ようとするものである。

（発明が解決しようとする課題） しかし、前述した従来のべき乗剰余演算回路にあっては
、次のような理由から回路構成が大規模なものになると
いう問題がある。

まず、ＲＡＭ等からなる剰余テーブルを用いて剰余計算
を行っているが、この剰余テーブルは剰余計算を行う乗
算結果の積のビット長が除数のビット長よりも大きくな
ればなる程それに応じて容量を増加する必要がある。

また、回路内で扱うビット長は乗算を行うことによって
べき乗を行う数値のビット長の最大２倍程度となること
が考えられる。その結果、乗算のためのビットシフト部
や加算器等が増長するのである。

本発明は、このような問題に鑑みなされたもので、その
目的は、回路規模の縮小化を図り得るべき乗剰余演算回
路を提供することにある。

（課題を解決するための手段） 前記目的を達成するために、本発明のべき乗剰余演算回
路は次の如き構成を有する。

即ち、本発明のべき乗剰余演算回路は、０　＜　Ｍくｎ
およびＯ＜ｅ＜ｎなる関係にあり、かつそれぞれ等しい
ビット長で示される整数Ｍ、同ｅおよび同ｎを用いてＭ
＠＋ｍｏｄ　ｎ＝Ｃなるべき乗剰余演算を行い剰余Ｃを
求めるべき乗剰余演算回路であって；　このべき乗剰余
演算回路は、外部から入力される数値Ｍが被乗数として
初期設定されるとと６に、その後の演算過程で生成され
た剰余値と累算剰余値のいずれかが被乗数として格納さ
れる被乗数レジスタと；　外部から入力される数値ｎを
除数として格納する除数レジスタと：　前記被乗数レジ
スタの出力を前記除数レジスタの出力で除算して剰余を
求める剰余演算器と；　外部から入力された数ｆｉａｅ
をべき乗の指数として格納する指数レジスタと：　外部
から入力される前記数値Ｍを格納する入力レジスタと；
　前記指数レジスタの最上位ビットから最下位ビットに
至る各ビット出力に順次応答してその論理状態に応じて
前記入力レジスタと前記累算剰余値のいずれかを選択出
力する乗数セレクタと；　前記乗数セレクタの出力を乗
数として格納する乗数レジスタと；　前記乗数レジスタ
の最下位ビットから最上位ビットに至る各ビット出力に
順次応答してその論理値が°゛１°°のときは前記剰余
演算器の出力を選択出力し“Ｏ”のときは０値入力を選
択出力する乗余セレクタと；　前記剰余セレクタの出力
と前記累算剰余値を加算したものを前記除数レジスタの
出力で除算して剰余を求める累算剰余演算器と；　前記
累算剰余演算器の出力を格納しそれを前記累算剰余値と
して出力する累算剰余レジスタと；　前記剰余演算器の
出力である前記剰余値を前記被乗数レジスタに対し出力
するとともに、前記乗数レジスタの最上位ビットについ
ての演算が終了する度に前記累算剰余値を被乗数レジス
タに対し出力する被乗数セレクタと；　前記指数レジス
タの最下位ビットについての演算が終了した時の前記累
算剰余値を最終演算結果値として外部へ出力する出力レ
ジスタと；　を備えていることを特徴とするものである
。

（作　用） 次に、前記の如く構成される本発明のべき乗剰余演算回
路の作用を説明する。

前記式（１）で示す（Ｍ”＋ｏｄｎ）の演算を行うこと
は、基本的には（Ｍ”ｍｏｄ　ｏ）　、即ち（ＭＸＭｎ
ｏｄ　ｏ）を求めることである。そこで、Ｃ，Ｍ、ｎｔ
！−５１２ビツトの２進数で示される正の整数とし、か
つ、ｎ＞Ｍであるとき、Ｃ＋＝ＭＸＭ　ｎｏｄ　ｎは次
のようにして求める。

ｍ；をＭのｔ（０≦ｌ≦５１１）ビット目の数とすれば
、ＭＸＭの部分積ｍＨＸＭの剰余を求めるには ２’　Ｍ　ｌ１ｏｄ　ｏ＝＝ＭＨ の演算を行う必要があるが、この式（３）は２ＭＢ−１
ｓｏｄ　ｎ＝ＩＶｌ と示すことができる。従って、 Ｃ＝＋ＭｘＭ　ＩＯａ　ｎ ＝　　（ｍ、）ＸＭ　　ｌ１ｏｄ　　ｎ＋ｍ、Ｘ２Ｍ、
ｍｏｄ　　ｎ＋ｍ２Ｘ２Ｍ１　　ｓｏｄ　　ｎ＋−−−
−−−＋ｍ＋×２Ｍ＋−１ｍｏｄ　ｎ）　ｓｏｄ　ｎ＝
　（ｍＯＭ　ｓｏｄ　ｎ−Ｑ２２ｍＨＩＪ−１ｍｏｄ　
ｎ）　ｎｏｄ　ｎ　　　−ｍ−（５）、−１ （１≦に≦５１１） と展開でき、剰余Ｃを求めることができる０本発明は式
（５）で示される順次乗除方式に基づき所望の剰余を収
得しようとするものであって、従来例において検討され
た逐次乗除方式とは全く異なるものである。

剰余演算器において被乗数レジスタの出力を除数レジス
タの出力で除算して剰余を求め、それを被乗数セレクタ
を介して被乗数レジスタに設定して同様に剰余を求め、
これを繰り返す演算ループでは前記式（３）の演算を実
行しているのである。

そして、この演算ループから乗余セレクタへ逐一出力さ
れる剰余値は乗余セレクタにおいて乗数レジスタの対応
するビット（前記ｍ　＋　）との１’＊　（ｍｉｘ２　
Ｍ　ｎｏｄ　ｏ＞がとられ、これと累算剰余レジスタに
格納されている前回の累算剰余値Ｓ＋−ｔとの相につい
て除数レジスタの出力で除算することが累算剰余演算器
で行われ、その演算結果である今回の累算剰余値Ｓｉが
累算剰余レジスタに格納される。即ち、累算剰余演算器
は次の式（６）の演算を実行しているのである。

Ｓ；　＝　（Ｓ＋−ｔ＋２’ｍ＋　Ｍ　ｓｏｄ　ｎ）　
ｓｏｄ　ｎ　　　　　−−−−（６＞なお、剰余演算器
および累算剰余演算器における剰余計算は除数の２の補
数を加算することによって行われる。

乗数レジスタには、まず入力レジスタに格納された数値
Ｍが乗数セレクタを介して入力しそれが乗数として設定
されるから、乗数レジスタの全ビットについて式（６）
の演算が行われると、それは式（５）の演算が終了した
ことを示し、その演算結果である累算剰余値が被乗数セ
レクタを介して被乗数レジスタに設定される。指数レジ
スタに設定される数値ｅが値２であるときは、出力レジ
スタからＭ”ｍｏｄｎの演算結果が出力されることにな
るが、−ａに式（１）の演算を行う場合には、数値ｅの
各ビットの論理状態に応じて乗数レジス夕の内容が変更
操作される。

即ち、べき乗演算では、乗数セレクタが指数レジスタの
最上位ビットから最下位ビットに至る各ビット出力に順
次応答してその論理値が“０″のときは累算剰余レジス
タに格納されている前回の累算剰余値Ｓ（これが被乗数
レジスタに設定されている）を乗数レジスタに設定する
。その結果、５ＸＳｎ＋ｏｄｏの処理が実行される。ま
た、論理値が“′１”のときは、まず前回の累算剰余値
Ｓを乗数レジスタに設定して　ＳＸＳｍｏｄｎ　　を求
め、次いで入力レジスタの内容である数値Ｍを乗数レジ
スタに設定して （（ＳＸＳ　ｎｏｄ　ｎ）　ｘＭｌ　ｎｏｄ　ｎを求め
る。この乗数セレクタの操作は、指数である数値ｅの最
上位ビットから下位ビットに向かうビット配列において
、そのビットの論理値が０″であるときは前回の値を単
に２乗すれば良く、論理値が“ｌ”であるときは前回の
値を２乗してＭをかければ良いという特性に基づくもの
である。

以上のように、本発明のべき乗剰余演算回路によれば、
従来例の如き剰余テーブルを使用せずに所望の剰余演算
が行える。また、剰余計算は単純な加算処理によって行
うので回路内部で扱うビット長は除数のビット長よりも
にビット（Ｋは２よりも大きな整数）だけ長いだけで済
む。従って、従来例回路よりも大幅に回路規模を縮小す
ることができる。

（実　施　例） 以下、本発明の実施例を図面を参照して説明する。

第１図は、本発明の一実施例に係るべき乗剰余演算回路
を示す。

前記式（１）において、Ｍ、ｅ、ｎおよびＣはそれぞれ
５１２ビツトの２進数で示される正の整数であって、Ｒ
ＡＳ暗号化方式の定義からＭ＜ｎである。

被乗数レジスタ１と入力レジスタ７には、外部から数値
Ｍが初期設定される。また、除数レジスタ２には数値ｎ
が、指数レジスタ６には数値ｅがそれぞれ外部から供給
され数値設定がなされる。

これら外部から供給される数値はビン数削減の趣旨から
ビット直列で供給される。なお、本実施例では入力レジ
スタ７と乗数セレクタ９閏にバッファとしてｌＲ能する
１数レジスタ８を設けである。

即ち、入力レジスタ７ではビット直列で入力した数値Ｍ
をビット並列にして置数レジスタに設定し、入力レジス
タ７は新たな演算に必要な数値入力に備え得るようにし
である。

まず、被乗数レジスタ１、除数レジスタ２、剰余演算器
３および被乗数セレクタ１１からなる演算部では次の如
き処理が行われる。前記式（３）と同（４）において、
ｎ＞Ｍに注意すると、Ｍ　ｎｏｄ　ｎ＝＝Ｍ□はＭ　ｍ
ｏｄ　ｎ＝Ｍｏ＝Ｍ　　テア７、　、　ｉ　な、２ＭＯ
ｎｏｄ　ｎ＝Ｍ４はＭ、＝Ｍから　２Ｍ　ｌ１ｏｄ　ｎ
＝Ｍ１と表され、２Ｍ＜２ｎである。以下同様に、２Ｍ
；−ｔ＜２ｎである。故に、式（３）、同（４）で示さ
れるｓｏｄ　ｎの処理を行うことは２Ｍ＋−ｔから１１
を減算することに等しいということが理解できる。

このとき、２Ｍ、、からｎを減算できればその答えをＭ
；とし、減算できなければ２Ｍ＋−＋　をそのままＭ；
とするのである、この処理を剰余演算器３が行っている
のである。

即ち、剰余演算器３には被乗数レジスタ１に格納される
５１２ビツトの被乗数が左に１ビットシフＩ−した５１
３ビツトの形で入力する。また、除数レジスタ２に格、
納される除数ｎは２の補数に変換される。そこで、最初
に、数値Ｍと数値ｎの２の補数との加算を行ってＭ　ｍ
ａｄ　ｎを実行する。

その結果、５１４ビツト目が“１″であればＭからｎを
減算できたので、ＭＯが減算結果となる。

逆に、５１４ビツト目が“０“であれば減算できなかっ
たことになり、Ｍが減算結果となる。剰余演算器３はこ
のようにして剰余値Ｍ。または同Ｍを得、それを左へ１
ビツトシフトした形で剰余セレクタ１１を介して被乗数
レジスタ１へ出力し新たな被乗数の設定を行う、これに
より、２Ｍｍｏｄｎの演算が引き続いて実行される。以
後同様の演算が繰り返し実行される。斯くして、前記式
（３）において、２’Ｍ〜２５１１Ｍまでの剰余値が連
続して求められ、それらは剰余セレクタ１２へ逐一出力
される。

剰余セレクタ１２では、乗数レジスタ１０の最下位ビッ
トから最上位ビットに至る各ビット出力に順次応答して
その論理値が“１”のときは剰余演算器３の出力を選択
出力し０”のときはＯ値入力を選択出力する。つまり、
剰余演算器３がら逐一出力される剰余値と乗数レジスタ
１０の対応するビット（ｍｉ）との７９　（ｍｉＸ２’
Ｍ　ｎｏｄ　ｎ）　　カトラれ、それが累算剰余演算器
４へ入力する。

累算剰余演算器４では、この積（ｍｉＸ２’Ｍ　ｌ１ｏ
ｄ　ｎ）と累算剰余レジスタ５に格納されている前回の
累ｇ剰余値５ｉ−ｔとの和（Ｓｔ−＋＋２’ｍ＋　Ｍ　
ｇｏｄ　ｎ）を求め・これに除数レジスタ２の出力であ
る数値ｎの２の補数を加算し、その結果５１４ビツト目
の論理値が“１”ならば加算結果を今回の累算剰余値Ｓ
；とし、また５１４ビツト目の論理値が“０”ならば前
記和を今回の累算剰余値ＳＩとする。これらは累算剰余
レジスタに逐一格納される。即ち、前記式（６）の処理
が乗数レジスタ１０の５１２ビツトの全てについて行わ
れ、１回分のａＸｂｍｏｄｎ（前記式（２）〉の処理が
完了し、これにより被乗数セレクタ１１が制御される。

その結果、この完了時点の累算剰余値Ｓが被乗数セレク
タ１１を介して被乗数レジスタ１へ出力されるとともに
、乗数セレクタ９にも出力される。

次に、「べき乗」の処理を示す０乗数セレクタ９は、指
数レジスタ６の最上位ビット（ＭＳＢ）から最下位ビッ
ト（ＬＳＢ）に至る各ビット出力に応答してその論理状
態に応じて置数レジスタ８の出力と累算剰余レジスタ５
の出力のいずれかを選択しそれを乗数レジスタ１０へ出
力する。

具体的には次の通りである。今、Ｍを７３３乗すること
を考えると、 １２１４５６フ８９１０ ＝　Ｍ　７″３　　　　　　　　　　　　　　　　　　
　　　　　　　　（７）となるが、７３３を２進数で表
すと ７３３＝　（１０１１０１１１０１）２　　　　　　　
　　　　（８）となる、すると、式（７）と同（８）の
関係から次のことが判明する。即ち、最上位ビットから
下位ビットに向かうビット配列において、そのピッ（・
の論理値が０”であるときは前回の値を単に２乗すれば
良く、論理値が“１”であるときは前回の値を２乗して
Ｍをかければ良いということが理解できる。従って、乗
数セレクタ９は、指数レジスタ６の出力ビットの論理値
が“０”であるときは累算剰余レジスタ５の出力を選択
し、また論理値が１″であるときはまず累算剰余レジス
タ５の出力を選択し次いで置数レジスタ８の出力を泗択
することを行う、なお、指数レジスタ６の最上位ビット
出力は常に゛１°′であるが、第１回目の処理では累算
剰余レジスタ５には累算剰余値は存在せず、かつ第１回
目の処理はＭＸＭ　ｎｏｄ　ｎである。従って、第１回
目の処理では最上位ビットについての処理を省略し、置
数レジスタ８の出力、即ち数値Ｍが乗数レジスタ１０に
設定されることになる。

斯くして、べき乗演算では、乗数セレクタ９が指数レジ
スタ６の最上位ピッｉ・から最下位ビットに至る各ビッ
ト出力に順次応答してその論理値が“０“のときは累算
剰余レジスタ５に格納されている前回の累算剰余値Ｓを
乗数レジスタ１０に設定する。その結果、ＳＸＳ　ｓｏ
ｄ　ｎの処理が実行される。また、論理値が“１”のと
きは、まず前回の累算剰余値Ｓを乗数レジスタ１０に設
定してＳｘＳｍｏｄ　ｎ　　を求め、次いで置数レジス
タ８の内容である数値Ｍを乗数レジスタ１０に設定して
（（ＳＸＳ　　ｎｏｄ　　ａ）ＸＭ）ｎｏｄ　　ｎを求
める。そして、指数レジスタ６の最下位ビットについて
の処理が終了すると、出力レジスタ１３から所望の演算
結果が出力される。

なお、５１２ビツトについてのべき乗演算では、最上位
ビットについての処理は省略できるので、５１１ビツト
分の処理を行えば良いことになる。

そして、ビットの論理値が“１“のときは「２乗してＭ
をかける」という２回の処理を行うので、全ビットが“
ｌ”である場合が最大演算回数となる。　５１１　Ｘ　
２　＝　１０２２回である。また、１回のべき乗剰余演
算は５１２回の剰余演算からなる。従って、５１２ビツ
トからなる１つのＭについては最大１０２２Ｘ５１２　
＝５２３２６４回の剰余演算が行われることになる。し
かし、全て加算処理であるから、演算器やレジスタ等が
扱うビット数はそれ程大きくはならない、除数のビット
長よりも高々Ｋ（Ｋは２よりも大きい整数）ビット長く
なるだけであり、従来例回路の如く回路規模が増大する
ことはなく、縮小化を図ることができる。即ち、実施例
回路では、制御カウンタ等の追加分を考慮しても約５５
　Ｋセルで構成できる。対して従来例回路は前掲論文に
明記されているように２０にゲートのＬＳＩの８個で構
成される。諷著な差異が認められるのである。

（発明の効果） 以上説明したように、本発明のべき乗剰余演算回路によ
れば、ＲＡＳ暗号化方式であるという特徴、即ちべき乗
される数値は除数よりも小さいことに着目し、乗数とな
る数値の各ビットに対応した部分積の剰余を剰余演算器
において単純な加算によって計算して出力し、また累算
剰余演算部においても、剰余演算器から出力された剰余
を順次加算して累算値の剰余を求める処理を行うように
したので、従来例の如き剰余テーブルを使用せずに所望
の剰余演算が行える。また、剰余計算は単純な加算処理
によって行うので回路内部で扱うビット長は除数のビッ
ト長よりもにビット（Ｋは２よりも大きな整数ンだけ長
いだけで済む、従って、従来例回路よりも大幅に回路規
模を縮小することができ、本回路を実装する装置の小型
化が図れるという効果がある。

【図面の簡単な説明】

第１図は本発明の一実Ｉｆ！１例に係るべき乗剰余演算
回路の構成ブロック図である。 １・・・・・・被乗数レジスタ、　２・・・・・・除数
レジスタ、３・・・・・・剰余演算器、　４・・・・・
・累算剰余演算器、５・・・・・・累算剰余レジスタ、
　６・・・・・・指数レジスタ、７・・・・・・入力レ
ジスタ、　８・・・・・・置数レジスタ、９・・・・・
・乗数セレクタ、　１０・・・・・・乗数レジスタ４１
１・・・・・・被乗数セレクタ、　１２・・・用剰余セ
レクタ、　１３・・・・・・出力レジスタ。 手続補正書く自発） １、事件の表示 昭和６３年特許願第１６３７６１号 ２、発明の名称 べき乗剰余演算回路 ３、補正をする者 事件との関係　　特許出願人 住　　所　　　東京都港区西新橋三丁目２０番４号名　
　称　　　日本電気エンジニアリング株式会社代表者　
　宮　城　嘉　男 ４、代理人　〒１９２　ｔ　０４２６−４４−１８０８
住　　所　　　東京都八王子市横山町２５番１６号６、
補正の対象　　　く１）「特許請求の範囲」の欄く２）
「発明の詳細な説明」の欄 本光明のＸ１文創余濱簿回路グ膚り契剖第　７　訂 別　　紙 １．特許請求の範囲 ０＜Ｍ＜ｎおよびＯ＜ｅ＜ｎなる関係にあり、かつそれ
ぞれ等しいビット長で示される整数Ｍ。 同ｅおよび同ｎを用いてＭ＠ｍｏｄｎ＝Ｃなるべき乗剰
余演算を行い剰余Ｃを求めるべき乗剰余演算回路であっ
て；　このべき乗剰余演算回路は、外部から入力される
数値Ｍが被乗数として初期設定されるとともに、その後
の演算過程で生成された剰余値と累算剰余値のいずれか
が被乗数として格納される被乗数レジスタと；　外部か
ら入力される数値ｎを除数として格納する除数レジスタ
と；前記被乗数レジスタの出力を前記除数レジスタの出
力で除算して剰余を求める剰余演算器と；　外部から入
力された数値ｅをべき乗の指数として格納する指数レジ
スタと；　外部から入力される前記数値Ｍを格納する入
力レジスタと；　前記指数レジスタの最上位ビットから
最下位ビットに至る各ビット出力に順次応答してその論
理状態に応じて前記入力レジスタと前記累算剰余値のい
ずれかを選択出力する乗数セレクタと；　前記乗数セレ
クタの出力を乗数として格納する乗数レジスタと；　前
記乗数レジスタの最下位ビットから最上位ビットに至る
各ビット出力に順次応答してその論理値が“１”のとき
は前記剰余演算器の出力を選択出力し゛Ｏ”のときはＯ
値入力を選択出力する１余セレクタと；　前記剰余セレ
クタの出力と前記累算剰余値を加算したものを前記除数
レジスタの出力で除算して剰余を求める累算剰余演算器
と；　前記累算剰余演算器の出力を格納しそれを前記累
算剰余値として出力する累算剰余レジスタと：　前記剰
余演算器の出力である前記剰余値を前記被乗数レジスタ
に対し出力するとともに、前記乗数レジスタの最上位ビ
ットについての演算が終了する度に前記累算剰余値を被
乗数レジスタに対し出力する被乗数セレクタと；　前記
指数レジスタの最下位ビットについての演算が終了した
時の前記累算剰余値を最終演算結果値として外部へ出力
する出力レジスタと；　を備えていることを特徴とする
べき乗剰余演算回路。 ２、「発明の詳細な説明」の欄 く１）明細書第３頁第１９行目のｒＲＡｓＪをｒＲ５Ａ
Ｊと訂正する。 同頁第２０行目のｒ、ＲＡＳＪを「Ｒ８Ａ」と訂正する
。 （２）明細書第４頁第６〜７行目の「５１２ビット程度
」を「２進数で４００ビツト以上」と訂正する。 同頁第８行目の「ＲＡＳ」をｒＲ９ＡＪ　と訂正する。 （３）明、［Ｆ第７頁第８行目のｒ乗余」を「剰余」と
訂正する。 （４〉明４Ｉ書第８頁第９行目の「５１２ビツト」を「
Ｑビット」と訂正する。 同頁第１２行目の「（０≦ｉ≦５１１）Ｊをｒ（ｉは０
以上の整数）」と訂正する。 同頁第１３行目の「剰余を」を「剰余Ｍ６を」と訂正す
る。 （５）明細書第９頁第５行目の［（１≦に≦５１１）Ｊ
を「（１≦に≦Ｑ）Ｊど訂正する。 同頁第１６行目の「乗合」を「剰余」と訂正する。 同頁第１７行目の「乗合」を「剰余」と訂正する。 （６）明細書第１２頁第４行目の「Ｋビット（Ｋは」を
「Ｌビット（Ｌは」と訂正する。 同頁第１４行目の「５１２ビツト」を「Ｑビット」と訂
正する。 同頁第１５行目のｒＲＡｓＪをｒＲ８ＡＪと訂正する。 （７）明細書第１４頁第４行目の「５１２ビツト」を「
Ｑビット」と訂正する。 同頁第１１行目の「左に１ビツトシフトした５１３ビツ
トの形で」を削除する。 同頁第９行目の「５１４ビツト目が」を「最上位ビット
が」と訂正する。 同頁第１１行目の「５１４ビツト目が」を「最上位ビッ
トが」と訂正する。 同頁第１９行目のｒ　２”Ｍ　Ｊを「２Ｑ−ＩＭ」と訂
正する。 （８）明細書第１５頁第１４行目の「５１４ビツト目」
を「最上位ビット」と訂正する。 同頁第１６行目の「５１４ビツト目」を「最上位ビット
」と訂正する。 同頁下１９行目のｒ５１２Ｊを’ＱＪと訂正する。 （９）明細書第１８頁第１３行目のｒ５１２４を’ＱＪ
と訂正する。 同頁第５行目のｒ　５１１１を’Ｑ−ＩＪと訂正する。 同頁下１９行目のｒ’１ｔｔｘ　２　＝　１０２２回」
をｒ　（Ｑ−１）Ｘ２＝２　（Ｑ−１）回」と訂正する
。 同頁箱２０行目のｒ　５１２Ｊを「Ｑ」と訂正する。 （１０）明細書第１９頁第１行目のｒ　５１２Ｊを’Ｑ
Ｊと訂正する。 同頁第１〜２行目のｒ　１０２２Ｘ　５１２　＝　５２
３２６４回」をｒ２　（Ｑ−１）ＸＱ＝２Ｑ　（Ｑ−１
）回」と訂正する。 同頁第５行目のｒＫ　（Ｋは」をｒＬ　（Ｌは」と訂正
する。 同頁箱８〜１３行目の「即ち、・・・・・・認められる
のである。」を削除する。 同頁第１６行目のｒ、ＲＡＳＪをｒＲ３ＡＪと訂正する
。 （１１）明細書第２０頁第６行目の「Ｋビット（Ｋは」
を「Ｌビット（Ｌは」と訂正する。 以上

Claims (1)

【特許請求の範囲】
1. ０＜Ｍ＜ｎおよび０＜ｅ＜ｎなる関係にあり、かつそれ
   ぞれ等しいビット長で示される整数Ｍ、同ｅおよび同ｎ
   を用いてＭ＾ｅｍｏｄ　ｎ＝Ｃなるべき乗剰余演算を行
   い剰余Ｃを求めるべき乗剰余演算回路であって；このべ
   き乗剰余演算回路は、外部から入力される数値Ｍが被乗
   数として初期設定されるとともに、その後の演算過程で
   生成された剰余値と累算剰余値のいずれかが被乗数とし
   て格納される被乗数レジスタと；外部から入力される数
   値ｎを除数として格納する除数レジスタと：前記被乗数
   レジスタの出力を前記除数レジスタの出力で除算して剰
   余を求める剰余演算器と；外部から入力された数値ｅを
   べき乗の指数として格納する指数レジスタと；外部から
   入力される前記数値Ｍを格納する入力レジスタと；前記
   指数レジスタの最上位ビットから最下位ビットに至る各
   ビット出力に順次応答してその論理状態に応じて前記入
   力レジスタと前記累算剰余値のいずれかを選択出力する
   乗数セレクタと；前記乗数セレクタの出力を乗数として
   格納する乗数レジスタと；前記乗数レジスタの最下位ビ
   ットから最上位ビットに至る各ビット出力に順次応答し
   てその論理値が“１”のときは前記剰余演算器の出力を
   選択出力し“０”のときは０値入力を選択出力する乗余
   セレクタと；前記剰余セレクタの出力と前記累算剰余値
   を加算したものを前記除数レジスタの出力で除算して剰
   余を求める累算剰余演算器と前記累算剰余演算器の出力
   を格納しそれを前記累算剰余値として出力する累算剰余
   レジスタと前記剰余演算器の出力である前記剰余値を前
   記被乗数レジスタに対し出力するとともに、前記乗数レ
   ジスタの最上位ビットについての演算が終了する度に前
   記累算剰余値を被乗数レジスタに対し出力する被乗数セ
   レクタと；前記指数レジスタの最下位ビットについての
   演算が終了した時の前記累算剰余値を最終演算結果値と
   して外部へ出力する出力レジスタと；を備えていること
   を特徴とするべき乗剰余演算回路。