Fussy's Diary

次回の「アルゴリズムのコーナー」テーマは「素因数分解」としました。

現在、二次篩(QS)というアルゴリズムのサンプル・プログラムが完成したところです。バグに悩まされてかなり苦労しました。結局、非常に初歩的なミスが原因だったのにすぐに気づくことができなかったのが我ながら情けないです。素因数分解のアルゴリズムで大きなものとしては他に楕円曲線法(ECM)と連分数法(CFRAC)があります。とりあえずまだ勉強中ということで、QS法がまとまったらいったん公開しようと考えています。
素因数分解、単純そうに見えて結構奥深いテーマで、新しいアルゴリズムを考えるのも楽しそうなネタだと思います。そう簡単にいいアルゴリズムが見つかれば誰も苦労しませんが。現在の暗号技術の要にもなっているわけで、巨大な数を簡単に素因数分解できるアルゴリズムが見つかったらそれこそ大変なことになるでしょうし。