JPS63200183A - 分割整数剰余計算機 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔目次〕 概要 産業上の利用分野 従来の技術　（第４図、第５図） 発明が解決しようとする問題点 問題点を解決するための手段　（第１図）作用　（第２
図） 実施例　（第３図） 発明の効果 〔概要〕 本発明は分割整数剰余計算機において、剰余テーブルと
加算器および引算器を並列接続することにより、多数桁
の整数の剰余を高速演算処理により求めようとするもの
である。

〔産業上の利用分野〕

本発明は多数桁の整数値の剰余を分割処理して求める分
割整数剰余計算機に関し、特に数理形式の暗号処理分野
で利用されるべき乗剰余計算アルゴリズムを高速処理す
るために、剰余テーブルと加算器を使用して並列の剰余
計算を行い高速で正確な剰余計算を実現するようにした
分割整数剰余計算機に関する。

例えば商用通信の分野では、機密情報を通信する場合、
第三者による盗聴行為を防止するために、暗号処理技術
が多用されている。最近の商用暗号通信では、情報を暗
号化するための鍵と暗号化情報を復号化するための鍵が
異なる公開鍵暗号系が出現した。

この暗号系では、受信者（データを復号化する者）は予
め送信者（データを暗号化する者）へ公開鍵を送り、こ
の鍵によって送信情報を暗号化して送ってもらい、受信
者はこの情報を公開鍵と対になる秘密の復号鍵によって
復号化する。このためのアルゴリズムとしていわゆるＲ
３Ａ法が公知である。

このＲ５Ａ法は、Ｒｍ　Ｘ”　　（ｓｏｄ’　ｐ　）（
ＲはメツセージＸの暗号文、αは暗号化の鍵、ｐは合成
数） なる乗剰余針算によって暗号処理が達成される。

即ち送信者がＸＣＸ−なる被除数をＰなる除数で割った
剰余Ｒを暗号文とする。

これを受信者はＸ＝Ｒｄ　　（ｓｏｄ　ｐ　）によって
メツセージＸを復号化する（ここでｄは暗号文Ｒの秘密
の暗号鍵である）。

かかる暗号系では解読を困難とするためには除数Ｐが１
０進１５０桁程度の大きな値の場合、剰余Ｒをいかに高
速で算出するかということが問題となる。

〔従来の技術〕

従来、この剰余Ｒを算出するため、第４図に示す如く、
被除数Ｘ（第４図では例えば１０２４ｂｉｔ）を分割す
べき桁ごとに設けられた剰余テーブルト１．１・２−・
・１・３３：２・１．２・２−・−・２・３３；１２８
・１．１２８・２−１２８・３３が記入されるメモリ１
．２．３・−３２と、加算器３４．３５・・・・・６６
及び比較器６７．６Ｂ、６９−・９９を設ける。

先ずレジスタ１００に入力した被除数Ｘを各桁に分解し
、次いで分解した各桁の数値をアドレスとして上記剰余
テーブルト１〜１２８・３２を索引し、更に索引した各
テーブル内容を上記加算器３４．３５・−・６６により
すべて加算する。また比較器６７．６８−・−・９９に
は所定の除数Ｐが付加されているので、この比較器６７
、・・−・９９により前記加算器３４．３５・−・６６
における加算結果と比較する。

このとき該加算結果が除数Ｐよりも小であればその加算
結果を剰余Ｒとして出力する。しかし加算結果が該除数
Ｐより大であれば、その加算結果で再びメモリ１，２・
・−・３３内の剰余テーブルを索引し、この加算結果が
除数Ｐより小になるまでこのような処理を行う、このよ
うにして高速で剰余計算を行うことができる。

なお、剰余テーブルを索引する前記剰余計算をわかり易
＜１０進で説明すれば、第５図の如くなる。いま例えば
被除数ｒ２５３９６５０１Ｊを除数ｒ５０３９Ｊで除算
したときの剰余Ｒを求める場合、剰余テーブルとして１
０００万桁のテーブルと、１００万桁のテーブルと、１
０万桁のテーブルと、１万桁のテーブルと、干拓のテー
ブルを用意し、そのアドレス１〜９にそれぞれの数値を
除数ｒ５０３９Ｊで除算したときの剰余を記入しておく
。例えば１０００万桁のテーブルの２の領域には、２０
００万つまり２Ｘ１０７を５０３９で除算したときの剰
余ｒ０２０９Ｊを記入し、１００万桁のテーブルの５の
領域には５Ｘ１０Ｇを同じ＜５０３９で除算したときの
剰余ｒｌ　３１２」を記入しておく。

そして前記被除数をそれぞれ１０００万の桁〜１の桁に
分解し、１０００万の桁「２」で１０００万桁のテーブ
ルをアクセスしてｒｏ　２０９Ｊを得、以下同様に、１
００万桁のテープルー千桁のテーブルをアクセスしてｒ
ｌ　３１２Ｊ、「２６９９」、ｒ４３３７Ｊ、ｒｏ　９
８１Ｊを得る。そしてこれらの数と、剰余テーブルをア
クセスしない下３桁の５０１を加算して１００３９を得
る。これは除数５０３９より大きいのでこれを更に各桁
に分解して前記剰余テーブルを索引して５０００を得、
これが求める剰余となる。

なお、第４図において剰余テーブル（１・１）〜剰余テ
ーブル（１・３２）は、最上位桁をｏ。

０１とし残り下位をすべて０とするデータから、最上位
桁を１１１１とし下位桁すべて０とする２進データまで
の値（１０２４ビツト）を所定の除数（１・５１２ビツ
ト）で割ったときの剰余が横一列に書き込んであり、（
２・１）〜（２・３２）から（１２８・１）〜（１２８
・３２）についても同様に各桁の剰余が書き込まれてお
り、上位５１２ビツトのすべての剰余が索引できるよう
になっているものである。

〔発明が解決しようとする問題点〕

ところで第４図に示す如き分割整数計算機では、再び剰
余テーブルト１〜１２８・３２を引くかどうかを各加算
器３４〜６６の出力を比較器６７〜９９で除数Ｐと比較
するだけで決めているため、加算器３４〜６６の出力（
被除数Ｘ）の桁数が除数Ｐと同じであり、かつＸ＞Ｐの
とき、下記の如く剰余計算が終了せず、剰余テーブルを
引き続けるという問題点を有していた。

これを１０進の状態で説明すると、例えば被除数Ｘ−５
０６０で除数Ｐ−５０３９の場合、子桁のテーブルを索
引しても５０００が出力され、また除数より桁数の小さ
い下３桁はそのままシフトダウンされ、これらが加算さ
れて再び５０６０となり、これが繰返されるのみであり
剰余計算が終了しないものとなる。

したがって本発明の目的は、このような問題点を改善し
た、被除数がいかなる場合でも剰余Ｒを求めることがで
きる分割整数剰余計算機を提供することである。

〔問題点を解決するための手段〕

前記目的を達成するため、本発明では、第１図に示す如
（、剰余テーブルト１〜１２８・３２が設けられたメモ
リ１．２・−・３２と加算器３４．３５−・６５と、減
算器１０１．１０２−・−・１３２と、判定部１４０を
設ける。この判定部１４０は減算結果の正負を判定する
ものである。

なお剰余テーブルト１〜１２８・３２及び加算器３４．
３５・−・６５は前記第４図について説明したものと同
一である。

なお、第１図においてアドレス発生部１４１は各メモリ
１．２−・−３２の剰余テーブルの横の列（１・１）〜
（１・３２）、（２・１）〜（２・３２）−・・・、（
１２８・１）〜（１２８・３２）のいずれかを選択する
アドレスを発生するものであり、例えばアドレス発生部
１４１が剰余テーブルト１．１・２・−１・３２を選択
するアドレスを出力するときセレクタ１４２は被除数Ｘ
の最上位４ビツト（この例ではＥ）を出力し、剰余テー
ブル２・１２・２、・−・２・３２を選択するアドレス
を出力するとき被除数の最上位の次の４ビツト（この例
ではＯ）を出力し、剰余テーブル１２８・１．１２８・
２・−・１２８・３２を選択するアドレスを出力すると
き剰余テーブルをアクセスする桁の最下位の４ビツト（
この例ではＦ）を出力する。

〔作用〕

まず入力した被剰数Ｘを各桁に分解し、次いで分解した
各桁の数値をアドレスとしてその桁に対応した上記剰余
テーブルを索引する。そしてこの索引した各剰余テーブ
ルの内容を上記加算器３４．３５．３６・・・−・６５
により、シフトダウンした各桁の値とともにすべて加算
する。この加算結果を上記減算器１０１．１０２．１０
３・−・−・１３２によりこれらに付与されている所定
の除数Ｐを減算する。

この減算結果が判定部１４０にて判定される。減算結果
が正であれば、この減算結果を再度各桁に分解し、前記
と同じ操作を行って剰余テーブルト３２を索引し、各テ
ーブルの内容を再び加算し、この加算結果から再度除数
を減算する。これを減算結果が負になるまで繰返す、も
し減算が負であればその減算直前の加算結果を剰余Ｒと
して出力する。

これをわかり易く、１０進数で説明すれば、第２図のよ
うになる０例えば被除数Ｘ−２５３９６５０１を除数Ｐ
−５０３９で除算したときの剰余Ｒを求める場合、除数
の最上位と同じ桁（この場合は千の桁）までを各桁に分
解する。これにより子桁までは２Ｘ１０７．５Ｘ１０６
．３Ｘ１０５．９Ｘ１０”、６Ｘ１０”に分解される。

そして前記第５図と同様に１０７つまり１０００万桁の
剰余テーブルを２で索引して２０９を得、１０Ｂ桁の剰
余テーブルを５で索引して１３１２を得、１０５桁の剰
余テーブルを３で索引して２６９９を得、１０”桁の剰
余テーブルを９で索引して４３３７を得、１０３桁の剰
余テーブルを６で索引して９８０を得、これらの各剰余
と、剰余テーブルをアクセスせずにシフトダウンした５
０１を加算器で加算して剰余１００３９を得る。そして
減算器でこの剰余１００３９−５０３９の減算を行い、
その結果の５０００の正負を判定部１４０で判定する。

この判定結果が正なので、その最上位桁の数値５により
１０３桁の剰余テーブルを索引して５０００を得、シフ
トダウンした０００を加算した５０００より再び５０３
９を減算する。この結果は負になるので、この負の減算
のときの被除数５０００を求める剰余Ｒとして出力する
ことになる。なお判定部１４０の出力は、図示省略した
、ＣＰＵのような制御部に送出される。

このようにして本発明によれば、減算器における減算結
果を用いて剰余テーブルを索引するため、剰余Ｐと同じ
桁でｘ＞ｐとなる加算結果はＸ−Ｐ−Ｘ　’としてテー
ブル索引されることになるが、このような減算の繰返し
によりＸ′が負となり、必ず剰余を算出することができ
る。

〔実施例〕

本発明の一実施例を第３図により説明する。

図中、他国と同符号部分は同一部分を示す。

被除数Ｘは１０２４ビツトであり、除数Ｐは５１２ビツ
トとする。入力したデータである被除数Ｘを上位より１
６ビツト毎に分割して、レジスタＲＥＧＩ、ＲＥＧ２−
・・ＲＥＧ６４に入力する。

メモリ１．２・−３２は、第１図に示す如く、剰余テー
ブル（ｌ・１〜１２８・１）、（１・２〜１２８・２）
・・・・・（１・３２〜１２８・３２）を格納するメモ
リである。これらのメモリ１．２・−・３２は読出し、
書込み共に可能であり、各メモリ１．２−・３２に格納
されている前記剰余テーブル（１・１〜１２８・１）、
（１・２〜１２８・２）・−・（１・３２〜１２８・３
２）は、４ビツトがアドレスで１６ビツトがデータのも
のである。

これらの剰余テーブル（１・１〜１２８・１）、（１・
２〜１２８・２）−・（１・３２〜１２８・３２）は予
めの準備しておくが、この場合、最上位桁分解に対する
テーブル内容は最上位桁を０００１とし残り下位をすべ
てＯとするデータから最、　上位相を１１１１とし下位
桁すべてＯとする２進データまでの値（１０２４ビツト
）を所定の除数Ｐ（５１２ビツト）で割った剰余が剰余
テーブル（１・１．１・２．１・３・−・１・３２）、
（２・１．２・２．２・３・−・２・３２）・−・（１
２Ｂ・１．１２８・２．１２８・３・−・１２８・３２
）にわたって第１図の状態で横一列に書込んであり、す
べて索引できるようになっている。

加算器３４．３５・−・−・６５は索引結果の剰余テー
ブルの内容とレジスタＲＥＧ３３〜ＲＥＧ６４のデータ
を加算するものである。レジスタＲＥＧ３３〜ＲＥＧ６
４に格納されている各桁数は被除数のＤ１Ｇ２３〜Ｄｏ
ビットのうち下位のＤ４９５〜Ｄ４δ０・−・ＤＩ５〜
Ｄｏまでのビットであり、除数Ｐよりも小さい数である
ため、剰余テーブルを索引することなくそのままシフト
ダウンされて直接加算器３４．３５・−・６５へ入力さ
れる。

減算器１０１．１０２・−・１３２は上記加算器３４．
３５・−・６５における加算結果と除数Ｐとの引算を行
うものである。

判定部１４０は前記引算結果が正か負かを判別してこれ
を制御部に出力し、正ならばこの引算の結果を再びレジ
スタＲＥＧ３２〜ＲＥＧ６４に入力し、レジスタＲＥＧ
３２の桁については剰余テーブルを索引してその内容と
レジスタＲＥＧ３３〜ＲＥＧ６４を加算器３４〜６５に
て加算し、この加算結果と除数Ｐとの引算を行わせる。

しかし負ならばそのとき加算器３４〜６５から出力され
たデータを剰余Ｒとして出力する。このとき判定部１４
０は判定結果が負であることを制御部に出力し、制御部
は剰余Ｒの出力を行うことを報知する。

アドレス発生部１４１は各メモリ１．２−・・３２に設
けられた１２８個の剰余テーブルを選択するためのアド
レスを出力するものであり、またセレクタ１４２はレジ
スタＲＥＧＩ〜ＲＥＧ３２から、前記剰余テーブルの選
択アドレスに対応した被除数Ｘの桁を選択出力するもの
である。

第３図の動作を、わかり易く、第２図の１０進数表示と
して、被除数Ｘ−２５３９６５０１を除数Ｐ−５０３９
で割った剰余Ｒを求める例について説明する。

■　まず入力された上記被除数Ｘ−２５３９６５０１を
レジスタＲＥＧ１、ＲＥ　Ｇ　２−ＲＥ　Ｇ　６４に格
納する。

■　この格納により被除数Ｘ＝２５３９６５０１を１の
位から子方の位までに桁分解する。

■　このようにして分解した各桁の数値をアドレスにし
て剰余テーブルト１〜１２８・３２を参照して剰余を索
引する。このとき２Ｘ１０７から６Ｘ１０３まではこれ
により剰余が求められる。しかし５００から１までの各
桁は除数Ｐの最上位の桁より小さいのでそのままシフト
ダウンする。

■　このようにして得られた各桁の剰余およびシフトダ
ウンした５０１を加算器３４．３５・−・６５により加
算して１００３９を得る。これを減算器１０１．１０２
−・１３２により除数Ｐ−５０３９を引算して５ｏｏｏ
を得る０判定部１４０はこの引算結果が正であることを
！！！識する。

■　この引算結果が正であることにより、この引算結果
の５０００をレジスタＲＥＧ３２〜ＲＥＧ６４に入力す
る。これによりこの引算結果を各桁に分解する。

■　このうち５Ｘ１０３は、上記の場合と同様に剰余テ
ーブルを索引するが、この結果５０００が得られる。ま
た下位３桁の０００は、これまた上記の場合と同様にシ
フトダウンされる。そしてこれら剰余テーブルの索引結
果とシフトダウンされたデータが加算器３４．３５−・
６５により加算され、この結果の５０００が減算器１０
１．１０２−・１３２により除数Ｐ＝５０３９と引算さ
れる。

■　この引算の結果は−３９となり、判定部１４０はこ
れが負であることを判定し、このとき加算器３４．３５
−・６５の出力データ５０００を剰余Ｒとして出力させ
、また剰余Ｒの得られたことを報知する。

なお前記説明の被除数、除数はあくまでも一例にすぎず
またこれらのビット長もこれまた一例にすぎないもので
あり、本発明は勿論これらにのみ限定されるものではな
い。

〔発明の効果〕

本発明によれば被除数の分解した桁毎に剰余テーブルと
加算器と減算器を設け、減算器で除数Ｐを減算するよう
に処理するようにしたので、被除数Ｘの値により結果の
得られない場合がなくなり、しかも従来のものに比較し
て、例えば１０２４ビツトの被除数を５１２ビツトの除
数で剰余を求める回数が最大４回から３回になるなど、
剰余計算をより高速に実行することができる。

【図面の簡単な説明】

第１図は本発明の原理図、 第２図は本発明の動作説明図、 第３図は本発明の一実施例構成図、 第４図は従来例説明図、 第５図は剰余テーブル説明図である。 １．２．３〜３２−　メモリ

Claims (1)

1. 【特許請求の範囲】 被除数を分解すべき桁毎に除数に対する剰余の記入され
   た剰余テーブルと、剰余テーブルより得られた剰余が入
   力される加算手段（３４〜６５）を具備した分割整数剰
   余計算機において、 減算手段（１０１〜１３２）と、 判定手段（１４０）を設け、 上記加算手段（３４〜６５）より得られる剰余に係る加
   算値から除数を減算し、その減算結果が正の場合に減算
   結果を再度桁分解して剰余テーブルへのアクセス処理を
   行いそのアクセス結果を減算するように処理したことを
   特徴とする分割整数剰余計算機。