F2 Lanczos revisited

Michael Peterson; Chris Monico

doi:10.1016/j.laa.2007.09.016

F₂ Lanczos revisited

Michael Peterson, Chris Monico

Mathematics and Statistics

Research output: Contribution to journal › Article › peer-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 F₂. 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 W_i 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 W_i satisfy W_i^T W_j = 0 for i ≠ j as opposed to W_i^T AW_j = 0 in [6].

Original language	English
Pages (from-to)	1135-1150
Number of pages	16
Journal	Linear Algebra and Its Applications
Volume	428
Issue number	4
DOIs	https://doi.org/10.1016/j.laa.2007.09.016
State	Published - Feb 1 2008

Keywords

Finite field
Kernel
Lanczos

Access to Document

10.1016/j.laa.2007.09.016

Cite this

@article{22a9cda2710247bbb3833980e94c8120,

title = "F2 Lanczos revisited",

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].",

keywords = "Finite field, Kernel, Lanczos",

author = "Michael Peterson and Chris Monico",

note = "Funding Information: This research was partially supported by a grant from the Texas Tech University Research Enhancement Fund (REF). We are also grateful to the anonymous referee for pointing out the duality in Section 9, as well as providing other constructive feedback.",

year = "2008",

month = feb,

day = "1",

doi = "10.1016/j.laa.2007.09.016",

language = "English",

volume = "428",

pages = "1135--1150",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

number = "4",

}

TY - JOUR

T1 - F2 Lanczos revisited

AU - Peterson, Michael

AU - Monico, Chris

N1 - Funding Information: This research was partially supported by a grant from the Texas Tech University Research Enhancement Fund (REF). We are also grateful to the anonymous referee for pointing out the duality in Section 9, as well as providing other constructive feedback.

PY - 2008/2/1

Y1 - 2008/2/1

N2 - 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].

AB - 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].

KW - Finite field

KW - Kernel

KW - Lanczos

UR - http://www.scopus.com/inward/record.url?scp=37249072282&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2007.09.016

DO - 10.1016/j.laa.2007.09.016

M3 - Article

AN - SCOPUS:37249072282

SN - 0024-3795

VL - 428

SP - 1135

EP - 1150

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

IS - 4

ER -

F₂ Lanczos revisited

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this