Load balanced block Lanczos algorithm over GF(2) for factorization of large keys

被引：0
作者：
Hwang, Wontae [1 ]
Kim, Dongseung [1 ]
机构：
[1] Korea Univ, Dept Elect Engn, Seoul 136701, South Korea
来源：
HIGH PERFORMANCE COMPUTING - HIPC 2006, PROCEEDINGS | 2006年 / 4297卷
关键词：
parallel/cluster computing; cryptology; RSA key; load balancing; sparse matrix;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Researchers use NFS (Number Field Sieve) method with Lanczos algorithm to analyze big-sized RSA keys. NFS method includes the integer factorization process and nullspace computation of huge sparse matrices. Parallel processing is indispensible since sequential computation requires weeks (even months) of CPU time with supercomputers even for 150-digit RSA keys. This paper presents details of improved block Lanczos algorithm based on previous implementation[4,10]. It includes a new load balancing scheme by partitioning the matrix such that the numbers of nonzero components in the submatrices become equal. Experimentally, a speedup up to 6 and the maximum of efficiency of 0.74 have been achieved using an 8-node cluster with Myrinet interconnection.
引用
收藏
页码：375 / +
页数：3
相关论文
共 15 条
  • [1] Cavallar S, 1999, LECT NOTES COMPUT SC, V1716, P195
  • [2] CAVALLAR S, 2000, THEORY APPL CRYPTOGR, P1
  • [3] Cullum J. K., 1985, LANCZOS ALGORITHMS L, V1
  • [4] FLESCH I, 2002, THESIS UTRECHT U UTR
  • [5] Horn R. A., 1986, Matrix analysis
  • [6] HWANG W, 2005, THESIS KOREA U
  • [7] Fast broadcast by the divide-and-conquer algorithm
    Kim, DY
    Kim, DS
    [J]. 2004 IEEE INTERNATIONAL CONFERENCE ON CLUSTER COMPUTING, 2004, : 487 - 488
  • [8] AN ITERATION METHOD FOR THE SOLUTION OF THE EIGENVALUE PROBLEM OF LINEAR DIFFERENTIAL AND INTEGRAL OPERATORS
    LANCZOS, C
    [J]. JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS, 1950, 45 (04): : 255 - 282
  • [9] LENSTRA AK, 1990, 22ND P ANN ACM S THE, P564
  • [10] MONTGOMERY PL, 1994, P S APPL MATH, P567
12