3 * GCD using Euclidean algorithm. */
6 * GiNaC Copyright (C) 1999-2022 Johannes Gutenberg University Mainz, Germany
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23 #ifndef GINAC_GCD_EUCLID_H
24 #define GINAC_GCD_EUCLID_H
27 #include "remainder.h"
28 #include "normalize.h"
35 gcd_euclid(umodpoly& c, umodpoly /* passed by value */ a, umodpoly b)
45 bug_on(a[0].ring()->modulus != b[0].ring()->modulus,
48 normalize_in_field(a);
49 normalize_in_field(b);
50 if (degree(a) < degree(b))
54 while (b.size() != 0) {
55 remainder_in_field(r, a, b);
59 normalize_in_field(a);
66 #endif // ndef GINAC_GCD_EUCLID_H