"Phase transition phenomena of statistical mechanical models of the integer factorization problem"


Chihiro Nakajima (AIMR, Tohoku University)


We formulate the integer factorization problem as the searching problem for a ground state of a statistical mechanical Hamiltonian. The analysis of the density of states of two macroscopic quantities, energy and the Hamming distance from the correct solutions, leads a conclusion that the ground state (the correct solution) is completely isolated from other low energy states with the distance proportional to the system size. In addition, the characteristics of the microcanonical entropy of the model leads two peculiar features which are each related to two drastic changes of the energy region sampled by Monte Carlo simulation or simulated annealing. As a result, we find the peculiar first-order phase transition in our model.

Designed by CSS.Design Sample