Hatena::ブログ(Diary)

もうカツ丼でいいよな このページをアンテナに追加 RSSフィード Twitter

2009 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 12 |
2012 | 02 | 03 | 04 | 05 | 06 | 10 | 11 | 12 |
2013 | 01 | 02 | 04 | 06 |
2014 | 06 |

2011-05-05

[] ユークリッドの互除法とその拡張 17:51  ユークリッドの互除法とその拡張を含むブックマーク  ユークリッドの互除法とその拡張のブックマークコメント

ユークリッドの互除法

まずはユークリッドの互除法について確認。

ユークリッドの互除法は2つの正整数最大公約数をもとめる手法。

2つの正整数をm, nとする

  • E1. mをnで割った剰余をrとする
  • E2. rが0に等しければ終了。nが最大公約数である。
  • E3. m <- n、n <- rとしてE1に戻る。

ここで<-は代入操作を表す記号とする。

拡張されたユークリッドの互除法

2個の正整数m, nについて、その最大公約数がdであるとする。

このとき、2個の整数a, bを用いて

am + bn = d

という式を成立させることができる。

拡張ユークリッドの互除法最大公約数dだけでなく、上式における係数a, bを同時に求める。

  • E'1. a <- 0, a' <- 1, c <- m, b <- 1, b' <- 0, d <- n
    • a, a', b, b'の値はam+bn=d, a'm+b'n=cが成立するように選ばれている
  • E'2. cをdで割った商をq, 余りをrとする
  • E'3. r = 0なら終了。dは最大公約数であり、式am+bn=dは成立したままなのでa, bの値を参照すればよい。
  • E'4-1. c <- d, d <-r
    • ユークリッドの互除法におけるE3の手順と同様。
    • cとdが変更されたので、等式am+bn=d, a'm+b'n=cが成立するように各係数を変更する必要がある。
    • cにdを代入したので、a'm+b'n=cを成立させるにはa'にaを、b'にbを代入すればよい
    • dにrを代入したので、am+bn=dを成立させるにはaにa'-qaを、bにb'-qbを代入すればよい(※)
    • 上述の代入を一度に行うには、一時変数tを用意して
  • E'4-2. t <- a', a' <- a, a <- t - qa, t <- b', b' <- b, b <- t - qb
    • 代入後、E2へ戻る。

※部分の解説

(各変数はE'4-1の代入を行う前の値とする)

  • r = c - qdと表せるので、d = (c-r)/q
  • am + bn = dに代入して、am + bn = (c-r)/q
  • 整理して -qam - qbn + c = r
  • a'm + b'n = cを代入して整理すると(a'-qa)m + (b'-qb)n = r

参考

トラックバック - http://d.hatena.ne.jp/Rion778/20110505/1304585508