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

仕事でとある機械を設計する仕事をしていました。 3年前ぐらいに設計をPythonで自動化した経験について書きます。入社したときから設計に配属され、ずっと設計をしていました。 内製の多数の設計ツールを駆使して、手作業でひたすら計算して、設計クライテリ…

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

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