(57)【特許請求の範囲】
【請求項１】
入力値Ｘ，Ｙを入力する入力手段と、
これらＸ，Ｙをそれぞれ記憶する記憶手段と、
入力値Ｘ，Ｙから gcd(X，Y)＝gcd(U0，V0)2Z0かつz0が最大となるU0，V0，z0を演算するｇｃｄ演算初期設定手段と、gcd(A，B)は ＡとＢの最大公約数を表し、
入力値U0，V0から、予め定められた整数w'≧４に対して
gcd(U0，V0)＝gcd(｜uuU0−uvV0｜/2w'，｜vvV0−vuU0｜/2w')
を満たすuu，uv，vv，vuを演算するｇｃｄ演算疑似演算手段と、
入力値U0，V0，uu，uv，vv，vuから
U'＝｜uuU0−uvV0｜/2w'
V'＝｜vvV0−vuU0｜/2w'
を演算してU0、V0として出力するｇｃｄ演算多倍長演算手段と、
入力値U0，V0，z0から gcd(U0，V0)2Z0 を演算するｇｃｄ演算最終処理手段と、
演算の結果 gcd(X，Y)を出力する出力手段と、
上記各手段を順次動作させ、記憶手段に対する読出し書込みなどを行う制御手段、
とを含む最大公約数演算装置。
【請求項２】
請求項１の装置において、上記制御手段は、
入力値U0，V0の各ビットサイズ中の大きな方の値ｉを求めるビットサイズ取得手段と、
上記値ｉがｗ以下か否かを判定し、ｗ以下でなければ上記ｇｃｄ演算疑似演算手段を実行させ、ｗ以下であれば上記ｇｃｄ演算最終処理手段を実行されるビットサイズ検査手段と、上記ｗは予め決められた４以上の整数であり、
上記ｇｃｄ演算多倍長演算手段の出力中のＶ0 が０であるか否かを判定する最終判定手段と、
上記最終判定手段の判定がV0＝０でなければ上記ｇｃｄ演算多倍長演算手段の出力U0，V0を上記ビットサイズ取得手段に入力して、これを実行させ、上記V0＝０であれば上記ｇｃｄ演算最終処理手段を実行させる手段、
とを含むことを特徴とする最大公約数演算装置。
【請求項３】
請求項２の装置において、上記制御手段は、上記ｇｃｄ演算初期設定手段よりの入力がV0＝１又はU0＝１であるかを判定し、これが成立すれば、上記入力値U0，V0を上記ｇｃｄ演算疑似演算手段へ入力することなく、上記ｇｃｄ演算最終処理手段へ入力する初期判定手段を有していることを特徴とする最大公約数演算装置。
【請求項４】
請求項１，２又は３の装置において、上記制御手段は上記U0，V0から各上位ｗビットのua，vaと各下位ｗビットのｕx ，ｖx をそれぞれを取出す演算ビット取出し手段を有し、
上記ｇｃｄ演算疑似演算手段は、
上記ua，va，ux，vxと、初期値uu＝1，uv＝0，vu＝1，vv＝0とが入力されて、
uxが偶数か、vxが偶数か、ua＞vaか、を判定するux，vx，ua，va状態判定手段と、
uxが偶数でua＝[ua/2]，ux＝ux/2，vu＝2vu，vv＝2vvの演算、
vxが偶数でva＝[va/2]，vx＝vx/2，uu＝2uu，uv＝2uvの演算、
ua＞vaでua＝[(ua−va)/2]，ux＝(ux−vx)/2，及び
uu＝uu＋vu，uv＝uv＋vv，vu＝2vu，vv＝2vvの演算、
その他の場合でva＝[(va−ua)/2]，vx＝(vx−ux)/2，及び
vu＝vu＋uu，vv＝vv＋uv，uu＝2uu，uv＝2uvの演算、
の何れかを実行してuu，vv，uv，vuを更新する更新演算手段と、
上記更新演算手段が演算した回数ｃを計数する計数手段と、
上記回数ｃがw'となるまで上記ux，vx，ua，va状態判定手段と、上記更新演算手段と、上記計数手段とを繰返し実行させる手段、
とを含むことを特徴とする最大公約数演算装置。
【請求項５】
いずれか片方が奇数の入力値Ｘ，Ｎを入力する入力手段と、
これらＸ，Ｎをそれぞれ記憶する記憶手段と、
U0＝X，V0＝N，S0＝0，T0＝1，k＝0を初期設定する拡張ｇｃｄ演算初期設定手段と、
入力値Ｕ，Ｖから予め定められたw'に対して
gcd(U，V)＝ gcd(｜uuU0−uvV0｜/2w，｜vvV0−vuU0｜/2w')
を満たすuu，uv，vv，vuを演算し、ｋにw'を加算する、拡張ｇｃｄ演算疑似演算手段と、
入力値U，V，S，T，uu，uv，vv，vuから
U'＝(uuU0−uvV0)/2w'，    S'＝uuS0＋uvT0 
又は
U'＝−(uuU0−uvV0)/2w'，  S'＝−(uuS0＋uvT0)
と、
V'＝(vvV0−vuU0)/2w'，    T'＝vvT0＋vuS0 
又は
V'＝−(vvV0−vuU0)/2w'，  T'＝−(vvT0＋vuS0)
を演算してU'，V'，S'，T'をそれぞれU0，V0，S0，T0として出力する拡張ｇｃｄ演算多倍長演算手段と、
入力値U0，V0，S0，T0から
｜uuU0−uvV0｜/2c＝ gcd(U，V)
｜vvV0−vuU0｜/2c＝0
を満たすuu，uv，vv，vu，ｃを演算し、
S'＝uuS0＋uvT0 
を演算し、ｋにｃを加算する、拡張ｇｃｄ演算最終処理手段と、
拡張ｇｃｄ演算最終処理手段の演算の結果をS＝X-12k(modＮ)の演算結果として、これとｋを出力する出力手段と
上記各手段を順次動作させ、記憶手段に対する読出し書込みなどを行う制御手段、とを含む拡張最大公約数演算装置。
【請求項６】
請求項５の装置において、上記制御手段は、
入力値U0，V0の各ビットサイズ中の大きな方の値ｉを求めるビットサイズ取得手段と、
上記値ｉがｗ以下か否かを判定し、ｗ以下でなければ上記拡張ｇｃｄ演算疑似演算手段を実行させ、ｗ以下であれば上記拡張ｇｃｄ演算最終処理手段を実行させるビットサイズ検査手段と、
上記拡張ｇｃｄ演算多倍長演算手段の出力中のV0が０であるか否かを判定する最終判定手段と、
上記最終判定手段の判定がV0＝０でなければ上記拡張ｇｃｄ演算多倍長演算手段の出力U0，V0を上記ビットサイズ取得手段に入力して、これを実行させ、V0＝0であれば上記拡張ｇｃｄ演算最終処理手段を実行させる手段、
とを含むことを特徴とする拡張最大公約数演算装置。
【請求項７】
請求項５又は６の装置において、上記制御手段は上記U0，V0から各上位ｗビットのua，vaと、各下位ｗビットのux，vxをそれぞれ取出す演算ビット取出し手段を有し、
上記拡張ｇｃｄ演算疑似演算手段は、上記ua，va，ux，vxと、初期値uu＝1，uv＝0，vu＝1，vv＝0とｋが入力されて、
uxが偶数か、vxが偶数か、ua＞vaか、判定するux，vx，ua，va状態判定手段と、
uxが偶数でua＝[ua/2]，ux＝ux/2，vu＝2vu，vv＝2vvの演算、
vxが偶数でva＝[va/2]，vx＝vx/2，uu＝2uu，uv＝2uvの演算、
ua＞vaでua＝[(ua−va)/2]，ux＝(ux−vx)/2，及び
uu＝uu＋vu，uv＝uv＋vv，vu＝2vu，vv＝2vvの演算、
その他の場合でva＝[(va−ua)/2]，vx＝(vx−ux)/2，及び
vu＝vu＋uu，vv＝vv＋uv，uu＝2uu，uv＝2uvの演算、
の何れかを行ってuu，vu，uv，vvを更新する更新演算手段と、
上記更新演算手段が演算した回数ｃを計数する計数手段と、
上記回数ｃがw'となるまで上記ux，vx，ua，va状態判定手段と、上記更新演算手段と、上記計数手段との処理を繰返し実行させ、回数ｃがw'となった状態でｋをk＋w'に更新する手段、
とを含むことを特徴とする拡張最大公約数演算装置。
【請求項８】
請求項１乃至４の何れかに記載した最大公約数演算装置としてコンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項９】
請求項５乃至７の何れかに記載した拡張最大公約数演算装置としてコンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１０】
入力Ｘ，Ｎに対し、X-1modＮを出力する剰余環Z/NZ上の逆元演算装置であり、入力されたＸ及びＮに対し拡張２進ｇｃｄ演算を行う請求項５乃至７の何れかに記載の拡張最大公約数演算装置と、その拡張最大公約数演算装置から出力されたＳとｋ及び上記Ｎが入力され、Ｓ・２-kmodＮを演算してＸ-1modＮの演算結果として出力する剰余環Z/NZ上の２のべきによる除算装置とを有することを特徴とする逆元演算装置。
【請求項１１】
ｎビットの入力Ｘ，Ｎに対し、X-122nmodＮ を出力する剰余環Z/NZ上のモンゴメリ逆元演算装置であり、ＸとＮが入力され、Ｘ'＝Ｘ・２-tmodＮを演算してＸ'とｔを出力する剰余環Z/NZ上の２のべきによる除算装置と、
上記Ｘ'と上記Ｎが入力され、これらに対し拡張２進ｇｃｄ演算を行い、Ｓ＝Ｘ-1２kmodＮとｋを出力する、請求項５乃至７のいずれかに記載の拡張最大公約数演算装置と、
上記ＳとｋとＮとｔが入力され、Ｎのビット長ｎとｋとｔとから２ｎ−ｋ−ｔが負であればｋ'＝２ｎ＋ｋ＋ｔとＳ'＝Ｓを出力し、２ｎ−ｋ−ｔが正であればｋ'＝２ｎ−ｋ−ｔとＳ'＝Ｓを出力する比較装置と、
上記ｋ'＝−２ｎ＋ｋ＋ｔとＳ'とＮが入力され、Ｔ＝Ｓ'２-k'modＮを演算する剰余環Z／NZ上の２のべきによる除算装置と、
ｋ'＝２ｎ−ｋ−ｔとＳ'とＮが入力され、Ｔ＝Ｓ'２kmodＮを演算する剰余環Z/NZ上の２のべきによる乗算装置と、
上記除算装置及び上記乗算装置より出力される演算結果ＴをＸ-1２2nmodＮの演算結果として出力する出力部とを備えることを特徴とする逆元演算装置。
【請求項１２】
ｎビットの入力Ｘ，Ｎに対し、X-12nmodＮを出力する剰余環Z/NZ上の半モンゴメリ（Kaliski）逆元演算装置であり、入力されたＸ及びＮに対し拡張２進ｇｃｄ演算を行う請求項５乃至７の何れかに記載の拡張最大公約数演算装置と、その拡張最大公約数演算装置から出力されたＳとｋと上記Ｎとが入力され、Ｓ・２-(k-n)modＮ（ｎはＮのビット数）を演算し、Ｘ-1２nmodＮの演算結果として出力する剰余環Z/NZ上の２のべきによる除算装置とを有していることを特徴とする逆元演算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、有限体上の演算に関し、特に誤り訂正符号（代数幾何符号など）や情報セキュリティ技術（暗号鍵生成、ディジタル署名、ブラインド署名、楕円暗号など）を実現するために用いられる最大公約数演算装置、剰余逆元演算、演算装置、及びそのプログラム記録媒体に関する。
【０００２】
【従来の技術】
最大公約数（ｇｃｄ）を求める方法として、(1) Euclidの互除法、(2) ２進ｇｃｄ算法、(3) 算法Ｌが知られている。算法Ｌは大きい数に対するEuclidの互除法を効率化した方法である。
(1) Euclidの互除法
Euclidの互除法は
Xi＝ QiYi＋ Ri                                    (1)
としたときに、
gcd(Xi，Yi)＝ gcd(Yi，Ri)                          (2)
が成り立っていることを利用する。
Xi+1＝ Yi，  Yi+1＝ Ri                             (3)
として、式(1)を繰り返し適用して、X0，Y0からXi，Yiを求め、式(2)を用いて、
gcd(X0，Y0)＝ gcd(X1，Y1)＝…＝ gcd(Xj，0)＝Xj          (4)
であることから、 gcd(X0，Y0)を求めることが出来る。
（文献「D.E.Knuth（中川桂介訳）：“準数値算法／算術演算（THE ART OF COMPUTER PROGRAMMING 第４分冊）”pp．157，算法Ａ，サイエンス社，1986」を参照）
具体例をあげる。Euclidの互除法では、整数
X0 ＝２４，  Y0 ＝９
に対して、以下のような演算を行なう。
X1 ← Y0＝９，    Y1 ← X0 mod Y0＝６
X2 ← Y1＝６，    Y2 ← X1 mod Y1＝３
X3 ← Y2＝３，    Y3 ← X2 mod Y2＝０
この結果、 gcd(X0，Y0)＝gcd(X3，Y3)＝gcd(3，0)＝３が求まる。
Euclidの互除法を行なう装置は、除算装置と減算装置の組合せによって構成することができる。
【０００３】
(2) ２進ｇｃｄ算法
２進ｇｃｄ算法は、
Ｘが奇数、Ｙが偶数のとき：  gcd(X，Y)＝gcd(X，Y/2)
Ｘが偶数、Ｙが奇数のとき：  gcd(X，Y)＝gcd(X/2，Y)
Ｘが奇数、Ｙが奇数のとき：  gcd(X，Y)＝gcd(X，Y−X)
Ｘが偶数、Ｙが偶数のとき：  gcd(X，Y)＝2gcd(X/2，Y/2)
が成り立っていることを利用してｇｃｄを求める方法である。即ち、Xi，Yiのいずれかが奇数であるときに、次の処理、
(A) Xiが奇数、Yiが偶数のとき：  Xi+1←Xi；    Yi+1←Yi/2
(B) Xiが偶数、Yiが奇数のとき：  Xi+1←Xi/2；  Yi+1←Yi 
(C) Xiが奇数、Yiが奇数のとき：  Xi+1←Xi；    Yi+1←Xi−Yi 
を行うことにより得られるXi+1，Yi+1について次式、
gcd(Xi+1，Yi+1)＝ gcd(Xi，Yi)                    (5)
が成り立っていることを利用する。上記処理(A), (B) 及び(C) を繰り返し適用して、X0，Y0からXi，Yiを求め、式(5)を用いて、
gcd(X0，Y0)＝gcd(X1，Y1)＝…＝gcd(Xj，0)＝Xj
であることから、 gcd(X0，Y0)を求めることが出来る。
（文献「D.E.Knuth（中川桂介訳）：“準数値算法／算術演算（THE ART OF COMPUTER PROGRAMMING 第４分冊）”pp．158，算法Ｂ，サイエンス社，1986」を参照）
具体例をあげる。２進gcd 算法では、整数
X0＝２４，  Y0＝９
に対して、以下のような演算を行なう。
X1 ← X0/23＝3；        Y1 ← Y0＝9
X2 ← X1＝3；           Y2 ← (Y1−X1)/2＝3
X3 ← X2＝3；           Y3 ← (Y2−X2)/2＝0
この結果、 gcd(X0，Y0)＝gcd(X3，Y3)＝gcd(3，0)＝３が求まる。
【０００４】
２進 gcd算法は、例えば図１に示すような処理で実現できる。この例では入力Ｘ，Ｙに対応して変数Ｕ，Ｖを使用して以下のように処理を行う。
ステップＳ１：  Ｘ，Ｙをそれぞれ初期値としてＵ，Ｖに設定し、シフト計数ｚに初期値１を設定する。
ステップＳ２：  Ｕ，Ｖが共に偶数か判定する、即ち、最下位ビットが"0" であるか判定する。
ステップＳ３：  Ｕ，Ｖが共に偶数の場合、U/2，V/2をそれぞれＵ，Ｖに設定してシフト計数を２倍（１ビットシフト）し、ステップＳ２に戻る。
ステップＳ４：  Ｖが偶数であるか判定する。
ステップＳ５：  Ｖが偶数の場合、V/2 をＶに設定してステップＳ４に戻る。
ステップＳ６：  Ｖが奇数の場合、Ｕが偶数であるか判定する。
ステップＳ７：  Ｕが偶数の場合、U/2 をＵに設定してステップＳ６に戻る。
ステップＳ８：  Ｕ，Ｖが共に奇数の場合、U>V であるか判定する。
ステップＳ９：  U＞Vの場合、(U-V)/2 をＶに設定してステップＳ４に戻る。
ステップＳ１０：  U≦Vの場合、(V-U)/2 をＶに設定する。
ステップＳ１１：  V＝0か判定し、０でなければステップＳ４に戻る。
ステップＳ１２：  V＝0であればU×zをgcd(X, Y) の演算結果として出力する。
【０００５】
２進 gcd算法を行なう装置は、２による除算と減算のみで構成することができる。２による乗除算は１ビットシフトと等価であるため、電子回路や電子計算機で実装しやすいという利点がある。上記Euclidの互除法、２進ｇｃｄ算法では、入力値Ｘ，Ｙが大きい整数の場合、大きい整数のビットシフトや減算、除算を複数回行なう。例えば、512 ビットで表すことができる整数Ｘ，Ｙに対し、２進ｇｃｄ算法を行なう場合を考える。２進ｇｃｄ算法のループ回数ｋは入力値のサイズからその２倍（この場合は512 〜1024回）となり、ｋ回のビットシフトと、最大ｋ回（平均k/2 回）の減算を行う（図１のステップＳ９又はＳ１０に対応）。また、１回のビットシフト及び加減算にかかる時間も演算する値（この場合はＵ，Ｖ）のビットサイズに比例して大きくなる。このため、大きい整数の演算の回数を減らすことがｇｃｄ演算の高速化につながる。
大きい整数の演算の回数を減らすための方法のひとつに、以下に説明する疑似算法を利用する演算方法がある。これは、ループ中で、大きい整数を使った演算をする代わりに、小さい整数を使った演算により疑似的にｇｃｄ算法を行ない、その後疑似算法で得られた値を用いて、大きい整数の演算をまとめて行なう方法である。
【０００６】
(3) 算法Ｌ
従来、Euclidの互除法に対して、疑似算法を適用した方法があった。（例えば文献「D.E.Knuth（中川桂介訳）：“準数値算法／算術演算（THE ART OF COMPUTER PROGRAMMING 第４分冊）”pp．166，算法Ｌ，サイエンス社，1986」を参照）
具体例をあげる。算法Ｌでは、大きい整数
X0 ＝９１２３４５６７８９０１２３４５６７８９
Y0 ＝２０００００００００００００００００１
に対し、それらの上位例えば４桁の値と、それらの４桁の値に１をそれぞれ加算した値を以下のように小さい整数
x00 ＝９１２３
x10 ＝９１２４
y00 ＝２０００
y10 ＝２００１
として決める。
Xi+1 ＝Yi；      Yi+1 ＝XimodYi 
x0i+1 ＝y1i；    y1i+1 ＝x0imodｙ1i 
x1i+1 ＝y0i；    y0i+1 ＝x1imodｙ0i 
とすると、
x0i/y1i ＜ Xi/Yi ＜ x1i/y0i                       (6)
が成り立つ。算法Ｌでは、Xi，Yiを用いてEuclidの互除法を行うのではなく、x0i，y1i，x1i，y0iを用いてEuclidの互除法を行う。即ち、式(6)の右辺と左辺の整数部分の値が同じである間だけ小さい整数x0i，y1i，x1i，y0iを求める。これを疑似演算と呼ぶ。その後に、疑似演算により得られた値を用いて大きい整数Xi，Yiの演算を行なう。
これにより、大きい整数の演算をまとめて行なうことと同等の効果を得ることができる（例えば、x0i，x1i，y0i，y1iが１０桁の場合、約１２回分の演算を１度にまとめることができる）。また、この方法を２進ｇｃｄ算法へ適用することも可能である。
【０００７】
【発明が解決しようとする課題】
算法Ｌの問題点は、疑似演算において、x0i，y1iをもちいたEuclidの互除法とx1i，y0iをもちいたEuclidの互除法を両方とも行なう必要があることと、一度にまとめることが出来る演算の回数がその時によって異なることである。
通常の計算機はＭビット（Ｍは８、１６、３２等）の単位で読み書き可能な記憶装置を有している（条件１）。このことから、Ｍビット単位で演算を行なうと効率が良い。例えば、２進ｇｃｄ算法では、大きい整数の１ビットシフトを行なっている。しかし、条件１の下では、１ビットのシフトはＭビットまとめてシフトを行なうのと同じか、より多くのコストがかかる。更に、現代の計算機はＭビット（Ｍは８、１６、３２等）のシフタ、加減算器、乗算器などを有している（条件２）。この場合は、Ｍビット未満の演算を１回行なうのと、Ｍビットの演算を１回行なうのは同じ時間がかかる。このことから、Ｍビット単位で演算を行なうのが効率が良い。
一方、算法Ｌでは、まとめて行なえる演算のビット数がその時によって変わってしまうため、まとめ演算のメリット
（効果）が減ってしまう。
【０００８】
【課題を解決するための手段】
この発明では２進ｇｃｄ算法に対して疑似算法を用いるが、以下に詳細に説明するように誤差範囲を求めないで実現する。
算法Ｌでは、Xi，Yiの代わりに、小さい整数x0i，x1i，y0i，y1iを用いて疑似演算を行なう。x0iとx1iがそれぞれXiの取り得る値の下限と上限とを代表し、y0iとy1iがそれぞれYiの取り得る値の下限と上限とを代表する。上限と下限の差（誤差範囲）がある程度開くまで疑似演算を続ける。
この発明では、Xiの値を代表する小さい整数を、上限と下限の中間の値ｘa のみにする。また、誤差範囲を求めず、予め定められた回数w'回の疑似演算を行なう。
【０００９】
これによる利点は２つある。
(1) 誤差範囲を用いる方法に比べ、一度に多くの疑似演算を行なえるため、多倍長の演算の回数が減る。
(2) 一定の値w'ビットのシフト演算を行なうことができる。
これらによって２進ｇｃｄ算法の高速化を可能にする。
算法ＬはEuclid互除法や２進ｇｃｄ演算法の動作と同等の演算を行なうが、この発明では、同等の動作をしない場合もある。例えば、２進ｇｃｄ演算法では、ループ中でＵとＶの大小比較を行なう。Ｕ，Ｖの値が離れていれば、上位数桁のみを見ることによって大小比較が出来る。ところが、Ｕ，Ｖの値が近い場合には、Ｕ，Ｖの演算のシミュレートを行なっている小さい整数ua，va（Ｕ，Ｖの上位数桁に相当する）だけではどちらが大きいか判別不能な場合がある。このような場合、算法Ｌでは一度疑似演算を終了し、Ｕ，Ｖの値を計算しなおしてから大小判定をしていた。
この発明では、その場合でも疑似演算を続行する。従って、この発明では大小関係を誤る場合もある。大小関係を誤ると、Ｕ，Ｖが負の値になる（算法Ｌではそういうことは起こらない）。しかし、gcd(U，V)＝gcd(｜U｜，｜V｜)とすることによって、この発明が誤った答えが出力されることを防いでいる。これにより、この発明は算法Ｌよりも一度にまとめる演算数を増やし、多倍長の演算の回数を減らした。また、この発明は予め決められたビット数（w'ビット）ずつの演算を行なうことが可能となる。
【００１０】
ｇｃｄ演算アルゴリズム
以下にこの発明による拡張２進ｇｃｄ演算装置の理解を容易にするため、まずこの発明の原理を通常の２進ｇｃｄ演算に適用した場合のアルゴリズムを示す。
ステップＳ１（多倍長値初期設定）：
U←Y；V←X；S←0；T←1。
ステップＳ２（単精度値初期設定）：
ｉ←max(Ｖのサイズ；Ｕのサイズ)
va←Ｖの上位ｗビット；ua←Ｕの上位ｗビット
vx←Ｖの下位ｗビット；ux←Ｕの下位ｗビット
【数１】
0003673785.tif 000002
もしｉ≦ｗならばステップＳ５へ。
ステップＳ３（単精度演算ループ）：  以下をｗ回繰り返す：
(1) uxが偶数ならば
【数２】
0003673785.tif 000003
(2) vxが偶数ならば
【数３】
0003673785.tif 000004
(3) vx, ux が奇数かつua＞vaならば
【数４】
0003673785.tif 000005
(4) vx, ux が奇数かつua≦vaならば
【数５】
0003673785.tif 000006
ステップＳ４（多倍長値再計算）：
【数６】
0003673785.tif 000007
U ← ｜U'｜/2w；  V ←｜V'｜/2w
もしV＝0ならばステップＳ５へ、それ以外はステップＳ２へ。
ステップＳ５（最終処理演算）：
V＝0ならば  Ｕを出力。
V≠0ならば  gcd(U, V)を求めて出力（単精度ｗビット以下の演算）
上記アルゴリズムの妥当性
命題１：上記アルゴリズムが終了すれば、gcd(X, Y)を出力する。
証明：上記アルゴリズムでは常にgcd(U, V)＝gcd(X, Y)が成り立っている。これを帰納法により証明する。
【００１１】
１．ステップＳ１ではU＝X，V＝Yであるから、gcd(U, V)＝gcd(X, Y)が成り立つ。
２．ステップＳ３及びＳ４では
Ｕが偶数の場合：U←U/2
Ｖが偶数の場合：V←V/2
U, V が共に奇数でU＞Vの場合：U←(U-V)/2
U, V が共に奇数でU≦Vの場合：V←(V-U)/2
のうちのいずれかに相当する演算が行われる。即ち、ステップＳ３開始時にgcd(U, V)＝gcd(X, Y)ならば、ステップＳ４終了時にもgcd(U,           V)＝gcd(X, Y)が成り立っている。ただし、ここではgcd(U, V)＝gcd          (｜U｜, ｜V｜)とする。
上記１、２より、上記アルゴリズムが終了すればgcd(X, Y)を出力する。
上記アルゴリズム終了の根拠
命題２：ｗ≧４ならば上記アルゴリズムは有限時間で終了する。
証明：上記ステップＳ２の時点でのＵ，Ｖの値をU0, V0とし、ステップＳ４において再計算されるＵ，ＶをU1, V1とする。このとき、
U0＋V0＞U1＋V1
を示せばよい。上記アルゴリズム中でU＋Vは単調減少となり、U＋V＜2wとなった時点でステップＳ５が実行され、終了する。発明者は上記式が成り立つことを証明することができるが、ここでは省略する。
【００１２】
【発明の実施の形態】
ｇｃｄ演算装置
図２及び図３を参照してｇｃｄ演算装置1000を説明する。この装置1000は入力部１０１によりＸ，Ｙが入力され、出力部１０２からgcd(X, Y) を出力する装置であって、ｇｃｄ演算初期設定部１１０と、ｇｃｄ演算疑似演算部１２０と、ｇｃｄ演算多倍長演算部１３０と、ｇｃｄ演算最終演算部１４０と制御装置１５０と、記憶手段１６０とを備え、以下のように演算が実行される。
ステップＳ１：  ｇｃｄ演算初期設定部１１０は、入力Ｘ，Ｙに対して
gcd(X，Y)＝2Z0gcd(U，V)                     (7)
を満たすＵ，Ｖ，z0のうち、z0が最大となるものを求め、その時のＵ，ＶをそれぞれU0，V0として、制御装置１５０へ渡し、制御装置１５０を介してz0をｇｃｄ演算最終処理部１４０へ渡す。
ステップＳ２：  制御装置１５０は、入力U0，V0に対し、U0=1又はV0=1であるかどうかを検査する。検査に合格した場合、即ち、U0=1又はV0=1の場合は、ｇｃｄ演算最終処理部１４０にU0，V0を渡す。
ステップＳ３：  そうでない場合、制御装置１５０は、入力U0，V0に対し、そのビットサイズの大きい方の値ｉを求める。
ステップＳ４：  ビットサイズｉがｗビット以下であるかどうかを検査する。検査に合格した場合は、ｇｃｄ演算最終処理部１４０にU0，V0を渡す。ビットサイズｉがｗ以下でなかった場合は、
va＝V0の上位ｗビット（第ｉビット目から第i-w+1ビット目まで）
ua＝U0の上位ｗビット（第ｉビット目から第i-w+1ビット目まで）
vx＝V0の下位ｗビット
ux＝U0の下位ｗビット
の各値をｇｃｄ演算疑似演算部１２０へ渡し、U0，V0をｇｃｄ演算多倍長演算部１３０へ渡す。
【００１３】
ステップＳ５：  ｇｃｄ演算疑似演算部１２０は、U0，V0の上下位ｗビット分であるva，ua，vx，uxの各値を用いて、図６，７を参照して後述するようにｇｃｄ演算をシミュレートする。結果の値uu，uv，vu，vvをｇｃｄ演算多倍長演算部１３０へ渡す。
ステップＳ６：  ｇｃｄ演算多倍長演算部１３０は、
U0←｜uuU0−uvV0｜/2w；      V0←｜vvV0−vuU0｜/2w
を計算し、それぞれを更新されたU0，V0として、制御装置１５０へ渡す。
ステップＳ７：  制御装置１５０はV0＝0 かを検査し、０でなければ、ステップＳ３に戻り、V0＝0であればU0，V0をｇｃｄ演算最終演算部１４０へ渡す。
ステップＳ８：  ｇｃｄ演算最終演算部１４０は、入力U0，V0，z0に対して２Z0gcd(U0，V0)を求めて出力する。V0=0の場合は、2z0gcd(U0, 0)=U02z0を出力することになる。
従って制御装置１５０には、U0＝１又はV0＝１を検査する初期判定手段1-20、V0，U0のビットサイズの大きな方の値ｉを求めるビットサイズ取得手段1-30、ビットサイズｉがｗより小さいかを検査するビットサイズ検査手段1-40、V0＝０かを検査する最終検査手段1-70、前記ステップ４でV0，U0から各上位ｗビット、各下位ｗビットを取出す演算ビット取出し手段1-41を備え、またこのｇｃｄ演算装置1000には、各種データや演算、制御、処理上必要とするデータなどを記憶する記憶部１６０が設けられている。
【００１４】
ｇｃｄ演算初期設定部１１０
図４及び図５を参照してｇｃｄ演算初期設定部１１０の動作を説明する。
ステップＳ１：  数えあげ部１１１及び１１２は、入力X，Yそれぞれの最下位ビットから連続するゼロの個数を数えて、その値x0，y0を比較部１１３へ出力する（例えば入力の２進数表現が101000ならば、出力は３である）。
ステップＳ２：  比較部１１３は、入力された値x0，y0を比較し、より小さい方をz0として出力する。
ステップＳ３：  ２のべきによる除算部１１４及び１１５は、それぞれ入力Ｘ，Ｙとz0が入力され、入力された値Ｘ，Ｙに対してそれぞれ２Z0による除算を行ない、その除算結果U0，V0を出力する。ｇｃｄ演算初期設定１１０はU0，V0，z0を出力する。
【００１５】
ｇｃｄ演算疑似演算部１２０
図６，図７を参照して、ｇｃｄ演算疑似演算部１２０の動作を説明する。
ステップＳ１：  制御装置１５０からva，ua，vx，uxの各値が制御部１２１に入力されると、メモリ１２２は、決められたuu，uv，vu，vv，ｃの初期値を制御部１２１へ送る。
ステップＳ２：  制御部１２１は、データα＝｛va，ua，vx，ux，uu，uv，vu，vv，ｃ｝が入力されると、uxが偶数かどうかを検査する。偶数ならば、場合１ユニット１２３へデータα＝｛va，ua，vx，ux，uu，uv，vu，vv，ｃ｝を送る。
ステップＳ３：  uxが偶数の場合、場合１ユニット１２３は、
ua ← [ua/2]；    ux ← ux/2
vu ← 2vu；     vv ← 2vv 
の演算を行ない、制御部１２１へデータα'＝｛va，ua，vx，ux，uu，uv，vu，vv，ｃ｝を送る。
ステップＳ４：  uxが偶数でない場合、制御部１２１は、vxが偶数かどうかを検査する。偶数ならば、場合２ユニット１２４へデータα＝｛va，ua，vx，ux，uu，uv，vu，vv，ｃ｝を送る。
ステップＳ５：  uxが奇数でvxが偶数の場合、場合２ユニット１２４は、
va ← [va/2]；    vx ← vx/2
uu ← 2uu；     uv ← 2uv
の演算を行ない、制御部１２１へデータα'＝｛ｖa，ua，vx，ux，uu，uv，vu，vv，ｃ｝を送る。
【００１６】
ステップＳ６：  制御部１２１は、ux，vxが共に奇数の場合、uaとvaの大小比較を行なう。ua＞vaならば、場合３ユニット１２５へデータα＝｛va，ua，vx，ux，uu，uv，vu，vv，ｃ｝を送り、ux，vxともに奇数かつua≦vaならば、場合４ユニット１２６へデータα＝｛va，ua，vx，ux，uu，uv，vu，vv，ｃ｝を送る。ステップＳ７：  ux, vxが奇数で、ua＞vaの場合、場合３ユニット装置１２５は、
ua ← [(ua−va)/2]；  ux ← (ux−vx)/2
uu ← uu＋vu；        uv ← uv＋vv
vu ← 2vu；           vv ← 2vv
の演算を行ない、制御部１２１へデータα'＝｛va，ua，vx，ux，uu，uv，vu，vv，ｃ｝を送る。
ステップＳ８：  ux, vxが奇数でua≦vaの場合、場合４ユニット１２６は、
va ← [(va−ua)/2]；    vx ← (vx−ux)/2
vu ← vu＋uu；          vv ← vv＋uv
uu ← 2uu；             uv ← 2uv
の演算を行ない、制御部１２１へデータα'＝｛va，ua，vx，ux，uu，uv，vu，vv，ｃ｝を送る。
ステップＳ９：  場合１ユニット１２３乃至場合４ユニット１２６の何れかでデータαの処理がなされてデータα' として制御部１２１に戻されると、制御部１２１はｃの値を１増やす。
【００１７】
ステップＳ１０：  そのｃとw'とを比較し、ｃ＜w'であればステップＳ２に戻り、ｃ＝w'ならば｛uu，uv，vu，vv｝をｇｃｄ演算疑似演算部１２０からｇｃｄ演算多倍長演算部１３０へ出力する。
制御部１２１は入力されたux，vx，ua，vaの状態から場合１ユニット１２３〜場合４ユニット１２６の何れで処理させるかの状態判定手段6-21、場合ユニット１２３〜１２６で処理した結果を記憶する処理結果記憶手段6-22、処理回数ｃを計数する計数手段6-23、処理を終了とするか、つまりｃ＝w'か否かを判定する処理終了判定手段6-24を備えている。
このｇｃｄ演算疑似演算部１２０はU0，V0の各下位ｗビットの値ux，vxにより、それぞれU0，V0が偶数か否かの判定を行い、U0，V0の各上位ｗビットの値ua，vaによりU0とV0の大小比較を行い、これらにもとづいて、従来の２進ｇｃｄ算法と同様の処理を行っている。このことは図７の処理手順と、図１に示した従来の２進ｇｃｄ算法の処理手順とを比較すれば直ちに理解されよう。またここでは次式
gcd(U0，V0)＝gcd(｜uuU0−uvV0｜/2w'，｜vvV0−vuU0｜/2w')      (8)
を満たすuu，uv，vu，vvを求めていることになる。
【００１８】
ｇｃｄ多倍長演算部１３０
図８を参照してｇｃｄ多倍長演算部１３０の動作を説明する。
図８において、ｇｃｄ多倍長演算部１３０には制御装置１５０からU0，V0が、ｇｃｄ演算疑似演算部１２０からuu，uv，vu，vvをそれぞれ入力される。乗算器１３ａ〜１３ｄはそれぞれ積uuU0，uvVv，vuU0，vvV0を計算して出力する。
減算器１３ｅ及び１３ｆはそれぞれ差U1=uuU0−uvV0及びV1=vvV0−vuU0を計算して絶対値器１３ｇ及び１３ｈに出力する。
絶対値器１３ｇ及び１３ｈはそれぞれ入力U1及びV1の絶対値を計算して２のべきによる除算器１３ｉ及び１３ｊに出力する。
２のべきによる除算器１３ｉ及び１３ｊはそれぞれ入力｜U1｜及び｜V1｜の２w'による除算を計算しこれをU0及びV0としてｇｃｄ多倍長演算部１３０の出力とする。
図８のｇｃｄ多倍長演算部１３０の処理を以下にまとめて示す。
ステップＳ１：  V1＝(-vuU0＋vvV0)/2w'
U1＝(uuU0−uvV0)/2w'
を演算する。
ステップＳ２：  V1 ←｜V1｜；    U1 ←｜U1｜
ステップＳ３：  V0 ← V1   ；    U0 ← U1
図８においては、2w' による除算を、絶対値を求めた後に行っているが、上記ステップＳ１に示すように2w' による除算を、絶対値を求める前に行ってもよい。得られたU0，V0は制御装置１５０に入力され、図３で説明したようにV0＝０かのチェックが行われる。
【００１９】
ｇｃｄ演算最終処理部１４０
図９を参照してｇｃｄ演算最終処理部１４０の動作を説明する。
ｇｃｄ演算最終処理部１４０には制御装置１５０からU0，V0が、初期設定部１１０からｚ0 がそれぞれ入力される。小さい数のｇｃｄ演算部１４１は入力U0，V0のｇｃｄを計算して２のべき乗倍部１４２に出力する。２のべき乗倍部１４２は入力gcd(U0，V0) とz0を用いて2z0gcd(U0，V0)を計算してこの最終処理部１４０の出力とする。つまりｇｃｄ演算装置1000の出力となる。
このｇｃｄ演算最終処理装置１４０はその処理手順を図１０に示すように、最後のステップＳ１０で２Z0を乗算補正する以外は図１に示した従来の２進ｇｃｄ算法と基本的に同一手順である。更に詳細にみれば、図１０のステップＳ１〜Ｓ９は、図７のステップＳ１〜Ｓ９におけるux, uu, vx, vu, vvに対する処理と同じである。
以上のようにして入力Ｘ，Ｙの最大公約数を求めることができる。しかも、ｇｃｄ演算最終処理部１４０を除いては、全て演算単位がｗ又はw'ビットであり、全体として少ない処理で行うことができる。なお図２，図３についての説明から理解されるように、図２中の各部は順次処理されるものであり、従って図６では説明の便宜上制御部１２１を設けたが、この制御部１２１は制御装置１５０で行うことができ、その他の各部も制御装置１５０により制御され、また各部において各処理上必要とする記憶部（メモリ）は図２中の記憶部１６０を利用することができる。
【００２０】
拡張２進ｇｃｄ演算装置2000
図１１を参照して拡張２進ｇｃｄ演算装置2000を説明する。この装置2000はＸ，Ｙの入力に対して、gcd(X，Y) と、S＝2kX-1modＹ及びｋを出力する。
この装置2000は拡張ｇｃｄ演算初期設定部２１０、拡張ｇｃｄ演算疑似演算部２２０、拡張ｇｃｄ演算多倍長演算部２３０、拡張ｇｃｄ演算最終演算部２４０、制御装置２５０からなり、図１２に示すように以下の演算が実行される。
ステップＳ１：  拡張ｇｃｄ演算初期設定部２１０は、入力Ｘ，Ｙに対して
gcd(X，Y)＝2z0gcd(U0，V0)                    (9)
を満たすU0，V0，z0のうち、z0が最大となるものを求める。Ｓ，Ｔ，ｋの初期値S0＝０、T0＝１，ｋ＝０とともにU0，V0を制御装置２５０へ渡し、制御装置２５０を介してz0を拡張ｇｃｄ演算最終処理部２４０へ渡す。
ステップＳ２：  制御装置２５０は、入力U0，V0，S0，T0，ｋに対し、U0＝１またはV0＝１であるかどうかを検査する。検査に合格した場合は、拡張ｇｃｄ演算最終処理部２４０にU0，V0，S0，T0，ｋを渡す。
ステップＳ３：  制御装置２５０は、U0=1又はV0=1でなかった場合、入力U0，V0，S0，T0，ｋに対し、U0とV0のビットサイズ中の大きい方のビットサイズ値ｉを求める。
ステップＳ４：  制御装置２５０はその値ｉがｗビット以下であるかどうかを検査する。検査に合格した場合、拡張ｇｃｄ演算最終処理部２４０に、U0，V0，S0，T0，ｋを渡す。上記いずれの検査にも合格しなかった場合は、
va ＝V0 の上位ｗビット（第ｉビット目から第i-w+1ビット目まで）
ua ＝U0 の上位ｗビット（第ｉビット目から第i-w+1ビット目まで）
vx ＝V0 の下位ｗビット
ux ＝U0 の下位ｗビット
の各値を拡張ｇｃｄ演算疑似演算部２２０へ渡し、U0，V0，S0，T0を拡張ｇｃｄ演算多倍長演算部２３０へ渡す。ｋにw'を加算する。
【００２１】
ステップＳ５：  拡張ｇｃｄ演算疑似演算部２２０は、U0，V0の上下位ｗビット分であるva，ua，vx，uxの各値を用いて、拡張ｇｃｄ演算をシミュレートする。その結果の値uu，uv，vu，vvの各値を拡張ｇｃｄ演算多倍長演算部２３０へ渡す。
ステップＳ６：  拡張ｇｃｄ演算多倍長演算部２３０は、図１３を参照して後述するように
U'＝(uuU0−uvV0)/2w'，
V'＝(vvV0−vuU0)/2w'，
S'＝uuS0＋uvT0，
T'＝vvT0＋vuS0
を計算する。ここで、V'が負ならばV'とT'の符号を反転し、U'が負ならばU'とS'の符号を反転する。演算の結果得られたU'，V'，S'，T'をU0，V0，S0，T0として制御装置２５０へ渡す。
ステップＳ７：  制御装置２５０はV0＝０かを検査し、０でなければステップＳ３に戻り、０であれば拡張ｇｃｄ演算最終演算部２４０の処理に移る。
ステップＳ８：  拡張ｇｃｄ演算最終演算部２４０は、V0≠０なら入力U0，V0，z0に対して2Z0gcd(U0，V0)を求めて出力する。また、V0＝０ならS＝2kX-1modＹなるＳ，ｋを求め、出力する。
【００２２】
図１１には特に示していないが、この拡張ｇｃｄ演算装置2000にも、図２中に示した初期判定手段1-20、ビットサイズ取得手段1-30、ビットサイズ検査手段1-40、演算ビット取出手段1-41、最終判定手段1-70、記憶部１６０に対応するものが設けられている。
拡張ｇｃｄ演算初期設定部２１０は、図２中のｇｃｄ演算初期設定部１１０と同様に図４に示した機能構成を有し、図５に示した処理を行うが、これらと異なる点は記憶部に記憶されているＳ，Ｔ，ｋの各初期値S0＝０，T0＝１，ｋ＝０を出力して制御装置２５０へ渡す。
拡張ｇｃｄ演算疑似演算部２２０の機能構成は図６に示したｇｃｄ演算疑似演算部１２０のそれとほぼ同一であり、またその処理も図７に示した処理とほぼ同一であるが、異なる点は図７中のステップＳ９に括弧書きで示しているようにｋの値を１増加させる処理も行っている。つまり疑似演算部１２０で求めたuu，uv，vu，vvを出力すると共にｋにｗを加算して出力することになる。従って拡張ｇｃｄ演算疑似演算部２２０の制御部にはｋを計数する手段も設けられる。ステップＳ９でｋを＋１する代りに、ステップＳ１０でｃ＝ｗとなった時に、ｋ＋ｗ＝ｋとしてもよい。
【００２３】
拡張ｇｃｄ多倍長演算部２３０
図１３，図１４を参照して拡張ｇｃｄ多倍長演算部２３０の動作を説明する。この演算部２３０には図１１における制御装置２５０からU0，V0，S0，T0が、また拡張ｇｃｄ演算疑似演算部２２０からuu，uv，vu，vvが入力される。
乗算器２３ａ〜２３ｈはそれぞれ積uuU0，uvV0，vuU0，vvV0，uuS0，uvT0，vuS0，vvT0を計算して出力する。
減算器２３ｉ及び２３ｊはそれぞれ差U'＝uuU0−uvV0及びV'＝vuV0−uvU0を計算して出力する。
加算器２３ｋ及び２３ｌはそれぞれ和S'＝uuS0＋uvT0及びT'＝vvT0＋vuS0を計算して出力する。
制御部２３ｍは入力U'，S'に対して、U'＜０ならば、符号反転器２３ｏにU'，S'を出力し、符号反転器２３ｏから、−U'，−S'を新たな入力U"，S"として受ける。U'≧０ならば、U'を２のべきによる除算器２３ｑに出力し、S'をS0として演算部２３０より出力する。
制御部２３ｎは入力V'，T'に対して、V'＜０ならば、符号反転器２３ｐにV'，T'を出力し、符号反転器２３ｐから、−V'，−T'を新たな入力V"，T"として受ける。V'≧０ならば、V'を２のべきによる除算器２３ｒに出力し、T'をT0として演算部２３０から出力する。
【００２４】
２のべきによる除算器２３ｑは入力U'の２w'による商U1を計算してU0として演算部２３０の出力とする。２のべきによる除算器２３ｒは入力V'の２w'による商V1を計算してV0として演算部２３０の出力とする。
以上の拡張ｇｃｄ多倍長演算部２３０の処理をまとめて図１４に示す。
0003673785.tif 000008
を演算する。
ステップＳ２：  V1が０より小か判定し、０より小でなかったらそのままステップＳ４に移る。
ステップＳ３：  V1が０より小であれば、V1← -V1及びT1← -T1により符号を変える。
ステップＳ４：  U1が０より小か判定し、０より小でなければそのままステップＳ６に移る。
ステップＳ５：  U1が０より小であれば、U1← -U1及びS1← -S1により符号を変える。
ステップＳ６：  得られたV1, U1, S1, T1を更新されたV0, U0, S0, T0として出力する。
この拡張ｇｃｄ演算多倍長演算部２３０の出力は制御装置２５０に入力される。
【００２５】
拡張ｇｃｄ演算最終処理部２４０
拡張ｇｃｄ演算最終処理部２４０は図９に示した最終処理部１４０とほぼ同様の機能構成をとり、入力されU0，V0を初期値として、gcd(U，V) を演算し、その演算結果とgcd(U，V) とz0を用いて2z0gcd(U，V)が計算されて出力される。最終処理部１４０と異なる点は、この最終処理部２４０にはS0，T0，ｋも入力され、図１０に示したｇｃｄ演算処理の一部を図１５に示すようにステップＳ３、Ｓ５、Ｓ７、Ｓ８の次にｋを＋１するステップS8-1の処理を行ってステップＳ９に移る。またステップＳ９でvx＝０であれば、ステップS9-1でS＝(uuS0＋uvT0) を演算し、その結果Ｓと、ｋを出力する。このＳはS＝2kX-1modＹの演算結果と一致する。
この拡張ｇｃｄ演算装置2000も、ｇｃｄ演算装置1000と同様に１つの制御装置２５０で各部を処理することができ、またこれら演算処理をプログラムの解読実行により行うこともできる。その場合は各演算処理に当り、必要なデータを記憶手段から読出したり、一時的に蓄えたバッファから取出したり、また演算結果を記憶手段に書込んだり、バッファへ一時的に蓄えたりするステップを供することになる。この実施例では、入力Ｘ，Ｙが、共に偶数の場合は gcd(X，Y)＝２z0ux を出力し、Ｘ，Ｙの一方が奇数かつ、 gcd(X，Y)＝1の場合はＳとｋを出力させるようにした。従って、拡張ｇｃｄ演算初期設定部２１０では、Ｘ，Ｙの何れが奇数かをまず判断し、奇数の場合はz0を求めることなく、ＸをU0，ＹをV0とし、ｗ，S0＝０，T0＝１，ｋ＝０を出力するようにしてもよい。しかし、例えば逆元を求める場合はＸ、Ｙの一方が奇数でないと求められない。つまり、予め、入力値の一方が奇数であることがわかっている場合は、拡張ｇｃｄ演算初期設定部２１０では、単にU0＝X，V0＝Y，S0＝０，T0＝１，ｋ＝０とする初期設定のみを行えばよい。つまりＸをU0として、ＹをV0として、またS0＝０，T0＝１，ｋ＝０をメモリから読出して出力すればよい。
【００２６】
上述では一度に演算することのできるビット数をｗ及びw'としたが、疑似演算部（１２０，２２０）で一度に計算する量w'と多倍長演算部（１３０，２３０）とで一度に計算する量ｗとを同じ値としてもよい。
先に述べたように拡張２進ｇｃｄ演算装置は２のべきによる除算装置と組み合わせて剰余環Z/NZ上の逆元演算装置を構成することができる。図１６はこの発明の拡張２進ｇｃｄ演算装置を使って通常逆元演算装置を構成した場合である。図に示すように、整数ＸとＮがこの装置3000に入力され、まず図１１で説明した拡張２進ｇｃｄ演算装置３１５で拡張２進ｇｃｄ演算がなされ、S＝X-12kmodＮ とｋとが出力され、このＳ，ｋとＮがZ/NZ上の２のべきによる除算装置３１８に入力されS・2-kmodＮ が演算され、その演算結果としてX-1modＮ、つまりＸのZ/NZ上の逆元演算結果が得られる。
【００２７】
図１７に剰余環Z/NZ上の半モンゴメリ（Kaliski）逆元演算にこの発明の拡張ｇｃｄ演算装置を適用した場合の逆元演算装置3100を示す。この装置3100に整数Ｘ，Ｎが入力され、Ｘ，Ｎについて図１１を参照して説明した拡張ｇｃｄ演算装置３１５による演算がなされ、その結果のS＝X-12kmodＮ とｋと入力ＮとがZ/NZ上の２のべきによる除算装置３２０に入力されて、S・2-(k-n)modＮ が演算され（ｎはＮのビット数）、結果としてX-12nmodＮが得られる。
図１８はZ/NZ上のMontgomery逆元演算にこの発明の拡張２進ｇｃｄ演算装置を適用した場合の逆元演算装置3200を示す。図に示すように、入力された整数Ｘ，Ｎについて拡張ｇｃｄ演算装置３１５でS＝X-12kmodＮ 及びｋを求め、これに対しZ/NZ上の２のべき乗倍装置３２５でS・22n-kmodＮを演算してX-122nmodＮを得ることもできる。
【００２８】
図１９は、Z/NZ上のモンゴメリ逆元演算装置にこの発明の拡張ｇｃｄ演算装置を適用した場合の装置5000を示す。図１９に示すように、制御部５１０の制御のもとに、まずZ/NZ上の２のべきによる除算装置５１４でX'＝X・2-tmodＮ を演算し、その演算結果X'とＮについて拡張ｇｃｄ演算装置５１５によりS＝X-12kmodＮ とｋを求める。これらＳ，ｋを比較装置５１７に入力してＮのビット長ｎとｋとｔとから2n-k-tの正負を判定し、負ならばk'＝-2n+k+t とS'＝ＳをZ/NZ上の２のべきによる除算装置518Aに入力し、T＝S'2-k'modＮを演算する。2n-k-tが正ならばk'＝2n-k-tとS'＝ＳをZ/NZ上の２のべきによる乗算装置518Bに入力し、T＝S'2k'modＮ を演算する。出力部５１９は、演算装置518Aと518Bの何れかのＴをX-122nmodＮ の演算結果として出力する。
上述してきたこの発明による最大公約数又は拡張最大公約数演算装置あるいは逆元演算装置としてコンピュータを機能させるためのプログラムは、例えば図２０に示す演算装置１０Ａ内の主記憶装置１３に格納されて使用される。演算装置１０Ａは例えばコンピュータで実現され、ＣＰＵ１１と、ＲＡＭ１２と、主記憶装置１３とか等構成され、キーボード１４と、表示装置１５とが接続されている。ＣＰＵ１１として例えば１度に１６ビットずつ演算を行う１６ビットのチップセットを使用した場合、この発明の実施例で説明したように２のべきによる乗除算を行う場合に１６ビットずつまとめて行うのが好ましい。
【００２９】
ＣＰＵ１１は主記憶装置１３内の演算プログラムに従って最大公約数又は拡張最大公約数演算あるいは逆元演算を実行する。ＲＡＭ１２はこれら演算に必要な各種パラメータの値や変数値を保持したり、演算の途中結果や最終結果を保持する。利用者Ａはキーボード１４からプログラムの実行命令を入力し、演算の実行経過が表示装置１５に表示される。
ここで、この発明の逆元演算装置がセキュリティ技術の例であるディジタル署名において使用される場合について説明する。利用者Ａの演算装置１０Ａは例えばネットワークＮＷを介して利用者Ｂの演算装置１０Ｂに接続されており、利用者Ａは文書ｍに対しディジタル署名Ｓをつけて利用者Ｂの演算装置１０Ｂに送信し、利用者Ｂは受信した署名Ｓの正当性を検証する。ここでは、ディジタル署名として、ESIGN 方式を使う場合で説明する。この場合、利用者ＡとＢは公開鍵ｎとシステムパラメータｋを共有し、送信側利両者Ａは素数の秘密鍵ｐ，ｑを秘密に保持している。ただしｎ＝ｐｑである。
ディジタル署名方式ESIGN を実行するためのプログラム１３Ｐは主記憶装置１３ないに格納されている。そのプログラム１３Ｐの一部として、ディジタル署名生成の一過程で使用される逆元演算を含む式をこの発明の演算方法により実行する部分プログラム13PPが設けられている。
【００３０】
まず、利用者Ａの演算装置１０Ａでは、乱数ｘを生成する。次に、文書ｍをハッシュ関数に入れてh(m)を生成し、更に次式
ｗ＝［{h(m)−xkmod n}/p・q］                      (10)
を計算する。次に次式
Ｓ＝ x ＋｛w/(k・xk-1) mod p｝p・q                  (11)
を求める。式(11)中のw/(k・xk-1)mod p は先に説明した逆元演算と同じものである。従って、先に説明したように
ｙ＝w(k・xk-1)-1mod p＝ w・X-1mod p                  (12)
と表せば、図１９の説明で示した逆元演算処理手順によりｙを求めることができる。この様にして求めたｙを使って
Ｓ＝ｘ＋y・p・q                                    (13)
を計算し、（Ｓ，ｍ）を利用者Ｂの演算装置１０Ｂに送信する。
利用者Ｂの装置１０Ｂでは、受信したＳとｍを使って次式
Ｓk−2a≦h(m)≦Ｓk，  ただしａ＝［(2/3)log2ｎ］      (14)
が成立するか検証し、成立すれば文書ｍに対する署名Ｓは正しいものであると認める。
この発明の逆元演算プログラムの記録媒体が演算装置の主記憶装置１３に格納され、それを使用する場合を示したが、この様なプログラムを他のどの様な形態の記録媒体に格納して使用してもよいことは明らかである。
【００３１】
【発明の効果】
この発明の２進ｇｃｄ演算装置では、小さい整数を使った演算により、疑似的に２進ｇｃｄ算法を行なうことによって、大きい整数の演算を1/w に比例する割合で減らし、２進ｇｃｄ算法を高速に行なうことを可能としている。（ｗは計算機が一度に扱うことができるビット数８，１６，３２など）
また、「実際のｇｃｄ算法を正しくシミュレートしている保証がなくても決められた回数分の疑似演算を行なう」方法の導入により、疑似演算の効率を高めた。
これにより、例えば従来法である算法Ｌは、３２ビットの単精度整数による疑似算法で約１２周分のシミュレートを行なっていたが、この発明の装置では３２ビットの単精度整数による疑似算法で３２周分のシミュレートすることが可能である。この場合は算法Ｌの半分以下の大きい整数演算の回数でｇｃｄ演算が出来る。
【図面の簡単な説明】
【図１】従来の２進gcd 算法の計算手順を示す流れ図。
【図２】この発明によるｇｃｄ演算装置の機能構成を示す図。
【図３】図２の装置の動作の流れを示す流れ図。
【図４】図２中のｇｃｄ演算初期設定部１１０の機能構成を示す図。
【図５】図４の初期設定部１１０の動作の流れを示す流れ図。
【図６】図２中のｇｃｄ演算疑似演算部１２０の機能構成を示す図。
【図７】図６の疑似演算部１２０の動作の流れを示す流れ図。
【図８】図２中のｇｃｄ演算多倍長演算部１３０の機能構成を示す図。
【図９】図２中のｇｃｄ演算最終演算部１４０の機能構成を示す図。
【図１０】図９中の最終演算部１４０の動作の流れを示す図。
【図１１】この発明の変形例である拡張２進最大公約数演算装置の機能構成を示す図。
【図１２】図１１の拡張２進最大公約数演算装置の動作の流れを示す図。
【図１３】図１１中の拡張ｇｃｄ演算多倍長演算部２３０の機能構成を示す図。
【図１４】図１３の多倍長演算部２３０の動作の流れを示す図。
【図１５】図１１中の最終演算部２４０の動作の流れの一部を示す図。
【図１６】この発明の拡張２進ｇｃｄを適用した通常逆元演算装置の機能構成を示す図。
【図１７】この発明の拡張２進ｇｃｄを適用した半モンゴメリ（Kaliski）逆元演算装置の機能構成を示す図。
【図１８】この発明の拡張２進ｇｃｄを適用したMontgomery逆元演算装置の機能構成を示す図。
【図１９】この発明の拡張２進ｇｃｄを適用したMontgomery逆元演算装置の他の機能構成を示す図。
【図２０】この発明による演算プログラム記録媒体を使用してコンピュータによりこの発明装置を機能させるための機能構成例を示すブロック図。
【図１】
0003673785.tif 000009
【図２】
0003673785.tif 000010
【図３】
0003673785.tif 000011
【図４】
0003673785.tif 000012
【図５】
0003673785.tif 000013
【図６】
0003673785.tif 000014
【図７】
0003673785.tif 000015
【図８】
0003673785.tif 000016
【図９】
0003673785.tif 000017
【図１０】
0003673785.tif 000018
【図１１】
0003673785.tif 000019
【図１２】
0003673785.tif 000020
【図１３】
0003673785.tif 000021
【図１４】
0003673785.tif 000022
【図１５】
0003673785.tif 000023
【図１６】
0003673785.tif 000024
【図１７】
0003673785.tif 000025
【図１８】
0003673785.tif 000026
【図１９】
0003673785.tif 000027
【図２０】
0003673785.tif 000028