JP3673785B2 - Maximum common divisor arithmetic unit, inverse element arithmetic unit, and arithmetic program recording medium - Google Patents

Description

もしｉ≦ｗならばステップＳ５へ。
ステップＳ３（単精度演算ループ）： 以下をｗ回繰り返す：
(1) u_xが偶数ならば
【数２】

(2) v_xが偶数ならば
【数３】

(3) v_x, u_x が奇数かつu_a＞v_aならば
【数４】

(4) v_x, u_x が奇数かつu_a≦v_aならば
【数５】

ステップＳ４（多倍長値再計算）：
【数６】

U ← ｜U'｜/2^w； V ←｜V'｜/2^w
もし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)を出力する。
上記アルゴリズム終了の根拠
命題２：ｗ≧４ならば上記アルゴリズムは有限時間で終了する。
証明：上記ステップＳ２の時点でのＵ，Ｖの値をU₀, V₀とし、ステップＳ４において再計算されるＵ，ＶをU₁, V₁とする。このとき、
U₀＋V₀＞U₁＋V₁
を示せばよい。上記アルゴリズム中でU＋Vは単調減少となり、U＋V＜2^wとなった時点でステップＳ５が実行され、終了する。発明者は上記式が成り立つことを証明することができるが、ここでは省略する。
【００１２】
【発明の実施の形態】
ｇｃｄ演算装置
図２及び図３を参照してｇｃｄ演算装置1000を説明する。この装置1000は入力部１０１によりＸ，Ｙが入力され、出力部１０２からgcd(X, Y) を出力する装置であって、ｇｃｄ演算初期設定部１１０と、ｇｃｄ演算疑似演算部１２０と、ｇｃｄ演算多倍長演算部１３０と、ｇｃｄ演算最終演算部１４０と制御装置１５０と、記憶手段１６０とを備え、以下のように演算が実行される。
ステップＳ１： ｇｃｄ演算初期設定部１１０は、入力Ｘ，Ｙに対して
gcd(X，Y)＝2^Z0gcd(U，V) (7)
を満たすＵ，Ｖ，z₀のうち、z₀が最大となるものを求め、その時のＵ，ＶをそれぞれU₀，V₀として、制御装置１５０へ渡し、制御装置１５０を介してz₀をｇｃｄ演算最終処理部１４０へ渡す。
ステップＳ２： 制御装置１５０は、入力U₀，V₀に対し、U₀=1又はV₀=1であるかどうかを検査する。検査に合格した場合、即ち、U₀=1又はV₀=1の場合は、ｇｃｄ演算最終処理部１４０にU₀，V₀を渡す。
ステップＳ３： そうでない場合、制御装置１５０は、入力U₀，V₀に対し、そのビットサイズの大きい方の値ｉを求める。
ステップＳ４： ビットサイズｉがｗビット以下であるかどうかを検査する。検査に合格した場合は、ｇｃｄ演算最終処理部１４０にU₀，V₀を渡す。ビットサイズｉがｗ以下でなかった場合は、
v_a＝V₀の上位ｗビット（第ｉビット目から第i-w+1ビット目まで）
u_a＝U₀の上位ｗビット（第ｉビット目から第i-w+1ビット目まで）
v_x＝V₀の下位ｗビット
u_x＝U₀の下位ｗビット
の各値をｇｃｄ演算疑似演算部１２０へ渡し、U₀，V₀をｇｃｄ演算多倍長演算部１３０へ渡す。
【００１３】
ステップＳ５： ｇｃｄ演算疑似演算部１２０は、U₀，V₀の上下位ｗビット分であるv_a，u_a，v_x，u_xの各値を用いて、図６，７を参照して後述するようにｇｃｄ演算をシミュレートする。結果の値u_u，u_v，v_u，v_vをｇｃｄ演算多倍長演算部１３０へ渡す。
ステップＳ６： ｇｃｄ演算多倍長演算部１３０は、
U₀←｜u_uU₀−u_vV₀｜/2^w； V₀←｜v_vV₀−v_uU₀｜/2^w
を計算し、それぞれを更新されたU₀，V₀として、制御装置１５０へ渡す。
ステップＳ７： 制御装置１５０はV₀＝0 かを検査し、０でなければ、ステップＳ３に戻り、V₀＝0であればU₀，V₀をｇｃｄ演算最終演算部１４０へ渡す。
ステップＳ８： ｇｃｄ演算最終演算部１４０は、入力U₀，V₀，z₀に対して２^Z0gcd(U₀，V₀)を求めて出力する。V₀=0の場合は、2^z0gcd(U₀, 0)=U₀2^z0を出力することになる。
従って制御装置１５０には、U₀＝１又はV₀＝１を検査する初期判定手段1-20、V₀，U₀のビットサイズの大きな方の値ｉを求めるビットサイズ取得手段1-30、ビットサイズｉがｗより小さいかを検査するビットサイズ検査手段1-40、V₀＝０かを検査する最終検査手段1-70、前記ステップ４でV₀，U₀から各上位ｗビット、各下位ｗビットを取出す演算ビット取出し手段1-41を備え、またこのｇｃｄ演算装置1000には、各種データや演算、制御、処理上必要とするデータなどを記憶する記憶部１６０が設けられている。
【００１４】
ｇｃｄ演算初期設定部１１０
図４及び図５を参照してｇｃｄ演算初期設定部１１０の動作を説明する。
ステップＳ１： 数えあげ部１１１及び１１２は、入力X，Yそれぞれの最下位ビットから連続するゼロの個数を数えて、その値x₀，y₀を比較部１１３へ出力する（例えば入力の２進数表現が101000ならば、出力は３である）。
ステップＳ２： 比較部１１３は、入力された値x₀，y₀を比較し、より小さい方をz₀として出力する。
ステップＳ３： ２のべきによる除算部１１４及び１１５は、それぞれ入力Ｘ，Ｙとz₀が入力され、入力された値Ｘ，Ｙに対してそれぞれ２^Z0による除算を行ない、その除算結果U₀，V₀を出力する。ｇｃｄ演算初期設定１１０はU₀，V₀，z₀を出力する。
【００１５】
ｇｃｄ演算疑似演算部１２０
図６，図７を参照して、ｇｃｄ演算疑似演算部１２０の動作を説明する。
ステップＳ１： 制御装置１５０からv_a，u_a，v_x，u_xの各値が制御部１２１に入力されると、メモリ１２２は、決められたu_u，u_v，v_u，v_v，ｃの初期値を制御部１２１へ送る。
ステップＳ２： 制御部１２１は、データα＝｛v_a，u_a，v_x，u_x，u_u，u_v，v_u，v_v，ｃ｝が入力されると、u_xが偶数かどうかを検査する。偶数ならば、場合１ユニット１２３へデータα＝｛v_a，u_a，v_x，u_x，u_u，u_v，v_u，v_v，ｃ｝を送る。
ステップＳ３： u_xが偶数の場合、場合１ユニット１２３は、
u_a ← [u_a/2]； u_x ← u_x/2
v_u ← 2v_u； v_v ← 2v_v
の演算を行ない、制御部１２１へデータα'＝｛v_a，u_a，v_x，u_x，u_u，u_v，v_u，v_v，ｃ｝を送る。
ステップＳ４： u_xが偶数でない場合、制御部１２１は、v_xが偶数かどうかを検査する。偶数ならば、場合２ユニット１２４へデータα＝｛v_a，u_a，v_x，u_x，u_u，u_v，v_u，v_v，ｃ｝を送る。
ステップＳ５： u_xが奇数でv_xが偶数の場合、場合２ユニット１２４は、
v_a ← [v_a/2]； v_x ← v_x/2
u_u ← 2u_u； u_v ← 2u_v
の演算を行ない、制御部１２１へデータα'＝｛ｖ_a，u_a，v_x，u_x，u_u，u_v，v_u，v_v，ｃ｝を送る。
【００１６】
ステップＳ６： 制御部１２１は、u_x，v_xが共に奇数の場合、u_aとv_aの大小比較を行なう。u_a＞v_aならば、場合３ユニット１２５へデータα＝｛v_a，u_a，v_x，u_x，u_u，u_v，v_u，v_v，ｃ｝を送り、u_x，v_xともに奇数かつu_a≦v_aならば、場合４ユニット１２６へデータα＝｛v_a，u_a，v_x，u_x，u_u，u_v，v_u，v_v，ｃ｝を送る。ステップＳ７： u_x, v_xが奇数で、u_a＞v_aの場合、場合３ユニット装置１２５は、
u_a ← [(u_a−v_a)/2]； u_x ← (u_x−v_x)/2
u_u ← u_u＋v_u； u_v ← u_v＋v_v
v_u ← 2v_u； v_v ← 2v_v
の演算を行ない、制御部１２１へデータα'＝｛v_a，u_a，v_x，u_x，u_u，u_v，v_u，v_v，ｃ｝を送る。
ステップＳ８： u_x, v_xが奇数でu_a≦v_aの場合、場合４ユニット１２６は、
v_a ← [(v_a−u_a)/2]； v_x ← (v_x−u_x)/2
v_u ← v_u＋u_u； v_v ← v_v＋u_v
u_u ← 2u_u； u_v ← 2u_v
の演算を行ない、制御部１２１へデータα'＝｛v_a，u_a，v_x，u_x，u_u，u_v，v_u，v_v，ｃ｝を送る。
ステップＳ９： 場合１ユニット１２３乃至場合４ユニット１２６の何れかでデータαの処理がなされてデータα' として制御部１２１に戻されると、制御部１２１はｃの値を１増やす。
【００１７】
ステップＳ１０： そのｃとw'とを比較し、ｃ＜w'であればステップＳ２に戻り、ｃ＝w'ならば｛u_u，u_v，v_u，v_v｝をｇｃｄ演算疑似演算部１２０からｇｃｄ演算多倍長演算部１３０へ出力する。
制御部１２１は入力されたu_x，v_x，u_a，v_aの状態から場合１ユニット１２３〜場合４ユニット１２６の何れで処理させるかの状態判定手段6-21、場合ユニット１２３〜１２６で処理した結果を記憶する処理結果記憶手段6-22、処理回数ｃを計数する計数手段6-23、処理を終了とするか、つまりｃ＝w'か否かを判定する処理終了判定手段6-24を備えている。
このｇｃｄ演算疑似演算部１２０はU₀，V₀の各下位ｗビットの値u_x，v_xにより、それぞれU₀，V₀が偶数か否かの判定を行い、U₀，V₀の各上位ｗビットの値u_a，v_aによりU₀とV₀の大小比較を行い、これらにもとづいて、従来の２進ｇｃｄ算法と同様の処理を行っている。このことは図７の処理手順と、図１に示した従来の２進ｇｃｄ算法の処理手順とを比較すれば直ちに理解されよう。またここでは次式
gcd(U₀，V₀)＝gcd(｜u_uU₀−u_vV₀｜/2^w'，｜v_vV₀−v_uU₀｜/2^w') (8)
を満たすu_u，u_v，v_u，v_vを求めていることになる。
【００１８】
ｇｃｄ多倍長演算部１３０
図８を参照してｇｃｄ多倍長演算部１３０の動作を説明する。
図８において、ｇｃｄ多倍長演算部１３０には制御装置１５０からU₀，V₀が、ｇｃｄ演算疑似演算部１２０からu_u，u_v，v_u，v_vをそれぞれ入力される。乗算器１３ａ〜１３ｄはそれぞれ積u_uU₀，u_vV_v，v_uU₀，v_vV₀を計算して出力する。
減算器１３ｅ及び１３ｆはそれぞれ差U₁=u_uU₀−u_vV₀及びV₁=v_vV₀−v_uU₀を計算して絶対値器１３ｇ及び１３ｈに出力する。
絶対値器１３ｇ及び１３ｈはそれぞれ入力U₁及びV₁の絶対値を計算して２のべきによる除算器１３ｉ及び１３ｊに出力する。
２のべきによる除算器１３ｉ及び１３ｊはそれぞれ入力｜U₁｜及び｜V₁｜の２^w'による除算を計算しこれをU₀及びV₀としてｇｃｄ多倍長演算部１３０の出力とする。
図８のｇｃｄ多倍長演算部１３０の処理を以下にまとめて示す。
ステップＳ１： V₁＝(-v_uU₀＋v_vV₀)/2^w'
U₁＝(u_uU₀−u_vV₀)/2^w'
を演算する。
ステップＳ２： V₁ ←｜V₁｜； U₁ ←｜U₁｜
ステップＳ３： V₀ ← V₁ ； U₀ ← U₁
図８においては、2^w' による除算を、絶対値を求めた後に行っているが、上記ステップＳ１に示すように2^w' による除算を、絶対値を求める前に行ってもよい。得られたU₀，V₀は制御装置１５０に入力され、図３で説明したようにV₀＝０かのチェックが行われる。
【００１９】
ｇｃｄ演算最終処理部１４０
図９を参照してｇｃｄ演算最終処理部１４０の動作を説明する。
ｇｃｄ演算最終処理部１４０には制御装置１５０からU₀，V₀が、初期設定部１１０からｚ₀ がそれぞれ入力される。小さい数のｇｃｄ演算部１４１は入力U₀，V₀のｇｃｄを計算して２のべき乗倍部１４２に出力する。２のべき乗倍部１４２は入力gcd(U₀，V₀) とz₀を用いて2^z0gcd(U₀，V₀)を計算してこの最終処理部１４０の出力とする。つまりｇｃｄ演算装置1000の出力となる。
このｇｃｄ演算最終処理装置１４０はその処理手順を図１０に示すように、最後のステップＳ１０で２^Z0を乗算補正する以外は図１に示した従来の２進ｇｃｄ算法と基本的に同一手順である。更に詳細にみれば、図１０のステップＳ１〜Ｓ９は、図７のステップＳ１〜Ｓ９におけるu_x, u_u, v_x, v_u, v_vに対する処理と同じである。
以上のようにして入力Ｘ，Ｙの最大公約数を求めることができる。しかも、ｇｃｄ演算最終処理部１４０を除いては、全て演算単位がｗ又はw'ビットであり、全体として少ない処理で行うことができる。なお図２，図３についての説明から理解されるように、図２中の各部は順次処理されるものであり、従って図６では説明の便宜上制御部１２１を設けたが、この制御部１２１は制御装置１５０で行うことができ、その他の各部も制御装置１５０により制御され、また各部において各処理上必要とする記憶部（メモリ）は図２中の記憶部１６０を利用することができる。
【００２０】
拡張２進ｇｃｄ演算装置 2000
図１１を参照して拡張２進ｇｃｄ演算装置2000を説明する。この装置2000はＸ，Ｙの入力に対して、gcd(X，Y) と、S＝2^kX^-1modＹ及びｋを出力する。
この装置2000は拡張ｇｃｄ演算初期設定部２１０、拡張ｇｃｄ演算疑似演算部２２０、拡張ｇｃｄ演算多倍長演算部２３０、拡張ｇｃｄ演算最終演算部２４０、制御装置２５０からなり、図１２に示すように以下の演算が実行される。
ステップＳ１： 拡張ｇｃｄ演算初期設定部２１０は、入力Ｘ，Ｙに対して
gcd(X，Y)＝2^z0gcd(U₀，V₀) (9)
を満たすU₀，V₀，z₀のうち、z₀が最大となるものを求める。Ｓ，Ｔ，ｋの初期値S₀＝０、T₀＝１，ｋ＝０とともにU₀，V₀を制御装置２５０へ渡し、制御装置２５０を介してz₀を拡張ｇｃｄ演算最終処理部２４０へ渡す。
ステップＳ２： 制御装置２５０は、入力U₀，V₀，S₀，T₀，ｋに対し、U₀＝１またはV₀＝１であるかどうかを検査する。検査に合格した場合は、拡張ｇｃｄ演算最終処理部２４０にU₀，V₀，S₀，T₀，ｋを渡す。
ステップＳ３： 制御装置２５０は、U₀=1又はV₀=1でなかった場合、入力U₀，V₀，S₀，T₀，ｋに対し、U₀とV₀のビットサイズ中の大きい方のビットサイズ値ｉを求める。
ステップＳ４： 制御装置２５０はその値ｉがｗビット以下であるかどうかを検査する。検査に合格した場合、拡張ｇｃｄ演算最終処理部２４０に、U₀，V₀，S₀，T₀，ｋを渡す。上記いずれの検査にも合格しなかった場合は、
v_a ＝V₀ の上位ｗビット（第ｉビット目から第i-w+1ビット目まで）
u_a ＝U₀ の上位ｗビット（第ｉビット目から第i-w+1ビット目まで）
v_x ＝V₀ の下位ｗビット
u_x ＝U₀ の下位ｗビット
の各値を拡張ｇｃｄ演算疑似演算部２２０へ渡し、U₀，V₀，S₀，T₀を拡張ｇｃｄ演算多倍長演算部２３０へ渡す。ｋにw'を加算する。
【００２１】
ステップＳ５： 拡張ｇｃｄ演算疑似演算部２２０は、U₀，V₀の上下位ｗビット分であるv_a，u_a，v_x，u_xの各値を用いて、拡張ｇｃｄ演算をシミュレートする。その結果の値u_u，u_v，v_u，v_vの各値を拡張ｇｃｄ演算多倍長演算部２３０へ渡す。
ステップＳ６： 拡張ｇｃｄ演算多倍長演算部２３０は、図１３を参照して後述するように
U'＝(u_uU₀−u_vV₀)/2^w'，
V'＝(v_vV₀−v_uU₀)/2^w'，
S'＝u_uS₀＋u_vT₀，
T'＝v_vT₀＋v_uS₀
を計算する。ここで、V'が負ならばV'とT'の符号を反転し、U'が負ならばU'とS'の符号を反転する。演算の結果得られたU'，V'，S'，T'をU₀，V₀，S₀，T₀として制御装置２５０へ渡す。
ステップＳ７： 制御装置２５０はV₀＝０かを検査し、０でなければステップＳ３に戻り、０であれば拡張ｇｃｄ演算最終演算部２４０の処理に移る。
ステップＳ８： 拡張ｇｃｄ演算最終演算部２４０は、V₀≠０なら入力U₀，V₀，z₀に対して2^Z0gcd(U₀，V₀)を求めて出力する。また、V₀＝０ならS＝2^kX^-1modＹなるＳ，ｋを求め、出力する。
【００２２】
図１１には特に示していないが、この拡張ｇｃｄ演算装置2000にも、図２中に示した初期判定手段1-20、ビットサイズ取得手段1-30、ビットサイズ検査手段1-40、演算ビット取出手段1-41、最終判定手段1-70、記憶部１６０に対応するものが設けられている。
拡張ｇｃｄ演算初期設定部２１０は、図２中のｇｃｄ演算初期設定部１１０と同様に図４に示した機能構成を有し、図５に示した処理を行うが、これらと異なる点は記憶部に記憶されているＳ，Ｔ，ｋの各初期値S₀＝０，T₀＝１，ｋ＝０を出力して制御装置２５０へ渡す。
拡張ｇｃｄ演算疑似演算部２２０の機能構成は図６に示したｇｃｄ演算疑似演算部１２０のそれとほぼ同一であり、またその処理も図７に示した処理とほぼ同一であるが、異なる点は図７中のステップＳ９に括弧書きで示しているようにｋの値を１増加させる処理も行っている。つまり疑似演算部１２０で求めたu_u，u_v，v_u，v_vを出力すると共にｋにｗを加算して出力することになる。従って拡張ｇｃｄ演算疑似演算部２２０の制御部にはｋを計数する手段も設けられる。ステップＳ９でｋを＋１する代りに、ステップＳ１０でｃ＝ｗとなった時に、ｋ＋ｗ＝ｋとしてもよい。
【００２３】
拡張ｇｃｄ多倍長演算部２３０
図１３，図１４を参照して拡張ｇｃｄ多倍長演算部２３０の動作を説明する。この演算部２３０には図１１における制御装置２５０からU₀，V₀，S₀，T₀が、また拡張ｇｃｄ演算疑似演算部２２０からu_u，u_v，v_u，v_vが入力される。
乗算器２３ａ〜２３ｈはそれぞれ積u_uU₀，u_vV₀，v_uU₀，v_vV₀，u_uS₀，u_vT₀，v_uS₀，v_vT₀を計算して出力する。
減算器２３ｉ及び２３ｊはそれぞれ差U'＝u_uU₀−u_vV₀及びV'＝v_uV₀−u_vU₀を計算して出力する。
加算器２３ｋ及び２３ｌはそれぞれ和S'＝u_uS₀＋u_vT₀及びT'＝v_vT₀＋v_uS₀を計算して出力する。
制御部２３ｍは入力U'，S'に対して、U'＜０ならば、符号反転器２３ｏにU'，S'を出力し、符号反転器２３ｏから、−U'，−S'を新たな入力U"，S"として受ける。U'≧０ならば、U'を２のべきによる除算器２３ｑに出力し、S'をS₀として演算部２３０より出力する。
制御部２３ｎは入力V'，T'に対して、V'＜０ならば、符号反転器２３ｐにV'，T'を出力し、符号反転器２３ｐから、−V'，−T'を新たな入力V"，T"として受ける。V'≧０ならば、V'を２のべきによる除算器２３ｒに出力し、T'をT₀として演算部２３０から出力する。
【００２４】
２のべきによる除算器２３ｑは入力U'の２^w'による商U₁を計算してU₀として演算部２３０の出力とする。２のべきによる除算器２３ｒは入力V'の２^w'による商V₁を計算してV₀として演算部２３０の出力とする。
以上の拡張ｇｃｄ多倍長演算部２３０の処理をまとめて図１４に示す。

を演算する。
ステップＳ２： V₁が０より小か判定し、０より小でなかったらそのままステップＳ４に移る。
ステップＳ３： V₁が０より小であれば、V₁← -V₁及びT₁← -T₁により符号を変える。
ステップＳ４： U₁が０より小か判定し、０より小でなければそのままステップＳ６に移る。
ステップＳ５： U₁が０より小であれば、U₁← -U₁及びS₁← -S₁により符号を変える。
ステップＳ６： 得られたV₁, U₁, S₁, T₁を更新されたV₀, U₀, S₀, T₀として出力する。
この拡張ｇｃｄ演算多倍長演算部２３０の出力は制御装置２５０に入力される。
【００２５】
拡張ｇｃｄ演算最終処理部２４０
拡張ｇｃｄ演算最終処理部２４０は図９に示した最終処理部１４０とほぼ同様の機能構成をとり、入力されU₀，V₀を初期値として、gcd(U，V) を演算し、その演算結果とgcd(U，V) とz₀を用いて2^z0gcd(U，V)が計算されて出力される。最終処理部１４０と異なる点は、この最終処理部２４０にはS₀，T₀，ｋも入力され、図１０に示したｇｃｄ演算処理の一部を図１５に示すようにステップＳ３、Ｓ５、Ｓ７、Ｓ８の次にｋを＋１するステップS8-1の処理を行ってステップＳ９に移る。またステップＳ９でv_x＝０であれば、ステップS9-1でS＝(u_uS₀＋u_vT₀) を演算し、その結果Ｓと、ｋを出力する。このＳはS＝2^kX^-1modＹの演算結果と一致する。
この拡張ｇｃｄ演算装置2000も、ｇｃｄ演算装置1000と同様に１つの制御装置２５０で各部を処理することができ、またこれら演算処理をプログラムの解読実行により行うこともできる。その場合は各演算処理に当り、必要なデータを記憶手段から読出したり、一時的に蓄えたバッファから取出したり、また演算結果を記憶手段に書込んだり、バッファへ一時的に蓄えたりするステップを供することになる。この実施例では、入力Ｘ，Ｙが、共に偶数の場合は gcd(X，Y)＝２^z0u_x を出力し、Ｘ，Ｙの一方が奇数かつ、 gcd(X，Y)＝1の場合はＳとｋを出力させるようにした。従って、拡張ｇｃｄ演算初期設定部２１０では、Ｘ，Ｙの何れが奇数かをまず判断し、奇数の場合はz₀を求めることなく、ＸをU₀，ＹをV₀とし、ｗ，S₀＝０，T₀＝１，ｋ＝０を出力するようにしてもよい。しかし、例えば逆元を求める場合はＸ、Ｙの一方が奇数でないと求められない。つまり、予め、入力値の一方が奇数であることがわかっている場合は、拡張ｇｃｄ演算初期設定部２１０では、単にU₀＝X，V₀＝Y，S₀＝０，T₀＝１，ｋ＝０とする初期設定のみを行えばよい。つまりＸをU₀として、ＹをV₀として、またS₀＝０，T₀＝１，ｋ＝０をメモリから読出して出力すればよい。
【００２６】
上述では一度に演算することのできるビット数をｗ及びw'としたが、疑似演算部（１２０，２２０）で一度に計算する量w'と多倍長演算部（１３０，２３０）とで一度に計算する量ｗとを同じ値としてもよい。
先に述べたように拡張２進ｇｃｄ演算装置は２のべきによる除算装置と組み合わせて剰余環Z/NZ上の逆元演算装置を構成することができる。図１６はこの発明の拡張２進ｇｃｄ演算装置を使って通常逆元演算装置を構成した場合である。図に示すように、整数ＸとＮがこの装置3000に入力され、まず図１１で説明した拡張２進ｇｃｄ演算装置３１５で拡張２進ｇｃｄ演算がなされ、S＝X^-12^kmodＮ とｋとが出力され、このＳ，ｋとＮがZ/NZ上の２のべきによる除算装置３１８に入力されS・2^-kmodＮ が演算され、その演算結果としてX^-1modＮ、つまりＸのZ/NZ上の逆元演算結果が得られる。
【００２７】
図１７に剰余環Z/NZ上の半モンゴメリ（Kaliski）逆元演算にこの発明の拡張ｇｃｄ演算装置を適用した場合の逆元演算装置3100を示す。この装置3100に整数Ｘ，Ｎが入力され、Ｘ，Ｎについて図１１を参照して説明した拡張ｇｃｄ演算装置３１５による演算がなされ、その結果のS＝X^-12^kmodＮ とｋと入力ＮとがZ/NZ上の２のべきによる除算装置３２０に入力されて、S・2^-(k-n)modＮ が演算され（ｎはＮのビット数）、結果としてX^-12ⁿmodＮが得られる。
図１８はZ/NZ上のMontgomery逆元演算にこの発明の拡張２進ｇｃｄ演算装置を適用した場合の逆元演算装置3200を示す。図に示すように、入力された整数Ｘ，Ｎについて拡張ｇｃｄ演算装置３１５でS＝X^-12^kmodＮ 及びｋを求め、これに対しZ/NZ上の２のべき乗倍装置３２５でS・2^2n-kmodＮを演算してX^-12²ⁿmodＮを得ることもできる。
【００２８】
図１９は、Z/NZ上のモンゴメリ逆元演算装置にこの発明の拡張ｇｃｄ演算装置を適用した場合の装置5000を示す。図１９に示すように、制御部５１０の制御のもとに、まずZ/NZ上の２のべきによる除算装置５１４でX'＝X・2^-tmodＮ を演算し、その演算結果X'とＮについて拡張ｇｃｄ演算装置５１５によりS＝X^-12^kmodＮ とｋを求める。これらＳ，ｋを比較装置５１７に入力してＮのビット長ｎとｋとｔとから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'2^k'modＮ を演算する。出力部５１９は、演算装置518Aと518Bの何れかのＴをX^-12²ⁿmodＮ の演算結果として出力する。
上述してきたこの発明による最大公約数又は拡張最大公約数演算装置あるいは逆元演算装置としてコンピュータを機能させるためのプログラムは、例えば図２０に示す演算装置１０Ａ内の主記憶装置１３に格納されて使用される。演算装置１０Ａは例えばコンピュータで実現され、ＣＰＵ１１と、ＲＡＭ１２と、主記憶装置１３とか等構成され、キーボード１４と、表示装置１５とが接続されている。ＣＰＵ１１として例えば１度に１６ビットずつ演算を行う１６ビットのチップセットを使用した場合、この発明の実施例で説明したように２のべきによる乗除算を行う場合に１６ビットずつまとめて行うのが好ましい。
【００２９】
ＣＰＵ１１は主記憶装置１３内の演算プログラムに従って最大公約数又は拡張最大公約数演算あるいは逆元演算を実行する。ＲＡＭ１２はこれら演算に必要な各種パラメータの値や変数値を保持したり、演算の途中結果や最終結果を保持する。利用者Ａはキーボード１４からプログラムの実行命令を入力し、演算の実行経過が表示装置１５に表示される。
ここで、この発明の逆元演算装置がセキュリティ技術の例であるディジタル署名において使用される場合について説明する。利用者Ａの演算装置１０Ａは例えばネットワークＮＷを介して利用者Ｂの演算装置１０Ｂに接続されており、利用者Ａは文書ｍに対しディジタル署名Ｓをつけて利用者Ｂの演算装置１０Ｂに送信し、利用者Ｂは受信した署名Ｓの正当性を検証する。ここでは、ディジタル署名として、ESIGN 方式を使う場合で説明する。この場合、利用者ＡとＢは公開鍵ｎとシステムパラメータｋを共有し、送信側利両者Ａは素数の秘密鍵ｐ，ｑを秘密に保持している。ただしｎ＝ｐｑである。
ディジタル署名方式ESIGN を実行するためのプログラム１３Ｐは主記憶装置１３ないに格納されている。そのプログラム１３Ｐの一部として、ディジタル署名生成の一過程で使用される逆元演算を含む式をこの発明の演算方法により実行する部分プログラム13PPが設けられている。
【００３０】
まず、利用者Ａの演算装置１０Ａでは、乱数ｘを生成する。次に、文書ｍをハッシュ関数に入れてh(m)を生成し、更に次式
ｗ＝［{h(m)−x^kmod n}/p・q］ (10)
を計算する。次に次式
Ｓ＝ x ＋｛w/(k・x^k-1) mod p｝p・q (11)
を求める。式(11)中のw/(k・x^k-1)mod p は先に説明した逆元演算と同じものである。従って、先に説明したように
ｙ＝w(k・x^k-1)^-1mod p＝ w・X^-1mod p (12)
と表せば、図１９の説明で示した逆元演算処理手順によりｙを求めることができる。この様にして求めたｙを使って
Ｓ＝ｘ＋y・p・q (13)
を計算し、（Ｓ，ｍ）を利用者Ｂの演算装置１０Ｂに送信する。
利用者Ｂの装置１０Ｂでは、受信したＳとｍを使って次式
Ｓ^k−2^a≦h(m)≦Ｓ^k， ただしａ＝［(2/3)log₂ｎ］ (14)
が成立するか検証し、成立すれば文書ｍに対する署名Ｓは正しいものであると認める。
この発明の逆元演算プログラムの記録媒体が演算装置の主記憶装置１３に格納され、それを使用する場合を示したが、この様なプログラムを他のどの様な形態の記録媒体に格納して使用してもよいことは明らかである。
【００３１】
【発明の効果】
この発明の２進ｇｃｄ演算装置では、小さい整数を使った演算により、疑似的に２進ｇｃｄ算法を行なうことによって、大きい整数の演算を1/w に比例する割合で減らし、２進ｇｃｄ算法を高速に行なうことを可能としている。（ｗは計算機が一度に扱うことができるビット数８，１６，３２など）
また、「実際のｇｃｄ算法を正しくシミュレートしている保証がなくても決められた回数分の疑似演算を行なう」方法の導入により、疑似演算の効率を高めた。
これにより、例えば従来法である算法Ｌは、３２ビットの単精度整数による疑似算法で約１２周分のシミュレートを行なっていたが、この発明の装置では３２ビットの単精度整数による疑似算法で３２周分のシミュレートすることが可能である。この場合は算法Ｌの半分以下の大きい整数演算の回数でｇｃｄ演算が出来る。
【図面の簡単な説明】
【図１】従来の２進gcd 算法の計算手順を示す流れ図。
【図２】この発明によるｇｃｄ演算装置の機能構成を示す図。
【図３】図２の装置の動作の流れを示す流れ図。
【図４】図２中のｇｃｄ演算初期設定部１１０の機能構成を示す図。
【図５】図４の初期設定部１１０の動作の流れを示す流れ図。
【図６】図２中のｇｃｄ演算疑似演算部１２０の機能構成を示す図。
【図７】図６の疑似演算部１２０の動作の流れを示す流れ図。
【図８】図２中のｇｃｄ演算多倍長演算部１３０の機能構成を示す図。
【図９】図２中のｇｃｄ演算最終演算部１４０の機能構成を示す図。
【図１０】図９中の最終演算部１４０の動作の流れを示す図。
【図１１】この発明の変形例である拡張２進最大公約数演算装置の機能構成を示す図。
【図１２】図１１の拡張２進最大公約数演算装置の動作の流れを示す図。
【図１３】図１１中の拡張ｇｃｄ演算多倍長演算部２３０の機能構成を示す図。
【図１４】図１３の多倍長演算部２３０の動作の流れを示す図。
【図１５】図１１中の最終演算部２４０の動作の流れの一部を示す図。
【図１６】この発明の拡張２進ｇｃｄを適用した通常逆元演算装置の機能構成を示す図。
【図１７】この発明の拡張２進ｇｃｄを適用した半モンゴメリ（Kaliski）逆元演算装置の機能構成を示す図。
【図１８】この発明の拡張２進ｇｃｄを適用したMontgomery逆元演算装置の機能構成を示す図。
【図１９】この発明の拡張２進ｇｃｄを適用したMontgomery逆元演算装置の他の機能構成を示す図。
【図２０】この発明による演算プログラム記録媒体を使用してコンピュータによりこの発明装置を機能させるための機能構成例を示すブロック図。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to operations on a finite field, and in particular, the greatest common divisor used to implement error correction codes (such as algebraic geometric codes) and information security techniques (such as encryption key generation, digital signatures, blind signatures, elliptical encryption). The present invention relates to an arithmetic device, a remainder inverse operation, an arithmetic device, and a program recording medium thereof.
[0002]
[Prior art]
As a method for obtaining the greatest common divisor (gcd), (1) Euclid mutual division, (2) binary gcd arithmetic, and (3) arithmetic L are known. Arithmetic L is an efficient method of Euclid's division method for large numbers.
(1)Euclid Mutual division of
Euclid's mutual division is
X_i= Q_iY_i+ R_i                                   (1)
And when
   gcd (X_i, Y_i) = Gcd (Y_i, R_i(2)
Take advantage of the fact that
X_{i + 1}= Y_i, Y_{i + 1}= R_i                            (3)
As a result, X₀, Y₀To X_i, Y_iAnd using equation (2)
 gcd (X₀, Y₀) = Gcd (X₁, Y₁) ＝… ＝ gcd (X_j, 0) = X_j         (Four)
Gcd (X₀, Y₀).
(See the document "D.E.Knuth (translated by Keisuke Nakagawa):" Quasi-numerical arithmetic / arithmetic operation (THE ART OF COMPUTER PROGRAMMING, fourth volume) "pp.157, Arithmetic A, Science, 1986).)
A specific example is given. In Euclid's divisor, an integer
X₀= 24, Y₀= 9
For the above, the following calculation is performed.
X₁← Y₀= 9, Y₁← X₀ mod Y₀= 6
X₂← Y₁= 6, Y₂← X₁mod Y₁= 3
X_Three← Y₂= 3, Y_Three← X₂mod Y₂= 0
As a result, gcd (X₀, Y₀) ＝ gcd (X_Three, Y_Three) = Gcd (3,0) = 3.
An apparatus that performs Euclid's mutual division method can be configured by a combination of a division device and a subtraction device.
[0003]
(2)Binary gcd algorithm
The binary gcd algorithm is
When X is odd and Y is even: gcd (X, Y) = gcd (X, Y / 2)
When X is even and Y is odd: gcd (X, Y) = gcd (X / 2, Y)
When X is odd and Y is odd: gcd (X, Y) = gcd (X, Y−X)
When X is even and Y is even: gcd (X, Y) = 2gcd (X / 2, Y / 2)
This is a method for obtaining gcd using the fact that That is, X_i, Y_iWhen any of these are odd numbers,
  (A) X_iIs odd, Y_iWhen is even: X_{i + 1}← X_iY_{i + 1}← Y_i/ 2
  (B) X_iIs even, Y_iWhen is odd: X_{i + 1}← X_i/ 2; Y_{i + 1}← Y_i
  (C) X_iIs odd, Y_iWhen is odd: X_{i + 1}← X_iY_{i + 1}← X_i−Y_i
X obtained by performing_{i + 1}, Y_{i + 1}About the following formula,
 gcd (X_{i + 1}, Y_{i + 1}) = Gcd (X_i, Y_i) (Five)
Take advantage of the fact that Repeat the above process (A), (B) and (C)₀, Y₀To X_i, Y_iAnd using equation (5),
 gcd (X₀, Y₀) ＝ gcd (X₁, Y₁) ＝… ＝ gcd (X_j, 0) = X_j
Gcd (X₀, Y₀).
(See the document "D.E. Knuth (translated by Keisuke Nakagawa):" Quasi-numerical arithmetic / arithmetic operations (THE ART OF COMPUTER PROGRAMMING, Volume 4) "pp. 158, Arithmetic B, Science, 1986).)
A specific example is given. In binary gcd arithmetic, an integer
X₀= 24, Y₀= 9
For the above, the following calculation is performed.
X₁← X₀/ 2^Three= 3; Y₁← Y₀= 9
X₂← X₁= 3; Y₂← (Y₁−X₁) / 2 = 3
X_Three← X₂= 3; Y_Three← (Y₂−X₂) / 2 = 0
As a result, gcd (X₀, Y₀) ＝ gcd (X_Three, Y_Three) = Gcd (3,0) = 3.
[0004]
The binary gcd algorithm can be realized by a process as shown in FIG. In this example, processing is performed as follows using variables U and V corresponding to inputs X and Y.
Step S1: X and Y are set to U and V as initial values, respectively, and an initial value 1 is set to the shift count z.
Step S2: Determine whether both U and V are even numbers, that is, determine whether the least significant bit is "0".
Step S3: If U and V are both even, U / 2 and V / 2 are set to U and V, respectively, and the shift count is doubled (1 bit shift), and the process returns to Step S2.
Step S4: It is determined whether V is an even number.
Step S5: If V is an even number, V / 2 is set to V and the process returns to step S4.
Step S6: When V is an odd number, it is determined whether U is an even number.
Step S7: If U is an even number, set U / 2 to U and return to step S6.
Step S8: If U and V are both odd numbers, it is determined whether U> V.
Step S9: If U> V, set (U-V) / 2 to V and return to step S4.
Step S10: If U ≦ V, (V−U) / 2 is set to V.
Step S11: Determine whether V = 0, and if not 0, return to Step S4.
Step S12: If V = 0, U × z is output as the calculation result of gcd (X, Y).
[0005]
An apparatus that performs binary gcd arithmetic can be constructed by only division and subtraction by two. Since multiplication / division by 2 is equivalent to 1-bit shift, there is an advantage that it is easy to implement in an electronic circuit or an electronic computer. In the Euclid mutual division method and binary gcd calculation method, when the input values X and Y are large integers, bit shift, subtraction, and division of large integers are performed a plurality of times. For example, consider a case where binary gcd arithmetic is performed on integers X and Y that can be represented by 512 bits. The number of loops k in the binary gcd algorithm is twice the size of the input value (in this case, 512 to 1024 times), and k bit shifts and subtractions up to k times (average k / 2 times) are performed ( Corresponding to step S9 or S10 in FIG. 1). The time required for one bit shift and addition / subtraction also increases in proportion to the bit size of the value to be calculated (in this case, U, V). For this reason, reducing the number of large integer operations leads to faster gcd operations.
One method for reducing the number of operations for large integers is an operation method that uses a pseudo-arithmetic method described below. This is because, instead of performing an operation using a large integer in a loop, a pseudo gcd arithmetic is performed by an operation using a small integer, and then a large integer is calculated using a value obtained by the pseudo arithmetic. It is a method to perform collectively.
[0006]
(3)Arithmetic L
Conventionally, there is a method in which a pseudo-arithmetic method is applied to the Euclid mutual division method. (For example, refer to the document “D.E.
A specific example is given. In arithmetic L, a large integer
X₀= 912345567890123456789
Y₀= 2000000000000000001
For the upper 4 digits, for example, and the value obtained by adding 1 to the 4 digits, respectively, is a small integer as follows:
x0₀= 9123
x1₀= 9124
y0₀= 2000
y1₀= 2001
Decide as.
X_{i + 1}= Y_iY_{i + 1}= X_imodY_i
x0_{i + 1}= Y1_iY1_{i + 1}= X0_imody1_i
x1_{i + 1}= Y0_iY0_{i + 1}= X1_imody0_i
Then,
x0_i/ y1_i<X_i/ Y_i<X1_i/ y0_i                      (6)
Holds. In algorithm L, X_i, Y_iInstead of using Euclid's mutual division with x0_i, Y1_i, X1_i, Y0_iEuclid is used for mutual division. That is, an integer x0 that is small only while the values of the integer part of the right side and the left side of Equation (6) are the same_i, Y1_i, X1_i, Y0_iAsk for. This is called a pseudo operation. After that, using the value obtained by the pseudo operation, a large integer X_i, Y_iPerform the operation.
This can achieve the same effect as performing large integer operations together (for example, x0_i, X1_i, Y0_i, Y1_iIf is 10 digits, about 12 operations can be combined at once). It is also possible to apply this method to binary gcd arithmetic.
[0007]
[Problems to be solved by the invention]
The problem with Arithmetic L is that x0_i, Y1_iEuclid's mutual division method and x1_i, Y0_iIt is necessary to perform both Euclid's mutual division methods using, and the number of operations that can be combined at one time differs depending on the time.
A normal computer has a storage device that can read and write in units of M bits (M is 8, 16, 32, etc.) (Condition 1). For this reason, it is efficient to perform operations in units of M bits. For example, in binary gcd arithmetic, a large integer 1-bit shift is performed. However, under condition 1, a 1-bit shift is the same as or more costly than a M-bit shift. Further, a modern computer has an M-bit shifter (M is 8, 16, 32, etc.), an adder / subtracter, a multiplier, etc. (Condition 2). In this case, it takes the same time to perform an operation of less than M bits once and to perform an operation of M bits once. For this reason, it is efficient to perform the operation in units of M bits.
On the other hand, in the calculation method L, the number of bits of operations that can be performed together changes depending on the time.
(Effect) will decrease.
[0008]
[Means for Solving the Problems]
In the present invention, a pseudo-arithmetic method is used for the binary gcd arithmetic method, but it is realized without obtaining an error range as will be described in detail below.
In algorithm L, X_i, Y_iSmall integer x0 instead of_i, X1_i, Y0_i, Y1_iA pseudo operation is performed using. x0_iAnd x1_iEach X_iRepresenting the lower and upper limits of the possible values of y0_iAnd y1_iEach Y_iRepresents the lower and upper limits of possible values. The pseudo operation is continued until the difference between the upper limit and the lower limit (error range) opens to some extent.
In this invention, X_iA small integer representing the value of_aOnly. Further, the pseudo calculation is performed a predetermined number of times w ′ without obtaining the error range.
[0009]
This has two advantages.
(1) Compared to the method using the error range, many pseudo operations can be performed at one time, so the number of multiple length operations is reduced.
(2) A shift operation with a constant value w ′ bits can be performed.
These make it possible to speed up the binary gcd algorithm.
Arithmetic L performs an operation equivalent to the operation of the Euclid mutual division method or the binary gcd operation method. However, in the present invention, the operation may not be equivalent. For example, in the binary gcd calculation method, U and V are compared in size in a loop. If the values of U and V are separated, the size can be compared by looking at only the upper few digits. However, when the values of U and V are close, a small integer u simulating the operation of U and V_a, V_aIt may not be possible to determine which one is larger only (corresponding to the upper digits of U and V). In such a case, in the calculation method L, the pseudo operation is once terminated, and the U and V values are calculated again, and then the magnitude determination is performed.
In this invention, the pseudo-operation is continued even in that case. Therefore, in this invention, the magnitude relationship may be wrong. If the magnitude relationship is wrong, U and V become negative values (this is not the case with Arithmetic L). However, by setting gcd (U, V) = gcd (| U |, | V |), the present invention prevents an erroneous answer from being output. As a result, the present invention increases the number of operations to be summarized at once than the method L, and reduces the number of multiple-length operations. In addition, the present invention can perform an operation for each predetermined number of bits (w ′ bits).
[0010]
gcd calculation algorithm
In order to facilitate understanding of the extended binary gcd arithmetic apparatus according to the present invention, an algorithm in the case where the principle of the present invention is first applied to a normal binary gcd arithmetic will be described below.
Step S1 (Multiple-length value initial setting):
U ← Y; V ← X; S ← 0; T ← 1.
Step S2 (single precision value initial setting):
i ← max (size of V; size of U)
v_a← Upper w bit of V; u_a← Upper w bit of U
v_x← Lower w bit of V; u_x← Lower w bit of U
[Expression 1]

If i ≦ w, go to step S5.
Step S3 (single precision calculation loop): The following is repeated w times:
(1) u_xIf is even
[Expression 2]

        (2) v_xIf is even
[Equation 3]

        (3) v_x, u_x Is odd and u_a> V_aIf
[Expression 4]

        (4) v_x, u_x Is odd and u_a≦ v_aIf
[Equation 5]

Step S4 (multiple-length value recalculation):
[Formula 6]

            U ← ｜ U '｜ / 2^w; V ← | V '| / 2^w
If V = 0, go to step S5, otherwise go to step S2.
Step S5 (final processing calculation):
If V = 0, output U.
            If V ≠ 0, gcd (U, V) is obtained and output (operation with single precision w bits or less)
Validity of the above algorithm
Proposition 1: When the above algorithm ends, gcd (X, Y) is output.
Proof: In the above algorithm, gcd (U, V) = gcd (X, Y) always holds. This is proved by induction.
[0011]
1. In step S1, since U = X and V = Y, gcd (U, V) = gcd (X, Y) is established.
2. In steps S3 and S4
When U is even: U ← U / 2
When V is an even number: V ← V / 2
When U and V are both odd numbers and U> V: U ← (U-V) / 2
When U and V are both odd numbers and U ≦ V: V ← (V-U) / 2
An operation corresponding to any of the above is performed. That is, if gcd (U, V) = gcd (X, Y) at the start of step S3, then gcd (U, V) = gcd (X, Y) holds at the end of step S4. However, here gcd (U, V) = gcd (| U |, | V |).
From the above 1 and 2, gcd (X, Y) is output when the above algorithm is completed.
Rationale for completion of the above algorithm
Proposition 2: If w ≧ 4, the algorithm ends in a finite time.
Proof: The values of U and V at the time of the above step S2 are expressed as U₀, V₀U and V recalculated in step S4₁, V₁And At this time,
U₀+ V₀> U₁+ V₁
Can be shown. U + V decreases monotonically in the above algorithm, U + V <2^wAt this point, step S5 is executed and the process ends. The inventor can prove that the above equation holds, but it is omitted here.
[0012]
DETAILED DESCRIPTION OF THE INVENTION
gcd arithmetic unit
The gcd arithmetic device 1000 will be described with reference to FIGS. The device 1000 is a device that receives X and Y from the input unit 101 and outputs gcd (X, Y) from the output unit 102. The device 1000 includes a gcd operation initial setting unit 110, a gcd operation pseudo-operation unit 120, An arithmetic multiple length arithmetic unit 130, a gcd arithmetic final arithmetic unit 140, a control device 150, and a storage unit 160 are provided, and arithmetic is performed as follows.
Step S1: The gcd calculation initial setting unit 110 applies the inputs X and Y
   gcd (X, Y) = 2^Z0gcd (U, V) (7)
U, V, z satisfying₀Out of z₀Is the maximum, and U and V at that time are₀, V₀To the control device 150 and z through the control device 150₀To the gcd calculation final processing unit 140.
Step S2: The control device 150 receives the input U₀, V₀U₀= 1 or V₀Check if = 1. If the inspection passes, ie U₀= 1 or V₀When = 1, the gcd calculation final processing unit 140 receives U₀, V₀give.
Step S3: Otherwise, the control device 150 makes an input U₀, V₀On the other hand, the value i having the larger bit size is obtained.
Step S4: Check whether the bit size i is less than or equal to w bits. If the inspection passes, the gcd calculation final processing unit 140₀, V₀give. If bit size i is not less than w
v_a= V₀Upper w bits (from i-th bit to i-w + 1-th bit)
u_a= U₀Upper w bits (from i-th bit to i-w + 1-th bit)
v_x= V₀Lower w bits of
u_x= U₀Lower w bits of
Are passed to the gcd operation pseudo-operation unit 120 and U₀, V₀Is transferred to the gcd arithmetic multiple length arithmetic unit 130.
[0013]
Step S5: The gcd operation pseudo-operation unit 120₀, V₀V is the upper and lower w bits of_a, U_a, V_x, U_xAs described later with reference to FIGS. 6 and 7, the gcd operation is simulated. Result value u_u, U_v, V_u, V_vIs transferred to the gcd arithmetic multiple length arithmetic unit 130.
Step S6: The gcd calculation multiple length calculation unit 130
U₀← ｜ u_uU₀−u_vV₀｜ / 2^w; V₀← ｜ v_vV₀−v_uU₀｜ / 2^w
Calculate and update each U₀, V₀To the control device 150.
Step S7: The control device 150 is V₀= 0 and if not 0, return to step S3, V₀= 0 if U₀, V₀To the gcd calculation final calculation unit 140.
Step S8: The gcd calculation final calculation unit 140 inputs the input U₀, V₀, Z₀2 against^Z0gcd (U₀, V₀) And output. V₀If = 0, 2^z0gcd (U₀, 0) = U₀2^z0Will be output.
Therefore, the control device 150 has U₀= 1 or V₀= Initial determination means 1-20 to check = 1, V₀, U₀Bit size acquisition means 1-30 for obtaining the larger value i of the bit size of the bit, bit size inspection means 1-40 for checking whether the bit size i is smaller than w, V₀= Final inspection means 1-70 for inspecting if 0, V in step 4 above₀, U₀Is provided with arithmetic bit extracting means 1-41 for extracting each upper w bit and each lower w bit from the memory, and this gcd arithmetic unit 1000 stores various data and data required for arithmetic, control and processing. 160 is provided.
[0014]
gcd calculation initial setting unit 110
The operation of the gcd calculation initial setting unit 110 will be described with reference to FIGS.
Step S1: The counting units 111 and 112 count the number of consecutive zeros from the least significant bit of each of the inputs X and Y, and the value x₀, Y₀(For example, if the binary representation of the input is 101000, the output is 3).
Step S2: The comparison unit 113 receives the input value x₀, Y₀Compare the smaller z₀Output as.
Step S3: The division units 114 and 115 by the powers of 2 input X, Y and z, respectively.₀Is input, and 2 for each of the input values X and Y^Z0Divide by, and the division result U₀, V₀Is output. gcd calculation initial setting 110 is U₀, V₀, Z₀Is output.
[0015]
gcd operation pseudo-operation unit 120
The operation of the gcd operation pseudo-operation unit 120 will be described with reference to FIGS.
Step S1: From control device 150 v_a, U_a, V_x, U_xAre input to the control unit 121, the memory 122 stores the determined u._u, U_v, V_u, V_v, C are sent to the control unit 121.
Step S2: The control unit 121 sets the data α = {v_a, U_a, V_x, U_x, U_u, U_v, V_u, V_v, C} is entered, u_xChecks if is even. If it is even, the data α = {v_a, U_a, V_x, U_x, U_u, U_v, V_u, V_v, C}.
Step S3: u_xIs an even number, one unit 123 is
u_a← [u_a/ 2]; u_x← u_x/ 2
v_u← 2v_uV_v← 2v_v
And the data α ′ = {v_a, U_a, V_x, U_x, U_u, U_v, V_u, V_v, C}.
Step S4: u_xIs not an even number, the control unit 121 determines that v_xChecks if is even. If the number is even, the data α = {v_a, U_a, V_x, U_x, U_u, U_v, V_u, V_v, C}.
Step S5: u_xIs odd and v_xIf is even, then 2 units 124 are
v_a← [v_a/ 2]; v_x← v_x/ 2
u_u← 2u_uU_v← 2u_v
And the data α ′ = {v_a, U_a, V_x, U_x, U_u, U_v, V_u, V_v, C}.
[0016]
Step S6: The control unit 121_x, V_xIf both are odd, u_aAnd v_aCompare the size of. u_a> V_aIf so, data α = {v to 3 units 125_a, U_a, V_x, U_x, U_u, U_v, V_u, V_v, C} and u_x, V_xBoth odd and u_a≦ v_aIf so, the data α = {v_a, U_a, V_x, U_x, U_u, U_v, V_u, V_v, C}. Step S7: u_x, v_xIs odd and u_a> V_aIn this case, the three-unit device 125 is
u_a← [(u_a−v_a) / 2]; u_x← (u_x−v_x) / 2
u_u← u_u+ V_uU_v← u_v+ V_v
v_u← 2v_uV_v← 2v_v
And the data α ′ = {v_a, U_a, V_x, U_x, U_u, U_v, V_u, V_v, C}.
Step S8: u_x, v_xIs odd and u_a≦ v_aIn the case of 4 units 126,
v_a← [(v_a−u_a) / 2]; v_x← (v_x−u_x) / 2
v_u← v_u+ U_uV_v← v_v+ U_v
u_u← 2u_uU_v← 2u_v
And the data α ′ = {v_a, U_a, V_x, U_x, U_u, U_v, V_u, V_v, C}.
Step S9: When the data α is processed in any of the case 1 unit 123 to the case 4 unit 126 and returned to the control unit 121 as the data α ′, the control unit 121 increases the value of c by 1.
[0017]
Step S10: The c and w ′ are compared. If c <w ′, the process returns to step S2, and if c = w ′, {u_u, U_v, V_u, V_v} Is output from the gcd operation pseudo operation unit 120 to the gcd operation multiple length operation unit 130.
The control unit 121 receives the input u_x, V_x, U_a, V_aThe state determination means 6-21 for processing in the case 1 unit 123 to the case 4 unit 126 from the above state, the processing result storage means 6-22 for storing the results processed by the case units 123 to 126, and the processing count c. Counting means 6-23 for counting and processing end determining means 6-24 for determining whether or not to end the process, that is, c = w ′ are provided.
This gcd operation pseudo-operation unit 120 is U₀, V₀Value of each lower w bit of u_x, V_xRespectively₀, V₀Determine whether or not is an even number₀, V₀Value of each upper w bit of u_a, V_aBy U₀And V₀Based on these, the same processing as the conventional binary gcd algorithm is performed. This can be readily understood by comparing the processing procedure of FIG. 7 with the processing procedure of the conventional binary gcd algorithm shown in FIG. Also here
 gcd (U₀, V₀) ＝ gcd (| u_uU₀−u_vV₀｜ / 2^{w '}, | V_vV₀−v_uU₀｜ / 2^{w '}) (8)
Meet u_u, U_v, V_u, V_vWill be seeking.
[0018]
gcd multiple length arithmetic unit 130
The operation of the gcd multiple length arithmetic unit 130 will be described with reference to FIG.
In FIG. 8, the gcd multiple length arithmetic unit 130 receives a U from the control device 150.₀, V₀From the gcd operation pseudo-operation unit 120_u, U_v, V_u, V_vAre entered respectively. Each of the multipliers 13a to 13d has a product u_uU₀, U_vV_v, V_uU₀, V_vV₀Is calculated and output.
The subtractors 13e and 13f are respectively connected to the difference U₁= u_uU₀−u_vV₀And V₁= v_vV₀−v_uU₀Is output to the absolute value units 13g and 13h.
The absolute value units 13g and 13h are respectively input U₁And V₁Is calculated and output to the power-of-two dividers 13i and 13j.
The power-of-two dividers 13i and 13j are each input | U₁| And | V₁| No.2^{w '}Calculate the division by U₀And V₀As the output of the gcd multiple length arithmetic unit 130.
The processing of the gcd multiple length arithmetic unit 130 in FIG. 8 is summarized below.
Step S1: V₁= (-V_uU₀+ V_vV₀) / 2^{w '}
U₁= (U_uU₀−u_vV₀) / 2^{w '}
Is calculated.
Step S2: V₁← ｜ V₁｜; U₁← ｜ U₁｜
Step S3: V₀ ← V₁   ; U₀ ← U₁
In FIG. 8, 2^{w '} The division by is performed after the absolute value is obtained, but as shown in step S1, 2^{w '} The division by may be performed before the absolute value is obtained. U obtained₀, V₀Is input to the controller 150 and V as described in FIG.₀A check is made whether = 0.
[0019]
gcd calculation final processing unit 140
The operation of the gcd calculation final processing unit 140 will be described with reference to FIG.
The gcd calculation final processing unit 140 receives a U from the control device 150.₀, V₀However, the initial setting unit 110 to z₀Are entered respectively. A small number of gcd calculators 141 are input U₀, V₀Is calculated and output to the power-of-two multiplication unit 142. The power-of-two multiplier 142 of the input 2 is input gcd (U₀, V₀) And z₀With 2^z0gcd (U₀, V₀) Is calculated as the output of the final processing unit 140. That is, it becomes the output of the gcd arithmetic unit 1000.
As shown in FIG. 10, the gcd calculation final processing device 140 performs 2 in the last step S10.^Z0The procedure is basically the same as that of the conventional binary gcd algorithm shown in FIG. More specifically, steps S1 to S9 in FIG. 10 are the same as steps u in steps S1 to S9 in FIG._x, u_u, v_x, v_u, v_vIt is the same as the processing for.
As described above, the greatest common divisor of the inputs X and Y can be obtained. In addition, except for the gcd calculation final processing unit 140, the calculation unit is all w or w ′ bits, and can be performed with a small number of processes as a whole. As will be understood from the description of FIG. 2 and FIG. 3, each unit in FIG. 2 is sequentially processed. Therefore, in FIG. 6, a control unit 121 is provided for convenience of explanation. This can be performed by the control device 150, and other units are also controlled by the control device 150, and the storage unit (memory) necessary for each process in each unit can use the storage unit 160 in FIG. 2.
[0020]
Extended binary gcd arithmetic unit 2000
The extended binary gcd arithmetic device 2000 will be described with reference to FIG. This device 2000 accepts gcd (X, Y) and S = 2 for X and Y inputs.^kX^-1modY and k are output.
The apparatus 2000 includes an extended gcd calculation initial setting unit 210, an extended gcd calculation pseudo calculation unit 220, an extended gcd calculation multiple length calculation unit 230, an extended gcd calculation final calculation unit 240, and a control device 250, as shown in FIG. The following operations are performed:
Step S1: The extended gcd calculation initial setting unit 210 performs input X, Y
gcd (X, Y) = 2^z0gcd (U₀, V₀(9)
Meet U₀, V₀, Z₀Out of z₀Find the one that maximizes. Initial value S of S, T, k₀= 0, T₀= 1, k = 0 and U₀, V₀To the control device 250 and z through the control device 250₀To the extended gcd calculation final processing unit 240.
Step S2: The control device 250 receives the input U₀, V₀, S₀, T₀, K, U₀= 1 or V₀Check if = 1. If the inspection passes, the expanded gcd calculation final processing unit 240 receives U₀, V₀, S₀, T₀, K.
Step S3: The control device 250₀= 1 or V₀If not = 1, enter U₀, V₀, S₀, T₀, K, U₀And V₀The larger bit size value i of the bit sizes is obtained.
Step S4: The controller 250 checks whether the value i is less than w bits. If the inspection is passed, the expanded gcd calculation final processing unit 240 receives the U₀, V₀, S₀, T₀, K. If you do not pass any of the above tests,
v_a= V₀Upper w bits (from i-th bit to i-w + 1-th bit)
u_a= U₀Upper w bits (from i-th bit to i-w + 1-th bit)
v_x= V₀Lower w bits of
u_x= U₀Lower w bits of
Are passed to the extended gcd operation pseudo-operation unit 220, and U₀, V₀, S₀, T₀To the extended gcd arithmetic multiple length arithmetic unit 230. Add w 'to k.
[0021]
Step S5: The extended gcd operation pseudo-operation unit 220₀, V₀V is the upper and lower w bits of_a, U_a, V_x, U_xAre used to simulate an extended gcd operation. The resulting value u_u, U_v, V_u, V_vAre transferred to the extended gcd arithmetic multiple length arithmetic unit 230.
Step S6: The extended gcd calculation multiple length calculation unit 230 is described later with reference to FIG.
U '= (u_uU₀−u_vV₀) / 2^{w '},
V '= (v_vV₀−v_uU₀) / 2^{w '},
S '= u_uS₀+ U_vT₀,
T '= v_vT₀+ V_uS₀
Calculate Here, if V ′ is negative, the signs of V ′ and T ′ are inverted, and if U ′ is negative, the signs of U ′ and S ′ are inverted. U ', V', S ', T' obtained as a result of operation₀, V₀, S₀, T₀To the control device 250.
Step S7: The control device 250 is V₀If it is 0, the process returns to step S3. If it is 0, the process proceeds to the extended gcd calculation final calculation unit 240.
Step S8: The extended gcd calculation final calculation unit 240₀Input U if ≠ 0₀, V₀, Z₀Against 2^Z0gcd (U₀, V₀) And output. Also, V₀= 0 if S = 0^kX^-1Obtain and output S, k as modY.
[0022]
Although not specifically shown in FIG. 11, the extended gcd arithmetic unit 2000 also includes the initial determination means 1-20, the bit size acquisition means 1-30, the bit size inspection means 1-40, the arithmetic bits shown in FIG. Corresponding to extraction means 1-41, final determination means 1-70, and storage unit 160 are provided.
The extended gcd calculation initial setting unit 210 has the functional configuration shown in FIG. 4 similarly to the gcd calculation initial setting unit 110 in FIG. 2, and performs the processing shown in FIG. Initial values S of S, T, k stored in₀= 0, T₀= 1, k = 0 are output to the control device 250.
The functional configuration of the extended gcd operation pseudo-operation unit 220 is almost the same as that of the gcd operation pseudo-operation unit 120 shown in FIG. 6, and the processing is also almost the same as the processing shown in FIG. 7 is also performed to increase the value of k by 1 as shown in parentheses in step S9. That is, u obtained by the pseudo-operation unit 120_u, U_v, V_u, V_vAnd w is added to k and output. Therefore, the control unit of the extended gcd calculation pseudo-operation unit 220 is also provided with means for counting k. Instead of incrementing k by 1 in step S9, when c = w in step S10, k + w = k may be set.
[0023]
Extended gcd multiple length arithmetic unit 230
The operation of the extended gcd multiple length arithmetic unit 230 will be described with reference to FIGS. This calculation unit 230 includes a control unit 250 in FIG.₀, V₀, S₀, T₀However, the extended gcd operation pseudo-operation unit 220 to u_u, U_v, V_u, V_vIs entered.
Each of the multipliers 23a to 23h is a product u_uU₀, U_vV₀, V_uU₀, V_vV₀, U_uS₀, U_vT₀, V_uS₀, V_vT₀Is calculated and output.
The subtractors 23i and 23j are different from each other by a difference U ′ = u_uU₀−u_vV₀And V '= v_uV₀−u_vU₀Is calculated and output.
The adders 23k and 23l each have a sum S '= u_uS₀+ U_vT₀And T '= v_vT₀+ V_uS₀Is calculated and output.
If U ′ <0 with respect to the inputs U ′ and S ′, the control unit 23m outputs U ′ and S ′ to the sign inverter 23o, and newly outputs −U ′ and −S ′ from the sign inverter 23o. Input as "U" and S ". If U ′ ≧ 0, output U ′ to the power-of-two divider 23q and S ′ to S₀Is output from the arithmetic unit 230.
If V ′ <0 with respect to the inputs V ′ and T ′, the control unit 23n outputs V ′ and T ′ to the sign inverter 23p, and newly outputs −V ′ and −T ′ from the sign inverter 23p. Input as V "and T". If V ′ ≧ 0, output V ′ to the power-of-two divider 23r and T ′ to T₀Is output from the calculation unit 230.
[0024]
The power-of-two divider 23q is the input U ′ 2^{w '}Quotient by₁Calculate U₀As the output of the calculation unit 230. The power-of-two divider 23r is the input V ′ 2^{w '}Quotient by₁Calculate V₀As the output of the calculation unit 230.
The processing of the above extended gcd multiple length arithmetic unit 230 is collectively shown in FIG.

Is calculated.
Step S2: V₁Is less than 0, and if not less than 0, the process proceeds to step S4.
Step S3: V₁V is less than 0, V₁← -V₁And T₁← -T₁To change the sign.
Step S4: U₁Is less than 0, and if not less than 0, the process proceeds to step S6.
Step S5: U₁U is less than 0, U₁← -U₁And S₁← -S₁To change the sign.
Step S6: V obtained₁, U₁, S₁, T₁Updated V₀, U₀, S₀, T₀Output as.
The output of the extended gcd arithmetic multiple length arithmetic unit 230 is input to the control device 250.
[0025]
Extended gcd calculation final processing unit 240
The extended gcd calculation final processing unit 240 has substantially the same functional configuration as the final processing unit 140 shown in FIG.₀, V₀Is the initial value, gcd (U, V) is calculated, and the result of the calculation, gcd (U, V) and z₀With 2^z0gcd (U, V) is calculated and output. The difference from the final processing unit 140 is that the final processing unit 240 has S₀, T₀, K are also input. As shown in FIG. 15, a part of the gcd calculation process shown in FIG. 10 is followed by the process of step S8-1 in which k is incremented by 1 after steps S3, S5, S7, and S8. Move on. In step S9, v_xIf = 0, S = (u_uS₀+ U_vT₀) And outputs S and k as a result. This S is S = 2^kX^-1It matches the operation result of modY.
Similarly to the gcd arithmetic device 1000, this extended gcd arithmetic device 2000 can also process each part with one control device 250, and these arithmetic processing can also be performed by decoding and executing a program. In that case, in each calculation process, the necessary data is read from the storage means, taken out from the temporarily stored buffer, the calculation result is written in the storage means, or temporarily stored in the buffer. Will be served. In this embodiment, when the inputs X and Y are both even, gcd (X, Y) = 2^z0u_xWhen one of X and Y is an odd number and gcd (X, Y) = 1, S and k are output. Accordingly, the extended gcd calculation initial setting unit 210 first determines which of X and Y is an odd number.₀X without U₀, Y to V₀And w, S₀= 0, T₀= 1, k = 0 may be output. However, for example, when the inverse element is obtained, it is not obtained unless one of X and Y is an odd number. That is, when it is known in advance that one of the input values is an odd number, the extended gcd calculation initial setting unit 210 simply sets U₀= X, V₀= Y, S₀= 0, T₀Only the initial setting of = 1 and k = 0 may be performed. So X is U₀Y as V₀As S also₀= 0, T₀= 1, k = 0 may be read from the memory and output.
[0026]
In the above description, the number of bits that can be calculated at one time is set to w and w ′. The amount w to be calculated may be the same value.
As described above, the extended binary gcd arithmetic unit can be combined with a power-of-two division unit to constitute an inverse arithmetic unit on the remainder ring Z / NZ. FIG. 16 shows a case where a normal inverse element arithmetic unit is constructed using the extended binary gcd arithmetic unit of the present invention. As shown in the figure, integers X and N are input to the device 3000, and an extended binary gcd calculation unit 315 described with reference to FIG.^-12^kmodN and k are output, and S, k and N are input to the power-of-two divider 318 on Z / NZ and S · 2^-kmodN is calculated and the result is X^-1ModN, that is, the inverse operation result on Z / NZ of X is obtained.
[0027]
FIG. 17 shows an inverse element arithmetic unit 3100 when the extended gcd arithmetic unit of the present invention is applied to a half Montgomery (Kaliski) inverse element arithmetic on the remainder ring Z / NZ. Integers X and N are input to this device 3100, and the calculation by the extended gcd arithmetic device 315 described with reference to FIG. 11 is performed for X and N, and the result S = X^-12^kmodN, k and input N are input to a power-of-two divider 320 on Z / NZ and S · 2^-(kn)modN is calculated (n is the number of bits of N), and as a result, X^-12ⁿmodN is obtained.
FIG. 18 shows an inverse element arithmetic unit 3200 when the extended binary gcd arithmetic unit of the present invention is applied to Montgomery inverse element arithmetic on Z / NZ. As shown in the figure, for the input integers X and N, the extended gcd arithmetic unit 315 performs S = X^-12^kmodN and k are obtained, and on the other hand, S · 2 is multiplied by a power-of-two multiplier 325 on Z / NZ.^2n-kCalculate modN and X^-12²ⁿmodN can also be obtained.
[0028]
FIG. 19 shows an apparatus 5000 when the extended gcd arithmetic apparatus of the present invention is applied to the Montgomery inverse arithmetic apparatus on Z / NZ. As shown in FIG. 19, under the control of the control unit 510, first, X '= X · 2 by a power-of-two division unit 514 on Z / NZ.^-tmodN is calculated, and the calculation results X ′ and N are calculated by the extended gcd arithmetic unit 515 with S = X^-12^kFind modN and k. These S and k are input to the comparator 517 to determine the sign of 2n-kt from the bit lengths n, k and t of N. If negative, k ′ = − 2n + k + t and S ′ = S are set. Input to power division unit 518A on Z / NZ, T = S'2^{-k '}modN is calculated. If 2n-k-t is positive, input k '= 2n-k-t and S' = S to the power-of-two multiplier 518B on Z / NZ, and T = S'2^{k '}modN is calculated. The output unit 519 converts any one of the arithmetic devices 518A and 518B to X.^-12²ⁿIt is output as the operation result of modN.
The above-described program for causing the computer to function as the greatest common divisor or extended greatest common divisor computing device or inverse element computing device according to the present invention is stored in the main storage device 13 in the computing device 10A shown in FIG. 20, for example. Is done. The arithmetic device 10A is realized by a computer, for example, and includes a CPU 11, a RAM 12, a main storage device 13, and the like, and a keyboard 14 and a display device 15 are connected thereto. For example, when a 16-bit chip set that performs operations 16 bits at a time is used as the CPU 11, when performing multiplication / division by a power of 2, as described in the embodiment of the present invention, 16 bits are collectively performed. preferable.
[0029]
The CPU 11 executes the greatest common divisor or extended greatest common divisor calculation or inverse element calculation according to the calculation program in the main storage device 13. The RAM 12 holds various parameter values and variable values necessary for these calculations, and holds intermediate results and final results of the calculations. The user A inputs a program execution instruction from the keyboard 14, and the execution progress of the calculation is displayed on the display device 15.
Here, a case will be described in which the inverse operation unit of the present invention is used in a digital signature which is an example of security technology. The computing device 10A of the user A is connected to the computing device 10B of the user B through, for example, the network NW, and the user A attaches a digital signature S to the document m and transmits it to the computing device 10B of the user B. Then, user B verifies the validity of the received signature S. Here, a case where the ESIGN method is used as a digital signature will be described. In this case, the users A and B share the public key n and the system parameter k, and the transmitting party A holds the prime secret keys p and q in secret. However, n = pq.
A program 13P for executing the digital signature method ESIGN is stored in the main storage device 13. As a part of the program 13P, there is provided a partial program 13PP for executing an expression including an inverse element calculation used in a process of digital signature generation by the calculation method of the present invention.
[0030]
First, the computing device 10A of user A generates a random number x. Next, insert document m into a hash function to generate h (m), and then
w = [{h (m) −x^kmod n} / p ・ q] (10)
Calculate Then the following formula
S = x + {w / (k · x^k-1mod p} p ・ q (11)
Ask for. W / (k ・ x in equation (11)^k-1) mod p is the same as the inverse operation described above. Therefore, as explained above
y = w (k ・ x^k-1)^-1mod p = w ・ X^-1mod p (12)
In other words, y can be obtained by the inverse element calculation processing procedure shown in the explanation of FIG. Using y obtained in this way
S = x + y · p · q (13)
And (S, m) is transmitted to the computing device 10B of the user B.
User B's device 10B uses the received S and m to
S^k−2^a≦ h (m) ≦ S^k, Where a = [(2/3) log₂n] (14)
Is established, and if it is established, it is recognized that the signature S for the document m is correct.
Although the recording medium of the inverse arithmetic operation program of the present invention is stored in the main storage device 13 of the arithmetic unit and used, it is shown that such a program is stored in any other form of recording medium. Obviously, it may be used.
[0031]
【The invention's effect】
In the binary gcd arithmetic unit according to the present invention, by performing a pseudo binary gcd calculation by a calculation using a small integer, the calculation of a large integer is reduced at a rate proportional to 1 / w, and the binary gcd calculation is performed. It can be performed at high speed. (W is the number of bits that the computer can handle at one time 8, 16, 32, etc.)
In addition, the efficiency of the pseudo operation is increased by introducing a method of “performing a predetermined number of times even if there is no guarantee that the actual gcd algorithm is correctly simulated”.
Thus, for example, the conventional method L has been simulated for about 12 laps by a pseudo-arithmetic method using 32-bit single-precision integers. It is possible to simulate 32 laps. In this case, the gcd operation can be performed with a large number of integer operations less than half of the algorithm L.
[Brief description of the drawings]
FIG. 1 is a flowchart showing a calculation procedure of a conventional binary gcd algorithm.
FIG. 2 is a diagram showing a functional configuration of a gcd arithmetic device according to the present invention.
FIG. 3 is a flowchart showing an operation flow of the apparatus of FIG. 2;
4 is a diagram showing a functional configuration of a gcd calculation initial setting unit 110 in FIG. 2;
5 is a flowchart showing an operation flow of the initial setting unit 110 in FIG. 4;
6 is a diagram showing a functional configuration of a gcd operation pseudo-operation unit 120 in FIG. 2;
7 is a flowchart showing an operation flow of the pseudo operation unit 120 in FIG. 6;
8 is a diagram showing a functional configuration of a gcd arithmetic multiple length arithmetic unit 130 in FIG. 2. FIG.
9 is a diagram showing a functional configuration of a gcd calculation final calculation unit 140 in FIG. 2. FIG.
FIG. 10 is a diagram showing a flow of operation of a final calculation unit 140 in FIG. 9;
FIG. 11 is a diagram showing a functional configuration of an extended binary greatest common divisor arithmetic device according to a modification of the present invention.
12 is a diagram showing a flow of operations of the extended binary greatest common divisor computing device of FIG. 11;
13 is a diagram showing a functional configuration of an extended gcd arithmetic multiple length arithmetic unit 230 in FIG.
14 is a diagram showing a flow of operation of the multiple length arithmetic unit 230 of FIG. 13;
FIG. 15 is a diagram showing a part of the operation flow of the final computing unit 240 in FIG. 11;
FIG. 16 is a diagram showing a functional configuration of a normal inverse element arithmetic device to which the extended binary gcd of the present invention is applied.
FIG. 17 is a diagram showing a functional configuration of a half Montgomery (Kaliski) inverse element operation device to which the extended binary gcd of the present invention is applied;
FIG. 18 is a diagram showing a functional configuration of a Montgomery inverse element computing device to which the extended binary gcd of the present invention is applied.
FIG. 19 is a diagram showing another functional configuration of the Montgomery inverse element computing device to which the extended binary gcd of the present invention is applied.
FIG. 20 is a block diagram showing an example of a functional configuration for causing a computer to function according to the present invention by using a computer program recording medium according to the present invention.

Claims (12)

Input means for inputting input values X and Y;
Storage means for storing these X and Y respectively;
Input values X, Y from the gcd (X, Y) = gcd (U 0, V 0) and gcd calculation initialization means 2 ^Z0 and z ₀ is computed to U _0, V _0, z ₀ to the maximum, gcd ( A, B) represents the greatest common divisor of A and B
From input values U ₀ and V ₀ , for a predetermined integer w ′ ≧ 4
gcd (U ₀ , V ₀ ) = gcd (| u _u U ₀ −u _v V ₀ | / 2 ^{w ′} , | v _v V ₀ −v _u U ₀ | / 2 ^{w ′} )
Gcd operation pseudo-operation means for calculating u _u , u _v , v _v , and v _u satisfying
From input values U ₀ , V ₀ , u _u , u _v , v _v , v _u
U '= | u _u U ₀ −u _v V ₀ | / 2 ^{w ′}
V ′ = | v _v V ₀ −v _u U ₀ | / 2 ^{w ′}
Gcd operation multiple length calculation means for calculating and outputting as U ₀ and V ₀ ,
Gcd calculation final processing means for calculating gcd (U ₀ , V ₀ ) 2 ^Z ₀ from input values U ₀ , V ₀ , z ₀ ;
An output means for outputting the result gcd (X, Y);
Control means for sequentially operating each of the above means and performing read / write to the storage means,
The greatest common divisor arithmetic unit. 2. The apparatus of claim 1, wherein the control means comprises:
A bit size obtaining means for obtaining a larger value i of the bit sizes of the input values U ₀ and V ₀ ;
It is determined whether or not the value i is less than or equal to w. If it is not less than w, the gcd calculation pseudo-calculation means is executed, and if it is less than or equal to w, the bit size inspection means for executing the gcd calculation final processing means; w is a predetermined integer of 4 or more,
Final determination means for determining whether or not V _{0 in} the output of the gcd arithmetic multiple length arithmetic means is 0;
If the determination of the final determination means is not V ₀ = 0, the outputs U ₀ and V ₀ of the gcd operation multiple length calculation means are input to the bit size acquisition means and executed, and the V ₀ = 0 is executed. Means for executing the gcd calculation final processing means,
And the greatest common divisor computing device. 3. The apparatus according to claim 2, wherein the control means determines whether the input from the gcd calculation initial setting means is V ₀ = 1 or U ₀ = 1, and if this is established, the input values U ₀ , V A greatest common divisor computing device, comprising initial determination means for inputting ₀ to the gcd calculation final processing means without inputting ₀ to the gcd calculation pseudo-calculation means. 4. The apparatus according to claim 1, 2 or 3, wherein said control means extracts operation bits for extracting u _a and v _a of each upper w bit and u _x and v _x of each lower w bit from U ₀ and V ₀ , respectively. Having means,
The gcd operation pseudo-operation means is:
The above u _a , v _a , u _x , v _x and initial values u _u = 1, u _v = 0, v _u = 1, v _v = 0 are input,
u _x is or even, v _x is or even, u _a> v _a or, determining _{u x, v x, u a} , and v _a state determining means,
u _x is an even number, and u _a = [u _a / 2], u _x = u _x / 2, v _u = 2v _u , v _v = 2v _v ,
v _x is an even number and v _a = [v _a / 2], v _x = v _x / 2, u _u = 2u _u , u _v = 2u _v ,
u _a > v _a and u _a = [(u _a −v _a ) / 2], u _x = (u _x −v _x ) / 2, and
u _u = u _u + v _u , u _v = u _v + v _v , v _u = 2v _u , v _v = 2v _v ,
In other cases, v _a = [(v _a −u _a ) / 2], v _x = (v _x −u _x ) / 2, and
v _u = v _u + u _u , v _v = v _v + u _v , u _u = 2u _u , u _v = 2u _v ,
An update operation means for updating u _u , v _v , u _v , v _u by executing any of the following:
Counting means for counting the number of times c calculated by the update calculating means;
Means for repeatedly executing the u _x , v _x , u _a , and v _a state determination means, the update calculation means, and the counting means until the number of times c reaches w ′;
And the greatest common divisor computing device. An input means for inputting an input value X, N of which one is an odd number;
Storage means for storing these X and N respectively;
Extended gcd calculation initial setting means for initial setting U ₀ = X, V ₀ = N, S ₀ = 0, T ₀ = 1, k = 0;
From input values U and V to a predetermined w '
gcd (U, V) = gcd (| u _u U ₀ −u _v V ₀ | / 2 ^w , | v _v V ₀ −v _u U ₀ | / 2 ^{w ′} )
An extended gcd operation pseudo-operation means for calculating u _u , u _v , v _v , and v _u satisfying and adding w ′ to k;
From input values U, V, S, T, u _u , u _v , v _v , v _u
U ′ = (u _u U ₀ −u _v V ₀ ) / 2 ^{w ′} , S ′ = u _u S ₀ + u _v T ₀
Or
U '= − (u _u U ₀ −u _v V ₀ ) / 2 ^{w ′} , S ′ = − (u _u S ₀ + u _v T ₀ )
When,
V ′ = (v _v V ₀ −v _u U ₀ ) / 2 ^{w ′} , T ′ = v _v T ₀ + v _u S ₀
Or
V ′ = − (v _v V ₀ −v _u U ₀ ) / 2 ^{w ′} , T ′ = − (v _v T ₀ + v _u S ₀ )
And an extended gcd arithmetic multiple length arithmetic means for outputting U ′, V ′, S ′, T ′ as U ₀ , V ₀ , S ₀ , T ₀ , respectively,
From input values U ₀ , V ₀ , S ₀ , T ₀ | u _u U ₀ −u _v V ₀ | / 2 ^c = gcd (U, V)
｜ v _v V ₀ −v _u U ₀ ｜ / 2 ^c = 0
U _u , u _v , v _v , v _u , c satisfying
S '= u _u S ₀ + u _v T ₀
An extended gcd calculation final processing means for calculating c and adding c to k;
The calculation result of the extended gcd calculation final processing means is set as the calculation result of S = X ⁻¹ 2 ^k (modN), and this and the output means for outputting k and each of the above means are operated in order to read and write to the storage means. An extended greatest common divisor computing device including control means for performing the operation. 6. The apparatus of claim 5, wherein the control means is
A bit size obtaining means for obtaining a larger value i of the bit sizes of the input values U ₀ and V ₀ ;
A bit size checking means for determining whether or not the value i is less than or equal to w, and executing the extended gcd calculation pseudo-calculation means if it is not less than w, and executing the extended gcd calculation final processing means if it is less than or equal to w;
Final determining means for determining whether or not V _{0 in} the output of the extended gcd arithmetic multiple length arithmetic means is 0;
If the determination of the final determination means is not V ₀ = 0, the outputs U ₀ and V ₀ of the extended gcd calculation multiple length calculation means are input to the bit size acquisition means and executed, and V ₀ = 0. If so, means for executing the extended gcd calculation final processing means,
And an extended greatest common divisor computing device. 7. The apparatus according to claim 5 or 6, wherein said control means includes operation bit extraction means for extracting u _a and v _a of each upper w bit and u _x and v _x of each lower w bit from U ₀ and V ₀ , respectively. Have
The extended gcd operation pseudo-operation means receives the above u _a , v _a , u _x , v _x and initial values u _u = 1, u _v = 0, v _u = 1, v _v = 0 and k. ,
u _x is or even, v _x is or even, and u _a> v _a or determines _{u x, v x, u a} , v a state determining means,
u _x is an even number, and u _a = [u _a / 2], u _x = u _x / 2, v _u = 2v _u , v _v = 2v _v ,
v _x is an even number and v _a = [v _a / 2], v _x = v _x / 2, u _u = 2u _u , u _v = 2u _v ,
u _a > v _a and u _a = [(u _a −v _a ) / 2], u _x = (u _x −v _x ) / 2, and
u _u = u _u + v _u , u _v = u _v + v _v , v _u = 2v _u , v _v = 2v _v ,
In other cases, v _a = [(v _a −u _a ) / 2], v _x = (v _x −u _x ) / 2, and
v _u = v _u + u _u , v _v = v _v + u _v , u _u = 2u _u , u _v = 2u _v ,
Update calculation means for updating u _u , v _u , u _v , v _v by performing any of the following:
Counting means for counting the number of times c calculated by the update calculating means;
The number c is w 'said u _x until, v _x, u _a, and v _a state determining means, and the update computing unit, to execute repeatedly a process between the counting means, the number c is w' becomes Means for updating k to k + w '
And an extended greatest common divisor computing device.   A computer-readable recording medium storing a program for causing a computer to function as the greatest common divisor computing device according to any one of claims 1 to 4.   A computer-readable recording medium storing a program for causing a computer to function as the extended greatest common divisor computing device according to any one of claims 5 to 7. 8. An inverse operation unit on a remainder ring Z / NZ that outputs X ^-1 mod N for inputs X and N, and performs an extended binary gcd operation on input X and N The extended greatest common divisor computing device described above, S and k output from the extended greatest common divisor computing device, and N are input, and S · 2 ^−k mod N is calculated to calculate X ⁻¹ mod N An inverse element arithmetic unit comprising: a power-of-two division unit on a remainder ring Z / NZ that is output as an arithmetic result . A Montgomery inverse operation unit on the remainder ring Z / NZ that outputs X ^-1 2 ²ⁿ modN for n-bit inputs X and N, and X and N are input, and X ′ = X · 2 ^−t mod A power-of-two division unit on the remainder ring Z / NZ that computes N and outputs X ′ and t ;
The extended maximum commitment according to any one of claims 5 to 7, wherein X ' and N are input, an extended binary gcd operation is performed on these, and S = X ^-1 2 ^k mod N and k are output. A number arithmetic unit;
If S, k, N, and t are input and 2n−kt is negative from the bit lengths n, k, and t of N, k ′ = 2n + k + t and S ′ = S are output, and 2n−k− a comparator that outputs k ′ = 2n−kt and S ′ = S if t is positive ;
K ′ = − 2n + k + t, S ′, and N are inputted, and a division unit by a power of 2 on the remainder ring Z / NZ for calculating T = S ′ 2 ^{−k ′} mod N ;
k ′ = 2n−k−t, S ′, and N are input, and T = S ′ 2 ^k mod N is a multiplier by a power of 2 on the remainder ring Z / NZ ,
An inverse element computing device comprising: an output unit that outputs a computation result T output from the division device and the multiplication device as a computation result of X ^-1 2 ²ⁿ mod N. A half Montgomery (Kaliski) inverse operation unit on the remainder ring Z / NZ that outputs X ⁻¹ 2 ⁿ mod N for n-bit inputs X and N, and an extended binary gcd for the input X and N and extended greatest common divisor calculation unit according to any one of claims 5 to 7 performs calculation, the extended greatest common divisor output from the arithmetic unit S and k and the above N are input, S · 2 - ^{(kn )} Mod N (n is the number of bits of N), and outputs as a calculation result of X ⁻¹ 2 ⁿ mod N. Inverse element arithmetic unit.

Images