興味深い記事があったのでチェック
世界初、専用ハードウェアによる素因数分解実験に成功
それでも423bitの素因素分解に約1ヶ月ということで
RSAが破れるとかそういう話ではないわけですが(RSAでは一般に1024bit以上)
それでもなかなか興味深い数字です。
アルゴリズムは一般数体篩を使ってるということです。
今知られている素因数分解アルゴリズムの中では
漸近的には一番速いとされています。
(素因数分解の計算量の評価は難しいいのでこういう表現になってしまいます)
新しく劇的に速い素因数分解アルゴリズムが見つかる
もしくは、量子コンピューターの実用化(即ちshorのアルゴリズムの実用化)までは
このハードウェアでの結果は大きな意味を持つんじゃないでしょうか。(素人意見ですが)
素因数分解は古典的な方法での多項式時間アルゴリズムがあるのかね？
個人的にはあるような気がする。単なる勘だけど。
行列の積計算もO(n2)になるかもという考えもあるそうだし
アルゴリズム研究は本当に興味深い…。
