n項のGCD - crypto-writeup-public

$ax + by + cz = gcd(a, b, c)$ を満たす $x, y, z$ は計算できるし、n項に拡張できるという話

方法を引用するとこう

$(a,b)$

のベズー係数

$(p,q)$

を拡張ユークリッドの互除法を用いて一つ求める。

$(gcd(a,b),c)$

のベズー係数

$(r,s)$

を拡張ユークリッドの互除法を用いて一つ求める。

$(pr,qr,s)$

が

$(a,b,c)$

のベズー係数の一つである。

あとは再帰的にやれば良い