オイラーの因数分解法

オイラーの因数分解法は、数を 2 つの異なる方法で 2 つの平方の和として表すことによって因数分解する手法です。たとえば、数はまたは と表すことができ、オイラーの因数分解法では となります。 ${\displaystyle 1000009}$${\displaystyle 1000^{2}+3^{2}}$${\displaystyle 972^{2}+235^{2}}$${\displaystyle 1000009=293\cdot 3413}$

奇数の正の整数の 2 つの異なる表現が因数分解につながるという考えは、マリン・メルセンヌによって最初に提案されたようです。しかし、この考えが広く利用されるようになったのは、100 年後のオイラーによるものでした。現在では彼の名前が付けられているこの方法の最も有名な利用法は、数を因数分解したことでした。この数は、主要な素数判定では擬素数ではないにもかかわらず、以前は素数であると考えられていたようです。 ${\displaystyle 1000009}$

オイラーの因数分解法は、因数が互いに近くない整数に対してはフェルマーの因数分解法よりも効果的であり、2 つの平方の和としての数の表現をかなり簡単に見つけることができる場合は、試行除算よりもはるかに効率的になる可能性があります。2 つの平方の和としての数の表現を見つけるために使用される方法は、フェルマーの因数分解法で平方の差を見つける方法と基本的に同じです。

オイラーの因数分解法の大きな欠点は、 素因数分解で奇数乗になる 4 k + 3 形式の素因数を持つ整数の因数分解には適用できないことです。このような数は 2 つの平方数の和になることはありません。4 k + 1 形式の奇数の合成数でさえ、4 k + 3形式の 2 つの素数の積になることが多く (例: 3053 = 43 × 71)、これもオイラー法では因数分解できません。

この適用範囲の制限により、オイラー因数分解法はコンピュータ因数分解アルゴリズムには不向きとなっています。ランダムな整数を因数分解しようとするユーザーは、問題の整数にオイラー法が実際に適用できるかどうかを知る可能性は低いからです。オイラー法を適用できることがわかっている特殊な数に使用するためのコンピュータアルゴリズムにオイラー法を開発する試みがなされたのは、ごく最近のことです。

ブラフマグプタ・フィボナッチの等式は、2 つの平方の和の積は 2 つの平方の和であることを示しています。オイラーの方法はこの定理に依存していますが、 2 つの平方の和の積として 求めると、逆と見なすことができます。${\displaystyle n=a^{2}+b^{2}=c^{2}+d^{2}}$${\displaystyle n}$

まず推測すると

${\displaystyle a^{2}-c^{2}=d^{2}-b^{2}}$

そして両辺を因数分解すると

${\displaystyle (ac)(a+c)=(db)(d+b)}$（１）

ここで、ととすると、を満たす 定数が存在する。${\displaystyle k=\operatorname {gcd} (ac,db)}$${\displaystyle h=\operatorname {gcd} (a+c,d+b)}$${\displaystyle l,m,l',m'}$

• ${\displaystyle (ac)=kl}$、
• ${\displaystyle (db)=km}$、

${\displaystyle \operatorname {gcd} (l,m)=1}$

• ${\displaystyle (a+c)=hm'}$、
• ${\displaystyle (d+b)=hl'}$、

${\displaystyle \operatorname {gcd} (l',m')=1}$

これらを式（１）に代入すると、

${\displaystyle klhm'=kmhl'}$

共通因数を消去すると

${\displaystyle lm'=l'm}$

ここで、とが互いに素な数のペアである という事実を用いて、${\displaystyle (l,m)}$${\displaystyle \left(l',m'\right)}$

• ${\displaystyle l=l'}$
• ${\displaystyle m=m'}$

それで

• ${\displaystyle (ac)=kl}$
• ${\displaystyle (db)=km}$
• ${\displaystyle (a+c)=hm}$
• ${\displaystyle (d+b)=hl}$

私たちは今それを見ています${\displaystyle m=\operatorname {gcd} (a+c,db)}$${\displaystyle l=\operatorname {gcd} (ac,d+b)}$

ブラフマグプタ・フィボナッチの等式を適用すると、

${\displaystyle \left(k^{2}+h^{2}\right)\left(l^{2}+m^{2}\right)=(kl+hm)^{2}+(km-hl)^{2}={\bigl (}(ac)+(a+c){\bigr )}^{2}+{\bigl (}(db)-(d+b){\bigr )}^{2}=(2a)^{2}+(2b)^{2}=4n.}$

各因数は2つの平方数の和なので、そのうちの1つは必ず偶数、つまりまたは のいずれかを含む必要があります。一般性を失うことなく、ペアが偶数であると仮定します。因数分解は次のようになります。 ${\displaystyle (k,h)}$${\displaystyle (l,m)}$${\displaystyle (k,h)}$

${\displaystyle n=\left(\left(\left({\tfrac {k}{2}}\right)^{2}+\left({\tfrac {h}{2}}\right)^{2}\right)\left(l^{2}+m^{2}\right).\,}$

以来：${\displaystyle \ 1000009=1000^{2}+3^{2}=972^{2}+235^{2}}$

上記の式から次のようになります。

したがって、

${\displaystyle 1000009=\left[\left({\frac {4}{2}}\right)^{2}+\left({\frac {34}{2}}\right)^{2}\right]\cdot \left[\left({\frac {14}{2}}\right)^{2}+\left({\frac {116}{2}}\right)^{2}\right]\,}$

${\displaystyle =\left(2^{2}+17^{2}\right)\cdot \left(7^{2}+58^{2}\right)\,}$

${\displaystyle =(4+289)\cdot (49+3364)\,}$

${\displaystyle =293\cdot 3413\,}$

関数 Euler_factorize(int n) -> list[int]
   is_prime(n)ならば
       print("数値は因数分解できません")
       終了関数
   a=1 から a=ceiling(sqrt(n)) までの for ループ
       b2 = n - a*a
       b = 床(平方根(b2))
       b*b==b2の場合
           a、b を保存してループを中断する
   a*a+b*b!=nならば
       print("n を平方和として表す式が見つかりませんでした")
       終了関数
   c=a+1 から c=ceiling(sqrt(n)) までの for ループ
       d2 = n - c*c
       d = floor(sqrt(d2))
       d*d==d2ならば
           c、d を保存しながらループを中断する
   c*c+d*d!=nの場合
       print("n の二乗和の 2 番目の式が見つかりませんでした")
       終了関数
   A = ca、B = c+a
   C = bd、D = b+d
   k = GCD(A,C)//2、h = GCD(B,D)//2
   l = GCD(A,D)//2、m = GCD(B,C)//2
   係数1 = k*k + h*h
   係数2 = l*l + m*m
   リスト[因子1、因子2]を返す

• オーレ、オイステイン (1988)。「オイラーの因数分解法」。数論とその歴史。クーリエ社。pp. 59–64。ISBN 978-0-486-65620-5。
• マッキー、ジェームズ (1996)。「オイラー因数分解法を因数分解アルゴリズムに変換する」。ロンドン数学会報。4 (28): 351–355。doi :10.1112/ blms /28.4.351。