Skip to Main content Skip to Navigation
New interface
Book sections

A modified block Lanczos algorithm with fewer vectors

Emmanuel Thomé 1 
1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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. 1 Linear systems for integer factoring For factoring a composite integer N , algorithms based on the technique of combination of congruences look for several pairs of integers (x, y) such that x 2 ≡ y 2 mod N. This equality is hoped to be non trivial for at least one of the obtained pairs, letting gcd(x − y, N) unveil a factor of the integer N. Several algorithms use this strategy: the CFRAC algorithm, the quadratic sieve and its variants, and the number field sieve. Pairs (x, y) as above are obtained by combining relations which have been collected as a step of these algorithms. Relations are written multiplicatively as a set of valuations. All the algorithms considered seek a multiplicative combination of these relations which can be rewritten as an equality of squares. This is achieved by solving a system of linear equations defined over F 2 , where equations are parity constraints on
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Emmanuel Thomé Connect in order to contact the contributor
Submitted on : Thursday, March 24, 2016 - 3:21:29 PM
Last modification on : Friday, February 4, 2022 - 3:32:56 AM
Long-term archiving on: : Saturday, June 25, 2016 - 2:12:38 PM


Files produced by the author(s)




Emmanuel Thomé. A modified block Lanczos algorithm with fewer vectors. Joppe W. Bos; Arjen K. Lenstra. Topics in Computational Number Theory inspired by Peter L. Montgomery, Cambridge University Press, pp.175-188, 2017, 978-1-107-10935-3. ⟨10.1017/9781316271575.008⟩. ⟨hal-01293351⟩



Record views


Files downloads