連分数の因数分解

数論において、連分数因数分解法（CFRAC）は整数因数分解アルゴリズムである。これは汎用アルゴリズムであり、特殊な形式や特性に依存せず、任意の整数nを因数分解するのに適している。これは1931年にDHレーマーとREパワーズによって記述され、 ^[1] 1975年にマイケル・A・モリソンとジョン・ブリルハートによってコンピュータアルゴリズムとして開発された。^[2]

連分数法はディクソンの因数分解法に基づいている。これは、通常の連分数展開における収束式を使用する。

{\sqrt {kn}},\qquad k\in \mathbb {Z^{+}}

。

これは二次無理数なので、連分数は周期的である必要があります( nが平方の場合は因数分解が明らかであるため、除きます)。

O表記とL表記では、時間計算量はである。^[3] $O\left(e^{\sqrt {2\log n\log \log n}}\right)=L_{n}\left[1/2,{\sqrt {2}}\right]$

参考文献

^ Lehmer, DH; Powers, RE (1931). 「大きな数の因数分解について」アメリカ数学会報. 37 (10): 770–776. doi : 10.1090/S0002-9904-1931-05271-X .
^モリソン、マイケル A.、ブリル ハート、ジョン (1975年1 月)。「因数分解の方法と F7 の因数分解」。計算数学。29 (129 )。アメリカ数学会: 183–205。doi :10.2307/2005475。JSTOR 2005475。
^ ポメランス、カール(1996 年 12 月)。「2 つのふるいの物語」(PDF)。AMSの通知。第 43 巻、第 12 号。pp. 1473–1485。

サミュエル・S・ワグスタッフ・ジュニア(2013)。『因数分解の喜び』プロビデンス、ロードアイランド州：アメリカ数学会。pp. 143–171。ISBN 978-1-4704-1048-3。