Analysis of Euclidean algorithms for polynomials over finite fields

DOI10.1016/S0747-7171(08)80021-1MaRDI QIDQ912620zbMATH OpenFDO

Authors Keju Ma, Joachim von zur Gathen

Publication date 1990

Published in Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

factor shift Euclidean algorithmindeterminate shift Euclidean algorithmsubtractive indeterminate shift algorithmsubtractive linear factor shift algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polynomials over finite fields (11T06)

Recommendations

• Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field
• Precise Analyses of the Right- and Left-Shift Greatest Common Divisor Algorithms for $GF(q)[x]$
• The exact length of the Euclidean algorithm in [ X ]
• Analysis of generalized continued fraction algorithms over polynomials
• scientific article; zbMATH DE number 1670838

Cites work

• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 3481857 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 3581610 (Why is no real title available?)
• scientific article; zbMATH DE number 3336026 (Why is no real title available?)
• A New Algorithm for Factoring Polynomials Over Finite Fields
• A characterization of parenthesis languages
• Computational problems associated with Racah algebra
• Euclid's Algorithm for Large Numbers
• Factoring Polynomials Over Large Finite Fields
• Fast computation of GCDs
• Fast computation of continued fraction expansions.
• Fast parallel matrix and GCD computations
• On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
• On Euclid's Algorithm and the Theory of Subresultants
• Parallel Algorithms for Algebraic Problems
• Probabilistic Algorithms in Finite Fields
• Representations and Parallel Computations for Rational Functions
• Subresultants and Reduced Polynomial Remainder Sequences
• The Computational Complexity of Continued Fractions
• The Computing Time of the Euclidean Algorithm
• The number of steps in the Euclidean algorithm

Cited in

(15)

• On those multiplicative subgroups of \({\mathbb F}_{2^n}^\ast\) which are Sidon sets and/or sum-free sets
• Precise Analyses of the Right- and Left-Shift Greatest Common Divisor Algorithms for $GF(q)[x]$
• Subresultants in multiple roots: an extremal case
• scientific article; zbMATH DE number 15442 (Why is no real title available?)
• Analysis of generalized continued fraction algorithms over polynomials
• The polynomial Euclidean algorithm and the linear equation \(AX + BY = \gcd(A, B)\)
• Dynamics of the binary Euclidean algorithm: Functional analysis and operators
• The exact length of the Euclidean algorithm in [ X ]
• Probabilistic analyses of the plain multiple gcd algorithm
• Relatively prime polynomials and nonsingular Hankel matrices over finite fields
• Fine costs for Euclid's algorithm on polynomials and Farey maps
• Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field
• Computing GCD's by normalized division
• scientific article; zbMATH DE number 1504691 (Why is no real title available?)
• Numerical stability of Euclidean algorithm over ultrametric fields

This page was built for publication: Analysis of Euclidean algorithms for polynomials over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q912620)