Precise Analyses of the Right- and Left-Shift Greatest Common Divisor Algorithms for $GF(q)[x]$

DOI10.1137/0218042zbMath0677.68052OpenAlexW2061604308MaRDI QIDQ3833621

Graham H. Norton

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0218042

zbMATH Keywords

greatest common divisorfinite fieldpolynomial

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) General field theory (12E99)

Related Items (4)

Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field ⋮ Relatively prime polynomials and nonsingular Hankel matrices over finite fields ⋮ Fine costs for Euclid's algorithm on polynomials and Farey maps ⋮ Computing GCD's by normalized division

This page was built for publication: Precise Analyses of the Right- and Left-Shift Greatest Common Divisor Algorithms for $GF(q)[x]$