ysd@KLab > 因数分解 > 平方差分法

　下に示す方法を実行するより前に、最低限 2 で割れるだけ割って n が奇数になるようにしておきます。つまりこの方法は n が奇数であることが前提です。
　また、p と q が n=pq (p ≥ q) を満たす奇数であるとしましょう。素数かどうかは関係なく。その上で x=(p+q)/2, y=(p-q)/2 と定義すると p=x+y, q=x-y なので

n = pq = (x+y)(x-y) = x²-y²

となります。この式を逆に利用しようという魂胆です。

x = sqrt(n);
y = 0;
while( x * x - y * y != n ) {
  if( x * x - y * y < n ) x++;
  else y++;
}
printf("%d=%d*%d", n, x + y, x - y);

　単純に x²-y² が n より大きければ減少分を増やし、小さければ増加分を増やしています。ただ、これだと掛け算をとてつもない数する必要があるので多倍長計算向きではないなぁ、と考えると次のような形に変更できます。

x = sqrt(n);
y = 0;
res = x * x - y * y - n;
while( res != 0 ) {
  if( res < 0 ) {
    res += (2 * x + 1);
    x++;
  } else {
    res -= (2 * y + 1)
    y++;
  }
}
printf("%d=%d*%d", n, x + y, x - y);

　コンピュータでの計算を考えれば、途中にある2倍の計算は単にビットシフトでできるのがありがたいです。これでグッと速度向上、しているはずです。ただ、常に x < y なので時間的な割合としては殆ど y を増加させっぱなしになってるんじゃないかな？と考えて次のコードです。

x = sqrt(n);
y = sqrt(n - x * x);
while( x * x - y * y != 0 ) {
  x++;
  y = sqrt(n - x * x);
}
printf("%d=%d*%d", n, x + y, x - y);

　y の計算を式にしました。q が小さい場合には上のコードより終盤の速度が落ちるかも知れませんが、そんなことは殆ど無いだろうということで。全体の、平均的な速度はきっと速いはず。

　最初の方で p と q は奇数と言ったけれども奇素数とは言っていません。つまりどちらかが合成数になることもあるわけです…が、そんなことはお構いなしです。この方法の主目的は因数分解する数の桁数を落とすこと。なので p か q が合成数だと分かったら、また分解すればいいだけの話です。また同じアルゴリズムを使ってもいいし、小さな桁で速いアルゴリズムを使ってもいいし。

平方差分法

方法

あれ？

名前とか