2020-01-25T17:26:54Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000896772020-01-24T01:21:59Z06164:06165:07006:07054
A Parallel GNFS Algorithm with Reliable Look Ahead Block Lanczos for Integer FactorizationA Parallel GNFS Algorithm with Reliable Look Ahead Block Lanczos for Integer Factorizationengマルチメディア通信と分散処理ワークショップhttp://id.nii.ac.jp/1001/00089660/Conference Paperhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=89677&item_no=1&attribute_id=1&file_no=1Copyright (c) 2005 by the Information Processing Society of JapanInnovative Parallell Distributed ComputingSt. Francis Xavier UniversityLi, XuLaurenceT.YangMan, LinRSA is a very popular and secure public key cryptosystem, but the security relies on the difficulty of factoring large integers. The General Number Field Sieve (GNFS) algorithm is currently the best known method for factoring large integers over 110 digits. Our previous work on the parallel GNFS algorithm, which integrated the Montgomery's block Lanczos [13] algorithm to solve the large and sparse linear systems over GF(2), is less reliable. In this paper, we successfully implemented the parallel General Number Field Sieve (GNFS) algorithm and integrated with a new algorithm for solving large and sparse linear system called lookahead block Lanczos algorithm [6]. This new algorithm is based on the look-ahead technique, which can provide more reliability. The algorithm can find more dependencies than Montgomery's block Lanczos method using less iterations. The detailed experimental results on a SUN cluster will be presented as well.RSA is a very popular and secure public key cryptosystem, but the security relies on the difficulty of factoring large integers. The General Number Field Sieve (GNFS) algorithm is currently the best known method for factoring large integers over 110 digits. Our previous work on the parallel GNFS algorithm, which integrated the Montgomery's block Lanczos [13] algorithm to solve the large and sparse linear systems over GF(2), is less reliable. In this paper, we successfully implemented the parallel General Number Field Sieve (GNFS) algorithm and integrated with a new algorithm for solving large and sparse linear system called lookahead block Lanczos algorithm [6]. This new algorithm is based on the look-ahead technique, which can provide more reliability. The algorithm can find more dependencies than Montgomery's block Lanczos method using less iterations. The detailed experimental results on a SUN cluster will be presented as well.ISSN 1344-0640マルチメディア通信と分散処理 ワークショップ論文集2005192452502005-11-232013-01-24