(1 + i) - ary GCD Computation inZ[ i ]as an Analogue to the Binary GCD Algorithm |
| |
Affiliation: | Institut für Informatik II, Universität Bonn, Römerstraße 164, 53117 Bonn, Germany |
| |
Abstract: | 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(n2) 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(n2) bit operations. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|