素因数分解のフェルマー法とは何か

どうも、木村（@kimu3_slime）です。

今回は、素因数分解のフェルマー法とは何か、紹介します。

素因数分解のフェルマー法

すべての整数は、素数の積に分解できること（素因数分解）が知られています。しかし原理的に素数の積に分解できるからといって、実際に与えられた整数がどんな素数の積に分解されるかはわかりません。素因数分解を得るには、どうしたら良いのでしょうか？

素数の判定、素因数分解をするための一番単純な方法は、試し割り法です。\(n\)の素因数分解を求めるために、\(2,3,5,\dots\)と順に割っていけば良い、という発想ですね。原理的には、\(\sqrt{n}\)以下のすべての素数で割り切れるかどうか調べれば良いことが知られています。

手計算でやってみるとわかりますが、3桁くらいの数ならともかく、4桁の数になるとしんどくなってきます。何か良い方法はないのでしょうか。

そこで紹介するのが、フェルマー法（Fermat’s factorization method）と呼ばれる方法です。

\(n\)を正の整数とします。\(2\)で割り切れるかどうかは簡単なので、あらかじめ\(2\)で割っておいて、\(n\)が奇数のときどうするかを考えましょう。

発想としては、\(n=x^2-y^2\)、\(x,y\)は非負の整数、\(x\geq y\)という分解を考えます。もしこの形が得られたら、\(x^2-y^2=(x+y)(x-y)\)と因数分解できますね。

果たしてそんなことができるのでしょうか？　\(n=ab\)という因数分解を持ったとしましょう。すると、\(ab=(\frac{a+b}{2})^2-(\frac{a-b}{2})^2\)は常に成り立ち、\(n\)が奇数であることから、\(a,b\)も奇数で、\((\frac{a+b}{2})^2,(\frac{a-b}{2})^2\)は非負の整数となりますね。

というわけで、\(n=x^2-y^2\)を満たす\(x,y\)を求めれば良い、ということになります。

形を変えれば\(x^2-n=y^2\)で、\(y\)が整数ですから、\(\sqrt{x^2-n}\)が整数でなければならない、すなわち\(x^2-n\)が平方数（整数の2乗）でなければならないです。また、右辺が正であることから、\(x^2 \geq n\)でなければなりません。

まとめれば、\(k\geq \sqrt{n}\)を満たす最小の整数\(k\)をまず見つけ、その後\(k^2-n,(k+1)^2-n,\dots\)が平方数となるかチェックすれば良いです。\((k+\ell)^2-n=y^2\)となる\(y\)が見つけられたら、\(n=(k+\ell+y)(k+\ell-y)\)と因数分解されます。

平方数のチェックは、有限回のステップで必ず終わります。\((\frac{n+1}{2})^2-n=(\frac{n-1}{2})^2\)という形になるからです。このときは、\(n=n\cdot 1\)の分解が得られています。もし、それまでの数で平方数になっていなかったら、\(n\)が素数であるとわかるわけですね。

では、フェルマー法を実際に使ってみましょう。

\(n=2021\)を素因数分解したいです。

\(\sqrt{2021}\)より大きな最小の整数を求めます。おおざっぱには\(1600<2021<2500\)ですね。二乗を計算してあたりをつけていくと、\(43^2=1849,44^2=1936,45^2=2025\)なので、\(\sqrt{2021}\leq 45\)です。

\(k=45\)とします。\(k^2 -2021,(k+1)^2-2021,\dots\)が平方数となるかを順に調べれば良いわけです。が、\(k^2-2021=4=2^2\)で済んでいますね。よって、\(2021=(45+2)(45-2)=47\cdot 43\)と因数分解されました。\(43,47\)は素数です。

\(2021\)は試し割り法でも扱った数ですが、それに比べれば簡単に因数分解が見つかっています。そもそも、\(2021\)が平方数\(2025\)にかなり近い数なので、あたりがつけやすいですね。

もうひとつやってみましょう。

\(11418\)を素因数分解したいとします。まず\(2\)で割れば、\(5709\)の素因数分解を求める問題となります。

\(\sqrt{5709}\)より大きな最小の整数を求めましょう。まず、\(70^2=4900<5709<6400=80^2\)です。\(75^2=5625,76^2=5776\)なので、\(k=76\)とします。

\(k^2-n=67\)は平方数ではありません。\((k+1)^2-n=6084-5709=375\)は平方数ではありません。……とチェックしていくわけですが、電卓を使ってもかなりステップを踏んでしまいます。そして、\(103^2-n=10609-5709=7900=70^2\)が得られます。よって、\(n=(103+70)(103-70)=173\cdot 33\)です。

\(33=3\cdot 11\)ですが、\(173\)は素数でしょうか。再びフェルマー法でチェックしようとしますが、ひどく時間がかかります。最終的には\((\frac{n+1}{2})^2=87^2\)にたどり着き、\(173\)は素数です。

以上の結果をまとめれば、\(11418=2\cdot 3\cdot 11\cdot 173\)という素因数分解が得られました。

平方数に近い数の場合はフェルマー法は有効です。平方数\(x^2\)の値を多く知っていれば、\(x^2-1,x^2-4,x^2-9,x^2-16,\dots\)の分解もわかります。例えば\(46^2=2116\)からは、\(2115,2112,2107,2100,\dots\)の分解がわかります。\(2035=(46+9)(46-9)=55\cdot 37\)あたりは年号の問題で使えそうですね。

しかし、フェルマー法は実際には素数である数の判定にかなり時間がかかります。そういうときは試し割り法の方が良いですね。つまり、数に応じて、試し割り法とフェルマー法を使い分けるのが良いでしょう。

今回は、素因数分解のためのフェルマー法を紹介しました。

より現実的な素因数分解の方法としては、2次ふるい法（quadratic sieve）や数体ふるい法（general number field shieve）が知られています。それはフェルマー法を改良したもので、\(x^2 \equiv y^2 \,(\mathrm{mod} n)\)という合同式を考えます。素因数分解の世界記録は、かつては2次ふるい法、現在は数体ふるい法によるもののようです。

参考：素因数分解の現状 (古典計算編) – Qiita

いつでも\(n=x^2-y^2\)のような形に分解しやすいわけではありませんが、奇数がそのような形に分解できるから、原理的には見つけられる、という発想は面白いですね。

木村すらいむ（@kimu3_slime）でした。ではでは。