My Project
facFqBivarUtil.cc
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facFqBivarUtil.cc
5  *
6  * This file provides utility functions for bivariate factorization
7  *
8  * @author Martin Lee
9  *
10  **/
11 /*****************************************************************************/
12 
13 
14 #include "config.h"
15 
16 
17 #include "timing.h"
18 
19 #include "cf_map.h"
20 #include "cf_map_ext.h"
22 #include "ExtensionInfo.h"
23 #include "cf_algorithm.h"
24 #include "cf_factory.h"
25 #include "cf_util.h"
26 #include "imm.h"
27 #include "cf_iter.h"
28 #include "facFqBivarUtil.h"
29 #include "cfNewtonPolygon.h"
30 #include "facHensel.h"
31 #include "facMul.h"
32 
33 #ifdef HAVE_FLINT
34 #include "FLINTconvert.h"
35 #endif
36 
37 TIMING_DEFINE_PRINT(fac_log_deriv_div)
38 TIMING_DEFINE_PRINT(fac_log_deriv_mul)
39 TIMING_DEFINE_PRINT(fac_log_deriv_pre)
40 
41 void append (CFList& factors1, const CFList& factors2)
42 {
43  for (CFListIterator i= factors2; i.hasItem(); i++)
44  {
45  if (!i.getItem().inCoeffDomain())
46  factors1.append (i.getItem());
47  }
48  return;
49 }
50 
51 void decompress (CFList& factors, const CFMap& N)
52 {
53  for (CFListIterator i= factors; i.hasItem(); i++)
54  i.getItem()= N (i.getItem());
55 }
56 
57 void decompress (CFFList& factors, const CFMap& N)
58 {
59  for (CFFListIterator i= factors; i.hasItem(); i++)
60  i.getItem()= CFFactor (N (i.getItem().factor()), i.getItem().exp());
61 }
62 
63 void decompress (CFAFList& factors, const CFMap& N)
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 }
69 
70 void appendSwapDecompress (CFList& factors1, const CFList& factors2,
71  const CFList& factors3, const bool swap1,
72  const bool swap2, const CFMap& N)
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 }
96 
97 void swapDecompress (CFList& factors, const bool swap, const CFMap& N)
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 }
109 
110 static inline
111 bool GFInExtensionHelper (const CanonicalForm& F, const int number)
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 }
137 
138 static inline
139 bool FqInExtensionHelper (const CanonicalForm& F, const CanonicalForm& gamma,
140  const CanonicalForm& delta, CFList& source,
141  CFList& dest)
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 }
183 
184 bool isInExtension (const CanonicalForm& F, const CanonicalForm& gamma,
185  const int k, const CanonicalForm& delta,
186  CFList& source, CFList& dest)
187 {
188  bool result;
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 }
204 
206 mapDown (const CanonicalForm& F, const ExtensionInfo& info, CFList& source,
207  CFList& dest)
208 {
209  int k= info.getGFDegree();
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 }
222 
223 void appendTestMapDown (CFList& factors, const CanonicalForm& f,
224  const ExtensionInfo& info, CFList& source, CFList& dest)
225 {
226  int k= info.getGFDegree();
230  CanonicalForm gamma= info.getGamma();
231  CanonicalForm g= f;
232  int degMipoBeta=0;
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 }
265 
266 void
268  const ExtensionInfo& info, CFList& source, CFList& dest)
269 {
270  int k= info.getGFDegree();
273  CanonicalForm gamma= info.getGamma();
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 }
285 
286 void normalize (CFList& factors)
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 }
296 
297 void normalize (CFFList& factors)
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 }
308 
309 CFList subset (int index [], const int& s, const CFArray& elements,
310  bool& noSubset)
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 }
363 
364 CFArray copy (const CFList& list)
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 }
372 
373 void indexUpdate (int index [], const int& subsetSize, const int& setSize,
374  bool& noSubset)
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 }
427 
428 int subsetDegree (const CFList& S)
429 {
430  int result= 0;
431  for (CFListIterator i= S; i.hasItem(); i++)
432  result += degree (i.getItem(), Variable (1));
433  return result;
434 }
435 
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 }
456 
457 #ifdef HAVE_NTL
458 CFArray
461  )
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 }
499 
500 CFArray
502  int oldL, const CanonicalForm& oldQ, CanonicalForm& Q
503  )
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 }
583 #endif
584 
585 void
586 writeInMatrix (CFMatrix& M, const CFArray& A, const int column,
587  const int startIndex
588  )
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 }
598 
599 CFArray getCoeffs (const CanonicalForm& F, const int k)
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 }
621 
622 CFArray getCoeffs (const CanonicalForm& F, const int k, const Variable& alpha)
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;
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 }
660 
661 #ifdef HAVE_NTL
662 CFArray
663 getCoeffs (const CanonicalForm& G, const int k, const int l, const int degMipo,
664  const Variable& alpha, const CanonicalForm& evaluation,
665  const mat_zz_p& M)
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 }
701 #endif
702 
703 #ifdef HAVE_FLINT
704 CFArray
705 getCoeffs (const CanonicalForm& G, const int k, const int l, const int degMipo,
706  const Variable& alpha, const CanonicalForm& evaluation,
707  const nmod_mat_t M)
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 }
766 #endif
767 
768 int * computeBounds (const CanonicalForm& F, int& n, bool& isIrreducible)
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';
790  if (GF)
791  {
792  d= getGFDegree();
793  bufGFName=gf_name;
794  }
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
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 }
920 
921 int *
923  bool& isIrreducible)
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';
945  if (GF)
946  {
947  d= getGFDegree();
948  bufGFName=gf_name;
949  }
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
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 }
1087 
1088 int
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 }
1124 
1125 static int
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 }
1204 
1205 int recSubstituteCheck (const CanonicalForm& F, const int d)
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 }
1253 
1254 int substituteCheck (const CFList& L)
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 }
1273 
1274 void
1275 subst (const CanonicalForm& F, CanonicalForm& A, const int d, const Variable& x)
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 }
1293 
1295 reverseSubst (const CanonicalForm& F, const int d, const Variable& x)
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 }
1307 
1308 void
1309 reverseSubst (CFList& L, const int d, const Variable& x)
1310 {
1311  for (CFListIterator i= L; i.hasItem(); i++)
1312  i.getItem()= reverseSubst (i.getItem(), d, x);
1313 }
1314 
This file provides a class to store information about finite fields and extensions thereof.
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:255
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
#define swap(_i, _j)
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
AFactor< CanonicalForm > CFAFactor
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int degree(const CanonicalForm &f)
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
int getGFDegree()
Definition: cf_char.cc:75
Array< CanonicalForm > CFArray
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
List< CFFactor > CFFList
CanonicalForm Lc(const CanonicalForm &f)
Factor< CanonicalForm > CFFactor
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int l
Definition: cfEzgcd.cc:100
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
g
Definition: cfModGcd.cc:4090
bool isInPolygon(int **points, int sizePoints, int *point)
check if point is inside a polygon described by points
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
int polygon(int **points, int sizePoints)
compute a polygon
This file provides functions to compute the Newton polygon of a bivariate polynomial.
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
declarations of higher level algorithms.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define GaloisFieldDomain
Definition: cf_defs.h:18
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
Iterators for CanonicalForm's.
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
map polynomials
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:41
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:276
This file implements functions to map between extensions of finite fields.
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
FILE * f
Definition: checklibs.c:9
int size() const
Definition: ftmpl_array.cc:92
static int gettype()
Definition: cf_factory.h:28
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
CF_NO_INLINE int exp() const
get the current exponent
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
CF_NO_INLINE bool isZero() const
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
InternalCF * getval() const
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
bool inBaseDomain() const
bool isUnivariate() const
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:51
int getGFDegree() const
getter
CanonicalForm getGamma() const
getter
CanonicalForm getDelta() const
getter
Variable getAlpha() const
getter
Variable getBeta() const
getter
virtual class for internal CanonicalForm's
Definition: int_cf.h:47
T getFirst() const
Definition: ftmpl_list.cc:279
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
factory's class for variables
Definition: factory.h:127
int level() const
Definition: factory.h:143
CFFListIterator iter
Definition: facAbsBiFact.cc:53
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
const CanonicalForm int s
Definition: facAbsFact.cc:51
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
Variable beta
Definition: facAbsFact.cc:95
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
bool found
Definition: facFactorize.cc:55
static bool GFInExtensionHelper(const CanonicalForm &F, const int number)
CFFList multiplicity(CanonicalForm &F, const CFList &factors)
determine multiplicity of the factors
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
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
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
const CFList & factors2
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 fina...
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
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 normalize(CFList &factors)
normalize factors, i.e. make factors monic
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
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
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
void subst(const CanonicalForm &F, CanonicalForm &A, const int d, const Variable &x)
substitute x^d by x in F
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 copy(const CFList &list)
write elements of list into an array
int recSubstituteCheck(const CanonicalForm &F, const int d)
void swapDecompress(CFList &factors, const bool swap, const CFMap &N)
swap Variables in factors, then decompress factors
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
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 consid...
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)
static bool FqInExtensionHelper(const CanonicalForm &F, const CanonicalForm &gamma, const CanonicalForm &delta, CFList &source, CFList &dest)
void writeInMatrix(CFMatrix &M, const CFArray &A, const int column, const int startIndex)
write A into M starting at row startIndex
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
#define slong
void decompress(CFList &factors, const CFMap &N)
decompress a list of polys factors using the map N
This file provides utility functions for bivariate factorization.
const ExtensionInfo & info
< [in] sqrfree poly
int j
Definition: facHensel.cc:110
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
This file defines functions for Hensel lifting.
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2986
void newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
Definition: facMul.cc:380
This file defines functions for fast multiplication and division with remainder.
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
#define const
Definition: fegetopt.c:39
some useful template functions.
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
VAR char gf_name
Definition: gfops.cc:52
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int,...
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
STATIC_VAR TreeM * G
Definition: janet.cc:31
STATIC_VAR jList * Q
Definition: janet.cc:30
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25
int gcd(int a, int b)
Definition: walkSupport.cc:836