HomeIssuesImplementing main steps of Wiedemann — Coppersmith algorithm for binary systems of linear equations on clusters

Implementing main steps of Wiedemann — Coppersmith algorithm for binary systems of linear equations on clusters | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 4(22).

This paper concerns implementation of the main steps of block Wiede-mann's algorithm for solving systems of linear equations. Effective implementation of particular operations is provided. Specific problems of implementing the algorithm for running on clusters are studied.
Download file
Counter downloads: 190
  • Title Implementing main steps of Wiedemann — Coppersmith algorithm for binary systems of linear equations on clusters
  • Headline Implementing main steps of Wiedemann — Coppersmith algorithm for binary systems of linear equations on clusters
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 4(22)
  • Date:
  • DOI
Keywords
системы линейных уравнений, алгоритм Видемана — Коп-персмита, systems of linear equations, Wiedemann — Coppersmith's algorithm
Authors
References
www.open-mpi.org/doc/v1.6 — Open MPI v1.6.4 documentation. 2013.
CavallarS. Strategies for filtering in the number field sieve // Proc. ANTS IV. LNCS. 2000. V. 1838. P. 209-231.
Ахо А., Хопкрофт Д., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 с.
Thome E. Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm // J. Symb. Comput. 2002. No. 33. P. 757-775.
Рыжов А. С. О реализации алгоритма Копперсмита для двоичных матричных последовательностей на вычислителях кластерного типа // Прикладная дискретная математика. 2013. №3. С. 112-122.
Wiedemann D. H. Solving sparse linear equations over finite fields // IEEE Trans. Inform. Theory. 1986. V.IT-32(1). P. 54-62.
Kleinjung T., Aoki K., Franke J., et al. Factorization of a 768-bit RSA modulus // CRYPTO- 2010. LNCS. 2010. V.6223. P. 333-350.
Montgomery P. L. A block Lanczos algorithm for finding dependencies over GF(2) // EUROCRYPT'95. LNCS. 1995. V.921. P. 106-120.
Coppersmith D. Solving linear equations over GF(2) via block Wiedemann algorithm // Math. Comp. 1994. V. 62(205). P. 333-350.
Coppersmith D. Fast evaluation of logarithms in fields of characteristic two // IEEE Trans. Inform. Theory. 1984. V.IT-30(4). P. 587-594.
Implementing main steps of Wiedemann — Coppersmith algorithm for binary systems of linear equations on clusters | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 4(22).
Implementing main steps of Wiedemann — Coppersmith algorithm for binary systems of linear equations on clusters | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 4(22).
Download full-text version
Counter downloads: 340
Download file