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
Type de document :
Chapitre d'ouvrage
Topics in Computational Number Theory inspired by Peter L. Montgomery, Cambridge University Press, 2016
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

Contributeur : Emmanuel Thomé <>
Soumis le : jeudi 24 mars 2016 - 15:21:29
Dernière modification le : jeudi 22 septembre 2016 - 14:31:08
Document(s) archivé(s) le : samedi 25 juin 2016 - 14:12:38


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01293351, version 1
  • ARXIV : 1604.02277



Emmanuel Thomé. A modified block Lanczos algorithm with fewer vectors. Topics in Computational Number Theory inspired by Peter L. Montgomery, Cambridge University Press, 2016. 〈hal-01293351〉



Consultations de
la notice


Téléchargements du document