(57)【特許請求の範囲】
【請求項１】
入力された値ＳとＮに対し１度にｗビットずつ処理を行い２のべきによる除算を行う除算装置であり、
入力された値Ｓ，Ｎをそれぞれ格納するＳ記憶手段及びＮ記憶手段と、
この除算装置がハードウェア上で１度に処理するビット数ＭをM＝wとし、
n′＝−N-1mod２w
を演算する逆元演算手段と、
上記n′、上記Ｓ、上記ｗを用いて
s′＝S・n′mod２w
を計算する剰余乗算手段と、
上記Ｎ、上記Ｓ、上記ｓ′に対し
q＝S＋s′・N
を計算する乗算加算手段と、
上記ｑ、上記ｗに対し、q/2-w を計算し、その計算結果をS・2-wmodＮ の演算結果として出力する２のべきによる除算手段、
とを含むことを特徴とする除算装置。
【請求項２】
入力された値ＳとＮに対し１度にｗビットずつ処理を行い２のべきによる除算を行う除算装置であり、
入力された値Ｓ，Ｎをそれぞれ格納するＳ記憶手段及びＮ記憶手段と、
予め演算されたn′＝−N-1mod２wが保持されたn′記憶手段と、
この除算装置がハードウェア上で１度に処理するビット数ＭをM＝wとし、
上記n′、上記Ｓ、上記ｗを用いて
s′＝S・n′mod２w
を計算する剰余乗算手段と、
上記Ｎ、上記Ｓ、上記ｓ′に対し
q＝S＋s′・N
を計算する乗算加算手段と、
上記ｑ、上記ｗに対し、q/2-w を計算し、その計算結果をS・2-wmodＮ の演算結果として出力する２のべきによる除算手段、
とを含むことを特徴とする除算装置。
【請求項３】
入力された値Ｓ，Ｎ，ｋ（ｋは１以上の整数）に対し１度にｗビットずつ処理をして２のべきによる除算を行う除算装置であり、
上記Ｓ，Ｎ，ｋをそれぞれ格納するＳ記憶手段、Ｎ記憶手段、ｋ記憶手段と、
上記値Ｎとこの装置が１度に処理するビット数ｗとに対し、n′＝−N-1mod２w を演算する逆元演算手段と、
上記n′、上記Ｓ、上記ｗを用いてs′＝S・n′mod２w を計算する剰余乗算手段と、
上記Ｎ、上記Ｓ、上記s′に対しq＝S＋s′Ｎを計算する乗算加算手段と、
上記ｑ、上記ｗに対し、q/2-w を計算する２のべきによる除算手段と、
上記剰余乗算手段と、上記乗算加算手段と、上記２のべきによる除算手段とが行う上記の一連の処理をK＝[k/w]回（[a] は任意の実数ａを超えない最大の整数を表す）実行させた後、更にｋmodｗの演算結果を新たなｗとして、上記剰余乗算手段と、上記乗算加算手段と、上記２のべきによる除算手段とが行う上記の一連の処理を１回実行させ、その際に各２のべきによる除算手段の演算結果で上記Ｓ記憶手段のＳを更新し、上記K+1 回の実行の最後における上記２のべきによる除算手段の演算結果をS・2-kmodＮ の演算結果として出力する制御手段と、
を含むことを特徴とする除算装置。
【請求項４】
入力された値Ｓ，Ｎ，ｋ（ｋは１以上の整数）に対し１度にｗビットずつ処理をして２のべきによる除算を行う除算装置であり、
上記Ｓ，Ｎ，ｋをそれぞれ格納するＳ記憶手段、Ｎ記憶手段、ｋ記憶手段と、
予め演算されたn′＝−N-1mod２w を保持するn′記憶手段と、
上記n′、上記Ｓ、上記ｗを用いてs′＝S・n′mod２w を計算する剰余乗算手段と、
上記Ｎ、上記Ｓ、上記s′に対しq＝S＋s′Ｎを計算する乗算加算手段と、
上記ｑ、上記ｗに対し、q/2-w を計算する２のべきによる除算手段と、
上記剰余乗算手段と、上記乗算加算手段と、上記２のべきによる除算手段とが行う上記の一連の処理をK＝[k/w]回（[a] は任意の実数ａを超えない最大の整数を表す）実行させた後、更にｋmodｗの演算結果を新たなｗとして、上記剰余乗算手段と、上記乗算加算手段と、上記２のべきによる除算手段とが行う上記の一連の処理を１回実行させ、その際に各２のべきによる除算手段の演算結果で上記Ｓ記憶手段のＳを更新し、上記K+1 回の実行の最後における上記２のべきによる除算手段の演算結果をS・2-kmodＮの演算結果として出力する制御手段と、
を含むことを特徴とする除算装置。
【請求項５】
請求項１或いは３に記載された除算装置において、上記逆元演算手段は上記Ｎ，ｗに対しｙ＝Ｎmod２wを求める手段と、上記ｙ，ｗに対しn′＝-y-1mod２wを求める手段とを含むことを特徴とする除算装置。
【請求項６】
請求項１，３，５のいずれかの除算装置において、上記逆元演算手段は、上記演算したn′を上記Ｎに対して記憶するn′記憶手段と、上記入力Ｎに対し、上記n′記憶手段を読出し、n′が読出されるとこれを上記逆元演算手段の出力n′として出力する手段を含むことを特徴とする除算装置。
【請求項７】
入力された値Ｓ，Ｎ，ｋに対し２のべきによる除算を行う除算装置であり、
上記入力された値Ｓ，Ｎ，ｋ（ｋは１以上の整数）をそれぞれ格納するＳ記憶手段、Ｎ記憶手段、ｋ記憶手段と、
上記値ｋをk＝w1+w2+…+wp（wi>0, i＝1, 2,… , p）となるｐ個のw1, w2,… , wpに分割して出力する分割手段と、
ｐ個の除算部と、
を含み、
第ｊ番目（j＝1, 2,… , p-1）の上記除算部は、
その演算結果を第ｊ＋１番目の上記除算部に提供可能に構成され、
第ｉ番目の上記除算部は、
入力としてＮとSi-1（S0は上記Ｓ記憶手段に格納された値Sであり、S1,S2,...,Sp-1は第ｉ−１番目の上記除算部から出力された演算結果Si-1である）とwiとが与えられ、
上記Ｎ、上記wiを用いて、
n′＝−N-1mod２wi
を演算する逆元演算手段と、
上記n′、上記Si-1、上記wiを用いて
s′＝Si-1・n′mod２wi
を計算する剰余乗算手段と、
上記Ｎ、上記Si-1、上記s′に対し
q＝Si-1＋s′N
を演算する乗算加算手段と、
上記ｑ、上記wiに対し、q/2-wiを計算し、その演算結果をSiとして出力する２のべきによる除算手段と、
を含み、
ｐ番目の上記除算部は、
当該ｐ番目の除算部の上記除算手段における上記演算結果Spを、上記入力された値Ｓ，Ｎ，ｋに対するS・2-kmodＮ の演算結果として出力する、
ことを特徴とする除算装置。
【請求項８】
請求項１乃至７のいずれかに記載した２のべきによる除算装置としてコンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項９】
２をべきとする乗算装置であり、
ｎビットの値Ｎ，Ｓを入力する入力手段と、
上記Ｎ，Ｓがそれぞれ格納されたＮ記憶手段及びＳ記憶手段と、
値ｗ（w≦M、Ｍはこの装置がハードウェア上で１度に処理するビット数であり、M≦ｎを満たす）が格納されたｗ記憶手段と、
上記Ｎ記憶手段のＮ、上記Ｍ、上記ｎに対し、n"＝[2n+M-1/N]（[a] は任意の実数ａを超えない最大の整数を表す）を求める除算手段と、
上記n"を格納するn"記憶手段と、
上記ｎ″記憶手段のn"、上記Ｓ記憶手段のＳの上位Ｍビットのｓを用いてt′＝[s・n"/22M-W-1]を計算する第１演算手段と、
上記t′を格納するt′記憶手段と、
上記Ｓ記憶手段のＳ、上記Ｎ記憶手段のＮ、上記t′記憶手段のt′、上記ｗ記憶手段のｗを用いてS′＝S・2w-t′N を演算する第２演算手段と、
上記Ｓ′を格納するS′記憶手段と、
上記Ｓ′記憶手段のS′と上記Ｎ記憶手段のＮとを比較する比較手段と、
上記比較手段の比較結果がS′＞Ｎである場合にS′-Nを新たなS′とする処理を繰返し、0≦S′＜Nを満すS′を求める減算手段と、
上記比較手段の比較結果がS′＜Ｎの場合のS′又は上記減算手段で求めたS′をS・2wmodＮの演算結果として出力する制御手段、
とを含むことを特徴とする乗算装置。
【請求項１０】
２をべきとする乗算装置であり、
ｎビットの値Ｎ，Ｓを入力する入力手段と、
上記Ｎ，Ｓがそれぞれ格納されたＮ記憶手段及びＳ記憶手段と、
値ｗ（w≦M、Ｍはこの装置がハードウェア上で１度に処理するビット数であり、M≦ｎを満たす）が格納されたｗ記憶手段と、
予め演算されたn"＝[2n+M-1/N]（[a] は任意の実数ａを超えない最大の整数を表す）を保持するn"記憶手段と、
上記ｎ″記憶手段のn"、上記Ｓ記憶手段のＳの上位Ｍビットのｓを用いてt′＝[s・n"/22M-W-1]を計算する第１演算手段と、
上記t′を格納するt′記憶手段と、
上記Ｓ記憶手段のＳ、上記Ｎ記憶手段のＮ、上記t′記憶手段のt′、上記ｗ記憶手段のｗを用いてS′＝S・2w-t′N を演算する第２演算手段と、
上記Ｓ′を格納するS′記憶手段と、
上記Ｓ′記憶手段のS′と上記Ｎ記憶手段のＮとを比較する比較手段と、
上記比較手段の比較結果がS′＞Ｎである場合にS′-Nを新たなS′とする処理を繰返し、0≦S′＜Nを満すS′を求める減算手段と、
上記比較手段の比較結果がS′＜Ｎの場合のS′又は上記減算手段で求めたS′をS・2wmodＮの演算結果として出力する制御手段、
とを含むことを特徴とする乗算装置。
【請求項１１】
２をべきとする乗算装置であり、
値ｋとｎビットの各値Ｓ，Ｎを入力する入力手段と、
上記ｋ，Ｓ，Ｎをそれぞれ格納するｋ記憶手段、Ｓ記憶手段、Ｎ記憶手段と、
値ｗ（w≦M、Ｍはこの装置がハードウェア上で１度に処理するビット数であり、M≦ｎを満たす）が格納されたｗ記憶手段と、
上記Ｎ記憶手段のＮ、上記Ｍ、上記ｎに対し、n"＝[2n+M-1/N]（[a] は任意の実数ａを超えない最大の整数を表す）を求める除算手段と、
上記n"を格納するn"記憶手段と、
上記n"記憶手段のn"、上記Ｓ記憶手段のＳの上位のＭビットのｓを用いてt′＝[s・n"/22M-W-1]を計算する第１演算手段と、
上記t′を格納するt′記憶手段と、
上記Ｓ記憶手段のＳ、上記Ｎ記憶手段のＮ、上記t′記憶手段のt′、上記ｗ記憶手段のｗを用いてS′＝S・2w-t′N を演算する第２演算手段と、
上記S′を格納するS′記憶手段と、
上記S′記憶手段のS′と上記Ｎ記憶手段のＮを比較する比較手段と、
上記比較手段の比較結果がS′＞Ｎである場合にS′-Nを新たなS′とする処理を繰返し、0≦S′＜N を満すS′を求める減算手段と、
上記第１演算手段と、上記第２演算手段と、上記比較手段と、上記減算手段とが行う上記の一連の処理をK＝[k/w]回実行させた後、更にｋmodｗの演算結果を新たなｗとして、上記第１演算手段と、上記第２演算手段と、上記比較手段と、上記減算手段とが行う上記の一連の処理を１回実行させ、これら各１回の実行ごとにその時得られた上記S′-Nで上記Ｓ記憶手段のＳを更新し、これらK+1 回の実行後の結果のS′をS・2kmodＮの演算結果として出力する制御手段、
とを含むことを特徴とする乗算装置。
【請求項１２】
２をべきとする乗算装置であり、
値ｋとｎビットの各値Ｓ，Ｎを入力する入力手段と、
上記ｋ，Ｓ，Ｎをそれぞれ格納するｋ記憶手段、Ｓ記憶手段、Ｎ記憶手段と、
値ｗ（w≦M、Ｍはこの装置がハードウェア上で１度に処理するビット数であり、M≦ｎを満たす）が格納されたｗ記憶手段と、
予め演算されたn"＝[2n+M-1/N] （[a] は任意の実数ａを超えない最大の整数を表す）を保持するn"記憶手段と、
上記n"記憶手段のn"、上記Ｓ記憶手段のＳの上位のＭビットのｓを用いてt′＝[s・n"/22M-W-1]を計算する第１演算手段と、
上記t′を格納するt′記憶手段と、
上記Ｓ記憶手段のＳ、上記Ｎ記憶手段のＮ、上記t′記憶手段のt′、上記ｗ記憶手段のｗを用いてS′＝S・2w-t′N を演算する第２演算手段と、
上記S′を格納するS′記憶手段と、
上記S′記憶手段のS′と上記Ｎ記憶手段のＮを比較する比較手段と、
上記比較手段の比較結果がS′＞Ｎである場合にS′-Nを新たなS′とする処理を繰返し、0≦S′＜N を満すS′を求める減算手段と、
上記第１演算手段と、上記第２演算手段と、上記比較手段と、上記減算手段とが行う上記の一連の処理をK＝[k/w]回実行させた後、更にｋmodｗの演算結果を新たなｗとして、上記第１演算手段と、上記第２演算手段と、上記比較手段と、上記減算手段とが行う上記の一連の処理を１回実行させ、これら各１回の実行ごとにその時得られた上記S′-Nで上記Ｓ記憶手段のＳを更新し、これらK+1 回の実行後の結果のS′をS・2kmodＮの演算結果として出力する制御手段、
とを含むことを特徴とする乗算装置。
【請求項１３】
請求項９、１０、１１又は１２のいずれかの乗算装置において、上記第１演算手段は、
上記Ｓ記憶手段のＳと、上記ｗ記憶手段のｗと、上記ｎとによりs＝[S/2n-M]を計算する第１の２のべきによる除算手段と、
上記ｓを格納するｓ記憶手段と、
上記n"記憶手段のn"と、上記ｓ記憶手段のｓとからt＝n"・sを求める乗算手段と、
上記ｔを格納するｔ記憶手段と、
上記ｔ記憶手段のｔ、上記ｗ記憶手段のｗと、上記Ｍとからt′=[t/22M-W-1]を計算する第２の２のべきによる除算手段、
とを含むことを特徴とする乗算装置。
【請求項１４】
入力された値Ｓ，Ｎ，ｋに対し２のべきによる乗算を行う乗算装置であり、
上記入力された値ｋ，Ｓ，Ｎをそれぞれ格納するｋ記憶手段、Ｓ記憶手段、Ｎ記憶手段と、
上記値ｋをk＝w1+w2+…+wp（wi>0, wi≦M，i=1, 2,… , p，Ｍはこの装置がハードウェア上で１度に処理するビット数であり、M≦ｎを満たす。nは上記各値Ｓ，Ｎのビット数。）となるｐ個のw1, w2,… , wpに分割して出力する分割手段と、
ｐ個の乗算部と、
を含み、
第ｊ番目（j＝1, 2,… , p-1）の上記乗算部は、
その演算結果を第ｊ＋１番目の上記乗算部に提供可能に構成され、
第ｉ番目の上記乗算部は、
入力としてＮとSi-1（S0は上記Ｓ記憶手段に格納された値Sであり、S1,S2,...,Sp-1は第ｉ−１番目の上記乗算部から出力されたSi-1である）とwiとが与えられ、
値wiが格納されたwi記憶手段と、
上記Ｎ記憶手段のＮ、上記Ｍ、上記ｎに対し、n"＝[2n+M-1/N] （[a] は任意の実数ａを超えない最大の整数を表す）を求める除算手段と、
上記n"を格納するn"記憶手段と、
上記ｎ″記憶手段のn"、Si-1の上位Ｍビットのｓを用いてt′＝[s・n"/22M-Wi-1]を計算する第１演算手段と、
上記t′を格納するt′記憶手段と、
上記Si-1、上記Ｎ記憶手段のＮ、上記t′記憶手段のt′、上記wi記憶手段のwiを用いてS′＝Si-12wi-t′Nを演算する第２演算手段と、
上記S′を格納するS′記憶手段と、
上記S′記憶手段のS′と上記Ｎ記憶手段のＮとを比較する比較手段と、
上記比較手段の比較結果がS′＞Ｎである場合にS′-Nを新たなS′とする処理を繰返し、0≦S′＜N を満すS′を求める減算手段と、
上記比較手段の比較結果がS′＜Ｎの場合のS′又は上記減算手段で求めたS′をSiとして出力する制御手段と、
を含み、
第ｐ番目の上記乗算部は、
上記Sp（当該第ｐ番目の乗算部の上記比較手段における比較結果がS′＜Ｎの場合のS′又はその上記減算手段で求めたS′）を、上記入力された値ｋ，Ｓ，Ｎに対するS・2kmodＮの演算結果として出力する、
ことを特徴とする乗算装置。
【請求項１５】
入力された値Ｓ，Ｎ，ｋに対し２のべきによる乗算を行う乗算装置であり、
上記入力された値ｋ，Ｓ，Ｎをそれぞれ格納するｋ記憶手段、Ｓ記憶手段、Ｎ記憶手段と、
上記値ｋをk＝w1+w2+…+wp（wi>0, wi≦M，i=1, 2,… , p，Ｍはこの装置がハードウェア上で１度に処理するビット数であり、M≦ｎを満たす。nは上記各値Ｓ，Ｎのビット数。）となるｐ個のw1, w2,… , wpに分割して出力する分割手段と、
ｐ個の乗算部と、
を含み、
第ｊ番目（j＝1, 2,… , p-1）の上記乗算部は、
その演算結果を第ｊ＋１番目の上記乗算部に提供可能に構成され、
第ｉ番目の上記乗算部は、
入力としてＮとSi-1（S0は上記Ｓ記憶手段に格納された値Sであり、S1,S2,...,Sp-1は第ｉ−１番目の上記乗算部から出力されたSi-1である）とwiとが与えられ、
値wiが格納されたwi記憶手段と、
予め演算されたn"＝[2n+M-1/N]（[a] は任意の実数ａを超えない最大の整数を表す）を格納するn"記憶手段と、
上記ｎ″記憶手段のn"、Si-1の上位Ｍビットのｓを用いてt′＝[s・n"/22M-Wi-1]を計算する第１演算手段と、
上記t′を格納するt′記憶手段と、
上記Si-1、上記Ｎ記憶手段のＮ、上記t′記憶手段のt′、上記wi記憶手段のwiを用いてS′＝Si-12wi-t′Nを演算する第２演算手段と、
上記S′を格納するS′記憶手段と、
上記S′記憶手段のS′と上記Ｎ記憶手段のＮとを比較する比較手段と、
上記比較手段の比較結果がS′＞Ｎである場合にS′-Nを新たなS′とする処理を繰返し、0≦S′＜N を満すS′を求める減算手段と、
上記比較手段の比較結果がS′＜Ｎの場合のS′又は上記減算手段で求めたS′をSiとして出力する制御手段、
とを含み、
第ｐ番目の上記乗算部は、
上記Sp（当該第ｐ番目の乗算部の上記比較手段における比較結果がS′＜Ｎの場合のS′又はその上記減算手段で求めたS′）を、上記入力された値ｋ，Ｓ，Ｎに対するS・2kmodＮの演算結果として出力する、
ことを特徴とする乗算装置。
【請求項１６】
請求項９乃至１５のいずれかの乗算装置としてコンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、例えば情報セキュリティ技術（デジタル署名、ブラインド署名、楕円暗号など）で良く使われる有限体（ＧＦ（ｐ）：但しｐは素数）及び剰余環Ｚ／ＮＺ上の演算における、入力値Ｓ，Ｎ，ｗ（ｗ；正整数）に対しＳ・２ｗ  ｍｏｄ  ＮならびにＳ・２−ｗｍｏｄ  Ｎを演算する装置ならびにその演算プログラム記録媒体に関する。
【０００２】
【従来の技術】
単に２ｋ  による除算を行なう場合は、ｋビットのシフトを行なえばよい。例えば、２進表現で１０１０００と表される数４０（１０進表現）を２３  で割る場合、３  ｂｉｔ分、右シフトする。すると、２進表現で１０１  となり容易に５を求めることができる。しかし、例えば図２の除算部１４又は１８Ａにおける演算のように剰余環Ｚ／ＮＺ上の２ｋ  による除算は、単純にｋ  ｂｉｔシフトするだけでは出来ない。そこで従来、例えば、入力値Ｓ，ｋ，Ｎ（奇数）から、出力値Ｓ・２−ｋｍｏｄＮ  を求めるには次の処理を実行していた。
（ａ）  入力値Ｓが２で割り切れれば、Ｓ／２  の演算を行ない、その結果を新たにＳとする。
（ｂ）  入力値Ｓが２で割り切れなければ、（Ｓ＋Ｎ）／２  を行ない、その結果を新たにＳとする。
以上のステップ（ａ）  又は（ｂ）  をｋ回行なう。
ここで、Ｓ／２  ないし（Ｓ＋Ｎ）／２  で示した２による除算は、ビットシフトにより行うことができる。
【０００３】
一方、２ｋ  による乗算を行なう場合は、ｋ  ｂｉｔのシフトを行なえばよい。例えば、２進表現で１０１０００と表される数４０（１０進表現）に２３  を掛ける場合、３ビット分、左シフトする。すると、２進表現で１０１００００００  となり容易に３２０  を求めることができる。しかし、剰余環Ｚ／ＮＺ上の２ｋ  による乗算は、除算と同様に、単純にｋビットシフトするだけでは出来ない。そこで従来、例えば、入力値Ｓ，ｋ，Ｎ（奇数）から、出力値Ｓ・２ｋｍｏｄＮを求めるには、次の処理を実行していた。
（ａ）  入力値Ｓを２倍したＳ×２を求め、この結果を新たにＳとし、
（ｂ）  そのＳがＮより大きければ、Ｓ−Ｎを演算し、その結果を新たにＳとしてステップ（ａ）  に戻り、ＳがＮより大きくなければ、そのままステップ（ａ）  に戻る。
この操作（ａ），  （ｂ）  をｋ回行なう。ここで、Ｓ×２で示した２による乗算は、ビットシフト装置を用いて構成できる。
【０００４】
【発明が解決しようとする課題】
上述のＺ／ＮＺ上の２ｋ  による除算では、２による除算（１ビット右シフト）をちょうどｋ回行ない、＋Ｎの加算を最大ｋ回（平均ｋ／２回）行なう。また従来のＺ／ＮＺ上の２ｋ  による乗算では、２による乗算（１ビット左シフト）をちょうどｋ回行ない、−Ｎの減算を最大ｋ回（平均ｋ／２回）行なう。この様な２による乗除算及び加減算を実現するには、扱う値（入力値）のビット数に比例する演算時間がかかり、その大きさのｋ倍に比例して処理時間が増大することになる。従って、１度に複数ｗビット（ｗは２以上の正数）ずつ処理することにより、処理時間を短縮することが望まれる。
【０００５】
ところで、現代の計算機はハードウェア構成としてＭ  ｂｉｔ（Ｍは８、１６、３２等）の単位で読み書き可能な記憶装置を使って構成される（条件１）。このことから、２ｋによる乗除算における同時処理ビット数ｗを２≦ｗ≦Ｍ  の所望の値、好ましくはｗ＝Ｍ  に設定して、このＭビット単位に演算を行うのが効率が良い。
例えば従来の２ｋ  による除算や乗算装置では、入力値が大きい場合、大きい整数の１ビットシフトを繰り返し行なっている。しかし条件１の下では、１ビットのシフトはＭビット毎にまとめてシフトを行なうのと同じか、より多くの演算時間がかかる。
【０００６】
【課題を解決するための手段】
この発明では、１ビットずつシフトを行なって処理するかわりに、複数ｗビット、例えば演算装置がそのハードウェア構成として１度に処理するビット数Ｍ、ずつまとめて行なうことによって、シフトの回数を１ビットシフトの場合の１／Ｍに減らす。この場合、２のべきによる除算では、例えばｗ＝Ｍビットずつシフトを行い、そのｗビットシフトにおけるｗ回分のループ中で行なわれるであろう加算を予測してその分をまとめて加算する。ビット単位の処理で、Ｓ＋Ｎの加算が行われるかどうかは、Ｓの最下位の該当ビットが０か１かによって判定されるが、該当ビットの値はそれ以前の多重の加算の結果として決まる。このため、ｗ回分の処理をまとめて行う為に、Ｓの下位ビットとＮの下位ビットをまとめて処理する新たな演算が必要になる。
【０００７】
そこで、ｎ′＝−Ｎ−１ｍｏｄ２ｗ  を予め求めておき、ｓ′＝Ｓ・ｎ′ｍｏｄ２ｗ  とおけば、−ｓ′Ｎ＝Ｓ  ｍｏｄ２ｗなので少なくとも、下位ｗビットの範囲で−ｓ′ＮとＳは一致する。そこで、Ｓ＋ｓ′Ｎを２ｗ  で割ると、つまり、Ｓ＋ｓ′Ｎの下位ｗビット（００．．．０）分を除く上位ビットを新たなＳとおけば、等価的にＳ・２−ｗｍｏｄＮ  が求められる。
この原理は次の通り、中国人の剰余定理で知られる性質により、
Ｓ＝｛（Ｓ・Ｎ−１ｍｏｄｒ）Ｎ＋（Ｓ・ｒ−１ｍｏｄＮ）ｒ｝ｍｏｄ  Ｎ・ｒ
が成り立つ。ここで、ｒとＮは互いに素である。そこで、これを変形し、
Ｓ・ｒ−１ｍｏｄＮ＝｛Ｓ−（Ｓ・Ｎ−１ｍｏｄｒ）Ｎ  ｍｏｄＮ・ｒ｝／ｒ
が成り立つので、ｒ＝２ｗ  ，ｎ′＝−Ｎ−１ｍｏｄ  ２ｗ  とおけば、
0003616385.tif 000002
となる。ここで、ｓ′＝Ｓ・ｎ′ｍｏｄ２ｗ  である。
【０００８】
これを繰り返し利用することで、従来の除算法フローチャート中のｋ回ループをｋ／ｗ  回に短縮することも可能となる。
上述では除算の場合の手段を説明したが、乗算の場合も同様にして演算を行なうことが出来る。この場合、この発明の演算原理を実施するコンピュータが１度で処理するビット数をＭとすると、Ｍ以下のビット数ｗ（２≦ｗ≦Ｍ）ずつまとめて処理を行う。
２のべきによる乗算では、ｗ回分のループ中で行なわれるであろう−Ｎの減算分をまとめて減算する必要がある。ここでＮのビット数ｎとＳのビット数は同じであるとする。ｗは除算で１度に処理する予め設定されたビット数である。減算が行なわれるかどうかは、Ｓの上位の該当ビットが０か１かによって判定される。該当ビットの値はそれ以前の減算の結果が反映される。このため、予測にはＳの上位ビットとＮの上位ビットを用いた演算を行なう。
【０００９】
そこで、ｎをＮのビット数として、ｎ”＝［２ｎ＋Ｍ−１／Ｎ］（［ａ］  は任意の実数ａを超えない最大の整数、即ちａの小数点以下を切り捨てた値を表すものとする）を予め求めておき、
ステップ１：  Ｓ′＝Ｓ・２ｗ  を求める。
ステップ２：  ｓ′＝［Ｓ′／（２ｎ＋ｗ−Ｍ）］  を求める（つまり、Ｓ′の上位ｗビットをｓ′にする）。
ステップ３：  ｔ＝  ｓ′ｎ”  を求める（２Ｍビットの値）。
ステップ４：  ｔ′＝  ［ｔ／２２Ｍ−ｗ−１］  を求める。
少なくとも、上位２Ｍ−ｗ−２  ビットの範囲でｔ′とＳ′／Ｎは一致するので、Ｓ′−ｔ′Ｎ  を計算すれば、（Ｍ≧ｗ＋２という条件下では）等価的にＳ・２ｗｍｏｄＮを求めることができる。
この原理は、
（２ｎ＋Ｍ−１／Ｎ）−１  ＜ｎ”＜  ２ｎ＋Ｍ−１／Ｎ
Ｓ／２ｎ−Ｍ＋ｗ−１  ＜ｓ′＜  Ｓ／２ｎ−Ｍ＋ｗ  
なるｎ”とｓ′を求めているので、
２２Ｍ−ｗ−１Ｓ／Ｎ＞ｔ＝ｓ′ｎ”＞  （２２Ｍ−ｗ−１Ｓ／Ｎ）−ｓ′−ｎ”＋１
即ち、
0003616385.tif 000003
が成り立つことに基づいている。
これにより、従来の乗算法ｋ回ループをｋ／ｗ  回に短縮することができる。
【００１０】
【発明の実施の形態】
Ｚ／ＮＺ上の２のべきによる除算装置
図１にＺ／ＮＺ上の２のべきによる除算装置２００の実施例を示す。この装置２００はＳ，Ｎ，ｋの入力に対し、Ｓ・２−ｋｍｏｄＮ  を演算して出力するものであり、この装置２００が１度に処理するビット数ｗは、この装置を実施するコンピュータが１度に処理するビット数Ｍと同じものとする。ただし、ｋ＞ｗである。また、２ｗより大きい値は多倍長値と呼ばれ、２ｗ以下の値は単精度値と呼ばれている。
入力部２１により値Ｓ，ｋ，Ｎが入力され、それぞれ記憶部２２，２３，２４に記憶される。記憶部２４内のＮは２ｗ  を法とする逆元部２５に入力され、逆元部２５は入力Ｎに対して、ｎ′＝−Ｎ−１ｍｏｄ２ｗを求め、記憶部２５Ａに格納する。ただし、同じＮが２回以上逆元部２５に入力される場合は、図２Ａに示すように、２ｗ  を法とする逆元部２５中のメモリ２５Ａ内にｎ′＝−Ｎ−１ｍｏｄ２ｗをＮに対し保存しておき、入力Ｎによりメモリ２５Ａを読出して記憶部２６に格納してもよい。このメモリ２５Ａの読出し結果により、目的とするｎ′が存在していないことを判定部２５Ｂが判定すれば、演算部２５Ｃでｎ′＝−Ｎ−１ｍｏｄ２ｗを演算して記憶部２６に格納すると共にメモリ２５Ａに保存する。演算部２５ＣはＮの値が大きい場合、先ずｙ＝Ｎｍｏｄ２ｗ  を計算部２５Ｃａで行い、次にｎ′＝−ｙ−１ｍｏｄ２ｗ  を計算部２５Ｃｂで計算するとよい。
【００１１】
記憶部２２，２３，２４，２６は制御部２０に接続されている。制御部２０は装置２００内の各部の制御、処理の実行を行うが、まず図２Ｂに示すように、ステップＳ１で記憶部２３のｋの値が０か否かを調べ、０でなければステップＳ２でそのｋがｗ＝Ｍ（Ｍは例えばコンピュータの１回の計算の処理単位ビット数８，１６，３２などであり、予め設定されている）より小か否かを調べ、ｋがｗより小でなければ、ステップＳ３で記憶部２０Ａにｗをｗ′として格納し、その後、記憶部２３内のｋをｋ−ｗ′で更新する。
その後、ステップＳ４で以下のＳの更新処理を行う。即ち、制御部２０は２のべきによる剰余部３１、加算部３５へ記憶部２２のＳを供給し、乗算部３２に記憶部２６のｎ′を供給し、乗算部３４に記憶部２４のＮを供給し、２のべきによる剰余部３１，３３、及び２のべきによる除算部３６にそれぞれ記憶部２０Ａのｗ′を供給する。
【００１２】
また各部に対し、順次その処理とさせる。つまりまず２のべきによる剰余部３１は、その入力Ｓ，ｗ′からｓ＝Ｓ  ｍｏｄ２ｗ′を計算し、その結果を記憶部３１Ａに格納する。乗算部３２は、記憶部３１Ａのｓ＝Ｓ  ｍｏｄ２ｗ′とｎ′からｓ・ｎ′＝（Ｓ  ｍｏｄ２ｗ′）ｎ′を計算して記憶部３２Ａに格納する。２のべきによる剰余部３３は、ｗ′と記憶部３２Ａ内のｓ・ｎ′＝（Ｓ  ｍｏｄ２ｗ′）ｎ′とから
ｓ′＝（Ｓ  ｍｏｄ２ｗ′）ｎ′ｍｏｄ２ｗ′
を計算し、その結果を記憶部３３Ａに格納する。乗算部３４は、記憶部３３Ａからのｓ′と記憶部２４からのＮにより、ｓ′Ｎ  を計算し、その結果を記憶部３４Ａに格納する。加算部３５は、記憶部２２のＳと記憶部３４Ａのｓ′Ｎ  との加算ｑ＝Ｓ＋ｓ′Ｎを計算して記憶部３５Ａに格納する。２のべきによる除算部３６は、記憶部３５Ａのｑ＝Ｓ＋ｓ′Ｎとｗ′から（Ｓ＋ｓ′Ｎ）／２ｗ′を計算して、その値を新たなＳとして記憶部３６Ａに格納する。つまり（Ｓ＋ｓ′Ｎ）  の下位ｗ′ビットが０となることを利用してＳ＋ｓ′Ｎ  を２ｗ′で割る。
【００１３】
制御部２０は除算部３６の演算が終ると、その記憶部３６Ａの内容を新たなＳとして記憶部２２の内容を更新し、ステップＳ４の更新演算処理が終わる。
ステップＳ１〜Ｓ４はｋ≧ｗであるかぎり繰り返し実行される。ステップＳ１でｋ＝０でなく、かつステップＳ２でｋ＜ｗであれば、ステップＳ５で記憶部２０Ａにｗ′としてｋを格納し、その後、記憶部２３内のｋを０とし、ステップＳ６でステップＳ４と同様にＳの更新処理を行う。ステップＳ５、Ｓ６を実行するとｋ＝０となるので、次のステップＳ１では、記憶部２３のｋが０と判定され、ステップＳ７で記憶部２２の内容Ｓを演算結果Ｓ・２−ｋｍｏｄＮ  として出力して処理を終了する。
なお２のべきによる剰余部３１，３３及び乗算部３２は２のべきによる剰余手段３０Ａを構成し、加算部３５及び乗算部３４は乗算加算手段３０Ｂを構成している。
【００１４】
Ｚ／ＮＺ上の２のべきによる除算フロー
図３に、Ｚ／ＮＺ上の２のべきによる除算処理の流れを示す。演算自体は図１の装置と同様である。演算装置の１度に処理するビット数Ｍに対し、以下に説明するこの発明による除算方法における１度に処理するビット数ｗをｗ＝Ｍとする。
ステップＳ１：  まず、Ｋ＝［ｋ／ｗ］を演算し、
ステップＳ２：  またｙ＝Ｎ  ｍｏｄ２ｗを計算し、
ステップＳ３：  更にｎ′＝−ｙ−１ｍｏｄ２ｗを演算してｎ′＝−Ｎ−１ｍｏｄ２ｗ  を求める。
ステップＳ４：  その後、以下のステップＳ４〜Ｓ８をＫ＝［ｋ／ｗ］回行なう。つまりＫ＝０  かを調べ、０でなければ
ステップＳ５：  ｓ＝  Ｓ  ｍｏｄ２ｗ  を計算し、
ステップＳ６：  ｓ′＝  ｓ・ｎ′ｍｏｄ２ｗ  を計算し、
ステップＳ７：  Ｓ←（Ｓ＋ｓ′Ｎ）／２ｗ  によりＳを更新し、
ステップＳ８：  Ｋを１減らしてステップＳ４に戻る。
これらステップＳ４〜Ｓ８の処理は図２ＢのステップＳ２〜Ｓ４に相当する。
ステップＳ４でＫ＝０であれば、以下のステップＳ９〜Ｓ１２を実行する。
ステップＳ９：  ｗ′＝  ｋ  ｍｏｄｗを計算し、
ステップＳ１０：ｓ＝  Ｓ  ｍｏｄ２ｗ′を計算し、
ステップＳ１１：ｓ′＝ｓ・ｎ′ｍｏｄ２ｗ′を計算し、
ステップＳ１２：Ｓ←（Ｓ＋ｓ′Ｎ）／２ｗ′によりＳを更新し、その更新されたＳを出力する。
これらステップＳ９〜Ｓ１２の処理は図２ＢのステップＳ５、Ｓ６、Ｓ１、Ｓ７の処理に相当する。
【００１５】
図３では省略したが、図１に示したように、各演算結果は記憶手段に一時格納して利用される。また図２Ｂで示したｋに対する処理は、図３の説明から明らかなように、ｗ＝ｗ′としての処理をＫ＝［ｋ／ｗ］回行い（ｋ≧ｗ）、ｋｍｏｄｗ＝ｗ′としての処理（ｋ＜ｗ）を１回行うことを示しており、図３の処理と全く同じことである。図３と同様にＫ＝［ｋ／ｗ］を演算し、１回の処理ごとにＫから１を減算する処理としてもよい。このことは後述の図４に示す装置の処理にも同様に言える。
上述の説明から明らかなように、この発明の２のべきによる除算装置の基本はＳ・２−ｗｍｏｄＮ  の演算である。この演算を行うには図１において逆元演算部２５でｎ′を求め、２のべきによる剰余手段３０Ａでｓ′を求め、乗算加算手段３０Ｂでｑを求め、２のべきによる除算部３６でＳ＝ｑ／２ｗ  を演算し、その結果を出力すればよい。つまり図３においてはステップＳ２，Ｓ３，Ｓ５，Ｓ６，Ｓ７を実行し、ステップＳ７の実行結果を出力すればよい。
【００１６】
Ｚ／ＮＺ上の２のべきによる乗算装置
図４にこの発明によるＺ／ＮＺ上の２のべきによる乗算装置４００の実施例を示す。この装置４００はＳ，Ｎ，ｋの入力に対して、Ｓ・２ｋｍｏｄＮを出力し、演算装置の１度の演算ビット数がＭであり、この実施例による１度の乗算処理ビット数ｗがｗ≦Ｍに予め設定されている場合である。入力部４１により値Ｓ，ｋ，Ｎが入力され、それぞれ記憶部４２，４３，４４に格納される。記憶部４４内のＮについて除算部４５でｎ”＝［２ｎ＋Ｍ−１／Ｎ］が演算され、記憶部４６に格納される。ｎは値Ｎ、Ｓのビット数であり、制御部４０から除算部４５へ与えられる。ただし、同じＮが２回以上装置４００に入力される場合は、除算部４５中のメモリ内にｎ”＝［２ｎ＋Ｍ−１／Ｎ］を予め保存しておいてもよい。これは図２Ａについて述べたと同様な処理を行えばよい。
制御部４０は、乗算装置４００の各部の制御処理の実行を行い、また記憶部４３について図２Ｂに示したと同様の処理を行う。その後、２のべきによる乗算部５５に記憶部４２のＳと、図２Ｂにおけるｗ′と同様にして決定されたｗ′を入力してＳ２ｗ′を計算し、記憶部５５Ａに格納する。更に、制御部４０は２のべきによる除算部５１にビット数ｎと、記憶部４２のＳを入力してｓ＝［Ｓ／２ｎ−Ｍ］  を計算し、この結果を記憶部５１Ａに格納する。
制御部４０は乗算部５２に記憶部４６，５１Ａの各ｎ”，ｓを入力して、ｔ＝ｎ”ｓを計算し、その結果のｔを記憶部５２Ａに格納する。
【００１７】
次に２のべきによる除算部５３で記憶部５２Ａのｔとｗ′からｔ′＝［ｔ／２２Ｍ−ｗ′−１］を計算し、その結果を記憶部５３Ａに格納する。乗算部５４は、その記憶部５３Ａのｔ′と記憶部４４のＮに対してｔ′Ｎ  を計算し、その結果を記憶部５４Ａに格納する。減算部５６はこの記憶部５４Ａのｔ′Ｎ  と記憶部５５ＡのＳ・２ｗ′に対してＳ′＝Ｓ・２ｗ′−ｔ′Ｎを計算し、その結果Ｓ′  を記憶部５６Ａに格納する。このＳ′を求める計算はＳ・２ｗ′−ｔ′Ｎの上位Ｍ−２  ビットが０となることを利用している。この記憶部５６ＡのＳ′と記憶部４４のＮとを比較部５７で比較し、Ｓ′＜ＮならばＳ′を制御部４０へ渡し、記憶部４２のＳをＳ′で更新する。Ｓ′≧ＮならばＳ′を減算部５８へ渡す。減算部５８はその入力Ｓ′から記憶部４４のＮを減算し、その結果Ｓ′−ＮをＳ′として比較部５７に戻し、再びＳ′＜Ｎを満たすかチェックすることを繰り返す。満足すればそのＳ′を制御部４０に与え、記憶部４２のＳをＳ′により更新する。
制御部４０は、図２Ｂで説明した場合と同様に記憶部４２のＳをＳ′＜Ｎで比較器５７から受けたＳ′  により、またＳ′≧Ｎで減算部５８から受けたＳ′−Ｎにより更新し、図２ＢのステップＳ１に戻り、ここでｋ＝０であれば記憶部４２内のＳをＳ・２ｋｍｏｄＮの最終演算結果として出力する。
【００１８】
Ｚ／ＮＺ上の２のべきによる乗算フロー
図５に、この発明によるＺ／ＮＺ上の２のべきによる乗算の処理の流れを示す。この例も図４に示した装置と同様にＳ・２ｋｍｏｄＮを演算する場合である。
ステップＳ１：  まずＫ＝［ｋ／ｗ］を計算し、
ステップＳ２：  次にｎ”＝［２ｎ＋Ｍ−１／Ｎ］を求める。
ステップＳ３：  次に以下のステップＳ４〜Ｓ８をＫ＝［ｋ／ｗ］回行なう。まずＫ＝０かを調べ、Ｋ＝０でなければ、
ステップＳ４：  ｓ＝［Ｓ／２ｎ−Ｍ］を計算し、
ステップＳ５：  ｔ′＝［ｓ・ｎ”／２２Ｍ−ｗ−１］を計算し、
ステップＳ６：  Ｓ←Ｓ・２ｗ−ｔ′Ｎ  によりＳを更新し、
ステップＳ７：  Ｋを１減らし、
ステップＳ８：  Ｓ＜Ｎかを調べ、
ステップＳ９：  Ｓ＜ＮでなければＳ←Ｓ−Ｎ  を実行してステップＳ８に戻り、ステップＳ８でＳ＜ＮであればステップＳ３に戻り、ステップＳ３でＫ＝０であれば、以下のステップＳ１０〜Ｓ１５を実行する。つまり、
ステップＳ１０：ｗ′＝ｋｍｏｄｗを求め、
ステップＳ１１：ｎ”←［ｎ”／２ｗ−ｗ′］  によりｎ”を更新し、
ステップＳ１２：ｓ＝［Ｓ／２ｎ−Ｍ］ を求め、
ステップＳ１３：ｔ′＝［ｓ・ｎ”／２２Ｍ−ｗ′−１］  を求め、
ステップＳ１４：Ｓ←Ｓ・２ｗ′−ｔ′Ｎ  によりＳを更新し、
ステップＳ１５：Ｓ＜Ｎであるかを調べ、
ステップＳ１６：Ｓ＜ＮでなければＳ−Ｎ  をＳとしてステップＳ１５に戻り、Ｓ＜ＮであればステップＳ１４のＳを出力とする。
【００１９】
図５においても省略したが、図４に示したように、各演算結果は記憶手段に一時格納して利用される。２のべきによる乗算においても課題を解決する手段の項で説明したように、この発明の基本はＳ・２ｗｍｏｄＮの演算である。この演算を行うには、図４中で除算部４５でｎ”を求め、除算部５１、乗算部５２及び除算部５３よりなる第１演算手段５０Ａでｔ′を求め、乗算部５４，５５、減算部５６よりなる第２演算手段５０ＢでＳ’を求め、比較部５７と減算部５８とによりＳ′＜Ｎとなるまでの処理を行い、その結果のＳ′  をＳ・２ｗｍｏｄＮの演算結果として出力すればよい。
図３において、ステップＳ９〜Ｓ１２を先に演算した後、ステップＳ４〜Ｓ８を実行してもよい。同様に図５において、ステップＳ１０〜Ｓ１６を先に実行した後、ステップＳ３〜Ｓ９を実行してもよい。図１中の記憶部２２，２３，２４，２６，２０Ａ，３１Ａ〜３６Ａの全部又はいくつかは、１つの記憶装置の各別の記憶領域を用いることができる。同様に、図４中の記憶部４２，４３，４４，４６，５１Ａ〜５６Ａ，５８Ａの全部又はいくつかは、１つの記憶装置の各別の記憶領域を用いることができる。
【００２０】
１度の計算ビット数Ｍが異なる複数の演算装置を用いて２のべきによる除算Ｓ・２−ｋｍｏｄＮ  を演算する場合の実施例を図６に示す。この例ではｗ＝Ｍがそれぞれｗ１，ｗ２，…，ｗｐ  のｐ個の演算装置を用いる場合である。入力部２１より入力されたＳ，ｋ，Ｎはそれぞれ記憶部２２，２３，２４に格納され、ｋは分割部３７でｋ＝ｗ１＋ｗ２＋，…，＋ｗｐ（ｗｉ＞０，ｉ＝１，  ２，  …，ｐ）を満すｐ個に分割し、それぞれ記憶部３７Ａ１，３７Ａ２，…，３７Ａｐに格納される。２のべきの除算装置３８１，３８２，…，３８ｐ  が設けられ、これらはそれぞれ図１中の逆元演算部２５、剰余手段３０Ａ、乗算加算手段３０Ｂ及び除算部３６の組よりなり、それぞれｗ１，  ｗ２，…，  ｗｐ  が与えられている。除算装置３８１  ではＳ，ｗ１，Ｎを入力して、先に述べた処理でｗをｗ１として
Ｓ１＝Ｓ・２−ｗ１ｍｏｄＮ
を演算し、その結果を記憶部３８Ａ１に格納する。除算装置３８２  ではＳ１，ｗ１，Ｎを入力して、
Ｓ２＝Ｓ１２−ｗ２ｍｏｄＮ＝Ｓ・２−ｗ１−ｗ２ｍｏｄＮ
を演算し、その結果Ｓ２を記憶部３８Ａ２に格納する。以下同様の処理を行い、最終的には除算装置３８ｐ  で
Ｓｐ＝Ｓｐ−１２−ｗｐｍｏｄＮ＝Ｓ・２−ｋｍｏｄＮ
が演算され、これが除算結果として出力される。
【００２１】
なおｋのｐ個の分割ｗ１，ｗ２，…，ｗｐは必ずしも全てが互に異なるものでなくてもよく、同一のものが含まれてもよい。つまり例えばｗ１ビットずつの演算装置とｗ２ビットずつの演算装置との２個を用いる場合ｋ＝ａｗ１＋ｂｗ２＋ｃに分割し、ｗ１ビットずつの演算装置よりなる除算装置３８１  で図１で説明したようにａ回除算を行い、ｗ２ビットずつの演算装置よりなる除算装置３８２  でｂ回除算を行い、ｗ１又はｗ２以下のｃについてはこれをｗ１′又はｗ２′として除算装置３８１  又は３８２  で除算を行えばよい。つまりｗ１〜ｗｐの少くとも２つは異なり、除算装置３８１  〜３８ｐ  は同一のｗｉについては１つの除算装置で処理する。
【００２２】
同様のことは２のべきによる乗算についても言える。その例を図７に示す。入力されたＳ，ｋ，Ｎは記憶部４２，４３，４４に格納され、ｋは、分割部４７でｋ＝ｗ１＋ｗ２＋…＋ｗｐ（ｗｉ＞０，ｉ＝１，２，…，ｐ）を満すｐ個に分割され、記憶部４７Ａ１，４７Ａ２，…，４７Ａｐにそれぞれ格納される。これらｗ１，…，ｗｐは予め決められる。また一度の計算ビット数がＭ１，Ｍ２，…，Ｍｐの２のべきによる乗算装置４８１  ，４８２  ，…，４８ｐ  が設けられる。これら乗算装置４８１  ，４８２  ，…，４８ｐ  はそれぞれ図４中の除算部４５、第１演算手段５０Ａ、第２演算手段５０Ｂ、比較部５７、減算部５８により構成され、それぞれｗ１，  ｗ２，…，ｗｐが与えられる。除算装置４８１  ではＳ，ｗ１，Ｎを入力して、ｗ１をｗ′として上述した処理によりＳ１＝Ｓ・２ｗ１ｍｏｄＮ  を演算して記憶部４８Ａ１に格納する。除算装置４８２  ではＳ１，ｗ２，Ｎを入力して、Ｓ１をＳとし、ｗ２をｗ′として上述した処理により
Ｓ２＝  Ｓ１２ｗ２ｍｏｄＮ＝  Ｓ・２ｗ１＋ｗ２ｍｏｄＮ
を演算し、その結果を記憶部４８Ａ２に格納する。以下同様に処理し、最終的には除算装置４８ｐ  で入力されたＳｐ−１をＳとし、入力されたｗｐをｗ′として
Ｓｐ＝  Ｓｐ−１２ｗｐｍｏｄＮ＝  Ｓ・２ｋｍｏｄＮ
が演算され、Ｓｐが乗算結果として出力される。
【００２３】
なおこの例ではｗ１≦Ｍ１，ｗ３≦Ｍ２，…，ｗｐ≦Ｍｐであるが、除算の場合と同様に例えばｋ＝ａｗ１＋ｂｗ２＋ｃを満すように分割して処理してもよい。従ってこの場合も、乗算装置４８１  ，４８２  …はｐ個以下の数が用いられることになる。
これらの除算においてｎ′＝−Ｎ−１ｍｏｄ  ２ｗ  の値はＮとｗのみにより決まる値である。使用している情報セキュリティ技術においてＮは通常固定された値であり、また同時処理ビット数ｗも固定値であるので、ｎ′は予め計算し、定数として例えばＲＯＭに記憶しておき、必要に応じて読み出して使用するように構成してもよい。
上述した各除算装置、乗算装置はコンピュータによりプログラムを実行させて機能させることもできる。
【００２４】
【発明の効果】
この発明によれば、２のべきによる乗除算では、ｗビット分の演算をまとめて行なうことによって、大きい整数の演算を１／ｗに比例する割合で減らし、剰余環Ｚ／ＮＺ上の２ｋ  による乗除算を高速に行なうことを可能にしている（ｗは計算機が一度に扱うことができるビット数８，１６，３２など）。
これにより、例えば以下の様な効果がある。従来法においては、ｎビットのＳ，Ｎの入力に対して、ｋ回の多倍長ビットシフトと、平均ｋ／２回の多倍長加算（減算）を行なっていた。これに対して、この発明の一例である図１の装置は、ｎビットのＳ，Ｎの入力に対して、ｋ／ｗ回の多倍長ビットシフトと、ｋ／ｗ  回の単精度×多倍長乗算と、ｋ／ｗ回の加算と、ｋ／ｗ回の単精度乗算を行なう。単精度演算は、Ｎの大きさに比べてｗが小さければ、誤差となる。単精度演算（ビットシフト、加算、乗算）が全て同じ演算時間と仮定すると、演算時間は２／ｗになる。つまり、１６ビットの計算機では、Ｎの値が十分大きければ約８倍高速になる。ここで、「多倍長値」は２ｗより大きい値を表し、「単精度」は２ｗ以下の値を表す。
【図面の簡単な説明】
【図１】剰余環Ｚ／ＮＺ上の２のべきによる除算装置の実施例の機能構成を示すブロック図。
【図２】Ａは図１中の逆元演算部２５の具体例を示す機能構成図、Ｂは図１中の制御部２０の一部の処理手順の例を示す流れ図。
【図３】剰余環Ｚ／ＮＺ上の２のべきによる除算の処理手順の例を示す流れ図。
【図４】剰余環Ｚ／ＮＺ上の２のべきによる乗算装置の機能構成の例を示すブロック図。
【図５】剰余環Ｚ／ＮＺ上の２のべきによる乗算処理手順の例を示す流れ図。
【図６】除算装置の他の実施例を示す機能構成図。
【図７】乗算装置の他の実施例を示す機能構成図。
【図１】
0003616385.tif 000004
【図２】
0003616385.tif 000005
【図３】
0003616385.tif 000006
【図４】
0003616385.tif 000007
【図５】
0003616385.tif 000008
【図６】
0003616385.tif 000009
【図７】
0003616385.tif 000010