This paper concerns implementation of Coppersmith algorithm, which allows to calculate vector generating polynomials. Data representation for binary matrix sequences is considered. Effective parallelization for mul-ticore CPUs and clusters provided.
Download file
Counter downloads: 95
- Title Implementing Coppersmith algorithm for binary matrix sequences on clusters
- Headline Implementing Coppersmith algorithm for binary matrix sequences on clusters
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(21)
- Date:
- DOI
Keywords
matrix sequences, Coppersmith algorithm, матричные последовательности, алгоритм КопперсмитаAuthors
References
Coppersmith D. Fast evaluation of logarithms in fields of characteristic two // IEEE Trans. Inform. Theory. 1984. V.IT-30(4). P. 587-594.
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. No. 62(205). P. 333-350.
Wiedemann D. H. Solving sparse linear equations over finite fields // IEEE Trans. Inform. Theory. 1986. V.IT-32(1). P. 54-62.
Thome E. Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm // J. Symbolic Comput. 2002. No. 33. P. 757-775.
Ахо А., Хопкрофт Д., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 с.
Beckerman B. and Labahn G. A uniform approach for the fast computation of matrix-type Pade approximants // SIAM J. Matrix Anal. Appl. 1994. No. 15(3). P. 804-823.
Implementing Coppersmith algorithm for binary matrix sequences on clusters | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 3(21).
Download full-text version
Download fileCounter downloads: 319