1 /** @file eval_point_finder.h
3 * Functions for finding an evaluation point. */
6 * GiNaC Copyright (C) 1999-2024 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_PGCD_EVAL_POINT_FINDER_H
24 #define GINAC_PGCD_EVAL_POINT_FINDER_H
26 #include "operators.h"
32 /// Find a `good' evaluation point b \in Z_p for a pair of multivariate
33 /// polynomials A, B \in Z_p[x_n][x_0, \ldots, x_n]. Here `good' means
34 /// that b is not a root of GCD of contents of A and B. N.B. content
35 /// is univariate polynomial \in Z_p[x_n]
36 struct eval_point_finder
38 typedef long value_type;
40 std::set<value_type> points;
41 const random_modint modint_generator;
42 bool operator()(value_type& b, const ex& g, const ex& x);
43 eval_point_finder(const value_type& p_) : p(p_), modint_generator(p)
47 bool eval_point_finder::operator()(value_type& b, const ex& lc, const ex& x)
49 random_modint modint_generator(p);
50 // Search for a new element of field
51 while (points.size() < p - 1) {
52 value_type b_ = modint_generator();
53 // check if this evaluation point was already used
54 if (points.find(b_) != points.end())
57 // mark found value as used, even if it's a root of lc
58 // (so we don't need to do the check once more)
60 // Now make sure it's NOT the root of GCD's leading coeffient
61 if (lc.subs(x == numeric(b_)).smod(numeric(p)).is_zero())
63 // Nice, it's our next evaluation point
67 // All possible evaluation points were used.
73 #endif // ndef GINAC_PGCD_EVAL_POINT_FINDER_H