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

We present a novel algorithm for GCD computation over the ring of Gaussian integersZi ], that is similar to the binary GCD algorithm forZ, in which powers of 1  + i are extracted. Our algorithm has a running time of O(n²) bit operations with a small constant hidden in the O -notation if the two input numbers have a length ofO (n) bits. This is noticeably faster than a least remainder version of the Euclidean algorithm inZ i ] or the Caviness–Collins GCD algorithm that both have a running time ofO (n·μ(n)) bit operations, whereμ (n) denotes a good upper bound for the multiplication time of n -bit integers. Our new GCD algorithm is also faster by a constant factor than a Lehmer-type GCD algorithm (i.e. in every Euclidean step a small remainder is calculated, but this remainder need not to be a least remainder) inZ i ] which achieves a running time of O(n²) bit operations.