My Project  debian-1:4.1.1-p2+ds-4build2
Macros | Functions | Variables
facFqBivarUtil.cc File Reference
#include "config.h"
#include "timing.h"
#include "cf_map.h"
#include "cf_map_ext.h"
#include "templates/ftmpl_functions.h"
#include "ExtensionInfo.h"
#include "cf_algorithm.h"
#include "cf_factory.h"
#include "cf_util.h"
#include "imm.h"
#include "cf_iter.h"
#include "facFqBivarUtil.h"
#include "cfNewtonPolygon.h"
#include "facHensel.h"
#include "facMul.h"
#include "FLINTconvert.h"

Go to the source code of this file.

Macros

#define slong   long
 

Functions

 TIMING_DEFINE_PRINT (fac_log_deriv_div) TIMING_DEFINE_PRINT(fac_log_deriv_mul) TIMING_DEFINE_PRINT(fac_log_deriv_pre) void append(CFList &factors1
 
void decompress (CFList &factors, const CFMap &N)
 decompress a list of polys factors using the map N More...
 
void decompress (CFFList &factors, const CFMap &N)
 as above More...
 
void decompress (CFAFList &factors, const CFMap &N)
 as above More...
 
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 More...
 
void swapDecompress (CFList &factors, const bool swap, const CFMap &N)
 swap Variables in factors, then decompress factors More...
 
static bool GFInExtensionHelper (const CanonicalForm &F, const int number)
 
static bool FqInExtensionHelper (const CanonicalForm &F, const CanonicalForm &gamma, const CanonicalForm &delta, CFList &source, CFList &dest)
 
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) More...
 
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! More...
 
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 More...
 
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 More...
 
void normalize (CFList &factors)
 normalize factors, i.e. make factors monic More...
 
void normalize (CFFList &factors)
 as above More...
 
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(). More...
 
CFArray copy (const CFList &list)
 write elements of list into an array More...
 
void indexUpdate (int index[], const int &subsetSize, const int &setSize, bool &noSubset)
 update index More...
 
int subsetDegree (const CFList &S)
 compute the sum of degrees in Variable(1) of elements in S More...
 
CFFList multiplicity (CanonicalForm &F, const CFList &factors)
 determine multiplicity of the factors More...
 
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 More...
 
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 More...
 
void writeInMatrix (CFMatrix &M, const CFArray &A, const int column, const int startIndex)
 write A into M starting at row startIndex More...
 
CFArray getCoeffs (const CanonicalForm &F, const int k)
 extract coefficients of $ x^i $ for $i\geq k$ where $ x $ is a variable of level 1 More...
 
CFArray getCoeffs (const CanonicalForm &F, const int k, const Variable &alpha)
 extract coefficients of $ x^i $ for $i\geq k$ where $ x $ is a variable of level 1 More...
 
CFArray getCoeffs (const CanonicalForm &G, const int k, const int l, const int degMipo, const Variable &alpha, const CanonicalForm &evaluation, const mat_zz_p &M)
 extract coefficients of $ x^i $ for $i\geq k$ where $ x $ is a variable of level 1 More...
 
CFArray getCoeffs (const CanonicalForm &G, const int k, const int l, const int degMipo, const Variable &alpha, const CanonicalForm &evaluation, const nmod_mat_t M)
 extract coefficients of $ x^i $ for $i\geq k$ where $ x $ is a variable of level 1 More...
 
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 More...
 
int * computeBoundsWrtDiffMainvar (const CanonicalForm &F, int &n, bool &isIrreducible)
 as above just wrt to the other variable More...
 
int substituteCheck (const CanonicalForm &F, const Variable &x)
 check if a substitution x^n->x is possible More...
 
static int substituteCheck (const CanonicalForm &F, const CanonicalForm &G)
 
int recSubstituteCheck (const CanonicalForm &F, const int d)
 
int substituteCheck (const CFList &L)
 checks if a substitution x^n->x is possible More...
 
void subst (const CanonicalForm &F, CanonicalForm &A, const int d, const Variable &x)
 substitute x^d by x in F More...
 
CanonicalForm reverseSubst (const CanonicalForm &F, const int d, const Variable &x)
 reverse a substitution x^d->x More...
 
void reverseSubst (CFList &L, const int d, const Variable &x)
 reverse a substitution x^d->x More...
 

Variables

const CFList & factors2
 

Detailed Description

This file provides utility functions for bivariate factorization

Author
Martin Lee

Definition in file facFqBivarUtil.cc.

Macro Definition Documentation

◆ slong

#define slong   long

Function Documentation

◆ 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()

Definition at line 267 of file facFqBivarUtil.cc.

269 {
270  int k= info.getGFDegree();
271  Variable beta= info.getBeta();
272  Variable alpha= info.getAlpha();
273  CanonicalForm gamma= info.getGamma();
274  CanonicalForm delta= info.getDelta();
275  if (k > 1)
276  factors.append (GFMapDown (g, k));
277  else if (k == 1)
278  factors.append (g);
279  else if (!k && beta == Variable (1))
280  factors.append (g);
281  else if (!k && beta != Variable (1))
282  factors.append (mapDown (g, delta, gamma, alpha, source, dest));
283  return;
284 }

◆ 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

Definition at line 70 of file facFqBivarUtil.cc.

73 {
74  Variable x= Variable (1);
75  Variable y= Variable (2);
76  for (CFListIterator i= factors1; i.hasItem(); i++)
77  {
78  if (swap1)
79  {
80  if (!swap2)
81  i.getItem()= swapvar (i.getItem(), x, y);
82  }
83  else
84  {
85  if (swap2)
86  i.getItem()= swapvar (i.getItem(), y, x);
87  }
88  i.getItem()= N (i.getItem());
89  }
90  for (CFListIterator i= factors2; i.hasItem(); i++)
91  factors1.append (N (i.getItem()));
92  for (CFListIterator i= factors3; i.hasItem(); i++)
93  factors1.append (N (i.getItem()));
94  return;
95 }

◆ 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()

Definition at line 223 of file facFqBivarUtil.cc.

225 {
226  int k= info.getGFDegree();
227  Variable beta= info.getBeta();
228  Variable alpha= info.getAlpha();
229  CanonicalForm delta= info.getDelta();
230  CanonicalForm gamma= info.getGamma();
231  CanonicalForm g= f;
232  int degMipoBeta;
233  if (!k && beta.level() == 1)
234  degMipoBeta= 1;
235  else if (!k && beta.level() != 1)
236  degMipoBeta= degree (getMipo (beta));
237  if (k > 1)
238  {
239  if (!isInExtension (g, gamma, k, delta, source, dest))
240  {
241  g= GFMapDown (g, k);
242  factors.append (g);
243  }
244  }
245  else if (k == 1)
246  {
247  if (!isInExtension (g, gamma, k, delta, source, dest))
248  factors.append (g);
249  }
250  else if (!k && beta == Variable (1))
251  {
252  if (degree (g, alpha) < degMipoBeta)
253  factors.append (g);
254  }
255  else if (!k && beta != Variable (1))
256  {
257  if (!isInExtension (g, gamma, k, delta, source, dest))
258  {
259  g= mapDown (g, delta, gamma, alpha, source, dest);
260  factors.append (g);
261  }
262  }
263  return;
264 }

◆ 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

Definition at line 768 of file facFqBivarUtil.cc.

769 {
770  n= degree (F, 1);
771  int* result= new int [n];
772  int sizeOfNewtonPolygon;
773  int** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
774 
775  isIrreducible= false;
776  if (sizeOfNewtonPolygon == 3)
777  {
778  bool check1=
779  (newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
780  if (check1)
781  {
782  bool check2=
783  (newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
784  if (check2)
785  {
786  int p=getCharacteristic();
787  int d=1;
788  char bufGFName='Z';
789  bool GF= (CFFactory::gettype()==GaloisFieldDomain);
790  if (GF)
791  {
792  d= getGFDegree();
793  bufGFName=gf_name;
794  }
795  setCharacteristic(0);
796  CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]); // maybe it's better to use plain intgcd
797  tmp= gcd (tmp, newtonPolyg[1][0]);
798  tmp= gcd (tmp, newtonPolyg[1][1]);
799  tmp= gcd (tmp, newtonPolyg[2][0]);
800  tmp= gcd (tmp, newtonPolyg[2][1]);
801  isIrreducible= (tmp==1);
802  if (GF)
803  setCharacteristic (p, d, bufGFName);
804  else
805  setCharacteristic(p);
806  }
807  }
808  }
809 
810  int minX, minY, maxX, maxY;
811  minX= newtonPolyg [0] [0];
812  minY= newtonPolyg [0] [1];
813  maxX= minX;
814  maxY= minY;
815  int indZero= 0;
816  for (int i= 1; i < sizeOfNewtonPolygon; i++)
817  {
818  if (newtonPolyg[i][1] == 0)
819  {
820  if (newtonPolyg[indZero][1] == 0)
821  {
822  if (newtonPolyg[indZero][0] < newtonPolyg[i][0])
823  indZero= i;
824  }
825  else
826  indZero= i;
827  }
828  if (minX > newtonPolyg [i] [0])
829  minX= newtonPolyg [i] [0];
830  if (maxX < newtonPolyg [i] [0])
831  maxX= newtonPolyg [i] [0];
832  if (minY > newtonPolyg [i] [1])
833  minY= newtonPolyg [i] [1];
834  if (maxY < newtonPolyg [i] [1])
835  maxY= newtonPolyg [i] [1];
836  }
837 
838  int slopeNum, slopeDen, constTerm;
839  bool negativeSlope=false;
840  if (indZero != sizeOfNewtonPolygon - 1)
841  {
842  slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
843  slopeDen= newtonPolyg[indZero+1][1];
844  constTerm= newtonPolyg[indZero][0];
845  }
846  else
847  {
848  slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
849  slopeDen= newtonPolyg[0][1];
850  constTerm= newtonPolyg[indZero][0];
851  }
852  if (slopeNum < 0)
853  {
854  slopeNum= -slopeNum;
855  negativeSlope= true;
856  }
857  int k= 0;
858  int* point= new int [2];
859  for (int i= 0; i < n; i++)
860  {
861  if (((indZero+1) < sizeOfNewtonPolygon && (i+1) > newtonPolyg[indZero+1][1])
862  || ((indZero+1) >= sizeOfNewtonPolygon && (i+1) > newtonPolyg[0][1]))
863  {
864  if (indZero + 1 != sizeOfNewtonPolygon)
865  indZero++;
866  else
867  indZero= 0;
868  if (indZero != sizeOfNewtonPolygon - 1)
869  {
870  slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
871  slopeDen= newtonPolyg[indZero+1][1]-newtonPolyg[indZero][1];
872  constTerm= newtonPolyg[indZero][0];
873  }
874  else
875  {
876  slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
877  slopeDen= newtonPolyg[0][1]-newtonPolyg[indZero][1];
878  constTerm= newtonPolyg[indZero][0];
879  }
880  if (slopeNum < 0)
881  {
882  negativeSlope= true;
883  slopeNum= - slopeNum;
884  k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
885  slopeDen) + constTerm;
886  }
887  else
888  k= (int) (((long) slopeNum*((i+1)-newtonPolyg[indZero][1])) / slopeDen)
889  + constTerm;
890  }
891  else
892  {
893  if (negativeSlope)
894  k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
895  slopeDen) + constTerm;
896  else
897  k= (int) ((long) slopeNum*((i+1)-newtonPolyg[indZero][1])) / slopeDen
898  + constTerm;
899  }
900  if (i + 1 > maxY || i + 1 < minY)
901  {
902  result [i]= 0;
903  continue;
904  }
905  point [0]= k;
906  point [1]= i + 1;
907  if (!isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
908  k= 0;
909  result [i]= k;
910  }
911 
912  delete [] point;
913 
914  for (int i= 0; i < sizeOfNewtonPolygon; i++)
915  delete [] newtonPolyg[i];
916  delete [] newtonPolyg;
917 
918  return result;
919 }

◆ 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

Definition at line 922 of file facFqBivarUtil.cc.

924 {
925  n= degree (F, 2);
926  int* result= new int [n];
927  int sizeOfNewtonPolygon;
928  int** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
929 
930  isIrreducible= false;
931  if (sizeOfNewtonPolygon == 3)
932  {
933  bool check1=
934  (newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
935  if (check1)
936  {
937  bool check2=
938  (newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
939  if (check2)
940  {
941  int p=getCharacteristic();
942  int d=1;
943  char bufGFName='Z';
944  bool GF= (CFFactory::gettype()==GaloisFieldDomain);
945  if (GF)
946  {
947  d= getGFDegree();
948  bufGFName=gf_name;
949  }
950  setCharacteristic(0);
951  CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]);
952  tmp= gcd (tmp, newtonPolyg[1][0]);
953  tmp= gcd (tmp, newtonPolyg[1][1]);
954  tmp= gcd (tmp, newtonPolyg[2][0]);
955  tmp= gcd (tmp, newtonPolyg[2][1]);
956  isIrreducible= (tmp==1);
957  if (GF)
958  setCharacteristic (p, d, bufGFName);
959  else
960  setCharacteristic(p);
961  }
962  }
963  }
964 
965  int swap;
966  for (int i= 0; i < sizeOfNewtonPolygon; i++)
967  {
968  swap= newtonPolyg[i][1];
969  newtonPolyg[i][1]=newtonPolyg[i][0];
970  newtonPolyg[i][0]= swap;
971  }
972 
973  sizeOfNewtonPolygon= polygon(newtonPolyg, sizeOfNewtonPolygon);
974 
975  int minX, minY, maxX, maxY;
976  minX= newtonPolyg [0] [0];
977  minY= newtonPolyg [0] [1];
978  maxX= minX;
979  maxY= minY;
980  int indZero= 0;
981  for (int i= 1; i < sizeOfNewtonPolygon; i++)
982  {
983  if (newtonPolyg[i][1] == 0)
984  {
985  if (newtonPolyg[indZero][1] == 0)
986  {
987  if (newtonPolyg[indZero][0] < newtonPolyg[i][0])
988  indZero= i;
989  }
990  else
991  indZero= i;
992  }
993  if (minX > newtonPolyg [i] [0])
994  minX= newtonPolyg [i] [0];
995  if (maxX < newtonPolyg [i] [0])
996  maxX= newtonPolyg [i] [0];
997  if (minY > newtonPolyg [i] [1])
998  minY= newtonPolyg [i] [1];
999  if (maxY < newtonPolyg [i] [1])
1000  maxY= newtonPolyg [i] [1];
1001  }
1002 
1003  int slopeNum, slopeDen, constTerm;
1004  bool negativeSlope=false;
1005  if (indZero != sizeOfNewtonPolygon - 1)
1006  {
1007  slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
1008  slopeDen= newtonPolyg[indZero+1][1];
1009  constTerm= newtonPolyg[indZero][0];
1010  }
1011  else
1012  {
1013  slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
1014  slopeDen= newtonPolyg[0][1];
1015  constTerm= newtonPolyg[indZero][0];
1016  }
1017  if (slopeNum < 0)
1018  {
1019  slopeNum= -slopeNum;
1020  negativeSlope= true;
1021  }
1022  int k= 0;
1023 
1024  int* point= new int [2];
1025  for (int i= 0; i < n; i++)
1026  {
1027  if (((indZero+1) < sizeOfNewtonPolygon && (i+1) > newtonPolyg[indZero+1][1])
1028  || ((indZero+1) >= sizeOfNewtonPolygon && (i+1) > newtonPolyg[0][1]))
1029  {
1030  if (indZero + 1 != sizeOfNewtonPolygon)
1031  indZero++;
1032  else
1033  indZero= 0;
1034  if (indZero != sizeOfNewtonPolygon - 1)
1035  {
1036  slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
1037  slopeDen= newtonPolyg[indZero+1][1]-newtonPolyg[indZero][1];
1038  constTerm= newtonPolyg[indZero][0];
1039  }
1040  else
1041  {
1042  slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
1043  slopeDen= newtonPolyg[0][1]-newtonPolyg[indZero][1];
1044  constTerm= newtonPolyg[indZero][0];
1045  }
1046  if (slopeNum < 0)
1047  {
1048  negativeSlope= true;
1049  slopeNum= - slopeNum;
1050  k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
1051  slopeDen) + constTerm;
1052  }
1053  else
1054  k= (int) (((long) slopeNum*((i+1)-newtonPolyg[indZero][1])) / slopeDen)
1055  + constTerm;
1056  }
1057  else
1058  {
1059  if (negativeSlope)
1060  k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
1061  slopeDen) + constTerm;
1062  else
1063  k= (int) ((long) slopeNum*((i+1)-newtonPolyg[indZero][1])) / slopeDen
1064  + constTerm;
1065  }
1066  if (i + 1 > maxY || i + 1 < minY)
1067  {
1068  result [i]= 0;
1069  continue;
1070  }
1071 
1072  point [0]= k;
1073  point [1]= i + 1;
1074  if (!isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
1075  k= 0;
1076  result [i]= k;
1077  }
1078 
1079  delete [] point;
1080 
1081  for (int i= 0; i < sizeOfNewtonPolygon; i++)
1082  delete [] newtonPolyg[i];
1083  delete [] newtonPolyg;
1084 
1085  return result;
1086 }

◆ copy()

CFArray copy ( const CFList &  list)

write elements of list into an array

Returns
an array of polys

Definition at line 364 of file facFqBivarUtil.cc.

365 {
366  CFArray array= CFArray (list.length());
367  int j= 0;
368  for (CFListIterator i= list; i.hasItem(); i++, j++)
369  array[j]= i.getItem();
370  return array;
371 }

◆ decompress() [1/3]

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

as above

Definition at line 63 of file facFqBivarUtil.cc.

64 {
65  for (CFAFListIterator i= factors; i.hasItem(); i++)
66  i.getItem()= CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
67  i.getItem().exp());
68 }

◆ decompress() [2/3]

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

as above

Definition at line 57 of file facFqBivarUtil.cc.

58 {
59  for (CFFListIterator i= factors; i.hasItem(); i++)
60  i.getItem()= CFFactor (N (i.getItem().factor()), i.getItem().exp());
61 }

◆ decompress() [3/3]

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

decompress a list of polys factors using the map N

Definition at line 51 of file facFqBivarUtil.cc.

52 {
53  for (CFListIterator i= factors; i.hasItem(); i++)
54  i.getItem()= N (i.getItem());
55 }

◆ FqInExtensionHelper()

static bool FqInExtensionHelper ( const CanonicalForm &  F,
const CanonicalForm &  gamma,
const CanonicalForm &  delta,
CFList &  source,
CFList &  dest 
)
inlinestatic

Definition at line 139 of file facFqBivarUtil.cc.

142 {
143  bool result= false;
144  if (F.inBaseDomain())
145  return result;
146  else if (F.inCoeffDomain())
147  {
148  if (!fdivides (gamma, F))
149  return true;
150  else
151  {
152  int pos= findItem (source, F);
153  if (pos > 0)
154  return false;
155  Variable a;
156  hasFirstAlgVar (F, a);
157  int bound= ipower (getCharacteristic(), degree (getMipo (a)));
158  CanonicalForm buf= 1;
159  for (int i= 1; i < bound; i++)
160  {
161  buf *= gamma;
162  if (buf == F)
163  {
164  source.append (buf);
165  dest.append (power (delta, i));
166  return false;
167  }
168  }
169  return true;
170  }
171  }
172  else
173  {
174  for (CFIterator i= F; i.hasTerms(); i++)
175  {
176  result= FqInExtensionHelper (i.coeff(), gamma, delta, source, dest);
177  if (result == true)
178  return result;
179  }
180  }
181  return result;
182 }

◆ getCoeffs() [1/4]

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

extract coefficients of $ x^i $ for $i\geq k$ where $ x $ is a variable of level 1

Returns
coefficients of $ x^i $ for $i\geq k$
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&)}

Definition at line 599 of file facFqBivarUtil.cc.

600 {
601  ASSERT (F.isUnivariate() || F.inCoeffDomain(), "univariate input expected");
602  if (degree (F, 2) < k)
603  return CFArray();
604 
605  CFArray result= CFArray (degree (F) - k + 1);
606  CFIterator j= F;
607  for (int i= degree (F); i >= k; i--)
608  {
609  if (j.exp() == i)
610  {
611  result [i - k]= j.coeff();
612  j++;
613  if (!j.hasTerms())
614  return result;
615  }
616  else
617  result[i - k]= 0;
618  }
619  return result;
620 }

◆ getCoeffs() [2/4]

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

extract coefficients of $ x^i $ for $i\geq k$ where $ x $ is a variable of level 1

Returns
coefficients of $ x^i $ for $i\geq k$
See also
{getCoeffs (const CanonicalForm&, const int), getCoeffs (const CanonicalForm&, const int, const int, const int, const Variable&, const CanonicalForm&, const mat_zz_p&)}

Definition at line 622 of file facFqBivarUtil.cc.

623 {
624  ASSERT (F.isUnivariate() || F.inCoeffDomain(), "univariate input expected");
625  if (degree (F, 2) < k)
626  return CFArray ();
627 
628  int d= degree (getMipo (alpha));
629  CFArray result= CFArray ((degree (F) - k + 1)*d);
630  CFIterator j= F;
631  CanonicalForm buf;
632  CFIterator iter;
633  for (int i= degree (F); i >= k; i--)
634  {
635  if (j.exp() == i)
636  {
637  iter= j.coeff();
638  for (int l= degree (j.coeff(), alpha); l >= 0; l--)
639  {
640  if (iter.exp() == l)
641  {
642  result [(i - k)*d + l]= iter.coeff();
643  iter++;
644  if (!iter.hasTerms())
645  break;
646  }
647  }
648  j++;
649  if (!j.hasTerms())
650  return result;
651  }
652  else
653  {
654  for (int l= 0; l < d; l++)
655  result[(i - k)*d + l]= 0;
656  }
657  }
658  return result;
659 }

◆ getCoeffs() [3/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 $ x^i $ for $i\geq k$ where $ x $ is a variable of level 1

Returns
coefficients of $ x^i $ for $i\geq k$
See also
{getCoeffs (const CanonicalForm&, const int, const Variable& alpha), getCoeffs (const CanonicalForm&, const int)}

Definition at line 663 of file facFqBivarUtil.cc.

666 {
667  ASSERT (G.isUnivariate() || G.inCoeffDomain(), "univariate input expected");
668  CanonicalForm F= G (G.mvar() - evaluation, G.mvar());
669  if (F.isZero())
670  return CFArray ();
671 
672  Variable y= Variable (2);
673  F= F (power (y, degMipo), y);
674  F= F (y, alpha);
675  zz_pX NTLF= convertFacCF2NTLzzpX (F);
676  NTLF.rep.SetLength (l*degMipo);
677  NTLF.rep= M*NTLF.rep;
678  NTLF.normalize();
679  F= convertNTLzzpX2CF (NTLF, y);
680 
681  if (degree (F, 2) < k)
682  return CFArray();
683 
684  CFArray result= CFArray (degree (F) - k + 1);
685 
686  CFIterator j= F;
687  for (int i= degree (F); i >= k; i--)
688  {
689  if (j.exp() == i)
690  {
691  result [i - k]= j.coeff();
692  j++;
693  if (!j.hasTerms())
694  return result;
695  }
696  else
697  result[i - k]= 0;
698  }
699  return result;
700 }

◆ getCoeffs() [4/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 $ x^i $ for $i\geq k$ where $ x $ is a variable of level 1

Returns
coefficients of $ x^i $ for $i\geq k$
See also
{getCoeffs (const CanonicalForm&, const int, const Variable& alpha), getCoeffs (const CanonicalForm&, const int)}

Definition at line 705 of file facFqBivarUtil.cc.

708 {
709  ASSERT (G.isUnivariate() || G.inCoeffDomain(), "univariate input expected");
710  CanonicalForm F= G (G.mvar() - evaluation, G.mvar());
711  if (F.isZero())
712  return CFArray ();
713 
714  Variable y= Variable (2);
715  F= F (power (y, degMipo), y);
716  F= F (y, alpha);
717 
718  nmod_poly_t FLINTF;
719  nmod_mat_t MFLINTF, mulResult;
720  nmod_mat_init (MFLINTF, l*degMipo, 1, getCharacteristic());
721  nmod_mat_init (mulResult, l*degMipo, 1, getCharacteristic());
722 
723  convertFacCF2nmod_poly_t (FLINTF, F);
724 
725 #ifndef slong
726 #define slong long
727 #endif
728  slong i;
729 
730  for (i= 0; i < FLINTF->length; i++)
731  nmod_mat_entry (MFLINTF, i, 0)= FLINTF->coeffs[i];
732 
733  for (; i < MFLINTF->r; i++)
734  nmod_mat_entry (MFLINTF, i, 0)= 0;
735 
736  nmod_mat_mul (mulResult, M, MFLINTF);
737 
738  F= 0;
739  for (i= 0; i < mulResult->r; i++)
740  F += CanonicalForm ((long) nmod_mat_entry (mulResult, i, 0))*power (y, i);
741 
742  nmod_mat_clear (MFLINTF);
743  nmod_mat_clear (mulResult);
744  nmod_poly_clear(FLINTF);
745 
746  if (degree (F, 2) < k)
747  return CFArray();
748 
749  CFArray result= CFArray (degree (F) - k + 1);
750 
751  CFIterator j= F;
752  for (int i= degree (F); i >= k; i--)
753  {
754  if (j.exp() == i)
755  {
756  result [i - k]= j.coeff();
757  j++;
758  if (!j.hasTerms())
759  return result;
760  }
761  else
762  result[i - k]= 0;
763  }
764  return result;
765 }

◆ GFInExtensionHelper()

static bool GFInExtensionHelper ( const CanonicalForm &  F,
const int  number 
)
inlinestatic

Definition at line 111 of file facFqBivarUtil.cc.

112 {
113  if (F.isOne()) return false;
114  InternalCF* buf;
115  int exp;
116  bool result= false;
117  if (F.inBaseDomain())
118  {
119  buf= F.getval();
120  exp= imm2int (buf);
121  if (exp%number != 0)
122  return true;
123  else
124  return result;
125  }
126  else
127  {
128  for (CFIterator i= F; i.hasTerms(); i++)
129  {
130  result= GFInExtensionHelper (i.coeff(), number);
131  if (result == true)
132  return result;
133  }
134  }
135  return result;
136 }

◆ indexUpdate()

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

update index

Definition at line 373 of file facFqBivarUtil.cc.

375 {
376  noSubset= false;
377  if (subsetSize > setSize)
378  {
379  noSubset= true;
380  return;
381  }
382  int * v= new int [setSize];
383  for (int i= 0; i < setSize; i++)
384  v[i]= index[i];
385  if (subsetSize == 1)
386  {
387  v[0]= v[0] - 1;
388  if (v[0] >= setSize)
389  {
390  noSubset= true;
391  delete [] v;
392  return;
393  }
394  }
395  else
396  {
397  if (v[subsetSize - 1] - v[0] + 1 == subsetSize && v[0] > 1)
398  {
399  if (v[0] + subsetSize - 1 > setSize)
400  {
401  noSubset= true;
402  delete [] v;
403  return;
404  }
405  v[0]= v[0] - 1;
406  for (int i= 1; i < subsetSize - 1; i++)
407  v[i]= v[i - 1] + 1;
408  v[subsetSize - 1]= v[subsetSize - 2];
409  }
410  else
411  {
412  if (v[0] + subsetSize - 1 > setSize)
413  {
414  noSubset= true;
415  delete [] v;
416  return;
417  }
418  for (int i= 1; i < subsetSize - 1; i++)
419  v[i]= v[i - 1] + 1;
420  v[subsetSize - 1]= v[subsetSize - 2];
421  }
422  }
423  for (int i= 0; i < setSize; i++)
424  index[i]= v[i];
425  delete [] v;
426 }

◆ 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()

Definition at line 184 of file facFqBivarUtil.cc.

187 {
188  bool result;
189  if (CFFactory::gettype() == GaloisFieldDomain)
190  {
191  int p= getCharacteristic();
192  int orderFieldExtension= ipower (p, getGFDegree()) - 1;
193  int order= ipower (p, k) - 1;
194  int number= orderFieldExtension/order;
195  result= GFInExtensionHelper (F, number);
196  return result;
197  }
198  else
199  {
200  result= FqInExtensionHelper (F, gamma, delta, source, dest);
201  return result;
202  }
203 }

◆ 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

Definition at line 459 of file facFqBivarUtil.cc.

462 {
463  Variable x= Variable (2);
464  Variable y= Variable (1);
465  CanonicalForm xToL= power (x, l);
466  CanonicalForm q,r;
467  CanonicalForm logDeriv;
468 
469  TIMING_START (fac_log_deriv_div);
470  q= newtonDiv (F, G, xToL);
471  TIMING_END_AND_PRINT (fac_log_deriv_div, "time for division in logderiv1: ");
472 
473  TIMING_START (fac_log_deriv_mul);
474  logDeriv= mulMod2 (q, deriv (G, y), xToL);
475  TIMING_END_AND_PRINT (fac_log_deriv_mul, "time to multiply in logderiv1: ");
476 
477  if (degree (logDeriv, x) == 0)
478  {
479  Q= q;
480  return CFArray();
481  }
482 
483  int j= degree (logDeriv, y) + 1;
484  CFArray result= CFArray (j);
485  CFIterator ii;
486  for (CFIterator i= logDeriv; i.hasTerms() && !logDeriv.isZero(); i++)
487  {
488  if (i.coeff().inCoeffDomain())
489  result[0] += i.coeff()*power (x,i.exp());
490  else
491  {
492  for (ii= i.coeff(); ii.hasTerms(); ii++)
493  result[ii.exp()] += ii.coeff()*power (x,i.exp());
494  }
495  }
496  Q= q;
497  return result;
498 }

◆ 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

Definition at line 501 of file facFqBivarUtil.cc.

504 {
505  Variable x= Variable (2);
506  Variable y= Variable (1);
507  CanonicalForm xToL= power (x, l);
508  CanonicalForm xToOldL= power (x, oldL);
509  CanonicalForm xToLOldL= power (x, l-oldL);
510  CanonicalForm q,r;
511  CanonicalForm logDeriv;
512 
513  CanonicalForm bufF;
514  TIMING_START (fac_log_deriv_pre);
515  if ((oldL > 100 && l - oldL < 50) || (oldL < 100 && l - oldL < 30))
516  {
517  bufF= F;
518  CanonicalForm oldF= mulMod2 (G, oldQ, xToL);
519  bufF -= oldF;
520  bufF= div (bufF, xToOldL);
521  }
522  else
523  {
524  //middle product style computation of [G*oldQ]^{l}_{oldL}
525  CanonicalForm G3= div (G, xToOldL);
526  CanonicalForm Up= mulMod2 (G3, oldQ, xToLOldL);
527  CanonicalForm xToOldL2= power (x, (oldL+1)/2);
528  CanonicalForm G2= mod (G, xToOldL);
529  CanonicalForm G1= div (G2, xToOldL2);
530  CanonicalForm G0= mod (G2, xToOldL2);
531  CanonicalForm oldQ1= div (oldQ, xToOldL2);
532  CanonicalForm oldQ0= mod (oldQ, xToOldL2);
533  CanonicalForm Mid;
534  if (oldL % 2 == 1)
535  Mid= mulMod2 (G1, oldQ1*x, xToLOldL);
536  else
537  Mid= mulMod2 (G1, oldQ1, xToLOldL);
538  //computation of Low might be faster using a real middle product?
539  CanonicalForm Low= mulMod2 (G0, oldQ1, xToOldL)+mulMod2 (G1, oldQ0, xToOldL);
540  Low= div (Low, power (x, oldL/2));
541  Low= mod (Low, xToLOldL);
542  Up += Mid + Low;
543  bufF= div (F, xToOldL);
544  bufF -= Up;
545  }
546  TIMING_END_AND_PRINT (fac_log_deriv_pre, "time to preprocess: ");
547 
548  TIMING_START (fac_log_deriv_div);
549  if (l-oldL > 0)
550  q= newtonDiv (bufF, G, xToLOldL);
551  else
552  q= 0;
553  q *= xToOldL;
554  q += oldQ;
555  TIMING_END_AND_PRINT (fac_log_deriv_div, "time for div in logderiv2: ");
556 
557  TIMING_START (fac_log_deriv_mul);
558  logDeriv= mulMod2 (q, deriv (G, y), xToL);
559  TIMING_END_AND_PRINT (fac_log_deriv_mul, "time for mul in logderiv2: ");
560 
561  if (degree (logDeriv, x) == 0)
562  {
563  Q= q;
564  return CFArray();
565  }
566 
567  int j= degree (logDeriv,y) + 1;
568  CFArray result= CFArray (j);
569  CFIterator ii;
570  for (CFIterator i= logDeriv; i.hasTerms() && !logDeriv.isZero(); i++)
571  {
572  if (i.coeff().inCoeffDomain())
573  result[0] += i.coeff()*power (x,i.exp());
574  else
575  {
576  for (ii= i.coeff(); ii.hasTerms(); ii++)
577  result[ii.exp()] += ii.coeff()*power (x,i.exp());
578  }
579  }
580  Q= q;
581  return result;
582 }

◆ 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()

Definition at line 206 of file facFqBivarUtil.cc.

208 {
209  int k= info.getGFDegree();
210  Variable beta= info.getAlpha();
211  CanonicalForm primElem= info.getGamma();
212  CanonicalForm imPrimElem= info.getDelta();
213  if (k > 1)
214  return GFMapDown (F, k);
215  else if (k == 1)
216  return F;
217  if (/*k==0 &&*/ beta == Variable (1))
218  return F;
219  else /*if (k==0 && beta != Variable (1))*/
220  return mapDown (F, imPrimElem, primElem, beta, source, dest);
221 }

◆ multiplicity()

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

determine multiplicity of the factors

Returns
a list of factors of F with their multiplicity

Definition at line 436 of file facFqBivarUtil.cc.

437 {
438  if (F.inCoeffDomain())
439  return CFFList (CFFactor (F, 1));
440  CFFList result;
441  int multi= 0;
442  CanonicalForm quot;
443  for (CFListIterator i= factors; i.hasItem(); i++)
444  {
445  while (fdivides (i.getItem(), F, quot))
446  {
447  multi++;
448  F= quot;
449  }
450  if (multi > 0)
451  result.append (CFFactor (i.getItem(), multi));
452  multi= 0;
453  }
454  return result;
455 }

◆ normalize() [1/2]

void normalize ( CFFList &  factors)

as above

Definition at line 297 of file facFqBivarUtil.cc.

298 {
299  CanonicalForm lcinv;
300  for (CFFListIterator i= factors; i.hasItem(); i++)
301  {
302  lcinv= 1/ Lc (i.getItem().factor());
303  i.getItem()= CFFactor (i.getItem().factor()*lcinv,
304  i.getItem().exp());
305  }
306  return;
307 }

◆ normalize() [2/2]

void normalize ( CFList &  factors)

normalize factors, i.e. make factors monic

Definition at line 286 of file facFqBivarUtil.cc.

287 {
288  CanonicalForm lcinv;
289  for (CFListIterator i= factors; i.hasItem(); i++)
290  {
291  lcinv= 1/Lc (i.getItem());
292  i.getItem() *= lcinv;
293  }
294  return;
295 }

◆ recSubstituteCheck()

int recSubstituteCheck ( const CanonicalForm &  F,
const int  d 
)

Definition at line 1205 of file facFqBivarUtil.cc.

1206 {
1207  if (F.inCoeffDomain())
1208  return 0;
1209  Variable x= Variable (1);
1210  if (degree (F, x) <= 1)
1211  return 0;
1212  CanonicalForm f= swapvar (F, F.mvar(), x);
1213  int sizef= 0;
1214  for (CFIterator i= f; i.hasTerms(); i++, sizef++)
1215  {
1216  if (i.exp() == 1)
1217  return 0;
1218  }
1219  int * expf= new int [sizef];
1220  int j= 0;
1221  for (CFIterator i= f; i.hasTerms(); i++, j++)
1222  {
1223  expf [j]= i.exp();
1224  }
1225 
1226  int indf= sizef - 1;
1227  if (expf[indf] == 0)
1228  indf--;
1229 
1230  if ((d%expf [indf] != 0 && expf[indf]%d != 0) || (expf[indf] == 1))
1231  {
1232  delete [] expf;
1233  return 0;
1234  }
1235 
1236  int result;
1237  if (d%expf [indf] == 0)
1238  result= expf[indf];
1239  else
1240  result= d;
1241  for (int i= indf - 1; i >= 0; i--)
1242  {
1243  if (expf [i]%result != 0)
1244  {
1245  delete [] expf;
1246  return 0;
1247  }
1248  }
1249 
1250  delete [] expf;
1251  return result;
1252 }

◆ reverseSubst() [1/2]

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

reverse a substitution x^d->x

Definition at line 1309 of file facFqBivarUtil.cc.

1310 {
1311  for (CFListIterator i= L; i.hasItem(); i++)
1312  i.getItem()= reverseSubst (i.getItem(), d, x);
1313 }

◆ 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

Definition at line 1295 of file facFqBivarUtil.cc.

1296 {
1297  if (d <= 1)
1298  return F;
1299  if (degree (F, x) <= 0)
1300  return F;
1301  CanonicalForm f= swapvar (F, x, F.mvar());
1302  CanonicalForm result= 0;
1303  for (CFIterator i= f; i.hasTerms(); i++)
1304  result += i.coeff()*power (f.mvar(), d*i.exp());
1305  return swapvar (result, x, F.mvar());
1306 }

◆ 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.

Definition at line 309 of file facFqBivarUtil.cc.

311 {
312  int r= elements.size();
313  int i= 0;
314  CFList result;
315  noSubset= false;
316  if (index[s - 1] == 0)
317  {
318  while (i < s)
319  {
320  index[i]= i + 1;
321  result.append (elements[i]);
322  i++;
323  }
324  return result;
325  }
326  int buf;
327  int k;
328  bool found= false;
329  if (index[s - 1] == r)
330  {
331  if (index[0] == r - s + 1)
332  {
333  noSubset= true;
334  return result;
335  }
336  else {
337  while (found == false)
338  {
339  if (index[s - 2 - i] < r - i - 1)
340  found= true;
341  i++;
342  }
343  buf= index[s - i - 1];
344  k= 0;
345  while (s - i - 1 + k < s)
346  {
347  index[s - i - 1 + k]= buf + k + 1;
348  k++;
349  }
350  }
351  for (int j= 0; j < s; j++)
352  result.append (elements[index[j] - 1]);
353  return result;
354  }
355  else
356  {
357  index[s - 1] += 1;
358  for (int j= 0; j < s; j++)
359  result.append (elements[index[j] - 1]);
360  return result;
361  }
362 }

◆ 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

Definition at line 428 of file facFqBivarUtil.cc.

429 {
430  int result= 0;
431  for (CFListIterator i= S; i.hasItem(); i++)
432  result += degree (i.getItem(), Variable (1));
433  return result;
434 }

◆ subst()

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

substitute x^d by x in F

Definition at line 1275 of file facFqBivarUtil.cc.

1276 {
1277  if (d <= 1)
1278  {
1279  A= F;
1280  return;
1281  }
1282  if (degree (F, x) <= 0)
1283  {
1284  A= F;
1285  return;
1286  }
1287  CanonicalForm C= 0;
1288  CanonicalForm f= swapvar (F, x, F.mvar());
1289  for (CFIterator i= f; i.hasTerms(); i++)
1290  C += i.coeff()*power (f.mvar(), i.exp()/ d);
1291  A= swapvar (C, x, F.mvar());
1292 }

◆ substituteCheck() [1/3]

static int substituteCheck ( const CanonicalForm &  F,
const CanonicalForm &  G 
)
static

Definition at line 1126 of file facFqBivarUtil.cc.

1127 {
1128  if (F.inCoeffDomain() || G.inCoeffDomain())
1129  return 0;
1130  Variable x= Variable (1);
1131  if (degree (F, x) <= 1 || degree (G, x) <= 1)
1132  return 0;
1133  CanonicalForm f= swapvar (F, F.mvar(), x);
1134  CanonicalForm g= swapvar (G, G.mvar(), x);
1135  int sizef= 0;
1136  int sizeg= 0;
1137  for (CFIterator i= f; i.hasTerms(); i++, sizef++)
1138  {
1139  if (i.exp() == 1)
1140  return 0;
1141  }
1142  for (CFIterator i= g; i.hasTerms(); i++, sizeg++)
1143  {
1144  if (i.exp() == 1)
1145  return 0;
1146  }
1147  int * expf= new int [sizef];
1148  int * expg= new int [sizeg];
1149  int j= 0;
1150  for (CFIterator i= f; i.hasTerms(); i++, j++)
1151  {
1152  expf [j]= i.exp();
1153  }
1154  j= 0;
1155  for (CFIterator i= g; i.hasTerms(); i++, j++)
1156  {
1157  expg [j]= i.exp();
1158  }
1159 
1160  int indf= sizef - 1;
1161  int indg= sizeg - 1;
1162  if (expf[indf] == 0)
1163  indf--;
1164  if (expg[indg] == 0)
1165  indg--;
1166 
1167  if ((expg[indg]%expf [indf] != 0 && expf[indf]%expg[indg] != 0) ||
1168  (expg[indg] == 1 && expf[indf] == 1))
1169  {
1170  delete [] expg;
1171  delete [] expf;
1172  return 0;
1173  }
1174 
1175  int result;
1176  if (expg [indg]%expf [indf] == 0)
1177  result= expf[indf];
1178  else
1179  result= expg[indg];
1180  for (int i= indf - 1; i >= 0; i--)
1181  {
1182  if (expf [i]%result != 0)
1183  {
1184  delete [] expf;
1185  delete [] expg;
1186  return 0;
1187  }
1188  }
1189 
1190  for (int i= indg - 1; i >= 0; i--)
1191  {
1192  if (expg [i]%result != 0)
1193  {
1194  delete [] expf;
1195  delete [] expg;
1196  return 0;
1197  }
1198  }
1199 
1200  delete [] expg;
1201  delete [] expf;
1202  return result;
1203 }

◆ substituteCheck() [2/3]

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

Definition at line 1089 of file facFqBivarUtil.cc.

1090 {
1091  if (F.inCoeffDomain())
1092  return 0;
1093  if (degree (F, x) < 0)
1094  return 0;
1095  CanonicalForm f= swapvar (F, F.mvar(), x);
1096  int sizef= 0;
1097  for (CFIterator i= f; i.hasTerms(); i++, sizef++)
1098  {
1099  if (i.exp() == 1)
1100  return 0;
1101  }
1102  int * expf= new int [sizef];
1103  int j= 0;
1104  for (CFIterator i= f; i.hasTerms(); i++, j++)
1105  expf [j]= i.exp();
1106 
1107  int indf= sizef - 1;
1108  if (expf[indf] == 0)
1109  indf--;
1110 
1111  int result= expf[indf];
1112  for (int i= indf - 1; i >= 0; i--)
1113  {
1114  if (expf [i]%result != 0)
1115  {
1116  delete [] expf;
1117  return 0;
1118  }
1119  }
1120 
1121  delete [] expf;
1122  return result;
1123 }

◆ substituteCheck() [3/3]

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

Definition at line 1254 of file facFqBivarUtil.cc.

1255 {
1256  ASSERT (L.length() > 1, "expected a list of at least two elements");
1257  if (L.length() < 2)
1258  return 0;
1259  CFListIterator i= L;
1260  i++;
1261  int result= substituteCheck (L.getFirst(), i.getItem());
1262  if (result <= 1)
1263  return result;
1264  i++;
1265  for (;i.hasItem(); i++)
1266  {
1267  result= recSubstituteCheck (i.getItem(), result);
1268  if (result <= 1)
1269  return result;
1270  }
1271  return result;
1272 }

◆ swapDecompress()

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

swap Variables in factors, then decompress factors

Definition at line 97 of file facFqBivarUtil.cc.

98 {
99  Variable x= Variable (1);
100  Variable y= Variable (2);
101  for (CFListIterator i= factors; i.hasItem(); i++)
102  {
103  if (swap)
104  i.getItem()= swapvar (i.getItem(), x, y);
105  i.getItem()= N (i.getItem());
106  }
107  return;
108 }

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_log_deriv_div  ) &

◆ writeInMatrix()

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

write A into M starting at row startIndex

Definition at line 586 of file facFqBivarUtil.cc.

589 {
590  ASSERT (A.size () - startIndex >= 0, "wrong starting index");
591  ASSERT (A.size () - startIndex <= M.rows(), "wrong starting index");
592  ASSERT (column > 0 && column <= M.columns(), "wrong column");
593  if (A.size() - startIndex <= 0) return;
594  int j= 1;
595  for (int i= startIndex; i < A.size(); i++, j++)
596  M (j, column)= A [i];
597 }

Variable Documentation

◆ factors2

const CFList& factors2
Initial value:
{
for (CFListIterator i= factors2; i.hasItem(); i++)
{
if (!i.getItem().inCoeffDomain())
factors1.append (i.getItem());
}
return

Definition at line 42 of file facFqBivarUtil.cc.

ExtensionInfo::getGFDegree
int getGFDegree() const
getter
Definition: ExtensionInfo.h:139
ExtensionInfo::getBeta
Variable getBeta() const
getter
Definition: ExtensionInfo.h:118
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
k
int k
Definition: cfEzgcd.cc:92
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
x
Variable x
Definition: cfModGcd.cc:4023
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
result
return result
Definition: facAbsBiFact.cc:76
CFArray
Array< CanonicalForm > CFArray
Definition: canonicalform.h:390
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
CanonicalForm::inBaseDomain
bool inBaseDomain() const
Definition: canonicalform.cc:101
isIrreducible
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
Definition: gengftables-conway.cc:76
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
CFFList
List< CFFactor > CFFList
Definition: canonicalform.h:386
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
g
g
Definition: cfModGcd.cc:4031
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
InternalCF
virtual class for internal CanonicalForm's
Definition: int_cf.h:41
iter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
gf_name
char gf_name
Definition: gfops.cc:52
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition: canonicalform.h:339
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
CxxTest::delta
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
CFIterator::hasTerms
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
Definition: cf_iter_inline.cc:75
CanonicalForm
factory's main class
Definition: canonicalform.h:77
found
bool found
Definition: facFactorize.cc:56
reverseSubst
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
Definition: facFqBivarUtil.cc:1295
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:243
evaluation
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:56
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:22
factors2
const CFList & factors2
Definition: facFqBivarUtil.cc:42
i
int i
Definition: cfEzgcd.cc:125
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
Array
Definition: ftmpl_array.h:17
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
M
#define M
Definition: sirandom.c:24
buf
int status int void * buf
Definition: si_signals.h:59
Array::size
int size() const
Definition: ftmpl_array.cc:92
TIMING_START
TIMING_START(fac_alg_resultant)
ExtensionInfo::getGamma
CanonicalForm getGamma() const
getter
Definition: ExtensionInfo.h:125
CFIterator::exp
CF_NO_INLINE int exp() const
get the current exponent
Definition: cf_iter_inline.cc:105
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
setCharacteristic
void setCharacteristic(int c)
Definition: cf_char.cc:23
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
CFAFactor
AFactor< CanonicalForm > CFAFactor
Definition: canonicalform.h:382
Variable::level
int level() const
Definition: factory.h:134
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
mulMod2
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2853
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_algorithm.cc:338
beta
Variable beta
Definition: facAbsFact.cc:99
ExtensionInfo::getDelta
CanonicalForm getDelta() const
getter
Definition: ExtensionInfo.h:132
substituteCheck
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
Definition: facFqBivarUtil.cc:1089
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
FqInExtensionHelper
static bool FqInExtensionHelper(const CanonicalForm &F, const CanonicalForm &gamma, const CanonicalForm &delta, CFList &source, CFList &dest)
Definition: facFqBivarUtil.cc:139
getGFDegree
int getGFDegree()
Definition: cf_char.cc:56
exp
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:358
Factor
Definition: ftmpl_factor.h:18
div
CF_NO_INLINE CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm div, mod ( const CanonicalForm & lhs, const CanonicalForm & rhs )
Definition: cf_inline.cc:553
newtonPolygon
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
Definition: cfNewtonPolygon.cc:282
newtonDiv
void newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
Definition: facMul.cc:376
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
GFInExtensionHelper
static bool GFInExtensionHelper(const CanonicalForm &F, const int number)
Definition: facFqBivarUtil.cc:111
List::length
int length() const
Definition: ftmpl_list.cc:273
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
isInPolygon
bool isInPolygon(int **points, int sizePoints, int *point)
check if point is inside a polygon described by points
Definition: cfNewtonPolygon.cc:383
imm2int
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
Variable
factory's class for variables
Definition: factory.h:117
bound
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
CFIterator::coeff
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
Definition: cf_iter_inline.cc:88
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
findItem
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:37
l
int l
Definition: cfEzgcd.cc:93
polygon
int polygon(int **points, int sizePoints)
compute a polygon
Definition: cfNewtonPolygon.cc:172
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
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
recSubstituteCheck
int recSubstituteCheck(const CanonicalForm &F, const int d)
Definition: facFqBivarUtil.cc:1205
p
int p
Definition: cfModGcd.cc:4019
List
Definition: ftmpl_list.h:20
swap
#define swap(_i, _j)
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
Q
#define Q
Definition: sirandom.c:25
ExtensionInfo::getAlpha
Variable getAlpha() const
getter
Definition: ExtensionInfo.h:111
G
static TreeM * G
Definition: janet.cc:32
CFFactor
Factor< CanonicalForm > CFFactor
Definition: canonicalform.h:385
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
index
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
A
#define A
Definition: sirandom.c:23
info
const ExtensionInfo & info
< [in] sqrfree poly
Definition: facFqFactorize.h:38
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
slong
#define slong
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:248
ListIterator
Definition: ftmpl_list.h:17
CanonicalForm::getval
InternalCF * getval() const
Definition: canonicalform.cc:31
Generated on Tue Mar 24 2020 14:10:46 for My Project by   doxygen 1.8.17 for Singular debian-1:4.1.1-p2+ds-4build2