フェルマーの因数分解法

ピエール・ド・フェルマーにちなんで名付けられたフェルマーの因数分解法は、奇数を2つの平方数の差として表現することに基づいている。

${\displaystyle N=a^{2}-b^{2}.}$

その差は代数的に因数分解でき、${\displaystyle (a+b)(ab)}$どちらの因数も 1 に等しくない場合、それはNの適切な因数分解です。

それぞれの奇数にはそのような表現があります。実際、${\displaystyle N=cd}$Nの因数分解である場合、

${\displaystyle N=\left({\frac {c+d}{2}}\right)^{2}-\left({\frac {cd}{2}}\right)^{2}.}$

Nは奇数なので、cとdも奇数となり、これらの半分は整数になります。（4の倍数は平方差でもあります。cとdを偶数とします。）

最も単純な形では、フェルマー法は試行除算よりも遅くなる可能性もある（最悪の場合）。しかしながら、試行除算とフェルマー法を組み合わせることで、どちらか一方だけを用いるよりも効果的になる。

aのさまざまな値を試して、${\displaystyle a^{2}-N=b^{2}}$正方形。

FermatFactor(N): // Nは奇数である必要があります a ← ceiling(sqrt(N)) b2 ← a*a - N b2が正方形になるまで繰り返す： a ← a + 1 b2 ← a*a - N // 同様に： // b2 ← b2 + 2*a + 1 // a ← a + 1 return a - sqrt(b2) // または a + sqrt(b2)

例えば、因数分解するには${\displaystyle N=5959}$最初の試みは、5959の平方根を切り上げて次の整数にしたもの、つまり78です。${\displaystyle b^{2}=78^{2}-5959=125}$125は平方数ではないので、 aの値を1増やして2回目の試みを行います。282はやはり平方数ではないため、2回目の試みも失敗します。

3回目の試行で、441の平方数が得られます。したがって、${\displaystyle a=80}$、${\displaystyle b=21}$5959の約数は${\displaystyle ab=59}$そして${\displaystyle a+b=101}$。

N が 2 個以上の素因数を持つと仮定します。この手順では、まずaとbの値が最小となる因数分解を見つけます。つまり、${\displaystyle a+b}$はNの平方根以上の最小の因数であり、したがって${\displaystyle ab=N/(a+b)}$は、ルートN以下の最大の因子です。手順が${\displaystyle N=1\cdot N}$これはNが素数であることを示している。

のために${\displaystyle N=cd}$c を最大の部分根因子とする。${\displaystyle a=(c+d)/2}$したがって、ステップ数はおよそ${\displaystyle (c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c}$。

Nが素数である場合(つまり、${\displaystyle c=1}$) 必要${\displaystyle O(N)}$ステップ。これは素数性を証明するのに悪い方法です。しかし、N が平方根に近い因数を持つ場合、この方法はすぐに機能します。より正確には、c が以下より小さい場合${\displaystyle {\left(4N\right)}^{1/4}}$から${\displaystyle {\sqrt {N}}}$この方法は1つのステップしか必要としません。これはNのサイズに依存しません。

素数N = 2,345,678,917を因数分解することを考えてみましょう。ただし、その過程でbとa − bも計算してください。${\displaystyle {\sqrt {N}}}$次の整数に切り上げると48,433となり、以下のように表にまとめることができます。

実際には、bが整数になるまで最後の行は気にしなくてよい。しかし、Nが上の部分根因子を持っている場合、${\displaystyle ab=47830.1}$フェルマーの方法であれば、既にそれを見つけていただろう。

試行除法では通常48,432まで試しますが、フェルマーのステップを4回踏むだけで、47,830まで除算するだけで因数を見つけたり素数性を証明したりできます。

これは全て、複合因数分解法を示唆している。何らかの境界を選択する。${\displaystyle a_{\mathrm {max} }>{\sqrt {N}}}$; フェルマー法を用いて、間の因数を求める${\displaystyle {\sqrt {N}}}$そして${\displaystyle a_{\mathrm {max} }}$これにより、試行除算の上限が与えられます。${\displaystyle a_{\mathrm {max} }-{\sqrt {a_{\mathrm {max} }^{2}-N}}}$上記の例では、${\displaystyle a_{\mathrm {max} }=48436}$試算部門の上限は47830です。妥当な選択肢としては、${\displaystyle a_{\mathrm {max} }=55000}$上限値は28937となる。

この点において、フェルマーの方法は収穫逓減の法則に従う。人は必ずこの段階に達する前に研究を中止するだろう。

表を検討する際には${\displaystyle N=2345678917}$すぐにわかるように、${\displaystyle b^{2}}$正方形です。

すべての平方根を計算する必要はありません${\displaystyle a^{2}-N}$、またaのすべての値を調べることさえしません。 平方数は常に 0、1、4、5、9、16 を法として20 と合同です。これらは20 の平方剰余だからです。値はaが10 ずつ増加するたびに繰り返されます。 この例では、N は 17 mod 20 なので、17 mod 20 を減算（または 3 を加算）すると、${\displaystyle a^{2}-N}$これらの値に対して、20 を法として 3、4、7、8、12、19 を生成します。このリストから 4 だけが平方数になり得ることは明らかです。したがって、$\displaystyle a^{2}}$aは 1 mod 20 でなければなりません。つまり、aは 1、9、11、または 19 mod 20 です。${\displaystyle b^{2}}$これは 20 を法として 4 で終わり、平方数の場合は、b は10 を法として 2 または 8 で終わります。

これは任意のモジュラスで実行できます。同じものを使用します${\displaystyle N=2345678917}$、

一般的には、法ごとに異なる素数のべき乗を選択する。

一連のa値（開始値、終了値、ステップ値）と法値が与えられた場合、次のように進めることができます。

FermatSieve(N、astart、aend、astep、modulus) スタート ← スタート 剰余倍数を実行します。 b2 ← a*a - N b2 が正方形の 場合、モジュロ modulus: FermatSieve(N , a, aend, astep * modulus, NextModulus) endif a ← a + astep エンドド

しかし、再帰は残りのa の値が少なくなったとき、つまり ( aend-astart )/ astepが小さくなったときに停止します。また、aのステップサイズは一定であるため、加算によって連続する b2 を計算できます。

フェルマーの方法は、 Nの平方根に近い因数がある場合に最も効果的です。

2 つの要因のおおよその比率 (${\displaystyle d/c}$) が既知であれば、有理数${\displaystyle v/u}$その値に近い値を選ぶことができます。${\displaystyle Nuv=cv\cdot du}$そして、Nuvにフェルマーの方法を適用すると、次の因子が見つかります。${\displaystyle cv}$そして${\displaystyle du}$すぐに。それから。${\displaystyle \gcd(N,cv)=c}$そして${\displaystyle \gcd(N,du)=d}$（ただし、cがuを割り切るか、dがvを割り切る場合は除く。）

一般的に、比率が不明な場合は、さまざまな${\displaystyle u/v}$値を試して、結果として得られる各Nuv を因数分解しようと試みることができます。R. Lehman はこれを行う体系的な方法を考案し、フェルマーのプラス試行除法によって N を因数分解することができます。${\displaystyle O(N^{1/3})}$時間。^{[ 1 ]}

フェルマーの因数分解法の基本概念は、大きな半素数を因数分解するための最もよく知られたアルゴリズムである二次篩法と一般数体篩法の基礎となっており、これらは「最悪のケース」である。二次篩法がフェルマーの因数分解法よりも優れている主な点は、単に数列の中で平方数を見つけるのではなく、${\displaystyle a^{2}-n}$このアルゴリズムは、この数列の要素のうち、積が平方数となる部分集合を非常に効率的に見つけ出します。最終的な結果は同じで、平方数の差を法nで表したものとなり、それが自明でない場合は、 n を因数分解するために使用できます。

• 正方形を完成させる
• 多項式の因数分解
• 因数定理
• FOILルール
• モノイド分解
• パスカルの三角形
• プライムファクター
• 因数分解
• オイラーの因数分解法
• 整数因数分解
• プログラム合成
• ガウス整数因数分解表
• 一意の因数分解

• フェルマー (1894)、『フェルマー作品集』、第 1 巻。 2、p.  256
• McKee, J (1999). 「フェルマーの因数分解法の高速化」 .計算数学. 68 (228): 1729–1737 . doi : 10.1090/S0025-5718-99-01133-3 .

• フェルマーの因数分解の実行時間、blogspot.in
• フェルマーの因数分解オンライン計算機（ windowspros.ru）