Modification of the Coppersmith algorithm for matrix multiplication over GF(2)

Abstract

In recent years, increasingly requires the use of algorithms that work effectively with machine words and such that the main work can be done in the processor cache, that is, the time to data overwrite less. It is important to note that the size of the released processor cache in modern computers is growing rapidly. In this paper, we propose a new modification of the Coppersmith algorithm for multiplying block vectors whose width is equal to the length of the machine word, on each other and on square matrices. We consider the case when the coefficients lie in a field with two elements. These algorithms are among the block algorithms in which operations are performed with machine words, that is, with each of the 64 bits in parallel. Our results can be applied to Boolean matrices without significant changes. Since these algorithms are of the algorithms with pre-calculations, these estimates are of practical interest when using processors with an increased size of the memory cache of the first level. The algorithms considered in this article give an increase in speed in proportion to the logarithm of the first level cache volume. For use in tasks where these matrix operations are basic (for example, the integer factorization), this can be significant.