## Abstract

We present a new variant of the block Lanczos algorithm for finding vectors in the kernel of a symmetric matrix over F_{2}. 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 | |

State | Published - Feb 1 2008 |

## Keywords

- Finite field
- Kernel
- Lanczos

## Fingerprint

Dive into the research topics of 'F_{2}Lanczos revisited'. Together they form a unique fingerprint.