The Universal Block Lanczos–Padé Method for Linear Systems Over Large Prime Fields

Abstract

In this paper, we propose a universal algorithm designed for solving large sparse linear systems over finite fields with a large prime number of elements. Such systems arise in the solution of the discrete logarithm problem modulo a prime number. The algorithm has been developed for parallel computing systems with various parallel architectures and properties. The new method inherits the structural properties of the Lanczos method. However, it provides flexible control over the complexity of parallel computations and the intensity of exchanges.