Art

J-GLOBAL ID：201302273297887760   Reference number：13A1770938

Statistical Mechanical Formulation and Simulation of Prime Factorization of Integers

整数の素因数分解の統計力学的定式化とシミュレーション

Author (1)： NAKAJIMA Chihiro H (Dep. of Physics, Kyushu Univ.)
Material： Interdisciplinary Information Sciences  (Interdiscip Inf Sci)
Volume： 19  Issue： 1  Page： 51-56 (J-STAGE)  Publication year： 2013 
JST Material Number： L2559A  ISSN： 1340-9050  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *factorization ,  *prime number ,  *statistical mechanics ,  ground state ,  *simulation ,  Monte Carlo method ,  search problem ,  computer algorithm ,  NP hard ,  Markov chain ,  computational complexity
Semi thesaurus term： factorization in prime numbers ,  computational complexity ,  first passage time ,  calculation cost ,  numerical experiment

JST classification (2)： Mathematical physics  (BA03000W) ,  Statistical mechanics in general,many-body problems,etc.  (BA08010Q)

Reference (19)：

• 1) Garey, M. R., and Johnson, D. S., Computers and Intractability, Freeman, San Francisco (1979).
• 2) Lenstra, A. K., and Lenstra, H. W., The Development of the Number Field Sieve, Lecture Notes in Math. No. 1554, Springer-Verlag, Berlin (1993).
• 3) Shor, P. W., ``Algorithms for quantum computation: Discrete logarithms and factoring,'' Proc. 35th Symp. Foundations of Computer Science, 124-134 (1994).
• 4) Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., and Troyansky, L., ``Determining computational complexity from characteristic `phase transitions','' Nature, 400: 133-137 (1999).
• 5) Martin, O. C., Monasson, R., and Zecchina, R., ``Statistical mechanics methods and phase transitions in optimization problems,'' Theor. Comput. Sci., 265: 3-67 (2001).

Terms in the title (5)： 整数 ,  素因数分解 ,  統計力学 ,  定式化 ,  シミュレーション