+/** @file pgcd.cpp
+ *
+ * GCD for polynomials in prime field. */
+
+/*
+ * GiNaC Copyright (C) 1999-2010 Johannes Gutenberg University Mainz, Germany
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
#include "pgcd.h"
#include "collect_vargs.h"
#include "smod_helpers.h"
#include "newton_interpolate.h"
#include "divide_in_z_p.h"
-namespace GiNaC
-{
+namespace GiNaC {
extern void
primpart_content(ex& pp, ex& c, ex e, const exvector& vars, const long p);
const ex lc_gcd = euclid_gcd(AL, BL, mainvar, p);
// The estimate of degree of the gcd of Ab and Bb
- int gcd_deg = std::min(degree(Aprim, mainvar), degree(Bprim, mainvar));
+ exp_vector_t gcd_deg = std::min(degree_vector(Aprim, restvars),
+ degree_vector(Bprim, restvars));
eval_point_finder::value_type b;
eval_point_finder find_eval_point(p);
const cln::cl_I correct_lc = smod(lcb_gcd*recip(Cblc, p), p);
Cb = (Cb*numeric(correct_lc)).smod(pn);
+ const exp_vector_t img_gcd_deg = degree_vector(Cb, restvars);
+ // Test for relatively prime polynomials
+ if (zerop(img_gcd_deg))
+ return cont_gcd;
// Test for unlucky homomorphisms
- const int img_gcd_deg = Cb.degree(restvars.back());
if (img_gcd_deg < gcd_deg) {
// The degree decreased, previous homomorphisms were
// bad, so we have to start it all over.
const ex H_lcoeff = lcoeff_wrt(H, restvars);
if (H_lcoeff.is_equal(lc_gcd)) {
- if ((Hprev-H).expand().smod(pn).is_zero())
- continue;
ex C /* primitive part of H */, contH /* dummy */;
primpart_content(C, contH, H, vars, p);
// Normalize GCD so that leading coefficient is 1
if (divide_in_z_p(Aprim, C, dummy1, vars, p) &&
divide_in_z_p(Bprim, C, dummy2, vars, p))
return (cont_gcd*C).expand().smod(pn);
- else if (img_gcd_deg == 0)
- return cont_gcd;
// else continue building the candidate
}
} while(true);
}
} // namespace GiNaC
-