Complexity transitions in global algorithms for sparse linear systems over finite fields

被引:12
作者
Braunstein, A
Leone, M
Ricci-Tersenghi, F
Zecchina, R
机构
[1] Int Ctr Theoret Phys, I-34100 Trieste, Italy
[2] SISSA, I-34100 Trieste, Italy
[3] INFM, I-34100 Trieste, Italy
[4] Univ Roma La Sapienza, Dipartimento Fis, I-00185 Rome, Italy
[5] Univ Paris 11, Lab Phys Theor & Modeles Statist, F-91405 Orsay, France
来源
JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL | 2002年 / 35卷 / 35期
关键词
D O I
10.1088/0305-4470/35/35/301
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
We study the computational complexity of a very basic problem, namely that of finding solutions to a very large set of random linear equations in a finite Galois field modulo q. Using tools from statistical mechanics we are able to identify phase transitions in the structure of the solution space and to connect them to the changes in the performance of a global algorithm, namely Gaussian elimination. Crossing phase boundaries produces a dramatic increase in memory and CPU requirements necessary for the algorithms. In turn, this causes the saturation of the upper bounds for the running time. We illustrate the results on the specific problem of integer factorization, which is of central interest for deciphering messages encrypted with the RSA cryptosystem.
引用
收藏
页码:7559 / 7574
页数:16
相关论文
共 7 条
[1]  
BRODER AZ, 1993, PROCEEDINGS OF THE FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P322
[2]   Exact solutions for diluted spin glasses and optimization problems [J].
Franz, S ;
Leone, M ;
Ricci-Tersenghi, F ;
Zecchina, R .
PHYSICAL REVIEW LETTERS, 2001, 87 (12) :127209-127209
[3]   Phase coexistence and finite-size scaling in random combinatorial problems [J].
Leone, M ;
Ricci-Tersenghi, F ;
Zecchina, R .
JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 2001, 34 (22) :4615-4626
[4]  
Ricci-Tersenghi F, 2001, PHYS REV E, V63, DOI 10.1103/PhysRevE.63.026702
[5]  
[No title captured]
[6]  
[No title captured]
[7]  
[No title captured]