  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 $\not\equiv$ 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
