(57)【要約】【課題】  剰余算出をより小規模の回路で、より高速に実行する。【解決手段】  符号付き２進数  Ａ、Ｂ  （Ａ，Ｂ  ＞  ０）  において、演算結果  Ａ−Ｂ  及び  Ａ  を符号無し２進数として大小比較を行い、小さいほうを選択出力する。【選択図】  図１
2007034038.tif 000002
【特許請求の範囲】
【請求項１】
Kビットの符号付き２進数 A, B (A, B >0) において、
演算結果 A-B, 及び A を Kビットの符号無し２進数として大小比較を行い、
小さいほうを選択出力することを特徴とする演算装置。
【請求項２】
Kビットの符号付き２進数 A, B (A, B >0) を入力するための第１及び第２の入力手段と、
前記第１、第２の入力手段から入力された符号付き２進数を減算するための符号付きKビット２進数減算手段と、
前記減算手段の出力及びKビット２進数Aを符号無しKビット２進数として比較するための符号無しKビット２進数比較手段と、
前記比較手段の出力に応じ前記減算手段、２進数Aのうちいずれか一方を出力するための出力選択手段を有する事を特徴とする演算装置。
【請求項３】
Kビットの符号付き２進数 A, B (A, B >0)において、
Kビットの符号付き２進数を減算する処理を前記２つの数について実行し、
Kビットの符号無し２進数の比較処理を実行し、小さな方の値を出力する処理を実行する演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は剰余算の剰余を算出する技術に関する。
【背景技術】
【０００２】
データ通信やデータ記憶においては、許可されていない者が不正に情報を取得する等を防止するため、情報を暗号に変換（暗号化）し、それを元の情報に復元（復号化）する技術がある。
【０００３】
この暗号化・復号化技術は、要約すると入力された「暗号化する情報（元情報）」または「暗号化されている情報（暗号）」に予め決められた演算を施し、その演算結果を予め与えられた数値で割り算したときの余りを「暗号」または「元情報」とする方式である。
【０００４】
この種の暗号化・復号化技術には様々なものがあるが、それらの技術で広く使用される処理が、剰余演算処理である。
【０００５】
剰余演算では、加算、減算、乗算、除算などの演算に対して必ずある数で割った余りを取るようになっている。
【０００６】
例えばある数を7とすると、その剰余表現
3 mod 7 = 3
13 mod 7 = 6
などとなり、全ての演算結果は 0,1, 2, 3, 4, 5, 6 のいずれかで表現される。
【０００７】
実際の暗号化では、上記剰余数表示を用いて、
暗号化する情報を M, 暗号化された情報を C とすると
C = M^e mod n;
M - C^d mod n;
などの処理によって、暗号化や復号化が行われる。
【０００８】
ここで、 e, d, n は所謂暗号「鍵」である。
【０００９】
上記のような暗号処理を実現するには、べき乗剰余演算、加算、剰余加算、剰余乗算などの処理が必要となり、前記処理の繰り返し処理回数も極めて大きなものとなるため、大規模な処理手段、長い処理手段を要するものとなっており、これを克服するため様々な高速化・効率的な処理手法が考案・提案されている。
【００１０】
又、別の従来例としては、特許文献１及び特許文献２をあげることが出来る。
【特許文献１】特開平06-348461号公報
【特許文献２】特開2002-268873号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
前記の暗号化において、数は基本的に剰余数系表現となる。
【００１２】
従って、ある数 X において、
X mod n の演算が実行されるが、これは
1)除算を実行して、算出する。
【００１３】
2)除算を減算処理のループで実現して実行、ループ終了後剰余が算出されている。
【００１４】
などによって得られる。このうち 2) の手法は、ループ内の減算が実行可能か否かの判断処理が必要になる。すなわち、
A-B を出力 : A >= B の時
A   を出力 : A < B の時
を実行する必要がある。
【００１５】
処理中の条件判断は、条件の検出・検出結果に応じた制御など実現手段、手法の大規模化・複雑化・処理スピードの低下の原因となっていた。
【課題を解決するための手段】
【００１６】
上記課題を解決するために、本発明によれば、
Kビットの符号付き２進数 A, B (A, B >0) において、
演算結果 A-B, 及び A を Kビットの符号無２進数として
大小比較を行い、小さいほうを選択する演算を実行する
事によって、高速・容易に剰余を算出できる演算手段、演算装置、演算手法を提供する事を可能にしている。
【発明の効果】
【００１７】
以上、本発明によれば、剰余を算出するための演算手段を小規模で実現するという効果、また、実行のパフォーマンスを低下させる分岐・条件判断などの要因を減少させて剰余を算出できる演算手法を提供する事が可能になる。
【発明を実施するための最良の形態】
【００１８】
次に、本発明の詳細を実施例の記述に従って説明する。
【実施例１】
【００１９】
以下、実施例を用いて本発明を詳述する。
【００２０】
図１は本発明実施の演算装置の一構成例を表わす図である。
【００２１】
演算装置は、
２つの K ビット入力端子 X, n、
被減数入力A, 減数入力B, 出力Yを有する符号付き K bit 減算器 (signed K subtractor)
２つの K ビット入力A,Bを有する符号無 K bit 比較器 (unsigned K comparator)
２つの K ビット入力A,B 出力選択制御入力 S を有する選択器 (selector)で構成され、
２つの K ビット入力端子には符号付きデータX0, n0 (X0, n0 > 0)が入力される。
【００２２】
X0, n0 はともに正の整数であるため X0, n0 の符号ビットすなわち最上位ビットは常に１となる。
【００２３】
前記２つのデータX0, n0はX0を被減数、n0を減数として前記減算器に供給され、減算器出力Yから減算結果
X0 - n0 
が選られる。
【００２４】
前記被減数データ X0 及び、前記減算結果 X0 - n0は、前記符合無し K bit 比較器の２つの入力 A, B に供給されており、前記比較器により比較処理が行われる。
【００２５】
比較器の比較結果出力は前記選択器の出力選択制御入力に供給されており、
前記比較器の出力に応じて、２つの入力 A, B に供給されたデータ、前記減算器からの減算出力
X0 - noと前記入力データ X0 のいずれか一方を選択して出力する事になっている。
【００２６】
前記減算器では、符号付付き減算が実行される。
【００２７】
従って、減算器出力からは減算結果 X0 - n0 が出力される。
【００２８】
ここでの出力結果 X0 - n0 の最上位ビットの値は、
(X0 - n0)k-1  = 0 (X0 >= n0 の時)
= 1 (X) < n0 の時)
となる。
【００２９】
前記比較器には、前記入力データ X0 と前記減算器出力 X0-n0 が入力され k-1 ビット符号無データとして大小比較が行われる。２つのデータ入力A,Bに入力されるデータの大小関係が A>=B の時 Y = 0 とすると、
Yの値は下記のようになる。
Y = 0  (X0 >= n0 の時は X0 > X0 - n0 (>0) であるから) 
Y = 1  (X0 < n0  の時は X0 - n0 < 0 なので、 (X0 - n0)の最上位ビット (X0 - n0)k-1 = 1 であるから unsigned (X0 - n0) > unsigned X0 )
前記比較器比較結果に応じて、前記選択手段からは下記のデータが選択される。
Y = X0 - n0 (S=0 すなわち X0 >= n0 のとき)
= X0     (S=1 すなわち X0 < n0 のとき)
上記処理を繰り返す事によって、被除数 X0 除数 n0 とした時の剰余 X0 mod n0 が得られる事になる。
【００３０】
上記処理の繰り返しの制御については、例えば、上記一連の処理で選られた選択器出力 Y を再び被除数としてXに入力し、処理結果である選択器出力Yと入力Xとを比較する事で可能である。すなわち入力した値と得られた出力結果が同一であれば剰余算出が終了している事になる。
【００３１】
図２は本発明実施の演算手法の一構成例を表わしたものである。
【００３２】
本例では、プログラムによって処理内容を規定し実行する手段を用いて本発明を実施した場合のプログラムの構成例を示すものである。
【００３３】
プログラムは前記実行する手段が備えている命令によって構成されるが、本発明を適用した実行手段は、下記のような処理を行う命令をも備えており、命令は命令そのものの種類に加え、命令に供給するデータの型によってさらに細分化されている。
SSUB/USUB : signed/unsigned subtraction : 符号付き/符号無し  減算
SLE/ULE   : signed/unsigned less equal  ：符号付き/符号無し  小さいほうの値を出力
上記命令を適用して本発明を実施した場合、
SSUB m0, X0, n0 : m0 = signed (X0) - sogned (n0) ;  X0, n0 を符号付きの値とみなして減算を行う。
【００３４】
ULE  m0, m0, X0 : m0 = LE( unsigned (m0), unsigned(n0) ) : m0, n0 を符号無しの値とみなして小さいほうの値を出力
を繰り返し実行する事によって、被除数 X0 除数 n0 とした時の剰余 m0 が得られる事になる。
【００３５】
(ただし、X0, n0 > 0)
【図面の簡単な説明】
【００３６】
【図１】本発明の一実施例の構成を表わす図。
【図２】本発明の一実現例を表わす。
【図１】
2007034038.tif 000003
【図２】
2007034038.tif 000004