F2 Lanczos revisited

Michael Peterson, Chris Monico

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We present a new variant of the block Lanczos algorithm for finding vectors in the kernel of a symmetric matrix over F2. Our algorithm is at least as efficient as that of Montgomery [Peter L. Montgomery, A block Lanczos algorithm for finding dependencies over GF(2). in: Advances in Cryptology-EUROCRYPT'95 (Saint-Malo, 1995), Lecture Notes in Comput. Sci., vol. 921, Springer, Berlin, 1995, pp. 106-120], while the sequence of matrices Wi constructed here have different algebraic properties that may be useful in eventually providing a provable upper bound on the time required to solve this problem. Namely, our Wi satisfy WiT Wj = 0 for i ≠ j as opposed to WiT AWj = 0 in [6].

Original languageEnglish
Pages (from-to)1135-1150
Number of pages16
JournalLinear Algebra and Its Applications
Volume428
Issue number4
DOIs
StatePublished - Feb 1 2008

Keywords

  • Finite field
  • Kernel
  • Lanczos

Fingerprint Dive into the research topics of 'F<sub>2</sub> Lanczos revisited'. Together they form a unique fingerprint.

Cite this