New techniques for the computation of linear recurrence coefficients

DOI10.1006/ffta.1999.0267zbMath0978.65130OpenAlexW2043768406MaRDI QIDQ1971066

Pan, Victor Y.

Publication date: 21 January 2002

Published in: Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/ffta.1999.0267

zbMATH Keywords

power sumsBerlekamp-Massey linear recurrence problemsparse matrices over finite fieldssparse multivariate polynomial interpolation

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Complexity and performance of numerical algorithms (65Y20)

Related Items

Algebraic diagonals and walks: algorithms, bounds, complexity, Deterministic root finding over finite fields using Graeffe transforms, A LINEAR COMPLEXITY ANALYSIS OF QUADRATIC RESIDUES AND PRIMITIVE ROOTS SPACINGS, Fast computation of special resultants, The Berlekamp-Massey algorithm revisited, On Elkies subgroups of \(\ell\)-torsion points in elliptic curves defined over a finite field, Block diagonalization and LU-equivalence of Hankel matrices, Symbolic and numeric methods for exploiting structure in constructing resultant matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On fast multiplication of polynomials over arbitrary algebras
• A probabilistic remark on algebraic program testing
• Parallel computation of polynomial GCD and some related parallel computations over abstract fields
• Representations and Parallel Computations for Rational Functions
• Solving sparse linear equations over finite fields
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• A method for solving key equation for decoding goppa codes
• Continued Fractions and Linear Recurrences
• The algebraic decoding of Goppa codes
• Fast computation of GCDs
• Minimal torsion spaces and the partial input/output problem
• A method for decoding of generalized Goppa codes (Corresp.)
• On the complexity of decoding Goppa codes (Corresp.)
• Fast parallel computation of characteristic polynomials by Leverrier's power sum method adapted to fields of finite characteristic
• Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
• Shift-register synthesis and BCH decoding
• The Padé Table and Its Relation to Certain Algorithms of Numerical Analysis