Paper 2016/329

A modified block Lanczos algorithm with fewer vectors

Emmanuel Thomé

Abstract

The block Lanczos algorithm proposed by Peter Montgomery is an efficient means to tackle the sparse linear algebra problem which arises in the context of the number field sieve factoring algorithm and its predecessors. We present here a modified version of the algorithm, which incorporates several improvements: we discuss how to efficiently handle homogeneous systems and how to reduce the number of vectors stored in the course of the computation. We also provide heuristic justification for the success probability of our modified algorithm. While the overall complexity and expected number of steps of the block Lanczos is not changed by the modifications presented in this article, we expect these to be useful for implementations of the block Lanczos algorithm where the storage of auxiliary vectors sometimes has a non-negligible cost.

Note: This article is based on work by the author contributed as chapter~7 in {Topics in Computational Number Theory inspired by Peter L. Montgomery}, by Joppe W. Bos and Arjen K. Lenstra, to be published by Cambdridge University Press.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Topics in Computational Number Theory inspired by Peter L. Montgomery
Contact author(s)
Emmanuel Thome @ inria fr
History
2016-03-25: received
Short URL
https://ia.cr/2016/329
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/329,
      author = {Emmanuel Thomé},
      title = {A modified block Lanczos algorithm with fewer vectors},
      howpublished = {Cryptology ePrint Archive, Paper 2016/329},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/329}},
      url = {https://eprint.iacr.org/2016/329}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.