| 講演抄録／キーワード |
| 講演名 |
2014-05-12 00:00
［ポスター講演］素因数分解の統計力学的定式化
○中島千尋（東北大） |
| 抄録 |
（和） |
本研究では、素因数分解の問題を統計力学ハミルトニアンの基底状態探索問題として定式化することで解くアプローチを提案する。この定式化を通して、素因数分解の平均的な計算複雑性についての知見を得ることを目指す。こうした視点に基づき、まずレプリカ交換モンテカルロ法によるシミュレーションを試みた。解が見つかるまでにかかるシミュレーションステップを調べ、計算量がシステムサイズに対して、大まかにではあるが指数関数的に依存することを見いだした。
また、正解に対するハミング距離とエネルギーについての状態密度分布を調べた。これにより、エネルギーランドスケープの多谷構造の存在を示唆する結果を得た。 |
| （英） |
We propose a new approach to solve the problem of the prime factorization, formulating the problem as a ground state searching problem of statistical mechanics Hamiltonian. This formulation is expected to give a new insight to this problem. Especially in the context of computational complexity, one would expect to yield the information which leads to determination of the typical case computational complexity of the factorizing process. With this perspective, first we perform simulation with replica exchange Monte Carlo method. We investigated the first passage time that the correct form of prime factorization is found and observed the behavior which seems to indicate exponential computational hardness.
The above result is followed by the analysis of the density of states on two macroscopic quantities; energy and hamming distence from correct solutions. The behavior of the density of states seems to imply the complex energy landscape with many local minima. |
| キーワード |
（和） |
レプリカ交換モンテカルロ法 / 素因数分解 / 統計力学 / / / / / |
| （英） |
replica exchange Monte Carlo mathod / prime factorization / statistical mechanics / / / / / |
| 文献情報 |
信学技報 |
| 資料番号 |
|
| 発行日 |
|
| ISSN |
|
| PDFダウンロード |
|