(1+I)-ary GCD Computation in Z[i] as an Analogue to the Binary GCD Algorithm

摘要

We present a novel algorithm for GCD computation over the ring of Gaussian integers Z[i], that is similar to the binary GCD algorithm for Z, in which powers of 1+I are extracted. Our algorithm has a running time of O(n~2) bit operations with a small con- stant hidden in the O-notation if the two input numbers have a length of O(n) bits. This is noticeably faster than a least remainder version of the Euclidean algorithm in Z[i] or the Caviness-Collins GCD algorithm that both have a running time of O(n.μ(n)) bit operations, where μ(n) denotes a good upper bound for the multiplication time of n-bit integers.