کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4944819 1438009 2017 37 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An improved parallel block Lanczos algorithm over GF(2) for integer factorization
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
An improved parallel block Lanczos algorithm over GF(2) for integer factorization
چکیده انگلیسی
RSA algorithm is one of the most popular and secure public key cryptographic algorithms and has been widely used in many real-life applications. The security of the RSA algorithm lies in the difficulty of factoring large integers efficiently and the General Number Field Sieve (GNFS) algorithm is the most efficient algorithm for factoring integers greater than 110 digits at present. In this paper, targeted to speed up the factorization process of RSA, we discuss the current research about solving large and sparse linear systems over GF(2), which is one of the most time-consuming steps of the GNFS algorithm. With that, we propose an improved parallel block Lanczos (IBL) algorithm to reduce the communication cost of solving large and sparse linear systems over GF(2). More specifically, we firstly re-implement the parallel block Lanczos algorithm from the BSP paradigm to Open MPI. To further improve the performance, we then reorganize and redesign the algorithm to reduce the synchronization and communication costs during the outer product step. After this, we integrate the improved parallel block Lanczos algorithm with the GNFS algorithm. Finally, theoretical and experimental results demonstrate that the IBL algorithm greatly enhances the performance of GNFS compared with previous parallel block Lanczos (PBL) algorithm, in terms of both execution time and speedup.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 379, 10 February 2017, Pages 257-273
نویسندگان
, , , , ,