Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm

DOI10.1006/jsco.2002.0533zbMath1010.65024OpenAlexW2026390316MaRDI QIDQ697496

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

zbMATH Keywords

fast Fourier transformationcomplexity reductionWiedemann algorithmlinear generator for matrix sequences

Mathematics Subject Classification ID

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

• gmp

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