tailieunhanh - Parallelization of the Lanczos Algorithm on Multi-Core Platforms

In this paper, we report our parallel implementations of the Lanczos sparse linear system solving algorithm over large prime fields, on a multi-core platform. We employ several load-balancing methods suited to these platforms. | Parallelization of the Lanczos Algorithm on Multi-Core Platforms Souvik Bhattacherjee and Abhijit Das Department of Computer Science Engineering Indian Institute of Technology Kharagpur India 721302 souvikb abhij @ Abstract. In this paper we report our parallel implementations of the Lanczos sparse linear system solving algorithm over large prime fields on a multi-core platform. We employ several load-balancing methods suited to these platforms. We have carried out process-level and threadlevel parallel implementations under two different arithmetic libraries and the best speedup obtained is on eight cores. To the best of our knowledge no implementation of the Lanczos algorithm on a multi-core platform is ever reported in the literature. Moreover we seem to have achieved significantly larger speedup compared to all previously reported implementations of this algorithm. Key words sparse linear system Lanczos algorithm modular arithmetic prime field multi-core machine parallelization load balancing 1 Introduction The discrete logarithm problem over finite fields serves as the basis of several cryptographic primitives. For example the Diffie-Hellman key-agreement protocol the ElGamal public-key cryptosystem and the digital signature algorithm DSA 1 rely on the difficulty of solving the discrete logarithm problem for their security. The fastest known algorithms for solving the discrete logarithm problem require the solution of large sparse linear systems over finite rings. As the size of the system of equations increases standard Gaussian elimination becomes impractical. Some alternative methods prove to be computationally more attractive than Gaussian elimination particularly for large and sparse linear systems. Efficient implementations of these iterative system solvers are quite challenging and the linear-algebra phase often turns out to be the practical bottleneck in the context of solving the discrete logarithm problem. The Lanczos method .

crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.