拡張ユークリッドの互除法
ユークリッドの互除法の拡張
通常のユークリッドの互除法
最大公約数\gcd(a,b)を求める
拡張ユークリッドの互除法
2つの整数a,bから、d=\gcd(a,b)かつd=ax+byとなる整数x,yを求める
通常のユークリッドの互除法と何が異なるか
入力m,nの最小公倍数dだけでなく、d=am+bnを満たすa,bも同時に求めて、d,a,bを返す
行列を用いた解法
ぱっと思い出せれば確実にこっちのほうが計算量も少ないし、計算ミスも少ない
手順
例としてa=96, b=701の最大公約数を求める
1. いつもどおり701=96*7+29の形の式を+0になる直前まで求める
2. 行列を作る
\left(\begin{array}{cc}{0} & {1} \\ {1} & {-7}\end{array}\right)\left(\begin{array}{c}{701} \\ {96}\end{array}\right)=\left(\begin{array}{l}{96} \\ {29}\end{array}\right).
左側は\left(\begin{array}{cc}{0} & {1} \\ {1} & -\mathrm{商}\end{array}\right)
以下のような順番で書くとたぶん速い
→
→
→
3. 行列をかけ合わせる
覚えていなくても冷静に考えればわかる
上の画像の最後のようになったときE*D*C*B*A*\left(\begin{array}{c}{701} \\ {96}\end{array}\right)=\left(\begin{array}{c}{1} \\ {0}\end{array}\right)
Eに下から一つずつ代入している
このときの右辺の1行目の1が最大公約数
4. 求めたものの1行目が答え
E*D*C*B*A=\left(\begin{array}{cc}{-43} & {314} \\ {10} & {-73}\end{array}\right).
となったら、答えは(a,b)=(-43,314)
参考
関数型言語での拡張ユークリッドの互除法の実装
引数6つの補助関数を作る
拡張ユークリッドの互除法って2ループ前の変数を保存してないと行けないからこうなるんだな
以下の数列を定めて実装する ref
\left(\begin{array}{ll}{u_{0}} & {v_{0}} \\ {u_{1}} & {v_{1}}\end{array}\right)=\left(\begin{array}{ll}{1} & {0} \\ {0} & {1}\end{array}\right)
\left(\begin{array}{cc}{u_{k}} & {v_{k}} \\ {u_{k+1}} & {v_{k+1}}\end{array}\right)=\left(\begin{array}{cc}{0} & {1} \\ {1} & {-q_{k}}\end{array}\right)\left(\begin{array}{cc}{u_{k-1}} & {v_{k-1}} \\ {u_{k}} & {v_{k}}\end{array}\right) \quad(k>0)
この2式から、x_n,u_n,v_nの漸化式とその初期値が求まるので、それを実装に落とし込む
Mathematicaで実装した
nb// an,bnはa_next,b_nextのつもり。
Rec[a_, b_, _, _, m_, 0] := {a, b, m};
Rec[a_, b_, an_, bn_, m_, n_] := Module[{r, q},
{q, r} = QuotientRemainder[m, n];
Return[Rec[an, bn, (a-q*an), (b-q*bn), n, r]];
]
ExGDCRec[m_, n_] := Rec[1, 0, 0, 1, m, n]参考
参考
『現代暗号の基礎数理』 7章
表を作りながら解いて行くと良い