Loading...
Searching...
No Matches
facFqBivarUtil.h File Reference

This file provides utility functions for bivariate factorization. More...

`#include "cf_map.h"`
`#include "ExtensionInfo.h"`
`#include "NTLconvert.h"`
`#include "FLINTconvert.h"`

Go to the source code of this file.

## Functions

void | append (CFList &factors1, const CFList &factors2)
| append factors2 on factors1
void | decompress (CFList &factors, const CFMap &N)
| decompress a list of polys factors using the map N
void | decompress (CFFList &factors, const CFMap &N)
| as above
void | decompress (CFAFList &factors, const CFMap &N)
| as above
void | appendSwapDecompress (CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
| first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and finally decompress factors1
void | swapDecompress (CFList &factors, const bool swap, const CFMap &N)
| swap Variables in factors, then decompress factors
bool | isInExtension (const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
| tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case)
CanonicalForm | mapDown (const CanonicalForm &F, const ExtensionInfo &info, CFList &source, CFList &dest)
| map a poly into a subfield of the current field, no testing is performed!
void | appendTestMapDown (CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
| test if g is in a subfield of the current field, if so map it down and append it to factors
void | appendMapDown (CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
| map g down into a subfield of the current field and append it to factors
void | normalize (CFList &factors)
| normalize factors, i.e. make factors monic
void | normalize (CFFList &factors)
| as above
CFList | subset (int index[], const int &s, const CFArray &elements, bool &noSubset)
| extract a subset given by index of size s from elements, if there is no subset we have not yet considered noSubset is set to true. index encodes the next subset, e.g. if s= 3, elements= {a,b,c,d}, index= {1, 2, 4, 0}, then subset= {a,c,d}. index is of size elements.size().
CFArray | copy (const CFList &list)
| write elements of list into an array
void | indexUpdate (int index[], const int &subsetSize, const int &setSize, bool &noSubset)
| update index
int | subsetDegree (const CFList &S)
| compute the sum of degrees in Variable(1) of elements in S
CFFList | multiplicity (CanonicalForm &F, const CFList &factors)
| determine multiplicity of the factors
CFArray | logarithmicDerivative (const CanonicalForm &F, const CanonicalForm &G, int l, CanonicalForm &Q)
| compute the coefficients of the logarithmic derivative of G mod Variable (2)^l over Fq
CFArray | logarithmicDerivative (const CanonicalForm &F, const CanonicalForm &G, int l, int oldL, const CanonicalForm &oldQ, CanonicalForm &Q)
| compute the coefficients of the logarithmic derivative of G mod Variable (2)^l over Fq with oldQ= F/G mod Variable (2)^oldL
int * | computeBounds (const CanonicalForm &F, int &n, bool &isIrreducible)
| compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij, J. Klüners, and A. Steel, Factoring polynomials over global fields
int * | computeBoundsWrtDiffMainvar (const CanonicalForm &F, int &n, bool &isIrreducible)
| as above just wrt to the other variable
CFArray | getCoeffs (const CanonicalForm &F, const int k)
| extract coefficients of for where is a variable of level 1
CFArray | getCoeffs (const CanonicalForm &F, const int k, const Variable &alpha)
| extract coefficients of for where is a variable of level 1
CFArray | getCoeffs (const CanonicalForm &F, const int k, const int l, const int degMipo, const Variable &alpha, const CanonicalForm &evaluation, const mat_zz_p &M)
| extract coefficients of for where is a variable of level 1
CFArray | getCoeffs (const CanonicalForm &F, const int k, const int l, const int degMipo, const Variable &alpha, const CanonicalForm &evaluation, const nmod_mat_t M)
| extract coefficients of for where is a variable of level 1
void | writeInMatrix (CFMatrix &M, const CFArray &A, const int column, const int startIndex)
| write A into M starting at row startIndex
int | substituteCheck (const CFList &L)
| checks if a substitution x^n->x is possible
void | subst (const CanonicalForm &F, CanonicalForm &A, const int d, const Variable &x)
| substitute x^d by x in F
CanonicalForm | reverseSubst (const CanonicalForm &F, const int d, const Variable &x)
| reverse a substitution x^d->x
void | reverseSubst (CFList &L, const int d, const Variable &x)
| reverse a substitution x^d->x
int | substituteCheck (const CanonicalForm &F, const Variable &x)
| check if a substitution x^n->x is possible

## Detailed Description

This file provides utility functions for bivariate factorization.

Author
  Martin Lee

Definition in file facFqBivarUtil.h.

## Function Documentation

## append()

void append | ( | CFList & | factors1,
|  | const CFList & | factors2 )

append factors2 on factors1

Parameters

  [in,out] | factors1 | a list of polys
  [in] | factors2 | a list of polys

## appendMapDown()

void appendMapDown | ( | CFList & | factors,
|  | const CanonicalForm & | g,
|  | const ExtensionInfo & | info,
|  | CFList & | source,
|  | CFList & | dest )

map g down into a subfield of the current field and append it to factors

See also
  mapDown(), appendTestMapDown()

Parameters

  [in,out] | factors | a list of polys
  [in] | g | a poly
  [in] | info | information about extension
  [in,out] | source |

See also
  mapDown()

Parameters

  [in,out] | dest |

See also
  mapDown()

Definition at line 267 of file facFqBivarUtil.cc.

{
int k= info.getGFDegree();
Variable beta= info.getBeta();
Variable alpha= info.getAlpha();
CanonicalForm gamma= info.getGamma();
CanonicalForm delta= info.getDelta();
if (k > 1)
factors.append (GFMapDown (g, k));
else if (k == 1)
factors.append (g);
else if (!k && beta == Variable (1))
factors.append (g);
else if (!k && beta != Variable (1))
factors.append (mapDown (g, delta, gamma, alpha, source, dest));
return;
}
k
int k
Definition cfEzgcd.cc:99
g
g
Definition cfModGcd.cc:4098
GFMapDown
CanonicalForm GFMapDown(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:277
mapDown
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
Definition cf_map_ext.cc:124
CanonicalForm
factory's main class
Definition canonicalform.h:86
List::append
void append(const T &)
Definition ftmpl_list.cc:256
Variable
factory's class for variables
Definition factory.h:127
alpha
Variable alpha
Definition facAbsBiFact.cc:52
beta
Variable beta
Definition facAbsFact.cc:95
info
#define info
Definition libparse.cc:1256
CxxTest::delta
bool delta(X x, Y y, D d)
Definition TestSuite.h:160

## appendSwapDecompress()

void appendSwapDecompress | ( | CFList & | factors1,
|  | const CFList & | factors2,
|  | const CFList & | factors3,
|  | const bool | swap1,
|  | const bool | swap2,
|  | const CFMap & | N )

first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and finally decompress factors1

Parameters

  [in,out] | factors1 | a list of polys
  [in] | factors2 | a list of polys
  [in] | factors3 | a list of polys
  [in] | swap1 | indicates the need to swap
  [in] | swap2 | indicates the need to swap
  [in] | N | a map

Definition at line 70 of file facFqBivarUtil.cc.

{
Variable x= Variable (1);
Variable y= Variable (2);
for (CFListIterator i= factors1; i.hasItem(); i++)
{
if (swap1)
{
if (!swap2)
i.getItem()= swapvar (i.getItem(), x, y);
}
else
{
if (swap2)
i.getItem()= swapvar (i.getItem(), y, x);
}
i.getItem()= N (i.getItem());
}
for (CFListIterator i= factors2; i.hasItem(); i++)
factors1.append (N (i.getItem()));
for (CFListIterator i= factors3; i.hasItem(); i++)
factors1.append (N (i.getItem()));
return;
}
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
i
int i
Definition cfEzgcd.cc:132
x
Variable x
Definition cfModGcd.cc:4090
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
factors2
const CFList & factors2
Definition facFqBivarUtil.cc:42

## appendTestMapDown()

void appendTestMapDown | ( | CFList & | factors,
|  | const CanonicalForm & | f,
|  | const ExtensionInfo & | info,
|  | CFList & | source,
|  | CFList & | dest )

test if g is in a subfield of the current field, if so map it down and append it to factors

See also
  mapDown(), isInExtension()

Parameters

  [in,out] | factors | a list of polys
  [in] | f | a poly
  [in] | info | information about extension
  [in,out] | source |

See also
  mapDown()

Parameters

  [in,out] | dest |

See also
  mapDown()

Definition at line 223 of file facFqBivarUtil.cc.

{
int k= info.getGFDegree();
Variable beta= info.getBeta();
Variable alpha= info.getAlpha();
CanonicalForm delta= info.getDelta();
CanonicalForm gamma= info.getGamma();
CanonicalForm g= f;
int degMipoBeta=0;
if (!k && beta.level() == 1)
degMipoBeta= 1;
else if (!k && beta.level() != 1)
degMipoBeta= degree (getMipo (beta));
if (k > 1)
{
if (!isInExtension (g, gamma, k, delta, source, dest))
{
g= GFMapDown (g, k);
factors.append (g);
}
}
else if (k == 1)
{
if (!isInExtension (g, gamma, k, delta, source, dest))
factors.append (g);
}
else if (!k && beta == Variable (1))
{
if (degree (g, alpha) < degMipoBeta)
factors.append (g);
}
else if (!k && beta != Variable (1))
{
if (!isInExtension (g, gamma, k, delta, source, dest))
{
g= mapDown (g, delta, gamma, alpha, source, dest);
factors.append (g);
}
}
return;
}
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
f
FILE * f
Definition checklibs.c:9
mapDown
CanonicalForm mapDown(const CanonicalForm &F, const ExtensionInfo &info, CFList &source, CFList &dest)
map a poly into a subfield of the current field, no testing is performed!
Definition facFqBivarUtil.cc:206
isInExtension
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case)
Definition facFqBivarUtil.cc:184
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207

## computeBounds()

int * computeBounds | ( | const CanonicalForm & | F,
|  | int & | n,
|  | bool & | isIrreducible )

compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij, J. Klüners, and A. Steel, Factoring polynomials over global fields

Returns
  computeBounds returns bounds as described above

Parameters

  [in] | F | compressed bivariate polynomial
  [in,out] | n | length of output
  [in,out] | isIrreducible | check if poly is irreducible

Definition at line 768 of file facFqBivarUtil.cc.

{
n= degree (F, 1);
int* result= new int [n];
int sizeOfNewtonPolygon;
int** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
isIrreducible= false;
if (sizeOfNewtonPolygon == 3)
{
bool check1=
(newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
if (check1)
{
bool check2=
(newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
if (check2)
{
int p=getCharacteristic();
int d=1;
char bufGFName='Z';
bool GF= (CFFactory::gettype()==GaloisFieldDomain);
if (GF)
{
d= getGFDegree();
bufGFName=gf_name;
}
setCharacteristic(0);
CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]); // maybe it's better to use plain intgcd
tmp= gcd (tmp, newtonPolyg[1][0]);
tmp= gcd (tmp, newtonPolyg[1][1]);
tmp= gcd (tmp, newtonPolyg[2][0]);
tmp= gcd (tmp, newtonPolyg[2][1]);
isIrreducible= (tmp==1);
if (GF)
setCharacteristic (p, d, bufGFName);
else
setCharacteristic(p);
}
}
}
int minX, minY, maxX, maxY;
minX= newtonPolyg [0] [0];
minY= newtonPolyg [0] [1];
maxX= minX;
maxY= minY;
int indZero= 0;
for (int i= 1; i < sizeOfNewtonPolygon; i++)
{
if (newtonPolyg[i][1] == 0)
{
if (newtonPolyg[indZero][1] == 0)
{
if (newtonPolyg[indZero][0] < newtonPolyg[i][0])
indZero= i;
}
else
indZero= i;
}
if (minX > newtonPolyg [i] [0])
minX= newtonPolyg [i] [0];
if (maxX < newtonPolyg [i] [0])
maxX= newtonPolyg [i] [0];
if (minY > newtonPolyg [i] [1])
minY= newtonPolyg [i] [1];
if (maxY < newtonPolyg [i] [1])
maxY= newtonPolyg [i] [1];
}
int slopeNum, slopeDen, constTerm;
bool negativeSlope=false;
if (indZero != sizeOfNewtonPolygon - 1)
{
slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[indZero+1][1];
constTerm= newtonPolyg[indZero][0];
}
else
{
slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[0][1];
constTerm= newtonPolyg[indZero][0];
}
if (slopeNum < 0)
{
slopeNum= -slopeNum;
negativeSlope= true;
}
int k= 0;
int* point= new int [2];
for (int i= 0; i < n; i++)
{
if (((indZero+1) < sizeOfNewtonPolygon && (i+1) > newtonPolyg[indZero+1][1])
|| ((indZero+1) >= sizeOfNewtonPolygon && (i+1) > newtonPolyg[0][1]))
{
if (indZero + 1 != sizeOfNewtonPolygon)
indZero++;
else
indZero= 0;
if (indZero != sizeOfNewtonPolygon - 1)
{
slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[indZero+1][1]-newtonPolyg[indZero][1];
constTerm= newtonPolyg[indZero][0];
}
else
{
slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[0][1]-newtonPolyg[indZero][1];
constTerm= newtonPolyg[indZero][0];
}
if (slopeNum < 0)
{
negativeSlope= true;
slopeNum= - slopeNum;
k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
slopeDen) + constTerm;
}
else
k= (int) (((long) slopeNum*((i+1)-newtonPolyg[indZero][1])) / slopeDen)
+ constTerm;
}
else
{
if (negativeSlope)
k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
slopeDen) + constTerm;
else
k= (int) ((long) slopeNum*((i+1)-newtonPolyg[indZero][1])) / slopeDen
+ constTerm;
}
if (i + 1 > maxY || i + 1 < minY)
{
result [i]= 0;
continue;
}
point [0]= k;
point [1]= i + 1;
if (!isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
k= 0;
result [i]= k;
}
delete [] point;
for (int i= 0; i < sizeOfNewtonPolygon; i++)
delete [] newtonPolyg[i];
delete [] newtonPolyg;
return result;
}
getGFDegree
int getGFDegree()
Definition cf_char.cc:75
setCharacteristic
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
p
int p
Definition cfModGcd.cc:4086
isInPolygon
bool isInPolygon(int **points, int sizePoints, int *point)
check if point is inside a polygon described by points
Definition cfNewtonPolygon.cc:383
newtonPolygon
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
Definition cfNewtonPolygon.cc:282
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
result
return result
Definition facAbsBiFact.cc:76
isIrreducible
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
Definition gengftables-conway.cc:77
gf_name
VAR char gf_name
Definition gfops.cc:52
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836

## computeBoundsWrtDiffMainvar()

int * computeBoundsWrtDiffMainvar | ( | const CanonicalForm & | F,
|  | int & | n,
|  | bool & | isIrreducible )

as above just wrt to the other variable

Returns
  computeBounds returns bounds as described above

Parameters

  [in] | F | compressed bivariate polynomial
  [in,out] | n | length of output
  [in,out] | isIrreducible | check if poly is irreducible

Definition at line 922 of file facFqBivarUtil.cc.

{
n= degree (F, 2);
int* result= new int [n];
int sizeOfNewtonPolygon;
int** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
isIrreducible= false;
if (sizeOfNewtonPolygon == 3)
{
bool check1=
(newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
if (check1)
{
bool check2=
(newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
if (check2)
{
int p=getCharacteristic();
int d=1;
char bufGFName='Z';
bool GF= (CFFactory::gettype()==GaloisFieldDomain);
if (GF)
{
d= getGFDegree();
bufGFName=gf_name;
}
setCharacteristic(0);
CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]);
tmp= gcd (tmp, newtonPolyg[1][0]);
tmp= gcd (tmp, newtonPolyg[1][1]);
tmp= gcd (tmp, newtonPolyg[2][0]);
tmp= gcd (tmp, newtonPolyg[2][1]);
isIrreducible= (tmp==1);
if (GF)
setCharacteristic (p, d, bufGFName);
else
setCharacteristic(p);
}
}
}
int swap;
for (int i= 0; i < sizeOfNewtonPolygon; i++)
{
swap= newtonPolyg[i][1];
newtonPolyg[i][1]=newtonPolyg[i][0];
newtonPolyg[i][0]= swap;
}
sizeOfNewtonPolygon= polygon(newtonPolyg, sizeOfNewtonPolygon);
int minX, minY, maxX, maxY;
minX= newtonPolyg [0] [0];
minY= newtonPolyg [0] [1];
maxX= minX;
maxY= minY;
int indZero= 0;
for (int i= 1; i < sizeOfNewtonPolygon; i++)
{
if (newtonPolyg[i][1] == 0)
{
if (newtonPolyg[indZero][1] == 0)
{
if (newtonPolyg[indZero][0] < newtonPolyg[i][0])
indZero= i;
}
else
indZero= i;
}
if (minX > newtonPolyg [i] [0])
minX= newtonPolyg [i] [0];
if (maxX < newtonPolyg [i] [0])
maxX= newtonPolyg [i] [0];
if (minY > newtonPolyg [i] [1])
minY= newtonPolyg [i] [1];
if (maxY < newtonPolyg [i] [1])
maxY= newtonPolyg [i] [1];
}
int slopeNum, slopeDen, constTerm;
bool negativeSlope=false;
if (indZero != sizeOfNewtonPolygon - 1)
{
slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[indZero+1][1];
constTerm= newtonPolyg[indZero][0];
}
else
{
slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[0][1];
constTerm= newtonPolyg[indZero][0];
}
if (slopeNum < 0)
{
slopeNum= -slopeNum;
negativeSlope= true;
}
int k= 0;
int* point= new int [2];
for (int i= 0; i < n; i++)
{
if (((indZero+1) < sizeOfNewtonPolygon && (i+1) > newtonPolyg[indZero+1][1])
|| ((indZero+1) >= sizeOfNewtonPolygon && (i+1) > newtonPolyg[0][1]))
{
if (indZero + 1 != sizeOfNewtonPolygon)
indZero++;
else
indZero= 0;
if (indZero != sizeOfNewtonPolygon - 1)
{
slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[indZero+1][1]-newtonPolyg[indZero][1];
constTerm= newtonPolyg[indZero][0];
}
else
{
slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[0][1]-newtonPolyg[indZero][1];
constTerm= newtonPolyg[indZero][0];
}
if (slopeNum < 0)
{
negativeSlope= true;
slopeNum= - slopeNum;
k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
slopeDen) + constTerm;
}
else
k= (int) (((long) slopeNum*((i+1)-newtonPolyg[indZero][1])) / slopeDen)
+ constTerm;
}
else
{
if (negativeSlope)
k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
slopeDen) + constTerm;
else
k= (int) ((long) slopeNum*((i+1)-newtonPolyg[indZero][1])) / slopeDen
+ constTerm;
}
if (i + 1 > maxY || i + 1 < minY)
{
result [i]= 0;
continue;
}
point [0]= k;
point [1]= i + 1;
if (!isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
k= 0;
result [i]= k;
}
delete [] point;
for (int i= 0; i < sizeOfNewtonPolygon; i++)
delete [] newtonPolyg[i];
delete [] newtonPolyg;
return result;
}
swap
#define swap(_i, _j)
polygon
int polygon(int **points, int sizePoints)
compute a polygon
Definition cfNewtonPolygon.cc:172

## copy()

CFArray copy | ( | const CFList & | list | ) |

write elements of list into an array

Returns
  an array of polys

Parameters

  [in] | list | a list of polys

Definition at line 364 of file facFqBivarUtil.cc.

{
CFArray array= CFArray (list.length());
int j= 0;
for (CFListIterator i= list; i.hasItem(); i++, j++)
array[j]= i.getItem();
return array;
}
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
List::length
int length() const
Definition ftmpl_list.cc:273
j
int j
Definition facHensel.cc:110

## decompress() [1/3]

void decompress | ( | CFAFList & | factors,
|  | const CFMap & | N )

as above

Parameters

  [in,out] | factors | a list of factors
  [in] | N | a map

Definition at line 63 of file facFqBivarUtil.cc.

{
for (CFAFListIterator i= factors; i.hasItem(); i++)
i.getItem()= CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
i.getItem().exp());
}
CFAFactor
AFactor< CanonicalForm > CFAFactor
Definition canonicalform.h:389
CFAFListIterator
ListIterator< CFAFactor > CFAFListIterator
Definition canonicalform.h:391

## decompress() [2/3]

void decompress | ( | CFFList & | factors,
|  | const CFMap & | N )

as above

Parameters

  [in,out] | factors | a list of factors
  [in] | N | a map

Definition at line 57 of file facFqBivarUtil.cc.

{
for (CFFListIterator i= factors; i.hasItem(); i++)
i.getItem()= CFFactor (N (i.getItem().factor()), i.getItem().exp());
}
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392

## decompress() [3/3]

void decompress | ( | CFList & | factors,
|  | const CFMap & | N )

decompress a list of polys factors using the map N

Parameters

  [in,out] | factors | a list of polys
  [in] | N | a map

Definition at line 51 of file facFqBivarUtil.cc.

{
for (CFListIterator i= factors; i.hasItem(); i++)
i.getItem()= N (i.getItem());
}

## getCoeffs() [1/4]

CFArray getCoeffs | ( | const CanonicalForm & | F,
|  | const int | k )

extract coefficients of for where is a variable of level 1

Returns
  coefficients of for

See also
  {getCoeffs (const CanonicalForm&, const int, const Variable&), getCoeffs (const CanonicalForm&, const int, const int, const int, const Variable&, const CanonicalForm&, const mat_zz_p&)}

Parameters

  [in] | F | compressed bivariate poly over F_p
  [in] | k | some int

Definition at line 599 of file facFqBivarUtil.cc.

{
ASSERT (F.isUnivariate() || F.inCoeffDomain(), "univariate input expected");
if (degree (F, 2) < k)
return CFArray();
CFArray result= CFArray (degree (F) - k + 1);
CFIterator j= F;
for (int i= degree (F); i >= k; i--)
{
if (j.exp() == i)
{
result [i - k]= j.coeff();
j++;
if (!j.hasTerms())
return result;
}
else
result[i - k]= 0;
}
return result;
}
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition canonicalform.cc:155

## getCoeffs() [2/4]

CFArray getCoeffs | ( | const CanonicalForm & | F,
|  | const int | k,
|  | const int | l,
|  | const int | degMipo,
|  | const Variable & | alpha,
|  | const CanonicalForm & | evaluation,
|  | const mat_zz_p & | M )

extract coefficients of for where is a variable of level 1

Returns
  coefficients of for

See also
  {getCoeffs (const CanonicalForm&, const int, const Variable& alpha), getCoeffs (const CanonicalForm&, const int)}

Parameters

  [in] | F | compressed bivariate poly
  [in] | k | some int
  [in] | l | precision
  [in] | degMipo | degree of minimal poly
  [in] | alpha | algebraic variable
  [in] | evaluation | evaluation point
  [in] | M | bases change matrix

Definition at line 663 of file facFqBivarUtil.cc.

{
ASSERT (G.isUnivariate() || G.inCoeffDomain(), "univariate input expected");
CanonicalForm F= G (G.mvar() - evaluation, G.mvar());
if (F.isZero())
return CFArray ();
Variable y= Variable (2);
F= F (power (y, degMipo), y);
F= F (y, alpha);
zz_pX NTLF= convertFacCF2NTLzzpX (F);
NTLF.rep.SetLength (l*degMipo);
NTLF.rep= M*NTLF.rep;
NTLF.normalize();
F= convertNTLzzpX2CF (NTLF, y);
if (degree (F, 2) < k)
return CFArray();
CFArray result= CFArray (degree (F) - k + 1);
CFIterator j= F;
for (int i= degree (F); i >= k; i--)
{
if (j.exp() == i)
{
result [i - k]= j.coeff();
j++;
if (!j.hasTerms())
return result;
}
else
result[i - k]= 0;
}
return result;
}
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition NTLconvert.cc:255
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition NTLconvert.cc:105
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
l
int l
Definition cfEzgcd.cc:100
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
evaluation
const CanonicalForm int const CFList & evaluation
Definition facAbsFact.cc:52
G
STATIC_VAR TreeM * G
Definition janet.cc:31
M
#define M
Definition sirandom.c:25

## getCoeffs() [3/4]

CFArray getCoeffs | ( | const CanonicalForm & | F,
|  | const int | k,
|  | const int | l,
|  | const int | degMipo,
|  | const Variable & | alpha,
|  | const CanonicalForm & | evaluation,
|  | const nmod_mat_t | M )

extract coefficients of for where is a variable of level 1

Returns
  coefficients of for

See also
  {getCoeffs (const CanonicalForm&, const int, const Variable& alpha), getCoeffs (const CanonicalForm&, const int)}

Parameters

  [in] | F | compressed bivariate poly
  [in] | k | some int
  [in] | l | precision
  [in] | degMipo | degree of minimal poly
  [in] | alpha | algebraic variable
  [in] | evaluation | evaluation point
  [in] | M | bases change matrix

Definition at line 705 of file facFqBivarUtil.cc.

{
ASSERT (G.isUnivariate() || G.inCoeffDomain(), "univariate input expected");
CanonicalForm F= G (G.mvar() - evaluation, G.mvar());
if (F.isZero())
return CFArray ();
Variable y= Variable (2);
F= F (power (y, degMipo), y);
F= F (y, alpha);
nmod_poly_t FLINTF;
nmod_mat_t MFLINTF, mulResult;
nmod_mat_init (MFLINTF, l*degMipo, 1, getCharacteristic());
nmod_mat_init (mulResult, l*degMipo, 1, getCharacteristic());
convertFacCF2nmod_poly_t (FLINTF, F);
#ifndef slong
#define slong long
#endif
slong i;
for (i= 0; i < FLINTF->length; i++)
nmod_mat_entry (MFLINTF, i, 0)= FLINTF->coeffs[i];
for (; i < MFLINTF->r; i++)
nmod_mat_entry (MFLINTF, i, 0)= 0;
nmod_mat_mul (mulResult, M, MFLINTF);
F= 0;
for (i= 0; i < mulResult->r; i++)
F += CanonicalForm ((long) nmod_mat_entry (mulResult, i, 0))*power (y, i);
nmod_mat_clear (MFLINTF);
nmod_mat_clear (mulResult);
nmod_poly_clear(FLINTF);
if (degree (F, 2) < k)
return CFArray();
CFArray result= CFArray (degree (F) - k + 1);
CFIterator j= F;
for (int i= degree (F); i >= k; i--)
{
if (j.exp() == i)
{
result [i - k]= j.coeff();
j++;
if (!j.hasTerms())
return result;
}
else
result[i - k]= 0;
}
return result;
}
slong
#define slong
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear
nmod_poly_clear(FLINTmipo)

## getCoeffs() [4/4]

CFArray getCoeffs | ( | const CanonicalForm & | F,
|  | const int | k,
|  | const Variable & | alpha )

extract coefficients of for where is a variable of level 1

Returns
  coefficients of for

See also
  {getCoeffs (const CanonicalForm&, const int), getCoeffs (const CanonicalForm&, const int, const int, const int, const Variable&, const CanonicalForm&, const mat_zz_p&)}

Parameters

  [in] | F | compressed bivariate poly over F_p(alpha)
  [in] | k | some int
  [in] | alpha | algebraic variable

Definition at line 622 of file facFqBivarUtil.cc.

{
ASSERT (F.isUnivariate() || F.inCoeffDomain(), "univariate input expected");
if (degree (F, 2) < k)
return CFArray ();
int d= degree (getMipo (alpha));
CFArray result= CFArray ((degree (F) - k + 1)*d);
CFIterator j= F;
CanonicalForm buf;
CFIterator iter;
for (int i= degree (F); i >= k; i--)
{
if (j.exp() == i)
{
iter= j.coeff();
for (int l= degree (j.coeff(), alpha); l >= 0; l--)
{
if (iter.exp() == l)
{
result [(i - k)*d + l]= iter.coeff();
iter++;
if (!iter.hasTerms())
break;
}
}
j++;
if (!j.hasTerms())
return result;
}
else
{
for (int l= 0; l < d; l++)
result[(i - k)*d + l]= 0;
}
}
return result;
}
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
buf
int status int void * buf
Definition si_signals.h:69

## indexUpdate()

void indexUpdate | ( | int | index[],
|  | const int & | subsetSize,
|  | const int & | setSize,
|  | bool & | noSubset )

update index

Parameters

  [in,out] | index | an array encoding a subset of size subsetSize
  [in] | subsetSize | size of the subset
  [in] | setSize | size of the given set
  [in,out] | noSubset | if there is no subset we have not yet considered noSubset is true

Definition at line 373 of file facFqBivarUtil.cc.

{
noSubset= false;
if (subsetSize > setSize)
{
noSubset= true;
return;
}
int * v= new int [setSize];
for (int i= 0; i < setSize; i++)
v[i]= index[i];
if (subsetSize == 1)
{
v[0]= v[0] - 1;
if (v[0] >= setSize)
{
noSubset= true;
delete [] v;
return;
}
}
else
{
if (v[subsetSize - 1] - v[0] + 1 == subsetSize && v[0] > 1)
{
if (v[0] + subsetSize - 1 > setSize)
{
noSubset= true;
delete [] v;
return;
}
v[0]= v[0] - 1;
for (int i= 1; i < subsetSize - 1; i++)
v[i]= v[i - 1] + 1;
v[subsetSize - 1]= v[subsetSize - 2];
}
else
{
if (v[0] + subsetSize - 1 > setSize)
{
noSubset= true;
delete [] v;
return;
}
for (int i= 1; i < subsetSize - 1; i++)
v[i]= v[i - 1] + 1;
v[subsetSize - 1]= v[subsetSize - 2];
}
}
for (int i= 0; i < setSize; i++)
index[i]= v[i];
delete [] v;
}
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
index
static int index(p_Length length, p_Ord ord)
Definition p_Procs_Impl.h:592

## isInExtension()

bool isInExtension | ( | const CanonicalForm & | F,
|  | const CanonicalForm & | gamma,
|  | const int | k,
|  | const CanonicalForm & | delta,
|  | CFList & | source,
|  | CFList & | dest )

tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case)

Returns
  isInExtension returns true if F is not contained in a subfield defined by gamma (Fq case) or k (GF case), false else

See also
  appendTestMapDown()

Parameters

  [in] | F | a poly over F_p (alpha)=Fq or GF(p^l)
  [in] | gamma | a primitive element defining a subfield of Fq if we are not over some GF
  | k | some int k such that k divides l if we are not over some Fq
  [in] | delta | image of gamma
  [in,out] | source | list of preimages
  [in,out] | dest | list of images

Definition at line 184 of file facFqBivarUtil.cc.

{
bool result;
if (CFFactory::gettype() == GaloisFieldDomain)
{
int p= getCharacteristic();
int orderFieldExtension= ipower (p, getGFDegree()) - 1;
int order= ipower (p, k) - 1;
int number= orderFieldExtension/order;
result= GFInExtensionHelper (F, number);
return result;
}
else
{
result= FqInExtensionHelper (F, gamma, delta, source, dest);
return result;
}
}
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition cf_util.cc:27
GFInExtensionHelper
static bool GFInExtensionHelper(const CanonicalForm &F, const int number)
Definition facFqBivarUtil.cc:111
FqInExtensionHelper
static bool FqInExtensionHelper(const CanonicalForm &F, const CanonicalForm &gamma, const CanonicalForm &delta, CFList &source, CFList &dest)
Definition facFqBivarUtil.cc:139

## logarithmicDerivative() [1/2]

CFArray logarithmicDerivative | ( | const CanonicalForm & | F,
|  | const CanonicalForm & | G,
|  | int | l,
|  | CanonicalForm & | Q )

compute the coefficients of the logarithmic derivative of G mod Variable (2)^l over Fq

Returns
  an array of coefficients of the logarithmic derivative of G mod Variable (2)^l

Parameters

  [in] | F | a bivariate poly
  [in] | G | a factor of F
  [in] | l | lifting precision
  [in,out] | Q | F/G

Definition at line 459 of file facFqBivarUtil.cc.

{
Variable x= Variable (2);
Variable y= Variable (1);
CanonicalForm xToL= power (x, l);
CanonicalForm q,r;
CanonicalForm logDeriv;
TIMING_START (fac_log_deriv_div);
q= newtonDiv (F, G, xToL);
TIMING_END_AND_PRINT (fac_log_deriv_div, "time for division in logderiv1: ");
TIMING_START (fac_log_deriv_mul);
logDeriv= mulMod2 (q, deriv (G, y), xToL);
TIMING_END_AND_PRINT (fac_log_deriv_mul, "time to multiply in logderiv1: ");
if (degree (logDeriv, x) == 0)
{
Q= q;
return CFArray();
}
int j= degree (logDeriv, y) + 1;
CFArray result= CFArray (j);
CFIterator ii;
for (CFIterator i= logDeriv; i.hasTerms() && !logDeriv.isZero(); i++)
{
if (i.coeff().inCoeffDomain())
result[0] += i.coeff()*power (x,i.exp());
else
{
for (ii= i.coeff(); ii.hasTerms(); ii++)
result[ii.exp()] += ii.coeff()*power (x,i.exp());
}
}
Q= q;
return result;
}
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition canonicalform.h:346
CFIterator::exp
CF_NO_INLINE int exp() const
get the current exponent
CFIterator::coeff
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
CFIterator::hasTerms
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
mulMod2
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition facMul.cc:2992
newtonDiv
void newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
Definition facMul.cc:386
Q
#define Q
Definition sirandom.c:26
TIMING_START
#define TIMING_START(t)
Definition timing.h:92
TIMING_END_AND_PRINT
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94

## logarithmicDerivative() [2/2]

CFArray logarithmicDerivative | ( | const CanonicalForm & | F,
|  | const CanonicalForm & | G,
|  | int | l,
|  | int | oldL,
|  | const CanonicalForm & | oldQ,
|  | CanonicalForm & | Q )

compute the coefficients of the logarithmic derivative of G mod Variable (2)^l over Fq with oldQ= F/G mod Variable (2)^oldL

Returns
  an array of coefficients of the logarithmic derivative of G mod Variable (2)^l

Parameters

  [in] | F | bivariate poly truncated at Variable(2)^l
  [in] | G | a factor of F
  [in] | l | lifting precision
  [in] | oldL | old precision
  [in] | oldQ | F/G mod Variable(2)^oldL
  [in,out] | Q | F/G

Definition at line 501 of file facFqBivarUtil.cc.

{
Variable x= Variable (2);
Variable y= Variable (1);
CanonicalForm xToL= power (x, l);
CanonicalForm xToOldL= power (x, oldL);
CanonicalForm xToLOldL= power (x, l-oldL);
CanonicalForm q,r;
CanonicalForm logDeriv;
CanonicalForm bufF;
TIMING_START (fac_log_deriv_pre);
if ((oldL > 100 && l - oldL < 50) || (oldL < 100 && l - oldL < 30))
{
bufF= F;
CanonicalForm oldF= mulMod2 (G, oldQ, xToL);
bufF -= oldF;
bufF= div (bufF, xToOldL);
}
else
{
//middle product style computation of [G*oldQ]^{l}_{oldL}
CanonicalForm G3= div (G, xToOldL);
CanonicalForm Up= mulMod2 (G3, oldQ, xToLOldL);
CanonicalForm xToOldL2= power (x, (oldL+1)/2);
CanonicalForm G2= mod (G, xToOldL);
CanonicalForm G1= div (G2, xToOldL2);
CanonicalForm G0= mod (G2, xToOldL2);
CanonicalForm oldQ1= div (oldQ, xToOldL2);
CanonicalForm oldQ0= mod (oldQ, xToOldL2);
CanonicalForm Mid;
if (oldL % 2 == 1)
Mid= mulMod2 (G1, oldQ1*x, xToLOldL);
else
Mid= mulMod2 (G1, oldQ1, xToLOldL);
//computation of Low might be faster using a real middle product?
CanonicalForm Low= mulMod2 (G0, oldQ1, xToOldL)+mulMod2 (G1, oldQ0, xToOldL);
Low= div (Low, power (x, oldL/2));
Low= mod (Low, xToLOldL);
Up += Mid + Low;
bufF= div (F, xToOldL);
bufF -= Up;
}
TIMING_END_AND_PRINT (fac_log_deriv_pre, "time to preprocess: ");
TIMING_START (fac_log_deriv_div);
if (l-oldL > 0)
q= newtonDiv (bufF, G, xToLOldL);
else
q= 0;
q *= xToOldL;
q += oldQ;
TIMING_END_AND_PRINT (fac_log_deriv_div, "time for div in logderiv2: ");
TIMING_START (fac_log_deriv_mul);
logDeriv= mulMod2 (q, deriv (G, y), xToL);
TIMING_END_AND_PRINT (fac_log_deriv_mul, "time for mul in logderiv2: ");
if (degree (logDeriv, x) == 0)
{
Q= q;
return CFArray();
}
int j= degree (logDeriv,y) + 1;
CFArray result= CFArray (j);
CFIterator ii;
for (CFIterator i= logDeriv; i.hasTerms() && !logDeriv.isZero(); i++)
{
if (i.coeff().inCoeffDomain())
result[0] += i.coeff()*power (x,i.exp());
else
{
for (ii= i.coeff(); ii.hasTerms(); ii++)
result[ii.exp()] += ii.coeff()*power (x,i.exp());
}
}
Q= q;
return result;
}
div
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)

## mapDown()

CanonicalForm mapDown | ( | const CanonicalForm & | F,
|  | const ExtensionInfo & | info,
|  | CFList & | source,
|  | CFList & | dest )

map a poly into a subfield of the current field, no testing is performed!

Returns
  mapDown returns F mapped into a subfield of the current field

See also
  appendTestMapDown(), appendMapDown()

Parameters

  [in] | F | a poly
  [in] | info | information about the sub- and current field
  [in,out] | source | in case we are over some F_p (alpha) and want to map down into F_p (beta) source contains powers of the primitive element of F_p (alpha)
  [in,out] | dest | as source but contains the corresponding powers of the primitive element of F_p (beta)

Definition at line 206 of file facFqBivarUtil.cc.

{
int k= info.getGFDegree();
Variable beta= info.getAlpha();
CanonicalForm primElem= info.getGamma();
CanonicalForm imPrimElem= info.getDelta();
if (k > 1)
return GFMapDown (F, k);
else if (k == 1)
return F;
if (/*k==0 &&*/ beta == Variable (1))
return F;
else /*if (k==0 && beta != Variable (1))*/
return mapDown (F, imPrimElem, primElem, beta, source, dest);
}

## multiplicity()

CFFList multiplicity | ( | CanonicalForm & | F,
|  | const CFList & | factors )

determine multiplicity of the factors

Returns
  a list of factors of F with their multiplicity

Parameters

  [in] | F | a poly
  [in] | factors | a list of factors of F

Definition at line 436 of file facFqBivarUtil.cc.

{
if (F.inCoeffDomain())
return CFFList (CFFactor (F, 1));
CFFList result;
int multi= 0;
CanonicalForm quot;
for (CFListIterator i= factors; i.hasItem(); i++)
{
while (fdivides (i.getItem(), F, quot))
{
multi++;
F= quot;
}
if (multi > 0)
result.append (CFFactor (i.getItem(), multi));
multi= 0;
}
return result;
}
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)

## normalize() [1/2]

void normalize | ( | CFFList & | factors | ) |

as above

Parameters

  [in,out] | factors | a list of factors

Definition at line 297 of file facFqBivarUtil.cc.

{
CanonicalForm lcinv;
for (CFFListIterator i= factors; i.hasItem(); i++)
{
lcinv= 1/ Lc (i.getItem().factor());
i.getItem()= CFFactor (i.getItem().factor()*lcinv,
i.getItem().exp());
}
return;
}
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307

## normalize() [2/2]

void normalize | ( | CFList & | factors | ) |

normalize factors, i.e. make factors monic

Parameters

  [in,out] | factors | a list of polys

Definition at line 286 of file facFqBivarUtil.cc.

{
CanonicalForm lcinv;
for (CFListIterator i= factors; i.hasItem(); i++)
{
lcinv= 1/Lc (i.getItem());
i.getItem() *= lcinv;
}
return;
}

## reverseSubst() [1/2]

void reverseSubst | ( | CFList & | L,
|  | const int | d,
|  | const Variable & | x )

reverse a substitution x^d->x

Parameters

  [in,out] | L | a list of polys, returns the given list with x replaced by x^d
  [in] | d | an integer > 0
  [in] | x | a Variable

Definition at line 1309 of file facFqBivarUtil.cc.

{
for (CFListIterator i= L; i.hasItem(); i++)
i.getItem()= reverseSubst (i.getItem(), d, x);
}
reverseSubst
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
Definition facFqBivarUtil.cc:1295

## reverseSubst() [2/2]

CanonicalForm reverseSubst | ( | const CanonicalForm & | F,
|  | const int | d,
|  | const Variable & | x )

reverse a substitution x^d->x

Returns
  a poly with x replaced by x^d

Parameters

  [in] | F | a poly
  [in] | d | an integer > 0
  [in] | x | a Variable

Definition at line 1295 of file facFqBivarUtil.cc.

{
if (d <= 1)
return F;
if (degree (F, x) <= 0)
return F;
CanonicalForm f= swapvar (F, x, F.mvar());
CanonicalForm result= 0;
for (CFIterator i= f; i.hasTerms(); i++)
result += i.coeff()*power (f.mvar(), d*i.exp());
return swapvar (result, x, F.mvar());
}
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition canonicalform.cc:593

## subset()

CFList subset | ( | int | index[],
|  | const int & | s,
|  | const CFArray & | elements,
|  | bool & | noSubset )

extract a subset given by index of size s from elements, if there is no subset we have not yet considered noSubset is set to true. index encodes the next subset, e.g. if s= 3, elements= {a,b,c,d}, index= {1, 2, 4, 0}, then subset= {a,c,d}. index is of size elements.size().

Returns
  subset returns a list of polys of length s if there is a subset we have not yet considered.

Parameters

  [in,out] | index | an array encoding the next subset
  [in] | s | size of the subset
  [in] | elements | an array of polys
  [in,out] | noSubset | if there is no subset we have not yet considered noSubset is true

Definition at line 309 of file facFqBivarUtil.cc.

{
int r= elements.size();
int i= 0;
CFList result;
noSubset= false;
if (index[s - 1] == 0)
{
while (i < s)
{
index[i]= i + 1;
result.append (elements[i]);
i++;
}
return result;
}
int buf;
int k;
bool found= false;
if (index[s - 1] == r)
{
if (index[0] == r - s + 1)
{
noSubset= true;
return result;
}
else {
while (found == false)
{
if (index[s - 2 - i] < r - i - 1)
found= true;
i++;
}
buf= index[s - i - 1];
k= 0;
while (s - i - 1 + k < s)
{
index[s - i - 1 + k]= buf + k + 1;
k++;
}
}
for (int j= 0; j < s; j++)
result.append (elements[index[j] - 1]);
return result;
}
else
{
index[s - 1] += 1;
for (int j= 0; j < s; j++)
result.append (elements[index[j] - 1]);
return result;
}
}
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
Array::size
int size() const
Definition ftmpl_array.cc:92
s
const CanonicalForm int s
Definition facAbsFact.cc:51
found
bool found
Definition facFactorize.cc:55

## subsetDegree()

int subsetDegree | ( | const CFList & | S | ) |

compute the sum of degrees in Variable(1) of elements in S

Returns
  subsetDegree returns the sum of degrees in Variable(1) of elements in S

Parameters

  [in] | S | a list of polys

Definition at line 428 of file facFqBivarUtil.cc.

{
int result= 0;
for (CFListIterator i= S; i.hasItem(); i++)
result += degree (i.getItem(), Variable (1));
return result;
}

## subst()

void subst | ( | const CanonicalForm & | F,
|  | CanonicalForm & | A,
|  | const int | d,
|  | const Variable & | x )

substitute x^d by x in F

Parameters

  [in] | F | a polynomial
  [in,out] | A | returns F with x^d replaced by x
  | d | d > 1 such that a substitution x^d -> x [in] is possible
  [in] | x | a Variable

Definition at line 1275 of file facFqBivarUtil.cc.

{
if (d <= 1)
{
A= F;
return;
}
if (degree (F, x) <= 0)
{
A= F;
return;
}
CanonicalForm C= 0;
CanonicalForm f= swapvar (F, x, F.mvar());
for (CFIterator i= f; i.hasTerms(); i++)
C += i.coeff()*power (f.mvar(), i.exp()/ d);
A= swapvar (C, x, F.mvar());
}
A
#define A
Definition sirandom.c:24

## substituteCheck() [1/2]

int substituteCheck | ( | const CanonicalForm & | F,
|  | const Variable & | x )

check if a substitution x^n->x is possible

Returns
  an integer n > 1, if a substitution described as above is possible else n <= 1

Parameters

  [in] | F | a polynomial
  [in] | x | some variable

Definition at line 1089 of file facFqBivarUtil.cc.

{
if (F.inCoeffDomain())
return 0;
if (degree (F, x) < 0)
return 0;
CanonicalForm f= swapvar (F, F.mvar(), x);
int sizef= 0;
for (CFIterator i= f; i.hasTerms(); i++, sizef++)
{
if (i.exp() == 1)
return 0;
}
int * expf= new int [sizef];
int j= 0;
for (CFIterator i= f; i.hasTerms(); i++, j++)
expf [j]= i.exp();
int indf= sizef - 1;
if (expf[indf] == 0)
indf--;
int result= expf[indf];
for (int i= indf - 1; i >= 0; i--)
{
if (expf [i]%result != 0)
{
delete [] expf;
return 0;
}
}
delete [] expf;
return result;
}

## substituteCheck() [2/2]

int substituteCheck | ( | const CFList & | L | ) |

checks if a substitution x^n->x is possible

Returns
  an integer n > 1, if a substitution described as above is possible else n <= 1

Parameters

  [in] | L | a list of univariate polys

Definition at line 1254 of file facFqBivarUtil.cc.

{
ASSERT (L.length() > 1, "expected a list of at least two elements");
if (L.length() < 2)
return 0;
CFListIterator i= L;
i++;
int result= substituteCheck (L.getFirst(), i.getItem());
if (result <= 1)
return result;
i++;
for (;i.hasItem(); i++)
{
result= recSubstituteCheck (i.getItem(), result);
if (result <= 1)
return result;
}
return result;
}
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
recSubstituteCheck
int recSubstituteCheck(const CanonicalForm &F, const int d)
Definition facFqBivarUtil.cc:1205
substituteCheck
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
Definition facFqBivarUtil.cc:1089

## swapDecompress()

void swapDecompress | ( | CFList & | factors,
|  | const bool | swap,
|  | const CFMap & | N )

swap Variables in factors, then decompress factors

Parameters

  [in,out] | factors | a list of polys
  [in] | swap | indicates the need to swap
  [in] | N | a map

Definition at line 97 of file facFqBivarUtil.cc.

{
Variable x= Variable (1);
Variable y= Variable (2);
for (CFListIterator i= factors; i.hasItem(); i++)
{
if (swap)
i.getItem()= swapvar (i.getItem(), x, y);
i.getItem()= N (i.getItem());
}
return;
}

## writeInMatrix()

void writeInMatrix | ( | CFMatrix & | M,
|  | const CFArray & | A,
|  | const int | column,
|  | const int | startIndex )

write A into M starting at row startIndex

Parameters

  [in,out] | M | some matrix
  [in] | A | array of polys
  [in] | column | column in which A is written
  [in] | startIndex | row in which to start

Definition at line 586 of file facFqBivarUtil.cc.

{
ASSERT (A.size () - startIndex >= 0, "wrong starting index");
ASSERT (A.size () - startIndex <= M.rows(), "wrong starting index");
ASSERT (column > 0 && column <= M.columns(), "wrong column");
if (A.size() - startIndex <= 0) return;
int j= 1;
for (int i= startIndex; i < A.size(); i++, j++)
M (j, column)= A [i];
}