Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm
From MaRDI portal
Publication:697496
DOI10.1006/jsco.2002.0533zbMath1010.65024OpenAlexW2026390316MaRDI QIDQ697496
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
fast Fourier transformationcomplexity reductionWiedemann algorithmlinear generator for matrix sequences
Numerical computation of solutions to systems of equations (65H10) Numerical methods for discrete and fast Fourier transforms (65T50) Complexity and performance of numerical algorithms (65Y20)
Related Items
Polynomial evaluation and interpolation on special sets of points ⋮ A connection of series approximations and the basis of the Krylov space in block algorithms of Coppersmith and Montgomery ⋮ Accelerating Iterative SpMV for the Discrete Logarithm Problem Using GPUs ⋮ A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions ⋮ A Kilobit Special Number Field Sieve Factorization ⋮ Faster Multiplication in GF(2)[x] ⋮ Rigorous analysis of a randomised number field sieve ⋮ A Kilobit Hidden SNFS Discrete Logarithm Computation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A double large prime variation for small genus hyperelliptic index calculus ⋮ Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Distributed matrix-free solution of large sparse linear systems over finite fields
- Asymptotically fast solution of Toeplitz and related systems of linear equations
- Solving linear equations over GF(2): Block Lanczos algorithm
- On the computational power of pushdown automata
- 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
- Fast evaluation of logarithms in fields of characteristic two
- Solving sparse linear equations over finite fields
- Solving Homogeneous Linear Equations Over GF(2) via Block Wiedemann Algorithm
- 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
- Reduction of Huge, Sparse Matrices over Finite Fields Via Created Catastrophes
