Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm
DOI10.1006/JSCO.2002.0533zbMATH Open1010.65024OpenAlexW2026390316MaRDI QIDQ697496FDOQ697496
Authors: Emmanuel Thomé 
Publication date: 17 September 2002
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/inria-00103417/file/jsc.pdf
Recommendations
- Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm
- A block Wiedemann rank algorithm
- Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
- scientific article; zbMATH DE number 1253961
- scientific article; zbMATH DE number 503196
complexity reductionWiedemann algorithmfast Fourier transformationlinear generator for matrix sequences
Complexity and performance of numerical algorithms (65Y20) Numerical computation of solutions to systems of equations (65H10) Numerical methods for discrete and fast Fourier transforms (65T50)
Cites Work
- On the computational power of pushdown automata
- An algorithm for solving the discrete log problem on hyperelliptic curves
- Asymptotically fast solution of Toeplitz and related systems of linear equations
- Title not available (Why is that?)
- Solving sparse linear equations over finite fields
- Solving Homogeneous Linear Equations Over GF(2) via Block Wiedemann Algorithm
- Modern computer algebra
- Distributed matrix-free solution of large sparse linear systems over finite fields
- Title not available (Why is that?)
- A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
- Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
- Fast evaluation of logarithms in fields of characteristic two
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Solving linear equations over GF(2): Block Lanczos algorithm
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm
- Fast algorithms for rational Hermite approximation and solution of Toeplitz systems
- Recursive Evaluation of Padé Approximants for Matrix Sequences
- Title not available (Why is that?)
- Title not available (Why is that?)
- Reduction of Huge, Sparse Matrices over Finite Fields Via Created Catastrophes
Cited In (16)
- Online order basis algorithm and its impact on the block Wiedemann algorithm
- Accelerating Iterative SpMV for the Discrete Logarithm Problem Using GPUs
- A double large prime variation for small genus hyperelliptic index calculus
- The hardness of LPN over any integer ring and field for PCG applications
- Faster Multiplication in GF(2)[x]
- Title not available (Why is that?)
- Title not available (Why is that?)
- A block Wiedemann rank algorithm
- Rigorous analysis of a randomised number field sieve
- Polynomial evaluation and interpolation on special sets of points
- A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions
- Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm
- A Kilobit Special Number Field Sieve Factorization
- A connection of series approximations and the basis of the Krylov space in block algorithms of Coppersmith and Montgomery
- Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment
- A Kilobit Hidden SNFS Discrete Logarithm Computation
Uses Software
This page was built for publication: Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q697496)
