GPU Acceleration of Dense Matrix and Block Operations for Lanczos Method for Systems Over GF(2)

Abstract

The algebraic operations with the dense matrices and blocks are bounding the scalability of block Lanczos–Montgomery method, that is used for the linear part in the RSA decomposition problem. This paper explores the possibility of implementation of the following algebraic operations over field \(\mathbb{F}_2\) on GPU: (1) multiplication of two 64k × 64k matrices; (2) multiplication of two N × 64k blocks. For matrix multiplication, we consider two algorithms: (a) the “naive” algorithm; (b) the “fast” algorithm by 4 Russians. For block multiplication, we consider just the “naive” algorithm. It seems that by now this is the only work where BLAS acceleration over \(\mathbb{F}_2\) are relatively successful accelerated on GPU.