×

zbMATH — the first resource for mathematics

\((1+i)\)-ary GCD computation in \(\mathbb Z[i]\) as an analogue to the binary GCD algorithm. (English) Zbl 1053.11093
Summary: We present a novel algorithm for GCD computation over the ring of Gaussian integers \(\mathbb Z[i]\), that is similar to the binary GCD algorithm for \(\mathbb Z\), in which powers of \(1+i\) are extracted. Our algorithm has a running time of \(O(n^2)\) bit operations with a small constant 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 \(\mathbb Z[i]\) or the Caviness-Collins GCD algorithm that both have a running time of \(O(n\cdot\mu (n))\) bit operations, where \(\mu (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) in \(\mathbb Z[i]\) which achieves a running time of \(O(n^2)\) bit operations.

MSC:
11Y16 Number-theoretic algorithms; complexity
68W40 Analysis of algorithms
Software:
CALYPSO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bach, E.; Shallit, J., Algorithmic number theory, volume I: efficient algorithms, (1996), MIT Press Cambridge, MA, USA
[2] Brent, R.P., Analysis of the binary Euclidean algorithm, (), 321-355
[3] Buhler, J.P., ed., Proceedings of the third international algorithmic number theory symposium ANTS III (Reed college, Portland, oregon, USA, June 21-25, 1998), (1998), Springer-Verlag Berlin · Zbl 0891.00022
[4] Caviness, B.F., A Lehmer-type greatest common divisor algorithm for Gaussian integers, SIAM rev., 15, 414, (1973)
[5] Caviness, B.F.; Collins, G.E., Algorithms for Gaussian integer arithmetic, (), 36-45 · Zbl 0465.12008
[6] Cesari, G., Parallel implementation of schönhage’s integer GCD algorithm. in buhler (1998), ed., (1998), p. 64-76 · Zbl 0918.11064
[7] Heath, T.L., The thirteen books of euclid’s elements, (1956), Cambridge University Press New York · Zbl 0071.24203
[8] Ireland, K.; Rosen, M., A classical introduction to modern number theory, (1990), Springer-Verlag Berlin · Zbl 0712.11001
[9] Jebelean, T., A generalization of the binary GCD algorithm, (), 111-116 · Zbl 0921.11074
[10] Jebelean, T., Comparing several GCD algorithms, (), 180-185
[11] Kaltofen, E.; Rolletschek, H., Arithmetic in quadratic fields with unique factorization, (), 279-288
[12] Kaltofen, E.; Rolletschek, H., Computing greatest common divisors and factorizations in quadratic number fields, Math. comput., 53, 697-720, (1989) · Zbl 0687.12001
[13] Knopfmacher, A.; Knopfmacher, J., The number of steps in the Euclidean algorithm over complex quadratic fields, Bit, 31, 286-292, (1991) · Zbl 0731.11057
[14] Knuth, D.E., Seminumerical algorithms, (1998), Addison-Wesley, Reading MA, USA · Zbl 0895.65001
[15] Lehmer, D.H., Euclid’s algorithm for large numbers, Amer. math. monthly, 45, 227-233, (1938) · Zbl 0018.29204
[16] Neukirch, J., Algebraic number theory, (1999), Springer-Verlag Berlin
[17] Norton, G.H., Extending the binary GCD algorithm, (), 363-372 · Zbl 0614.68033
[18] Norton, G.H., A shift-remainder GCD algorithm, (), 350-356
[19] Rolletschek, H., The euclidean algorithm for Gaussian integers, (), 12-23
[20] Rolletschek, H., On the number of divisions of the euclidean algorithm applied to Gaussian integers, J. symb. comput., 2, 261-291, (1986) · Zbl 0609.12001
[21] Rolletschek, H., Shortest division chains in imaginary quadratic number fields, (), 231-243
[22] Rolletschek, H., Shortest division chains in imaginary quadratic number fields, J. symb. comput., 9, 321-354, (1990) · Zbl 0764.11053
[23] Schönhage, A., Schnelle berechnung von kettenbruchentwicklungen, Acta inform., 1, 139-144, (1971) · Zbl 0223.68008
[24] A. Schönhage
[25] Schönhage, A.; Grotefeld, A.F.W.; Vetter, E., Fast algorithms—A multitape Turing machine implementation, (1994), BI Wissenschaftsverlag Mannheim, Germany · Zbl 0853.68108
[26] Schönhage, A.; Strassen, V., Schnelle multiplikation großer zahlen, Computing, 7, 281-292, (1971) · Zbl 0223.68007
[27] J. Sorenson, 1990, University of Wisconsin, Madison
[28] Sorenson, J., Two fast GCD algorithms, J. algorithms, 16, 110-144, (1994) · Zbl 0815.11065
[29] Stein, J., Computational problems associated with racah algebra, J. comput. phys., 1, 397-405, (1967) · Zbl 0168.15503
[30] Vallée, B., The complete analysis of the binary Euclidean algorithm. in buhler (1998), ed., (1998), p. 77-94 · Zbl 0908.11063
[31] Weber, K., The accelerated integer GCD algorithm, ACM trans. math. software, 21, 111-122, (1995) · Zbl 0883.11055
[32] Weber, K., Parallel implementation of the accelerated integer GCD algorithm, J. symb. comput., 21, 457-466, (1996) · Zbl 0865.68053
[33] A. Weilert, Z, i
[34] Weilert, A., Asymptotically fast GCD computation inZ[ i ], (), 595-613 · Zbl 1032.11063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.