連分数因数分解

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

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

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

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

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

参考文献

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

さらに読む

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