拡張ユークリッド互除法を非再帰ベースで理解する (C++)

2021/02/18 数式を修正しました

拡張ユークリッド互除法とは

方程式 の解 を 1 つ求めるアルゴリズム*1です。

注意

qnighy.hatenablog.com

書いた後で、概ね同じ内容を説明している記事を見つけました。分かりやすさには個人差があると思うので、本記事にも需要ありと信じて公開します。

本記事内で説明に使用しているコードは、コーナーケースやオーバーフロー、速度の定数倍、行儀などを一切考慮していません。

ユークリッド互除法 (非再帰)

int gcd(int a, int b) {

  s = a, t = b;

  while (s % t != 0) {

    int u = s % t;

    s = t;
    t = u;
  }

  return t;
}

単純に言えば、最初 として、 を に置き換えることを繰り返すアルゴリズムです。

拡張ユークリッド互除法

さて、ユークリッド互除法における と同時に「 の解 , の解 」を管理することにしてみます。 初期条件は何でしょうか？ なので、 です。同様に、 となります。

std::pair<int, int> extgcd(int a, int b) {

  int s = a, xs = 1, ys = 0, t = b, xt = 0, yt = 1;

  ~略~

さて、後は として が求まればユークリッド互除法と同様の繰り返しで求める が得られます。 このままでは難しいので、式を書き換えます。

\begin{align} u &= s \bmod t \\ \Leftrightarrow u &= s - t \left\lfloor \frac{s}{t} \right\rfloor \quad \text{剰余の定義} \\ \Leftrightarrow \left( ax_u + by_u \right) &= \left( ax_s + by_s \right) - \left( ax_t + by_t \right) \left\lfloor \frac{s}{t} \right\rfloor \quad s, t, u\text{を置換} \end{align} ここで最後の式を分解すると \begin{align} x_u &= x_s - x_t \left\lfloor \frac{s}{t} \right\rfloor \\ y_u &= y_s - y_t \left\lfloor \frac{s}{t} \right\rfloor \end{align} としてやれば条件を満たすことが分かります　( は共に整数になります)。

int temp = s / t; // floor(s / t)
int u = s - t * temp;
int xu = xs - xt * temp;
int yu = ys - yt * temp;

後は前述のコードと全く同様に、 を に置き換えていけば完成します。

std::pair<int, int> extgcd(int a, int b) {

  int s = a, xs = 1, ys = 0, t = b, xt = 0, yt = 1;

  while (s % t != 0) {

    int temp = s / t;
    int u = s - t * temp;
    int xu = xs - xt * temp;
    int yu = ys - yt * temp;

    s = t;
    xs = xt;
    ys = yt;
    t = u;
    xt = xu;
    yt = yu;
  }

  return {xt, yt};
}

*1:定義揺れはご了承ください