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

This file provides functions for squarefrees factorizing over $ F_{p} $ , $ F_{p}(\alpha ) $ or GF. More...

#include "cf_assert.h"
#include "cf_factory.h"
#include "fac_sqrfree.h"

Go to the source code of this file.

Functions

CFFList squarefreeFactorization (const CanonicalForm &F, const Variable &alpha)
 squarefree factorization over a finite field return a list of squarefree factors with multiplicity More...
 
CFFList FpSqrf (const CanonicalForm &F, bool sort=true)
 squarefree factorization over $ F_{p} $. If input is not monic, the leading coefficient is dropped More...
 
CFFList FqSqrf (const CanonicalForm &F, const Variable &alpha, bool sort=true)
 squarefree factorization over $ F_{p}(\alpha ) $. If input is not monic, the leading coefficient is dropped More...
 
CFFList GFSqrf (const CanonicalForm &F, bool sort=true)
 squarefree factorization over GF. If input is not monic, the leading coefficient is dropped More...
 
CanonicalForm sqrfPart (const CanonicalForm &F, CanonicalForm &pthPower, const Variable &alpha)
 squarefree part of F/g, where g is the product of those squarefree factors whose multiplicity is 0 mod p, if F a pth power pthPower= F. More...
 
CanonicalForm maxpthRoot (const CanonicalForm &F, int q, int &l)
 p^l-th root extraction, where l is maximal More...
 

Detailed Description

This file provides functions for squarefrees factorizing over $ F_{p} $ , $ F_{p}(\alpha ) $ or GF.

Author
Martin Lee

Definition in file facFqSquarefree.h.

Function Documentation

◆ FpSqrf()

CFFList FpSqrf ( const CanonicalForm F,
bool  sort = true 
)
inline

squarefree factorization over $ F_{p} $. If input is not monic, the leading coefficient is dropped

Returns
a list of squarefree factors with multiplicity
Parameters
[in]Fa poly
[in]sortsort factors by exponent?

Definition at line 38 of file facFqSquarefree.h.

41{
42 Variable a= 1;
43 int n= F.level();
44 CanonicalForm cont, bufF= F;
45 CFFList bufResult;
46
48 for (int i= n; i >= 1; i++)
49 {
50 cont= content (bufF, i);
51 bufResult= squarefreeFactorization (cont, a);
52 if (bufResult.getFirst().factor().inCoeffDomain())
53 bufResult.removeFirst();
54 result= Union (result, bufResult);
55 bufF /= cont;
56 if (bufF.inCoeffDomain())
57 break;
58 }
59 if (!bufF.inCoeffDomain())
60 {
61 bufResult= squarefreeFactorization (bufF, a);
62 if (bufResult.getFirst().factor().inCoeffDomain())
63 bufResult.removeFirst();
64 result= Union (result, bufResult);
65 }
66 if (sort)
68 result.insert (CFFactor (Lc(F), 1));
69 return result;
70}
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
CanonicalForm Lc(const CanonicalForm &f)
int i
Definition: cfEzgcd.cc:132
static void sort(int **points, int sizePoints)
factory's main class
Definition: canonicalform.h:86
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
factory's class for variables
Definition: variable.h:33
return result
Definition: facAbsBiFact.cc:75
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity
CFFList sortCFFList(CFFList &F)
Definition: fac_sqrfree.cc:25
template List< Variable > Union(const List< Variable > &, const List< Variable > &)

◆ FqSqrf()

CFFList FqSqrf ( const CanonicalForm F,
const Variable alpha,
bool  sort = true 
)
inline

squarefree factorization over $ F_{p}(\alpha ) $. If input is not monic, the leading coefficient is dropped

Returns
a list of squarefree factors with multiplicity
Parameters
[in]Fa poly
[in]alphaalgebraic variable
[in]sortsort factors by exponent?

Definition at line 77 of file facFqSquarefree.h.

81{
82 int n= F.level();
83 CanonicalForm cont, bufF= F;
84 CFFList bufResult;
85
87 for (int i= n; i >= 1; i++)
88 {
89 cont= content (bufF, i);
90 bufResult= squarefreeFactorization (cont, alpha);
91 if (bufResult.getFirst().factor().inCoeffDomain())
92 bufResult.removeFirst();
93 result= Union (result, bufResult);
94 bufF /= cont;
95 if (bufF.inCoeffDomain())
96 break;
97 }
98 if (!bufF.inCoeffDomain())
99 {
100 bufResult= squarefreeFactorization (bufF, alpha);
101 if (bufResult.getFirst().factor().inCoeffDomain())
102 bufResult.removeFirst();
103 result= Union (result, bufResult);
104 }
105 if (sort)
107 result.insert (CFFactor (Lc(F), 1));
108 return result;
109}
Variable alpha
Definition: facAbsBiFact.cc:51

◆ GFSqrf()

CFFList GFSqrf ( const CanonicalForm F,
bool  sort = true 
)
inline

squarefree factorization over GF. If input is not monic, the leading coefficient is dropped

Returns
a list of squarefree factors with multiplicity
Parameters
[in]Fa poly
[in]sortsort factors by exponent?

Definition at line 116 of file facFqSquarefree.h.

119{
121 "GF as base field expected");
122 return FpSqrf (F, sort);
123}
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define GaloisFieldDomain
Definition: cf_defs.h:18
static int gettype()
Definition: cf_factory.h:28
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped

◆ maxpthRoot()

CanonicalForm maxpthRoot ( const CanonicalForm F,
int  q,
int &  l 
)

p^l-th root extraction, where l is maximal

Returns
maxpthRoot returns a p^l-th root of F, where l is maximal
See also
pthRoot()
Parameters
[in]Fa poly which is a pth power
[in]qsize of the field
[in,out]ll maximal, s.t. F is a p^l-th power

Definition at line 127 of file facFqSquarefree.cc.

128{
130 bool derivZero= true;
131 l= 0;
132 while (derivZero)
133 {
134 for (int i= 1; i <= result.level(); i++)
135 {
136 if (!deriv (result, Variable (i)).isZero())
137 {
138 derivZero= false;
139 break;
140 }
141 }
142 if (!derivZero)
143 break;
144 result= pthRoot (result, q);
145 l++;
146 }
147 return result;
148}
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
int l
Definition: cfEzgcd.cc:100
static CanonicalForm pthRoot(const CanonicalForm &F, int q)
bool isZero(const CFArray &A)
checks if entries of A are zero

◆ sqrfPart()

CanonicalForm sqrfPart ( const CanonicalForm F,
CanonicalForm pthPower,
const Variable alpha 
)

squarefree part of F/g, where g is the product of those squarefree factors whose multiplicity is 0 mod p, if F a pth power pthPower= F.

Returns
sqrfPart returns 1, if F is a pthPower, else it returns the squarefree part of F/g, where g is the product of those squarefree factors whose multiplicity is 0 mod p
Parameters
[in]Fa poly
[in,out]pthPowerreturns F is F is a pthPower
[in]alphaalgebraic variable

Definition at line 303 of file facFqSquarefree.cc.

305{
306 if (F.inCoeffDomain())
307 {
308 pthPower= 1;
309 return F;
310 }
311 CFMap M;
313 Variable vBuf= alpha;
314 CanonicalForm w, v, b;
315 pthPower= 1;
317 int i= 1;
318 bool allZero= true;
319 for (; i <= A.level(); i++)
320 {
321 if (!deriv (A, Variable (i)).isZero())
322 {
323 allZero= false;
324 break;
325 }
326 }
327 if (allZero)
328 {
329 pthPower= F;
330 return 1;
331 }
332 w= gcd (A, deriv (A, Variable (i)));
333
334 b= A/w;
335 result= b;
336 if (degree (w) < 1)
337 return M (result);
338 i++;
339 for (; i <= A.level(); i++)
340 {
341 if (!deriv (w, Variable (i)).isZero())
342 {
343 b= w;
344 w= gcd (w, deriv (w, Variable (i)));
345 b /= w;
346 if (degree (b) < 1)
347 break;
349 g= gcd (b, result);
350 if (degree (g) > 0)
351 result *= b/g;
352 if (degree (g) <= 0)
353 result *= b;
354 }
355 }
356 result= M (result);
357 return result;
358}
int degree(const CanonicalForm &f)
g
Definition: cfModGcd.cc:4090
CanonicalForm b
Definition: cfModGcd.cc:4103
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
class CFMap
Definition: cf_map.h:85
const CanonicalForm & w
Definition: facAbsFact.cc:51
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
bool allZero
Definition: facFactorize.cc:56
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ squarefreeFactorization()

CFFList squarefreeFactorization ( const CanonicalForm F,
const Variable alpha 
)

squarefree factorization over a finite field return a list of squarefree factors with multiplicity

Parameters
[in]Fa poly
[in]alphaeither an algebraic variable, i.e. we are over some F_p (alpha) or a variable of level 1, i.e. we are F_p or GF

Definition at line 181 of file facFqSquarefree.cc.

182{
183 int p= getCharacteristic();
184 CanonicalForm A= F;
185 CFMap M;
186 A= compress (A, M);
187 Variable x= A.mvar();
188 int l= x.level();
189 int k;
191 k= getGFDegree();
192 else if (alpha.level() != 1)
193 k= degree (getMipo (alpha));
194 else
195 k= 1;
197 CanonicalForm tmp;
198
200 bool found;
201 for (int i= l; i > 0; i--)
202 {
203 buf= Variable (i);
204 if (degree (deriv (A, buf)) >= 0)
205 {
206 tmp1= sqrfPosDer (A, buf, tmp);
207 A= tmp;
208 for (CFFListIterator j= tmp1; j.hasItem(); j++)
209 {
210 found= false;
212 if (!k.hasItem() && !j.getItem().factor().inCoeffDomain()) tmp2.append (j.getItem());
213 else
214 {
215 for (; k.hasItem(); k++)
216 {
217 if (k.getItem().exp() == j.getItem().exp())
218 {
219 k.getItem()= CFFactor (k.getItem().factor()*j.getItem().factor(),
220 j.getItem().exp());
221 found= true;
222 }
223 }
224 if (found == false && !j.getItem().factor().inCoeffDomain())
225 tmp2.append(j.getItem());
226 }
227 }
228 }
229 }
230
231 bool degcheck= false;;
232 for (int i= l; i > 0; i--)
233 if (degree (A, Variable(i)) >= p)
234 degcheck= true;
235
236 if (degcheck == false && tmp1.isEmpty() && tmp2.isEmpty())
237 return CFFList (CFFactor (F/Lc(F), 1));
238
239 CanonicalForm buffer;
240#if defined(HAVE_NTL) || (HAVE_FLINT && __FLINT_RELEASE >= 20400)
241 if (alpha.level() == 1)
242#endif
243 buffer= pthRoot (A, ipower (p, k));
244#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
245 else
246 {
247 fmpz_t qq;
248 fmpz_init_set_ui (qq, p);
249 fmpz_pow_ui (qq, qq, k);
250 buffer= pthRoot (A, qq, alpha);
251 fmpz_clear (qq);
252 }
253#elif defined(HAVE_NTL)
254 else
255 {
256 ZZ q;
257 power (q, p, k);
258 buffer= pthRoot (A, q, alpha);
259 }
260#else
261 factoryError("NTL/FLINT missing: squarefreeFactorization");
262#endif
263
265
267 buf= alpha;
268 for (CFFListIterator i= tmp2; i.hasItem(); i++)
269 {
270 for (CFFListIterator j= tmp1; j.hasItem(); j++)
271 {
272 tmp= gcd (i.getItem().factor(), j.getItem().factor());
273 i.getItem()= CFFactor (i.getItem().factor()/tmp, i.getItem().exp());
274 j.getItem()= CFFactor (j.getItem().factor()/tmp, j.getItem().exp());
275 if (!tmp.inCoeffDomain())
276 {
277 tmp= M (tmp);
278 result.append (CFFactor (tmp/Lc(tmp),
279 j.getItem().exp()*p + i.getItem().exp()));
280 }
281 }
282 }
283 for (CFFListIterator i= tmp2; i.hasItem(); i++)
284 {
285 if (!i.getItem().factor().inCoeffDomain())
286 {
287 tmp= M (i.getItem().factor());
288 result.append (CFFactor (tmp/Lc(tmp), i.getItem().exp()));
289 }
290 }
291 for (CFFListIterator j= tmp1; j.hasItem(); j++)
292 {
293 if (!j.getItem().factor().inCoeffDomain())
294 {
295 tmp= M (j.getItem().factor());
296 result.append (CFFactor (tmp/Lc(tmp), j.getItem().exp()*p));
297 }
298 }
299 return result;
300}
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int getGFDegree()
Definition: cf_char.cc:75
List< CFFactor > CFFList
Factor< CanonicalForm > CFFactor
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
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
void append(const T &)
Definition: ftmpl_list.cc:256
int isEmpty() const
Definition: ftmpl_list.cc:267
int level() const
Definition: variable.h:49
bool found
Definition: facFactorize.cc:55
CFList tmp1
Definition: facFqBivar.cc:72
CanonicalForm buf2
Definition: facFqBivar.cc:73
CFList tmp2
Definition: facFqBivar.cc:72
static CFFList sqrfPosDer(const CanonicalForm &F, const Variable &x, CanonicalForm &c)
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity
int j
Definition: facHensel.cc:110
int status int void * buf
Definition: si_signals.h:59
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207