ユークリッドの互除法

世界最古に発見されたアルゴリズムのひとつとして知られるユークリッドの互除法は, 歴史上の価値のみならず, 公約数という素因数が絡む計算を素因数分解せずに効率的に求めることができるという点で非常に有用な手法となっています.

ユークリッドの互除法とは, 2つの0ではない整数a, b に対して, 次の手続を繰り返すことで ab の最大公約数を求めることができます.

  1. b=0 ならば a が求めるべき最大公約数である. アルゴリズムはここで終了する.
  2. c≡a (mod b) を計算し, ab を代入, bc を代入する.
  3. 最初に戻る.

ラメの定理により, アルゴリズムの繰り返し回数は a, b のうち小さい方の 10 進桁数を d とすれば, 高々 5d 回となることが知られており, 5d 回程度の繰り返しが発生する例はフィボナッチ数列(最初の2項を1としたもの)の隣接2項を対象とした場合が知られています.

もしも, これを素因数分解で解決しようとすると, a, b のうち小さい方の正の平方根の数だけ「試しに割り算して割り切れるかを確かめる」作業が必要となります。

つまり, abのもとで割算の回数を比較すると, ユークリッドの互除法ならば 2.2log(b), 素因数分解するなら √b と見積もることができます. b が大きい場合, どちらの方が効率がいいのかは明らかです.

この方法を拡張すると不定方程式 ax+by=gcd(a,b) の整数解を導出することができます. これが拡張されたユークリッドの互除法です. 拡張されたユークリッドの互除法の手順は次のとおりです.

  1. r0=a, s0=1, t0=0, r1=b, s1=0, t0=1, i=1 とする.
  2. ri+1=ri-1-qiri を 0≤ri+1≤abs(ri), qi は整数となるように定める.
  3. si+1=si-1-qisi, ti+1=ti-1-qiti とする.
  4. ri+1=0 の場合は x=si, y=ti であるので計算を終了する. ri+1≠0 の場合は次の項目に進む.
  5. i に 1 を加えて 2. の項目へ戻る.

ユークリッドの互除法の使用例

モジュラ逆数について

個人的メモ

m における整数 a のモジュラ逆数 a-1 (mod m) とは, aa-1≡1 (mod m) を満たす a-1x (mod m) なる整数 x の合同類である.

m における整数 a のモジュラ逆数が存在するための必要十分条件は gcd(m, a)=1 である.

a-1 (mod m) を求める最も汎用的な方法は拡張されたユークリッドの互除法を用いることである. つまり, a, m が所与であるもとでの ax-qm=gcd(a,m)=1 を満たす xa-1 (mod m) である.

他にも, オイラーのトーシェント関数を用いて a-1aφ(m)-1 (mod m) としたり, カーマイケル関数を用いて a-1aλ(m)-1 (mod m) と求める方法があるが, これは m を因数分解する必要があるので効率的な導出方法ではない. これらの特殊形として, m が素数 p であった場合は, a-1ap-2 (mod p) とすることができる.

具体例

合同式に関する諸性質

個人的なメモ

  • フェルマーの小定理とは次の関係を言う: 素数 pp とは互いに素な整数 a について ap-1≡1 (mod p) が成り立つ.
  • 数論におけるオイラーの定理とは次の関係を言う: 任意の正の整数 nn とは互いに素な整数 a について aφ(n)≡1 (mod n) が成り立つ.
    • φ(n) はオイラーのトーシェント関数であり、これは n 以下の n とは互いに素な正の整数の数となる。
    • nk=1mpkbk と素因数分解できたならば, φ(n)=nΠk=1m(1-1/pk)
  • カーマイケルの定理とは次の関係を言う: φ(n) は am≡1(mod n) を満たす最小の m であるとは限らない.
    最小の m はカーマイケル関数λ(n)で与えられる.

    • カーマイケル関数は次のように再帰的に定義される.
      • λ(2e)=1 (e=1), 2 (e=2), 2e-2 (e≧3)
      • 奇素数 p について λ(pe)=pe-1(p-1)
      • nk=1mpkbk と素因数分解できたならば λ(n)=lcm(λ(p1b1),...,λ(pmbm)). ただし, lcm は引数たちの最小公倍数(least common multiple)を表す。

    n≡1 (mod λ(n)) を満たすような n をカーマイケル数という.

以上によれば, 2n≡1 (mod 15) を満たす n は, フェルマーの小定理では導出できない (n=3×5)が,
オイラーの定理によれば n=8 のときに成立することが分かり, カーマイケルの定理によれば, 最小の整数 n は 4 である.