Precise Analyses of the Right- and Left-Shift Greatest Common Divisor Algorithms for $GF(q)[x]$
G.H. Norton · SIAM Journal on Computing · 1989
The precise average and worst-case running times of the right- and left-shift gcd algorithms for $GF(q)[x]$ are derived. A new approximate integer model for the binary greatest common divisor algorithm is obtained. The right-shift polynomial worst case differs markedly for $q = 2$ and $q > 2$. The method also yields an easy analysis of the Euclidean algorithm.