JPS63229531A - 剰余演算装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、暗号理論や符号理論の演算に用いられる剰余
演算を実行する剰余演算装置に関するものである。

従来の技術 暗号理論や符号理論における演算では剰余系の演算がし
ばしば用いられる。例えば公開鍵暗号として知られてい
るＲ８Ａ暗号においてはべき乗剰余演算が用いられる。

べき乗剰余演算は剰余乗算を基本とする演算である。こ
こで剰余乗算は１語長の大きな３つの正の整数ａ、ｂお
よびｎに対して、積ａ−ｂを整数ｎで割った剰余を求め
ることである。そして剰余乗算のような演算を高速に行
なうためには以下のような演算が基本となり、この演算
を繰り返して行なうことが求められる。

即ち ：１−Ｘ　−ａ　ＭＯＤ　ｎ　　　　・　・　・　・　
（１）ここで、ａ、１はそれぞれ５１２ビツトで表わさ
れる正の整数とし、整数ａを整数ｎで割った剰余をａ　
　ＭＯＤ　　ｎ’で表わす、また法となる整数ｎは ２　　＜＝ｎ＜２　　　　　　　・・・・（２）に正規
化されており、整数ａは予め ａ＜ｎ　　　　　　　　　　　・・・・（３）とされて
いるものとする。

（１）式のような演算を行なう場合に、”Ｘ・ａ”の値
がｎ以上の大きな数となった場合にＸ・ａからｎを繰り
返し減算することが必要となり。

この演算が高速に実行できないという問題があった。そ
こで従来、ｘ”ａのうち２５１１以上の部分の剰余を予
め計算しておいてメモリに格納しておき、このメモリに
格納された剰余とｘ”ａのうち２６１１より小さい部分
の加算を行なう方法が提案されている。この加算結果が
ｎ以上となった場合はその結果から１回だけｎを減算す
ればよい。

以下に図面を参照してこの従来の剰余演算装置を説明す
る。ここではｘ＝２０で表わされるものとする。

第６図はこの従来の、Ｃ＝２の場合の剰余演算を実現す
る剰余演算装置を示すブロック図である・第６図におい
て、１は被演算数ａもしくは演算の途中結果ａ１を格納
する５１３ビツトのレジスタ、２はレジスタ１の内容ａ
ｌを４倍、即ち２ビツト左シフトする左シフタ、３は左
シフタ２の出力５１５ビツトのうち上位４ビツトを上位
から順にｊ３＋　ｔｇ、ｔｌ＋　ｔｏとするとき、この
４ビツトをアドレスとして ｔ＝　ｔ３．２””ｔ＋ａ、２””ｔ＋、２”””ｔｏ
、２”’・・・・（４） をｎで割った剰余ｒを格納しておくメモリ、４は左シフ
タ２の下位５１１ビツトａ８とメモリ３の内容ｒを加算
する加算器、５は法とする整数ｎを保持する法レジスタ
、６はレジスタ１の内容ａｌから法レジスタの内容ｎを
減算する減算器、７は減算器の出力”ａｌ　　ｎ″が正
またはＯのときは減算器７の出力を選択し、減算器の出
力”ａｌ−ｎ”が負のときはレジスタ１の内容ａ＋を選
択して出力するマルチプレクサ、８はマルチプレクサ７
の出力を保持するレジスタである。

以上のように構成された従来の剰余演算装置においては
、まず５１２ビツトで表わされる被演算数ａを５１３ビ
ツトのレジスタ１に格納し、５１２ビツトで表わされる
法ｎを法レジスタ５に格納する。左シフタ２においては
レジスタ１の内容ａを２ビツト左にシフトし４ａを得る
。左シフタ２の出力５１５ビツトのうちの上位４ビツト
をアドレスとしてメモリ３をアクセスしくこの時最上位
ビットはＯである）（４）式の値ｔをｎで割った剰余ｒ
を得る。また左シフタ２の出力５１５ビツトのうちの下
位５１１ビツトａｓはそのまま加算器４に出力する。加
算器４においてはメモリ３の内容ｒと左シフタ２の出力
の下位５１１ビツトａｓを加算し加算結果をレジスタ１
に出力する。

ここで、メモリ３の内容ｒは２６目以上の値を法ｎで割
った剰余であるから ｒ＜ｎ　　　　　　　　　　・・・・（５）であり、ｎ
は（２）式のように正規化されているから左シフタ２の
出力の下位５１１ビツトａ８はａ８くｎ　　　　　　　
　　　　ｅ・・・　（６）を満たす。したがってレジス
タ１に出力された加算器４の加算結果ａ１は ａ＋＝ｒ＋ａ＠＜２ｎ　　　　　＊　ａ　ａ　＃　　（
７）となり、この結果は２　ａをｎで割った剰余系の数
であって５１３ビツトで表わされる数となる。

なお、最終的な剰余 ２２ａ　　ＭＯＤ　　ｎ　　＜ｎ を得るために以下の補正を行なう。即ち、減算器６でレ
ジスタ１の値ａ！から法レジスタ５の内容ｎを減算し”
ａｌ　　ｎ”を求める。マルチプレクサ７においては、
その結果が正またはＯならばその減算結果を選択し、負
ならばレジスタ１の内容ａ＋を選択してレジスタ８に出
力する。このようにしてレジスタ８には ａ＝２２ａ　　ＭＯＤ　　ｎ の最終結果が得られる。

さらに（１）式を繰り返して行なうためには第６図の回
路が繰り返し用いられる。即ち、（７）式で与えられた
５１３ビツトのレジスタ１の内容ａ１は再び左シフタ２
に出力される。左シフタ２においてはレジスタ１の内容
ａｔを２ビツト左にシフトし４ａ＋を得、その出力５１
５ビツトのうちの上位４ビツトをアドレスとしてメモリ
３をアクセスする。メモリ３によって値ｔをｎで割った
剰余ｒが与えられ、また左シフタ２の出力５１５ビツト
のうちの下位５１１ビツトａ８はそのまま加算器４に入
力される。加算器４においてはメモリ３の内容ｒと左シ
フタ２の出力の下位５１１ビツトａ８を加算しその加算
結果をレジスタ１に出力する。従って、ここでレジスタ
１の値を再びａｌとおけば、上記した議論と同様にレジ
スタ１の内容ａ＋は ａ＋＜２ｎ を満たし、かつ２４ａをｎで割った剰余系の数となって
いる。

このようにしてこの回路を繰り返し用いることにより（
１）式を繰り返して実行することができる。そして最終
段階に当たってのみ減算ｒＡ６及びマルチプレクサ７を
用いて上記した補正を行ない、最終の剰余はレジスタ８
に与えられろ。

発明が解決しようとする問題点 しかしながら上記のような構成では、メモリ３において
、４ビツトのアドレスに対して、（４）式で与えられる
値ｔを法ｎで割った剰余ｒとして最大１５通り必要であ
り、また各ワードは５１２ビツトという長語長なためメ
モリ容量が大きくなってしまうという問題点を有してい
た。

本発明はかかる点に鑑み。

ａ＝ｘ−ａ　ＭＯＤ　ｎ を繰り返して行なう剰余演算を高速に、かつ使用するメ
モリを従来の半分程度もしくはそれ以上に減することの
できる剰余演算装置を提供することを目的とする。

問題点を解決するための手段 本発明は、与えられた被演算数ａを定数Ｘ倍した値ａ”
ｘを予め定められた整数ｎで割った剰余を与える剰余演
算装置であって、上記被演算数を入力するレジスタと、
上記レジスタの値を定数Ｘ倍する倍数器と、上記倍数器
の出力のうち上記整数ｎの桁数以上の桁の部分の値を上
記整数ｎで割った商に関する情報を予め保持するメモリ
と。

上記メモリに保持された情報を用いて上記倍数器の出力
から上記の商と上記整数の法との積を減算した値を出力
する演算器とを備えた剰余演算装置である。

作用 本発明は上記した構成により、上記レジスタに被演算数
ａが代入されると上記倍数器はその値を定数Ｘ倍し、上
記メモリは上記倍数器の出力のうち整数ｎの桁数以上の
桁の部分の値を整数ｎで割った商に関する情報を予め保
持しておき、上記演算器は上記メモリに保持された情報
を用いて。

上記倍数器の出力から上記の商と整数ｎの積を減じた値
を求め、必要であればその値を再び上記レジスタに出力
する。本発明は上記倍数器の出力のうち整数ｎの桁数以
上の桁の部分の値の剰余を得るに当たり、メモリが剰余
を直接持つのではな（商に関する情報を保持しておくこ
とでメモリの有効活用を図るものである。

実施例 第１図は本発明の第１の実施例におけるＣ＝２の場合の
（１）式を実行する剰余演算装置のブロック図である。

第１図において、１は被演算数ａもしくは演算の途中結
果ａ１を格納する５１３ビツトのレジスタ、２はレジス
タ１の内容を４倍、即ち２ビツト左シフトする左シフタ
、３は左シフタ２の出力の上位４ビツトをｊ３ｒ　ｔ、
、ｔ＋＋ｔｏとしたときに ｔ　＝　ｔ３・２””ｔ２・２””ｔ＋・２””ｔｏ・
２”’・・・・（４） をｎで割った商をｑとすると、この４ビツトをアドレス
として商ｑと法ｎのｆＩｔｑ−ｎを格納するメモリ、４
は左シフタ２の５１５ビツト出力からメモリ３の内容ｑ
’ｎを減算する減算器、５は法とする整数ｎを保持する
法レジスタ、６はレジスタ１の内容ａ１から法レジスタ
５の内容ｎを減算する減算器、７は減算器の出力”ａ＋
　　ｎ’が正または０のときは減算２９７の出力を選択
し、減算器の出力”ａ＋　　ｎ”が負のときはレジ、ス
タ１の内容ａ１を選択して出力するマルチプレクサ、８
はマルチプレクサ７の出力を保持するレジスタである。

以上のように構成された本実施例の剰余演算装置につい
て以下その動作を説明する。

まず５１２ビツトで表わされる被演算数ａを５１３ビツ
トのレジスタ１に格納し、５１２ビツトで表わされる法
ｎを法レジスタ５に格納する。左シフタ２においてはレ
ジスタ１の内容ａを２ビツト左にシフトし４ａを得る。

左シフタ２の出力５１５ビツトのうちの上位４ビツトを
アドレスとしてメモリ３をアクセスしくこの時最上位ビ
ットは０である）メモリ３は（４）式の値ｔをｎで割っ
た商ｑと法ｎとの積ｑ’ｎを出力する。また左、シフタ
２の出力４ａはそのまま減算器４に出力する。減算器４
においては左シフタ２の出力４ａからメモリ３の出力Ｑ
”ｎを減算しその結果”４ａ−ｑ’ｎ”をレジスタ１に
出力する。

ここで、左シフタ２の出力４ａの下位５１１ビツトをａ
ｓとおき、（４）式のｔをｎで割った剰余をｒとお（と
、以下の式が成り立つ。即ち。

４ａ＝ｔ＋ａ　　　　　・・・・（８）ｔ＝ｑ＠ｎ＋ｒ
　　　・・−−（９） （８）（９）式より ４ａ＝ｑ−ｎ＋ｒ＋ａ８ 、’、４ａ−ｑ　ｍｎ＝ｒ＋ａｓ　　・・・（１０）ｒ
及びａｓは上記従来例で示した物と同一であるから（６
）式によりレジスタ１に格納された減算器４の出力ａｌ
は ａ＋＝４ａ−ｑ　ａｎ＝　ｒ＋ａａ＜２ｎ　・・（１１
）この結果は２２ａをｎで割った剰余系の数であって５
１３ビツトで表わされる数となる。

なお、最終的な剰余 ２２ａ　　ＭＯＤ　　ｎ　　＜ｎ を得るためには以下の補正を行なう。即ち、減算器６で
レジスタｌの値ａ＋から法レジスタ５の内容ｎを減算し
”ａ＋ｎ”を求める。マルチプレクサ７においては、そ
の結果が正またはＯならばその減算結果を選択し、負な
らばレジスタ１の内容ａ１を選択してレジスタ８に出力
する。このようにしてレジスタ８には ａ＝２”ａ　　ＭＯＤ　　ｎ の最終結果が得られる。

さらに（１）式を繰り返して行なうことを考える。（１
１）式で与えられた５１３ビツトのレジスタ１の内容ａ
ｔ＜２ｎは再び左シフタ２に出力される。左シフタ２に
おいてはレジスタ１の内容ａ＋を２ビツト左にシフトし
４ａ＋が得られる。ここで４ａ＋は（１１）式より ｔ＜４ａ＋＜８ｎ＜２　　・・・・（１２）であること
に注意しなければならない。その出力４ａ＋の５１５ビ
ツトのうちの上位４ビツトをアドレスとしてメモリ３を
アクセスする。メモリ３によって値ｔをｎで割った商ｑ
と法ｎの積ｑ’ｎが与えられる。ところが（１２）式よ
り。

ｔ＝ｑＩＩｎ＋ｒく８ｎ　・・・５（１３）であるから
メモリ３はｎ＝０〜７の８ワードが必要なだけである。

左シフタ２の出力５１５ビツトはそのまま減算＆＋に与
えられる。減算器４においては左シフタ２の出力４ａ＋
からメモリ３の内容ｑ”ｎを減算しその結果”４ａ＋−
ｑ−ｎ”をレジスタ１に出力する。従って、ここでレジ
スタ１の値を再びａｌとおけば上記した議論と同様にレ
ジスタ１の内容ａ１は ａ＋＝４ａ＋　　　　ｑｎ＜２ｎ を満たし、かつ２２ａをｎで割った剰余系の数となって
いる。

このようにしてこの回路を繰り返し用いることにより（
１）式を繰り返して実行することができる。そして最終
段階に当たってのみ減算器６及びマルチプレクサ７を用
いて上記した補正を行ない、最終の剰余はレジスタ８に
与えられる。

以上のように本実施例によれば、左シフタ２の上位４ビ
ットｔ３．ｊｇ＋　ｊ＋＋　ｊｏ＋に対し、（４）式の
値ｔをｎで割った。商をｑとすると、この４ビツトをア
ドレスとしてメモリ３に積ｑ’ｎを格納し、また減算器
４において左シフタ２の値がらメモリ３の出力を減じる
ようにしたことにより、メモリ３の容量は８ワード×５
１５ビツト＝４１２０ビツトとなり、上記従来例におけ
るメモリに必要な容量１５ワード×５１２ピッｌ−＝　
７６８０ビツトと比べてほぼ半分とすることができる。

以下にメモリ二３の内容を明らかにするために適当なビ
ット数を用いて本発明を説明する。第２図は被演算数ａ
及び法ｎをそれぞれ８ビツトとしたときの本発明の第２
の実施例におけるＣ＝２の場合のく１）式を実行する剰
余演算装置のブロック図である。第２図においては各ブ
ロックのビット数を除いて、構成、動作とも第１図と全
（同一である。第３図は第２図における法レジスタ５．
レジスタ１．２ビット左シフタ２．メモリ３．減算器４
のビットの対応関係を示すビット対応説明図である。本
実施例において左シフタ２の出力の１１ビツトのうち上
位４ビツトを上位から順にｔｊ。

ｊ２＋　　ｊｌ＋　　ｊＱ＋とするとき、この４ビツト
をアドレスとしてメモリ３がアクセスされる。

ｔ−ｔ　３・２６＋ｔ２・２５＋ｔ＋・２’＋　ｔｏ・
２３・　・　・　・　（１４） に対して、ｔを法ｎで割った商をｑとすると、メモリ３
には、ｆｆ１ｑ−ｎが８ワード格納されている。

第４図は、第３図におけるアドレスｔ３ｒ　ｔＺ＋ｔ＋
、ｔｏに対して、（１４）式で与えられる値ｔと、ｔを
法ｎ　（ｎ＝２５５とｎ＝２２１とする）で割った商ｑ
と、剰余ｒ及び積ｑ’ｎを示したメモリ３のアドレス−
データ対応図である。第４図を参照すると、従来例のよ
うに、アドレスｔ３．ｔｐ、、ｔ＋、ｔｏに対してｔを
ｎで割った剰余ｒを持つ方式では、剰余ｒがアドレスに
対応して最大１５通り必要であるのに対して１本実施例
のようにメモリ３がｔをｎで割った商ｑに対応してｆａ
　ｑ・ｎを持つ方式では商ｑが各アドレスに対して重複
することがあるため４ビツトのアドレスに対しても最大
８通りの値を持つだけでよい。このことは（１３）式で
しめしたようにｔ＝ｑ−ｎ＋ｒが８ｎより小さいことに
起因するものである。

以上のように本実施例では、従来例のように値ｔを法ｎ
で割った剰余ｒを持つ方式では１５ワード×８ビツト＝
１２０ビツト必要だったメモリ容量を、８ワード×１１
ビット−８８ビツトとすることができる。

一般に、被演算数ａ及び法ｎをそれぞれにビットとした
とき本実施例における剰余演算装置においては、従来例
のようにｔをｎで割った剰余ｒを持つ方式では（２”２
−１　）ワード×にビット必要だったメモリ容量を　２
　ｃ　＋　１ワード×（ｋ＋３）ビットとすることがで
きる。

なお、第１の実施例の説明において商ｑがＯのときにメ
モリ３内にｑ−ｎ−０・ｎとして５１５ビツトを格納す
るとしているが、このときには減算８４において減算を
しないようにするなど例外処理をすることによりｑ−ｎ
−Ｏ−ｎなる５１５ビツトを削減することができる。

また、第１の実施例の説明において商ｑが１のときにも
メモリ３内にｑ−ｎ＝１・ｎとして５１５ビツトを使用
するとしているが、このときには減算器４においてメモ
リ３からの出力ではなく法レジスタ５の値を減じるよう
−にするなど例外処理をすることによりｑ−ｎ＝１・ｎ
なる５１５ビツトを削減することができる。

また、第１の実施例の説明において商ｑが２゜４のとき
にもメモリ３内にｑ’ｎとして５１５ビツトを使用する
としているが、このときには減算器４においてメモリ３
からの出力ではな（法レジスタ５を１ビツトもしくは２
ビツト左にシフトした値を減じるようにするなど例外処
理をすることによりｑ−ｎ＝２・ｎ、４・ｎ、なる１０
３０ビツトを削減することができる。

このような簡単な例外処理を行なうことにより、第１の
実施例のメモリ３の容量は４ワード×５１５ビット−２
０６０ビツトとすることができ、上記従来例で必要であ
ったメモリ容量７６８０ビツトに比べ半分以下と著しく
減少させることができる。

さらに、第１の実施例においてメモリ３は、アドレスｔ
３＋　ｊｚ＋　ｊ＋＋　ｔｏに対して値ｔをｎで割った
商ｑに従ってｑ”ｎを保持するとしたが。

そのかわりに商ｑのみを保持するようにし１乗算器を用
いてその出力ｑと法ｎを乗算し積ｑ”ｎを求めるように
してもよい。

第５図は本発明の第３の実施例におけるＣ＝２の場合の
（１）式を実行する剰余演算装置のブロック図である。

第５図においてはブロック番号ｌから８の同一番号のブ
ロックについては構成。

動作とも第１図と同一である。９は左シフタ２の出力の
上位４ビツトをアドレスとして（４）式で与えられる値
ｔを！１で割った商ｑを格納するメモリ、１０はメモリ
９の出力である商ｑ（３ビツト）と法レジスタ５の内容
ｎ　（５１２ビツト）を乗算して積ｑ”ｎを出力する３
ビツト×５１２ビツトの乗算器である。このようにする
と、商ｑは高々７までの値なので９乗算器１０（一般に
３ビツト×にビットを実行する乗算器）が必要となるも
のの、メモリ９のメモリ容量は８ワード×３ビツト＝２
４ビツトを持つだけでよい。

このように１本第３の実施例においては極めて少ないメ
モリ容量で（１）式の剰余演算を実行することができる
。またこのようにメモリ容量が少なくなると、従来必要
であったような数にビットにわたる大量のデータを予め
外部から本装置内のメモリに転送・格納する手順を小さ
くすることができ、従って法となる整数ｎが変更された
場合にも柔軟に対応することができる。このような効果
は、メモリに、左シフタ２の出力の上位４ビツトをアド
レスとして（４）式で与えられる値ｔをｎで割った剰余
ｒを格納するのではな（商ｑを格納する本発明の主旨に
起因するものである。

発明の詳細 な説明したように２本発明によれば。

ａ＝ｘａａ　ＭＯＤ　ｎ を繰り返して行なう剰余演算を、高速に、かつ使用する
メモリを従来の半分程度もしくはそれ以上に著しく減す
ることのできる剰余演算装置を提供することができ、そ
の実用的効果はきわめて大きいものである。

【図面の簡単な説明】

第１図は本発明における第１の実施例の剰余演算装置の
ブロック図、第２図は本発明における第２の実施例の剰
余演算装置のブロック図、第３図は第２の実施例の剰余
演算装置におけるレジスタのビット対応説明図、第４図
は第２の実施例の剰余演算装置のメモリ３におけるアド
レス−データ対応図、第５図は本発明における第３の実
施例の剰余演算装置のブロック図、第６図は従来の剰余
演算装置のブロック図である。 １・・・レジスタ、２・・・左シフタ、３，９・・・メ
モリ、４・・・減算器、１０・・・乗算器。 代理人の氏名　弁理士　中尾敏男ほか１名第１ｒｌＡ 第２図 第３図 レジスフ１　　　　口＝＝＝＝＝＝＝＝コ（ｈ　＜　２
７１第４図 ｔへ８・７（ｔｒ＜１Ｊ７１ 第５図

Claims (2)

【特許請求の範囲】
1. （１）与えられた被演算数ａを定数ｘ倍した値ａ・ｘを
   予め定められた整数ｎで割った剰余を得る剰余演算装置
   であって、上記被演算数ａを保持するレジスタと、上記
   レジスタの値を定数ｘ倍する倍数器と、上記倍数器の出
   力のうち上記整数ｎの桁数以上の桁の値を上記整数ｎで
   割った商と上記整数ｎの積を格納するメモリと、上記倍
   数器の出力から上記メモリに格納された積を減算する演
   算器とを備えたことを特徴とする剰余演算装置。
2. （２）与えられた被演算数ａを定数ｘ倍した値ａ・ｘを
   予め定められた整数ｎで割った剰余を得る剰余演算装置
   であって、上記被演算数ａを保持するレジスタと、上記
   レジスタの値を定数ｘ倍する倍数器と、上記倍数器の出
   力のうち上記整数ｎの桁数以上の桁の値を上記整数ｎで
   割った商を格納するメモリと、上記メモリの内容と上記
   整数ｎの積を与える乗算器と、上記倍数器の出力から上
   記乗算器の出力を減算する演算器とを備えたことを特徴
   とする剰余演算装置。