https://blog.fltech.dev/entry/2025/05/23/annealing-based_factorization2
で紹介されていた
2048ビット合成数の素因数分解に成功したという論文を
読んでみました。
google翻訳で読んだのですが、
RSA攻撃における整数因数分解問題を組合せ最適化問題に変換して解いているようなので
部分的な解法という感じが否めません。
しかしながら、いよいよ
RSA暗号の寿命が尽きつつあるのも
間違いなさそうです。
注記：
geminiによる問題点の指摘は以下です。
整数因数分解問題を組合せ最適化問題に変換する際の問題点
整数因数分解問題を組合せ最適化問題に変換することは、その問題を量子アニーリングやイジングモデルといった特定の手法で解くための一般的なアプローチです。しかし、この変換にはいくつかの重大な問題点が伴います。
1. 問題サイズの爆発的増加 (スケーラビリティの問題)
整数 N を因数分解するために、通常は N=pq となるような p,q を見つけることを目指します。これを組合せ最適化問題に変換する場合、目的関数や制約条件を記述するために、多くの二値変数（ビット）が必要になります。
たとえば、N が L ビットの数である場合、p や q も概ね L/2 ビット程度の長さになります。これらのビットを表現するために、O(L) 個の変数が必要となり、さらにそれらの積を表現するためには、O(L2) 個の結合項（相互作用）を持つ高次の多項式が目的関数に含まれることになります。
この変数の数や結合の複雑さは、L が大きくなるにつれて指数関数的に増加します。現在の量子アニーリングマシンや古典コンピュータ上のシミュレータでは、扱える変数の数や結合の数が限られているため、実用的なサイズの整数（例えば、数百ビットのRSA暗号で使われるような数）を因数分解するための組合せ最適化問題は、現状のハードウェアでは対応しきれないほど巨大になってしまいます。
2. 目的関数の複雑化と局所解の問題
因数分解問題を組合せ最適化問題に変換する際、目的関数は通常、ある種の「最小値」が因数分解の解に対応するように設計されます。しかし、この目的関数はしばしば非常に複雑で、多くの局所解を持つ形になります。
イジングモデルなどの最適化手法は、エネルギーランドスケープの最小点を探すことによって解を見つけます。しかし、複雑な目的関数では、アルゴリズムが大域的な最小解ではなく、局所的な最小解に囚われてしまう可能性が高くなります。これにより、正しい因数分解の解に到達できない、または非常に長い探索時間が必要になるという問題が生じます。
3. ハードウェアへのマッピングの困難さ (埋め込み問題)
量子アニーリングマシンは、そのアーキテクチャによって、変数間の結合の仕方に制約があります。たとえば、D-Waveのマシンでは、すべての変数が互いに直接結合しているわけではありません。
このため、構築した組合せ最適化問題を実際に量子アニーリングマシンの物理的な構造に「埋め込む」必要があります。この埋め込みは、追加の補助変数（チェーン）を使用したり、複雑なマッピングアルゴリズムを必要としたりすることがあります。このプロセス自体が計算資源を消費し、さらに問題サイズを実質的に増加させてしまうことがあります。また、不完全な埋め込みは、解の精度や探索効率を低下させる原因にもなります。
4. 量子アニーリングの性能限界
量子アニーリングは、最適化問題に特化した量子計算の手法ですが、その能力はまだ発展途上にあります。現状では、古典的なアルゴリズム（例えば、一般数体ふるい法など）に比べて、大規模な整数因数分解問題に対してはるかに劣る性能しか示していません。
理論的な観点からも、量子アニーリングが因数分解に対してショアのアルゴリズムのような指数関数的な高速化をもたらすかどうかは、まだ活発な研究テーマであり、確立された結論はありません。
これらの問題点から、整数因数分解問題を組合せ最適化問題に変換するアプローチは、現在のところ学術的な研究対象としては非常に興味深いものの、実用的な因数分解ツールとしては課題が多いと言えます。特に大規模な数への適用には、ハードウェアとアルゴリズムの両面で大きな進歩が必要です。
