Geodesic
An extended Jebelean--Weber--Sedjelmaci GCD algorithm
Čebyševskij sbornik, Tome 19 (2018) no. 2, pp. 421-431.

Voir la notice de l'article provenant de la source Math-Net.Ru

There are large number of different algorithms for gcd computation. First of all, it is the Shonhage type gcd algorithms. They are used for very large numbers and have the best asymptotic complexity in the worst case — $ O (n \log ^ 2 (n) \log (\log (n))) $. For lesser numbers, generalized binary algorithms are used. They are based on the $ k $ -ary reduction: $ \alpha \gcd (u, v) = \gcd (v, \frac{| au \pm bv |} {k}) $, integers $ u> v> 0 $, $ \gcd (u, k) = \gcd (v, k) = 1 $, $ \alpha \geqslant 1 $. We use $+$ or $-$ depending on the type of gcd algorithm. The main task is to select the coefficients $ a, b $ such that $ au + bv = 0 \bmod k $. The number $ k $ is usually chosen as a prime number or a power of a prime number. Unfortunately, spirious factors can accumulate during the computation, so $ \alpha \geqslant 1 $. If $ k = 2 ^ s $, then we obtain generalized binary algorithms. It's five times faster than the binary gcd algorithm. Sedjelmaci modified the Jebelean-Weber's algorithm, he removed spirious factors. Asymptotic complexity of the algorithm in the worst case is $ O (n ^ 2 / \log (n)) $. Bezout Coefficients is a representation of gcd $ d $ of the numbers $ A, B $ of a linear combination $ Ax + By = d $, where $ x $ and $ y $ are integer numbers, called Bezout coefficients. In this paper we introduce the extended Jebelean–Weber–Sedjelmaci algorithm of two natural numbers, formulas and give examples that showing how to calculate inverse elements.
Keywords: GCD, Euclidean gcd, binary gcd, k-ary gcd, Schönhage gcd, Weber gcd, Lehmer gcd. 
@article{CHEB_2018_19_2_a29,
     author = {D. A. Dolgov},
     title = {An extended {Jebelean--Weber--Sedjelmaci} {GCD} algorithm},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {421--431},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2018_19_2_a29/}
}
TY  - JOUR
AU  - D. A. Dolgov
TI  - An extended Jebelean--Weber--Sedjelmaci GCD algorithm
JO  - Čebyševskij sbornik
PY  - 2018
SP  - 421
EP  - 431
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2018_19_2_a29/
LA  - ru
ID  - CHEB_2018_19_2_a29
ER  - 
%0 Journal Article
%A D. A. Dolgov
%T An extended Jebelean--Weber--Sedjelmaci GCD algorithm
%J Čebyševskij sbornik
%D 2018
%P 421-431
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2018_19_2_a29/
%G ru
%F CHEB_2018_19_2_a29
D. A. Dolgov. An extended Jebelean--Weber--Sedjelmaci GCD algorithm. Čebyševskij sbornik, Tome 19 (2018) no. 2, pp. 421-431. http://geodesic.mathdoc.fr/item/CHEB_2018_19_2_a29/

[1] D. H. Lehmer, “Euclid's algorithm for large numbers”, American Mathematical Monthly, 45:4 (1938), 227–233 | DOI | MR

[2] A. Schönhage, “Schnelle Berechnung von Kettenbruchentwicklungen”, Acta Informat., 1:2 (1971), 139-144 | DOI | Zbl

[3] R. D. Crandall, C. Pomerance, Prime Numbers, Springer-Verlag, New York, 2005, 597 pp. | MR | Zbl

[4] J. Stein, “Computational problems associated with Racah algebra”, J. Comp. Phys., 1:3 (1967), 397–405 | DOI | Zbl

[5] D. E. Knuth, The Art of Computer Programming: Seminumerical Algorithms, v. 2, 3 edition, Addison-Wesley Professional, 1997, 784 pp. | MR

[6] J. Sorenson, “An Analysis of Lehmer's Euclidean GCD Algorithm”, Proc. of the International Symposium on Symbolic and Algebraic Computation, 1995, 254–258 | Zbl

[7] G. Cesari, “Parallel implementation of Schönhage's integer GCD algorithm”, Algorithmic Number Theory, ANTS 1998, Lecture Notes in Computer Science, 1423, 1998, 64–76 | DOI | MR | Zbl

[8] D. Stehle, P. Zimmermann, “A Binary Recursive Gcd Algorithm”, Algorithmic Number Theory, ANTS 2004, Lecture Notes in Computer Science, 3076, 2004, 411–425 | DOI | MR | Zbl

[9] J. Sorenson, The $k$-ary gcd algorithm, Comp. Sciences Tech. Rep., No 979, Univ. of Wisconsin-Madison, 1990, 20 pp.

[10] J. Sorenson, “Two Fast GCD Algorithms”, J. of Algorithms, 16:1 (1994), 110–144 | DOI | MR | Zbl

[11] D. Dolgov, “Polynomial GCD as a solution of system of linear equations”, Lobachevskii J. Math., 39:7 (2018) | DOI | MR | Zbl

[12] D. Dolgov, “GCD calculation in the search task of pseudoprime and strong pseudoprime numbers”, Lobachevskii J. Math., 37:6 (2016), 734–739 | DOI | MR | Zbl

[13] L. Weber, “The Accelerated Integer GCD Algorithm”, ACM Trans. Math. Software, 21:1 (1995), 111–122 | DOI | MR | Zbl

[14] S. M. Sedjelmaci, “Jebelean-Weber's algorithm without spurious factors”, Information Processing Letters, 102:6 (2007), 247–252 | DOI | MR | Zbl

[15] P. Zimmermann, 50 largest factors found by ECM, https://members.loria.fr/PZimmermann/records/top50.html

[16] Yu. L. Sagalovich, Vvedenie v algebraicheskie kody, IPPI RAN, 2011, 302 pp.

[17] S. T. Ishmukhametov, B. G. Mubarakov, K. M. Al-Anni, “Calculation of Bezout's Coefficients for the k-Ary Algorithm of Finding GCD”, Russ Math., 61:11 (2017), 26–33 | DOI | MR | Zbl

[18] Bassalygo L. A., Zinoviev V. A., “Remark on balanced incomplete block designs, near-resolvable block designs, and $q$-ary constant-weight codes”, Problems of Information Transmission, 53:1 (2017), 51–54 | DOI | MR | Zbl

[19] Bespalov E. A., Krotov D. S., “MDS codes in Doob graphs”, Problems of Information Transmission, 53:2 (2017), 136–154 | DOI | MR | Zbl