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

М.А. Cherepniov

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.

Full Text:

PDF (Russian)

References


Albrecht, M. R., G. V. Bard, and W. Hart. "Efficient multiplication of dense matrices over GF (2). CoRR abs/0811.1714 (2008)."

Kriptograficheskie protokoly/ Cherepnjov M.A.// Moskva: MAKS Press, 2018.

Montgomery P.L. A Block Lanczos Algorithm for Finding Dependencies over GF(2)// Advances in Cryptology - EuroCrypt'95 / Louis C.Guillou and Jean-Jacques Quisquater, editors. Berlin: Springer-Verlag, Lect. Notes in Comp. Sci.-1995.-v.921- p.106-120.

Coppersmith D. Solving homogeneous linear systems over GF(2) via block Widemann algorithm.// Mathematics of Computation.-1994-v.62-no.205-p.333-350.

Ob jekonomnom postroenii tranzitivnogo zamykanija orientirovannogo grafa./ Arlazarov V.L., Dinic E.A., Kronrod M., Faradzhev I.A.//DAN SSSR.-1970.- t.194-#3-s.487-488.

Powers of tensors and fast matrix multiplication. / Le Gall F.// International Symposium on Symbolic and Algebraic Computation, pp. 296–303 (2014)

Multiplying matrices faster than coppersmith-winograd./ Virginia Vassilevska Williams// Proceedings of the 44th Symposium on Theory of Computing Conference, pp. 887–898 (2012)


Refbacks

  • There are currently no refbacks.


Abava  Absolutech IT-EDU 2019

ISSN: 2307-8162