Statistical Mechanical Formulation and Simulation of Prime Factorization of Integers

スポンサーリンク

概要

• 論文の詳細を見る

• 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. As a secondary purpose, we also expected that this method may become a new efficient algorithm to solve the factorization problem. But for now, our method seems to be not efficient comparing to the existing method; number field sieve.

著者

• Nakajima Chihiro

  Department Of Bioengineering And Robotics Tohoku University

関連論文

• C-Terminal Activation of Peptides with an Active Ester via an Oxazolone
• Analysis of the Dynamic Behavior of the Inner Hair Cell Stereocilia by the Finite Element Method
• Knot Localization in a Flexible Polymer Confined in a Tube(Statistical Physics and Topology of Polymers with Ramifications to Structure and Function of DNA and Proteins)
• Statistical Mechanical Formulation and Simulation of Prime Factorization of Integers
• Computing a Knot Invariant as a Constraint Satisfaction Problem

スポンサーリンク