My Project
Loading...
Searching...
No Matches
Functions
cfGcdUtil.h File Reference

coprimality check and change of representation mod n More...

Go to the source code of this file.

Functions

bool gcd_test_one (const CanonicalForm &f, const CanonicalForm &g, bool swap, int &d)
 Coprimality Check. f and g are assumed to have the same level. If swap is true, the main variables of f and g are swapped with Variable(1). If the result is false, d is set to the degree of the gcd of f and g evaluated at a random point in K^n-1. This gcd is a gcd of univariate polynomials. More...
 
CanonicalForm balance_p (const CanonicalForm &f, const CanonicalForm &q, const CanonicalForm &qh)
 same as balance_p ( const CanonicalForm & f, const CanonicalForm & q ) but qh= q/2 is provided, too. More...
 
CanonicalForm balance_p (const CanonicalForm &f, const CanonicalForm &q)
 static CanonicalForm balance_p ( const CanonicalForm & f, const CanonicalForm & q ) More...
 

Detailed Description

coprimality check and change of representation mod n

Definition in file cfGcdUtil.h.

Function Documentation

◆ balance_p() [1/2]

CanonicalForm balance_p ( const CanonicalForm f,
const CanonicalForm q 
)

static CanonicalForm balance_p ( const CanonicalForm & f, const CanonicalForm & q )

balance_p() - map f from positive to symmetric representation mod q.

This makes sense for polynomials over Z only. q should be an integer.

Definition at line 290 of file cfGcdUtil.cc.

291{
292 CanonicalForm qh = q / 2;
293 return balance_p (f, q, qh);
294}
CanonicalForm balance_p(const CanonicalForm &f, const CanonicalForm &q, const CanonicalForm &qh)
same as balance_p ( const CanonicalForm & f, const CanonicalForm & q ) but qh= q/2 is provided,...
Definition: cfGcdUtil.cc:258
FILE * f
Definition: checklibs.c:9
factory's main class
Definition: canonicalform.h:86

◆ balance_p() [2/2]

CanonicalForm balance_p ( const CanonicalForm f,
const CanonicalForm q,
const CanonicalForm qh 
)

same as balance_p ( const CanonicalForm & f, const CanonicalForm & q ) but qh= q/2 is provided, too.

Definition at line 258 of file cfGcdUtil.cc.

259{
260 Variable x = f.mvar();
264 for ( i = f; i.hasTerms(); i++ )
265 {
266 c = i.coeff();
267 if ( c.inCoeffDomain())
268 {
269 if ( c > qh )
270 result += power( x, i.exp() ) * (c - q);
271 else
272 result += power( x, i.exp() ) * c;
273 }
274 else
275 result += power( x, i.exp() ) * balance_p(c,q,qh);
276 }
277 return result;
278}
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int i
Definition: cfEzgcd.cc:132
Variable x
Definition: cfModGcd.cc:4082
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
bool inCoeffDomain() const
factory's class for variables
Definition: variable.h:33
return result
Definition: facAbsBiFact.cc:75

◆ gcd_test_one()

bool gcd_test_one ( const CanonicalForm f,
const CanonicalForm g,
bool  swap,
int &  d 
)

Coprimality Check. f and g are assumed to have the same level. If swap is true, the main variables of f and g are swapped with Variable(1). If the result is false, d is set to the degree of the gcd of f and g evaluated at a random point in K^n-1. This gcd is a gcd of univariate polynomials.

Definition at line 25 of file cfGcdUtil.cc.

26{
27 d= 0;
28 int count = 0;
29 // assume polys have same level;
30
31 Variable v= Variable (1);
32 bool algExtension= (hasFirstAlgVar (f, v) || hasFirstAlgVar (g, v));
34 if ( swap )
35 {
36 lcf = swapvar( LC( f ), Variable(1), f.mvar() );
37 lcg = swapvar( LC( g ), Variable(1), f.mvar() );
38 }
39 else
40 {
41 lcf = LC( f, Variable(1) );
42 lcg = LC( g, Variable(1) );
43 }
44
46 if ( swap )
47 {
48 F=swapvar( f, Variable(1), f.mvar() );
49 G=swapvar( g, Variable(1), g.mvar() );
50 }
51 else
52 {
53 F = f;
54 G = g;
55 }
56
57 #define TEST_ONE_MAX 50
58 int p= getCharacteristic();
59 bool passToGF= false;
60 int k= 1;
61 bool extOfExt= false;
62 Variable v3;
63 if (p > 0 && p < TEST_ONE_MAX && CFFactory::gettype() != GaloisFieldDomain && !algExtension)
64 {
65 if (p == 2)
66 setCharacteristic (2, 6, 'Z');
67 else if (p == 3)
68 setCharacteristic (3, 4, 'Z');
69 else if (p == 5 || p == 7)
70 setCharacteristic (p, 3, 'Z');
71 else
72 setCharacteristic (p, 2, 'Z');
73 passToGF= true;
74 }
76 {
77 k= getGFDegree();
78 if (ipower (p, 2*k) > TEST_ONE_MAX)
80 else
82 F= GFMapUp (F, k);
83 G= GFMapUp (G, k);
84 lcf= GFMapUp (lcf, k);
85 lcg= GFMapUp (lcg, k);
86 }
87 else if (p > 0 && p < TEST_ONE_MAX && algExtension)
88 {
89#if defined(HAVE_NTL) || defined(HAVE_FLINT)
90 int d= degree (getMipo (v));
91 CFList source, dest;
92 Variable v2;
93 CanonicalForm primElem, imPrimElem;
94 #if defined(HAVE_NTL) && !defined(HAVE_FLINT)
95 if (fac_NTL_char != p)
96 {
98 zz_p::init (p);
99 }
100 #endif
101 if (p == 2 && d < 6)
102 {
103 bool primFail= false;
104 Variable vBuf;
105 primElem= primitiveElement (v, vBuf, primFail);
106 ASSERT (!primFail, "failure in integer factorizer");
107 if (d < 3)
108 {
109 #ifdef HAVE_FLINT
110 nmod_poly_t Irredpoly;
111 nmod_poly_init(Irredpoly,p);
112 nmod_poly_randtest_monic_irreducible(Irredpoly, FLINTrandom, 3*d+1);
113 CanonicalForm newMipo=convertnmod_poly_t2FacCF(Irredpoly,Variable(1));
114 nmod_poly_clear(Irredpoly);
115 #elif defined(HAVE_NTL)
116 zz_pX NTLIrredpoly;
117 BuildIrred (NTLIrredpoly, d*3);
118 CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
119 #else
120 factoryError("NTL/FLINT missing:gcd_test_one");
121 #endif
122 v2= rootOf (newMipo);
123 }
124 else
125 {
126 #ifdef HAVE_FLINT
127 nmod_poly_t Irredpoly;
128 nmod_poly_init(Irredpoly,p);
129 nmod_poly_randtest_monic_irreducible(Irredpoly, FLINTrandom, 3*d+1);
130 CanonicalForm newMipo=convertnmod_poly_t2FacCF(Irredpoly,Variable(1));
131 nmod_poly_clear(Irredpoly);
132 #elif defined(HAVE_NTL)
133 zz_pX NTLIrredpoly;
134 BuildIrred (NTLIrredpoly, d*2);
135 CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
136 #else
137 factoryError("NTL/FLINT missing:gcd_test_one");
138 #endif
139 v2= rootOf (newMipo);
140 }
141 imPrimElem= mapPrimElem (primElem, v, v2);
142 extOfExt= true;
143 }
144 else if ((p == 3 && d < 4) || ((p == 5 || p == 7) && d < 3))
145 {
146 bool primFail= false;
147 Variable vBuf;
148 primElem= primitiveElement (v, vBuf, primFail);
149 ASSERT (!primFail, "failure in integer factorizer");
150 #ifdef HAVE_FLINT
151 nmod_poly_t Irredpoly;
152 nmod_poly_init(Irredpoly,p);
153 nmod_poly_randtest_monic_irreducible(Irredpoly, FLINTrandom, 2*d+1);
154 CanonicalForm newMipo=convertnmod_poly_t2FacCF(Irredpoly,Variable(1));
155 nmod_poly_clear(Irredpoly);
156 #elif defined(HAVE_NTL)
157 zz_pX NTLIrredpoly;
158 BuildIrred (NTLIrredpoly, d*2);
159 CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
160 #else
161 factoryError("NTL/FLINT missing:gcd_test_one");
162 #endif
163 v2= rootOf (newMipo);
164 imPrimElem= mapPrimElem (primElem, v, v2);
165 extOfExt= true;
166 }
167 if (extOfExt)
168 {
169 v3= v;
170 F= mapUp (F, v, v2, primElem, imPrimElem, source, dest);
171 G= mapUp (G, v, v2, primElem, imPrimElem, source, dest);
172 lcf= mapUp (lcf, v, v2, primElem, imPrimElem, source, dest);
173 lcg= mapUp (lcg, v, v2, primElem, imPrimElem, source, dest);
174 v= v2;
175 }
176#endif
177 }
178
179 CFRandom * sample;
180 if ((!algExtension && p > 0) || p == 0)
181 sample = CFRandomFactory::generate();
182 else
183 sample = AlgExtRandomF (v).clone();
184
185 REvaluation e( 2, tmax( f.level(), g.level() ), *sample );
186 delete sample;
187
188 if (passToGF)
189 {
190 lcf= lcf.mapinto();
191 lcg= lcg.mapinto();
192 }
193
194 CanonicalForm eval1, eval2;
195 if (passToGF)
196 {
197 eval1= e (lcf);
198 eval2= e (lcg);
199 }
200 else
201 {
202 eval1= e (lcf);
203 eval2= e (lcg);
204 }
205
206 while ( ( eval1.isZero() || eval2.isZero() ) && count < TEST_ONE_MAX )
207 {
208 e.nextpoint();
209 count++;
210 eval1= e (lcf);
211 eval2= e (lcg);
212 }
213 if ( count >= TEST_ONE_MAX )
214 {
215 if (passToGF)
217 if (k > 1)
219 if (extOfExt)
220 prune1 (v3);
221 return false;
222 }
223
224
225 if (passToGF)
226 {
227 F= F.mapinto();
228 G= G.mapinto();
229 eval1= e (F);
230 eval2= e (G);
231 }
232 else
233 {
234 eval1= e (F);
235 eval2= e (G);
236 }
237
238 CanonicalForm c= gcd (eval1, eval2);
239 d= c.degree();
240 bool result= d < 1;
241 if (d < 0)
242 d= 0;
243
244 if (passToGF)
246 if (k > 1)
248 if (extOfExt)
249 prune1 (v3);
250 return result;
251}
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:255
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
#define swap(_i, _j)
int degree(const CanonicalForm &f)
int getGFDegree()
Definition: cf_char.cc:75
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
CanonicalForm LC(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int k
Definition: cfEzgcd.cc:99
#define TEST_ONE_MAX
CanonicalForm lcg
Definition: cfModGcd.cc:4097
int p
Definition: cfModGcd.cc:4078
CanonicalForm lcf
Definition: cfModGcd.cc:4097
g
Definition: cfModGcd.cc:4090
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define GaloisFieldDomain
Definition: cf_defs.h:18
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:450
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
Definition: cf_map_ext.cc:342
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:70
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:240
GLOBAL_VAR flint_rand_t FLINTrandom
Definition: cf_random.cc:25
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
generate random elements in F_p(alpha)
Definition: cf_random.h:70
CFRandom * clone() const
Definition: cf_random.cc:165
static int gettype()
Definition: cf_factory.h:28
static CFRandom * generate()
Definition: cf_random.cc:170
virtual class for random element generation
Definition: cf_random.h:21
CF_NO_INLINE bool isZero() const
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
CanonicalForm mapinto() const
class to generate random evaluation points
Definition: cf_reval.h:26
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
nmod_poly_init(FLINTmipo, getCharacteristic())
nmod_poly_clear(FLINTmipo)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
VAR char gf_name
Definition: gfops.cc:52
STATIC_VAR TreeM * G
Definition: janet.cc:31
int status int void size_t count
Definition: si_signals.h:59
void prune1(const Variable &alpha)
Definition: variable.cc:291
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
int gcd(int a, int b)
Definition: walkSupport.cc:836