以前の記事でもちらっと書きましたが、素因数分解のアルゴリズムは大きなカテゴリーが２つあり、そのうちの１つにフェルマー法、２次ふるい法、連分数法、数体ふるい法が属しています。 今回はフェルマー法、２次ふるい法を紹介していきます。素因数分解(1) …

前回の記事（素因数分解(1) Pollardのρ法 - wacchoz’s note）でちらっと書きましたが、素因数分解のアルゴリズムは大きなカテゴリーが２つあり、そのうちの１つに法、法、楕円曲線法が属しています。 今回はそれらについて書いていきます。素因数分解(1) Pol…

RSA暗号が素因数分解の難しさを安全性の根拠にしていることからわかる通り、大きな数の素因数分解は非常に難しいです。 今のところ、200桁程度の数の素因数分解が限界のようです。 素因数分解(1) Pollardのρ法 - wacchoz’s note（今ここ） 素因数分解(2) p-1…

APR-CL素数判定法(Adleman–Pomerance–Rumely-Cohen-Lenstra primality test, APR-CL primality test)について概説＆実装してみる。 この素数判定法はAdleman–Pomerance–Rumelyらによって開発された方法で、のちにCohenとLenstraによって改良されています。 …