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

VL - 428

SP - 1135

EP - 1150

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

IS - 4

ER -