2017年1月
Statistical Mechanical Models of Integer Factorization Problem
JOURNAL OF THE PHYSICAL SOCIETY OF JAPAN
- ,
- 巻
- 86
- 号
- 1
- 開始ページ
- 014001
- 終了ページ
- 014001
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.7566/JPSJ.86.014001
- 出版者・発行元
- PHYSICAL SOC JAPAN
We formulate the integer factorization problem via a formulation of the searching problem for the ground state of a statistical mechanical Hamiltonian. The first passage time required to find a correct divisor of a composite number signifies the exponential computational hardness. The analysis of the density of states of two macroscopic quantities, i.e., the energy and the Hamming distance from the correct solutions, leads to the conclusion that the ground state (correct solution) is completely isolated from the other low-energy states, with the distance being proportional to the system size. In addition, the profile of the microcanonical entropy of the model has two peculiar features that are each related to two marked changes in the energy region sampled via Monte Carlo simulation or simulated annealing. Hence, we find a peculiar first-order phase transition in our model.
- リンク情報
- ID情報
-
- DOI : 10.7566/JPSJ.86.014001
- ISSN : 0031-9015
- Web of Science ID : WOS:000391858100015