A shift and cut GCD algorithm. (English) Zbl 0847.11064
This paper presents the shift and cut GCD algorithm, which requires \(O(n^2/\log n)\) bit operations to compute the GCD of two \(n\)-bit integers. This new algorithm is similar in spirit to the left-shift \(k\)-ary GCD algorithm of the reviewer [J. Algorithms 16, 110-144 (1994; Zbl 0815.11065)]. The authors show how their algorithm generalizes to compute polynomial GCDs, although this adapted algorithm requires a quadratic number of coefficient ring operations.
Reviewer: J.Sorenson (Indianapolis)
MSC:
11Y16 | Number-theoretic algorithms; complexity |
68W30 | Symbolic computation and algebraic computation |
11A05 | Multiplicative structure; Euclidean algorithm; greatest common divisors |