Welcome to the resource topic for 2006/163
Title:
Achieving a log(n) Speed Up for Boolean Matrix Operations and Calculating the Complexity of the Dense Linear Algebra step of Algebraic Stream Cipher Attacks and of Integer Factorization Methods
Authors: Gregory V. Bard
Abstract:The purpose of this paper is to calculate the running time of dense boolean matrix operations,
as used in stream cipher cryptanalysis and integer factorization. Several variations of Gaussian
Elimination, Strassen’s Algorithm and the Method of Four Russians are analyzed. In particular,
we demonstrate that Strassen’s Algorithm is actually slower than the Four Russians algorithm for
matrices of the sizes encountered in these problems. To accomplish this, we introduce a new model
for tabulating the running time, tracking matrix reads and writes rather than field operations, and
retaining the coefficients rather than dropping them. Furthermore, we introduce an algorithm known
heretofore only orally, a ``Modified Method of Four Russians’', which has not appeared in the literature
before. This algorithm is \log n times faster than Gaussian Elimination for dense boolean
matrices. Finally we list rough estimates for the running time of several recent stream cipher cryptanalysis
attacks.
ePrint: https://eprint.iacr.org/2006/163
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .