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

Wontae Hwang; Dongseung Kim

doi:10.1007/11945918_38

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

Wontae Hwang, Dongseung Kim

GREEN SCHOOL (Graduate School of Energy and Environment)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	High Performance Computing - HiPC 2006 - 13th International Conference Proceedings
Pages	375-386
Number of pages	12
DOIs	https://doi.org/10.1007/11945918_38
Publication status	Published - 2006
Event	13th International Conference on High Performance Computing, HiPC 2006 - Bangalore, India Duration: 2006 Dec 18 → 2006 Dec 21

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4297 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	13th International Conference on High Performance Computing, HiPC 2006
Country/Territory	India
City	Bangalore
Period	06/12/18 → 06/12/21

Keywords

Cryptology
Load balancing
Parallel/cluster computing
RSA key
Sparse matrix

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/11945918_38

Cite this

Hwang, W., & Kim, D. (2006). Load balanced block Lanczos algorithm over GF(2) for factorization of large keys. In High Performance Computing - HiPC 2006 - 13th International Conference Proceedings (pp. 375-386). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4297 LNCS). https://doi.org/10.1007/11945918_38

Load balanced block Lanczos algorithm over GF(2) for factorization of large keys. / Hwang, Wontae; Kim, Dongseung.
High Performance Computing - HiPC 2006 - 13th International Conference Proceedings. 2006. p. 375-386 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4297 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Hwang, W & Kim, D 2006, Load balanced block Lanczos algorithm over GF(2) for factorization of large keys. in High Performance Computing - HiPC 2006 - 13th International Conference Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4297 LNCS, pp. 375-386, 13th International Conference on High Performance Computing, HiPC 2006, Bangalore, India, 06/12/18. https://doi.org/10.1007/11945918_38

@inproceedings{5ba3386dfa2b4d8fa71319a7f8cef45b,

title = "Load balanced block Lanczos algorithm over GF(2) for factorization of large keys",

abstract = "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.",

keywords = "Cryptology, Load balancing, Parallel/cluster computing, RSA key, Sparse matrix",

author = "Wontae Hwang and Dongseung Kim",

year = "2006",

doi = "10.1007/11945918_38",

language = "English",

isbn = "354068039X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "375--386",

booktitle = "High Performance Computing - HiPC 2006 - 13th International Conference Proceedings",

note = "13th International Conference on High Performance Computing, HiPC 2006 ; Conference date: 18-12-2006 Through 21-12-2006",

}

TY - GEN

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

AU - Hwang, Wontae

AU - Kim, Dongseung

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

KW - Cryptology

KW - Load balancing

KW - Parallel/cluster computing

KW - RSA key

KW - Sparse matrix

UR - http://www.scopus.com/inward/record.url?scp=77049087568&partnerID=8YFLogxK

U2 - 10.1007/11945918_38

DO - 10.1007/11945918_38

M3 - Conference contribution

AN - SCOPUS:77049087568

SN - 354068039X

SN - 9783540680390

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 375

EP - 386

BT - High Performance Computing - HiPC 2006 - 13th International Conference Proceedings

T2 - 13th International Conference on High Performance Computing, HiPC 2006

Y2 - 18 December 2006 through 21 December 2006

ER -

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

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this