×

zbMATH — the first resource for mathematics

A block Lanczos algorithm for finding dependencies over GF(2). (English) Zbl 0973.11520
Guillou, Louis C. (ed.) et al., Advances in cryptology - EUROCRYPT ’95. International conference on the theory and application of cryptographic techniques, Saint-Malo, France, May 21-25, 1995. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 921, 106-120 (1995).
Summary: Some integer factorization algorithms require several vectors in the null space of a sparse \(m \times n\) matrix over the field GF(2). We modify the Lanczos algorithm to produce a sequence of orthogonal subspaces of \(\text{GF}(2)^{n}\), each having dimension almost \(N\), where \(N\) is the computer word size, by applying the given matrix and its transpose to \(N\) binary vectors at once. The resulting algorithm takes about \(n/(N - 0.76)\) iterations. It was applied to matrices larger than \(10^{6} \times 10^{6}\) during the factorizations of 105-digit and 119-digit numbers via the general number field sieve.
For the entire collection see [Zbl 0866.00067].

MSC:
11Y16 Number-theoretic algorithms; complexity
94A60 Cryptography
68P25 Data encryption (aspects in computer science)
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
PDF BibTeX XML Cite