source: git/factory/NTLconvert.cc @ 6deedd

spielwiese
Last change on this file since 6deedd was a52291, checked in by Martin Lee <martinlee84@…>, 12 years ago
replacing MP_INT by mpz_t Conflicts: factory/cf_factory.h
  • Property mode set to 100644
File size: 38.8 KB
Line 
1/* $Id$ */
2#include "config.h"
3
4#include "cf_assert.h"
5
6#include "cf_defs.h"
7#include "canonicalform.h"
8#include "cf_iter.h"
9#include "fac_berlekamp.h"
10#include "fac_cantzass.h"
11#include "fac_univar.h"
12#include "fac_multivar.h"
13#include "fac_sqrfree.h"
14#include "cf_algorithm.h"
15
16#include "cf_gmp.h"
17
18#ifdef HAVE_NTL
19#ifndef NOSTREAMIO
20#ifdef HAVE_CSTDIO
21#include <cstdio>
22#else
23#include <stdio.h>
24#endif
25#endif
26#include <string.h>
27#include <NTL/ZZXFactoring.h>
28#include <NTL/ZZ_pXFactoring.h>
29#include <NTL/lzz_pXFactoring.h>
30#include <NTL/GF2XFactoring.h>
31#include <NTL/ZZ_pEXFactoring.h>
32#include <NTL/lzz_pEXFactoring.h>
33#include <NTL/GF2EXFactoring.h>
34#include <NTL/tools.h>
35#include <NTL/mat_ZZ.h>
36#include "int_int.h"
37#include <limits.h>
38#include "NTLconvert.h"
39
40#define Alloc(L) malloc(L)
41#define Free(A,L) free(A)
42
43void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
44
45
46long fac_NTL_char = -1;         // the current characterstic for NTL calls
47                                // -1: undefined
48#ifdef NTL_CLIENT               // in <NTL/tools.h>: using of name space NTL
49NTL_CLIENT
50#endif
51
52////////////////////////////////////////////////////////////////////////////////
53// NAME: convertFacCF2NTLZZpX                                                 //
54//                                                                            //
55// DESCRIPTION:                                                               //
56// Conversion routine for Factory-type canonicalform into ZZpX of NTL,        //
57// i.e. polynomials over F_p. As a precondition for correct execution,        //
58// the characteristic has to a a prime number.                                //
59//                                                                            //
60// INPUT:  A canonicalform f                                                  //
61// OUTPUT: The converted NTL-polynomial over F_p of type ZZpX                 //
62////////////////////////////////////////////////////////////////////////////////
63
64ZZ_pX convertFacCF2NTLZZpX(CanonicalForm f)
65{
66  ZZ_pX ntl_poly;
67
68  CFIterator i;
69  i=f;
70
71  int NTLcurrentExp=i.exp();
72  int largestExp=i.exp();
73  int k;
74
75  // we now build up the NTL-polynomial
76  ntl_poly.SetMaxLength(largestExp+1);
77
78  for (;i.hasTerms();i++)
79  {
80    for (k=NTLcurrentExp;k>i.exp();k--)
81    {
82      SetCoeff(ntl_poly,k,0);
83    }
84    NTLcurrentExp=i.exp();
85
86    CanonicalForm c=i.coeff();
87    if (!c.isImm()) c=c.mapinto(); //c%= getCharacteristic();
88    if (!c.isImm())
89    {  //This case will never happen if the characteristic is in fact a prime
90       // number, since all coefficients are represented as immediates
91       #ifndef NOSTREAMIO
92       cout<<"convertFacCF2NTLZZ_pX: coefficient not immediate! : "<<f<<"\n";
93       #else
94       //NTL_SNS
95       printf("convertFacCF2NTLZZ_pX: coefficient not immediate!, char=%d\n",
96              getCharacteristic());
97       #endif
98       NTL_SNS exit(1);
99    }
100    else
101    {
102      SetCoeff(ntl_poly,NTLcurrentExp,c.intval());
103    }
104    NTLcurrentExp--;
105  }
106
107  //Set the remaining coefficients of ntl_poly to zero.
108  // This is necessary, because NTL internally
109  // also stores powers with zero coefficient,
110  // whereas factory stores tuples of degree and coefficient
111  //leaving out tuples if the coefficient equals zero
112  for (k=NTLcurrentExp;k>=0;k--)
113  {
114    SetCoeff(ntl_poly,k,0);
115  }
116
117  //normalize the polynomial and return it
118  ntl_poly.normalize();
119
120  return ntl_poly;
121}
122zz_pX convertFacCF2NTLzzpX(CanonicalForm f)
123{
124  zz_pX ntl_poly;
125
126  CFIterator i;
127  i=f;
128
129  int NTLcurrentExp=i.exp();
130  int largestExp=i.exp();
131  int k;
132
133  // we now build up the NTL-polynomial
134  ntl_poly.SetMaxLength(largestExp+1);
135
136  for (;i.hasTerms();i++)
137  {
138    for (k=NTLcurrentExp;k>i.exp();k--)
139    {
140      SetCoeff(ntl_poly,k,0);
141    }
142    NTLcurrentExp=i.exp();
143
144    CanonicalForm c=i.coeff();
145    if (!c.isImm()) c.mapinto(); //c%= getCharacteristic();
146    if (!c.isImm())
147    {  //This case will never happen if the characteristic is in fact a prime
148       // number, since all coefficients are represented as immediates
149       #ifndef NOSTREAMIO
150       cout<<"convertFacCF2NTLzz_pX: coefficient not immediate! : "<<f<<"\n";
151       #else
152       //NTL_SNS
153       printf("convertFacCF2NTLzz_pX: coefficient not immediate!, char=%d\n",
154              getCharacteristic());
155       #endif
156       NTL_SNS exit(1);
157    }
158    else
159    {
160      SetCoeff(ntl_poly,NTLcurrentExp,c.intval());
161    }
162    NTLcurrentExp--;
163  }
164
165  //Set the remaining coefficients of ntl_poly to zero.
166  // This is necessary, because NTL internally
167  // also stores powers with zero coefficient,
168  // whereas factory stores tuples of degree and coefficient
169  //leaving out tuples if the coefficient equals zero
170  for (k=NTLcurrentExp;k>=0;k--)
171  {
172    SetCoeff(ntl_poly,k,0);
173  }
174
175  //normalize the polynomial and return it
176  ntl_poly.normalize();
177
178  return ntl_poly;
179}
180
181////////////////////////////////////////////////////////////////////////////////
182// NAME: convertFacCF2NTLGF2X                                                 //
183//                                                                            //
184// DESCRIPTION:                                                               //
185// Conversion routine for Factory-type canonicalform into GF2X of NTL,        //
186// i.e. polynomials over F_2. As precondition for correct execution,          //
187// the characteristic must equal two.                                         //
188// This is a special case of the more general conversion routine for          //
189// canonicalform to ZZpX. It is included because NTL provides additional      //
190// support and faster algorithms over F_2, moreover the conversion code       //
191// can be optimized, because certain steps are either completely obsolent     //
192// (like normalizing the polynomial) or they can be made significantly        //
193// faster (like building up the NTL-polynomial).                              //
194//                                                                            //
195// INPUT:  A canonicalform f                                                  //
196// OUTPUT: The converted NTL-polynomial over F_2 of type GF2X                 //
197////////////////////////////////////////////////////////////////////////////////
198
199GF2X convertFacCF2NTLGF2X(CanonicalForm f)
200{
201  //printf("convertFacCF2NTLGF2X\n");
202  GF2X ntl_poly;
203
204  CFIterator i;
205  i=f;
206
207  int NTLcurrentExp=i.exp();
208  int largestExp=i.exp();
209  int k;
210
211  //building the NTL-polynomial
212  ntl_poly.SetMaxLength(largestExp+1);
213
214  for (;i.hasTerms();i++)
215  {
216
217    for (k=NTLcurrentExp;k>i.exp();k--)
218    {
219      SetCoeff(ntl_poly,k,0);
220    }
221    NTLcurrentExp=i.exp();
222
223    if (!i.coeff().isImm()) i.coeff()=i.coeff().mapinto();
224    if (!i.coeff().isImm())
225    {
226      #ifndef NOSTREAMIO
227      cout<<"convertFacCF2NTLGF2X: coefficient not immidiate! : " << f << "\n";
228      #else
229      //NTL_SNS
230      printf("convertFacCF2NTLGF2X: coefficient not immidiate!");
231      #endif
232      NTL_SNS exit(1);
233    }
234    else
235    {
236      SetCoeff(ntl_poly,NTLcurrentExp,i.coeff().intval());
237    }
238    NTLcurrentExp--;
239  }
240  for (k=NTLcurrentExp;k>=0;k--)
241  {
242    SetCoeff(ntl_poly,k,0);
243  }
244  //normalization is not necessary of F_2
245
246  return ntl_poly;
247}
248
249
250////////////////////////////////////////////////////////////////////////////////
251// NAME: convertNTLZZpX2CF                                                    //
252//                                                                            //
253// DESCRIPTION:                                                               //
254// Conversion routine for NTL-Type ZZpX to Factory-Type canonicalform.        //
255// Additionally a variable x is needed as a parameter indicating the          //
256// main variable of the computed canonicalform. To guarantee the correct      //
257// execution of the algorithm, the characteristic has a be an arbitrary       //
258// prime number.                                                              //
259//                                                                            //
260// INPUT:  A canonicalform f, a variable x                                    //
261// OUTPUT: The converted Factory-polynomial of type canonicalform,            //
262//         built by the main variable x                                       //
263////////////////////////////////////////////////////////////////////////////////
264
265CanonicalForm convertNTLZZpX2CF(ZZ_pX poly,Variable x)
266{
267  //printf("convertNTLZZpX2CF\n");
268  CanonicalForm bigone;
269
270
271  if (deg(poly)>0)
272  {
273    // poly is non-constant
274    bigone=0;
275    bigone.mapinto();
276    // Compute the canonicalform coefficient by coefficient,
277    // bigone summarizes the result.
278    for (int j=0;j<=deg(poly);j++)
279    {
280      if (coeff(poly,j)!=0)
281      {
282        bigone+=(power(x,j)*CanonicalForm(to_long(rep(coeff(poly,j)))));
283      }
284    }
285  }
286  else
287  {
288    // poly is immediate
289    bigone=CanonicalForm(to_long(rep(coeff(poly,0))));
290    bigone.mapinto();
291  }
292  return bigone;
293}
294
295CanonicalForm convertNTLzzpX2CF(zz_pX poly,Variable x)
296{
297  //printf("convertNTLzzpX2CF\n");
298  CanonicalForm bigone;
299
300
301  if (deg(poly)>0)
302  {
303    // poly is non-constant
304    bigone=0;
305    bigone.mapinto();
306    // Compute the canonicalform coefficient by coefficient,
307    // bigone summarizes the result.
308    for (int j=0;j<=deg(poly);j++)
309    {
310      if (coeff(poly,j)!=0)
311      {
312        bigone+=(power(x,j)*CanonicalForm(to_long(rep(coeff(poly,j)))));
313      }
314    }
315  }
316  else
317  {
318    // poly is immediate
319    bigone=CanonicalForm(to_long(rep(coeff(poly,0))));
320    bigone.mapinto();
321  }
322  return bigone;
323}
324
325CanonicalForm convertNTLZZX2CF(ZZX polynom,Variable x)
326{
327  //printf("convertNTLZZX2CF\n");
328  CanonicalForm bigone;
329
330  // Go through the vector e and build up the CFFList
331  // As usual bigone summarizes the result
332  bigone=0;
333  ZZ coefficient;
334
335  for (int j=0;j<=deg(polynom);j++)
336  {
337    coefficient=coeff(polynom,j);
338    if (!IsZero(coefficient))
339    {
340      bigone += (power(x,j)*convertZZ2CF(coefficient));
341    }
342  }
343  return bigone;
344}
345
346////////////////////////////////////////////////////////////////////////////////
347// NAME: convertNTLGF2X2CF                                                    //
348//                                                                            //
349// DESCRIPTION:                                                               //
350// Conversion routine for NTL-Type GF2X to Factory-Type canonicalform,        //
351// the routine is again an optimized special case of the more general         //
352// conversion to ZZpX. Additionally a variable x is needed as a               //
353// parameter indicating the main variable of the computed canonicalform.      //
354// To guarantee the correct execution of the algorithm the characteristic     //
355// has a be an arbitrary prime number.                                        //
356//                                                                            //
357// INPUT:  A canonicalform f, a variable x                                    //
358// OUTPUT: The converted Factory-polynomial of type canonicalform,            //
359//         built by the main variable x                                       //
360////////////////////////////////////////////////////////////////////////////////
361
362CanonicalForm convertNTLGF2X2CF(GF2X poly,Variable x)
363{
364  //printf("convertNTLGF2X2CF\n");
365  CanonicalForm bigone;
366
367  if (deg(poly)>0)
368  {
369    // poly is non-constant
370    bigone=0;
371    bigone.mapinto();
372    // Compute the canonicalform coefficient by coefficient,
373    // bigone summarizes the result.
374    // In constrast to the more general conversion to ZZpX
375    // the only possible coefficients are zero
376    // and one yielding the following simplified loop
377    for (int j=0;j<=deg(poly);j++)
378    {
379      if (coeff(poly,j)!=0) bigone+=power(x,j);
380     // *CanonicalForm(to_long(rep(coeff(poly,j))))) is not necessary any more;
381    }
382  }
383  else
384  {
385    // poly is immediate
386    bigone=CanonicalForm(to_long(rep(coeff(poly,0))));
387    bigone.mapinto();
388  }
389
390  return bigone;
391}
392
393////////////////////////////////////////////////////////////////////////////////
394// NAME: convertNTLvec_pair_ZZpX_long2FacCFFList                              //
395//                                                                            //
396// DESCRIPTION:                                                               //
397// Routine for converting a vector of polynomials from ZZpX to                //
398// a CFFList of Factory. This routine will be used after a successful         //
399// factorization of NTL to convert the result back to Factory.                //
400//                                                                            //
401// Additionally a variable x and the computed multiplicity, as a type ZZp     //
402// of NTL, is needed as parameters indicating the main variable of the        //
403// computed canonicalform and the multiplicity of the original polynomial.    //
404// To guarantee the correct execution of the algorithm the characteristic     //
405// has a be an arbitrary prime number.                                        //
406//                                                                            //
407// INPUT:  A vector of polynomials over ZZp of type vec_pair_ZZ_pX_long and   //
408//         a variable x and a multiplicity of type ZZp                        //
409// OUTPUT: The converted list of polynomials of type CFFList, all polynomials //
410//         have x as their main variable                                      //
411////////////////////////////////////////////////////////////////////////////////
412
413CFFList convertNTLvec_pair_ZZpX_long2FacCFFList
414                                  (vec_pair_ZZ_pX_long e,ZZ_p multi,Variable x)
415{
416  //printf("convertNTLvec_pair_ZZpX_long2FacCFFList\n");
417  CFFList result;
418  ZZ_pX polynom;
419  CanonicalForm bigone;
420
421  // Maybe, e may additionally be sorted with respect to increasing degree of x
422  // but this is not
423  //important for the factorization, but nevertheless would take computing time,
424  // so it is omitted
425
426
427  // Go through the vector e and compute the CFFList
428  // again bigone summarizes the result
429  for (int i=e.length()-1;i>=0;i--)
430  {
431    result.append(CFFactor(convertNTLZZpX2CF(e[i].a,x),e[i].b));
432  }
433  // the multiplicity at pos 1
434  if (!IsOne(multi))
435    result.insert(CFFactor(CanonicalForm(to_long(rep(multi))),1));
436  return result;
437}
438CFFList convertNTLvec_pair_zzpX_long2FacCFFList
439                                  (vec_pair_zz_pX_long e,zz_p multi,Variable x)
440{
441  //printf("convertNTLvec_pair_zzpX_long2FacCFFList\n");
442  CFFList result;
443  zz_pX polynom;
444  CanonicalForm bigone;
445
446  // Maybe, e may additionally be sorted with respect to increasing degree of x
447  // but this is not
448  //important for the factorization, but nevertheless would take computing time,
449  // so it is omitted
450
451
452  // Go through the vector e and compute the CFFList
453  // again bigone summarizes the result
454  for (int i=e.length()-1;i>=0;i--)
455  {
456    result.append(CFFactor(convertNTLzzpX2CF(e[i].a,x),e[i].b));
457  }
458  // the multiplicity at pos 1
459  if (!IsOne(multi))
460    result.insert(CFFactor(CanonicalForm(to_long(rep(multi))),1));
461  return result;
462}
463
464////////////////////////////////////////////////////////////////////////////////
465// NAME: convertNTLvec_pair_GF2X_long2FacCFFList                              //
466//                                                                            //
467// DESCRIPTION:                                                               //
468// Routine for converting a vector of polynomials of type GF2X from           //
469// NTL to a list CFFList of Factory. This routine will be used after a        //
470// successful factorization of NTL to convert the result back to Factory.     //
471// As usual this is simply a special case of the more general conversion      //
472// routine but again speeded up by leaving out unnecessary steps.             //
473// Additionally a variable x and the computed multiplicity, as type           //
474// GF2 of NTL, are needed as parameters indicating the main variable of the   //
475// computed canonicalform and the multiplicity of the original polynomial.    //
476// To guarantee the correct execution of the algorithm the characteristic     //
477// has a be an arbitrary prime number.                                        //
478//                                                                            //
479// INPUT:  A vector of polynomials over GF2 of type vec_pair_GF2X_long and    //
480//         a variable x and a multiplicity of type GF2                        //
481// OUTPUT: The converted list of polynomials of type CFFList, all             //
482//         polynomials have x as their main variable                          //
483////////////////////////////////////////////////////////////////////////////////
484
485CFFList convertNTLvec_pair_GF2X_long2FacCFFList
486    (vec_pair_GF2X_long e, GF2 /*multi*/, Variable x)
487{
488  //printf("convertNTLvec_pair_GF2X_long2FacCFFList\n");
489  CFFList result;
490  GF2X polynom;
491  long exponent;
492  CanonicalForm bigone;
493
494  // Maybe, e may additionally be sorted with respect to increasing degree of x
495  // but this is not
496  //important for the factorization, but nevertheless would take computing time
497  // so it is omitted.
498
499  //We do not have to worry about the multiplicity in GF2 since it equals one.
500
501  // Go through the vector e and compute the CFFList
502  // bigone summarizes the result again
503  for (int i=e.length()-1;i>=0;i--)
504  {
505    bigone=0;
506
507    polynom=e[i].a;
508    exponent=e[i].b;
509    for (int j=0;j<=deg(polynom);j++)
510    {
511      if (coeff(polynom,j)!=0)
512        bigone += (power(x,j)*CanonicalForm(to_long(rep(coeff(polynom,j)))));
513    }
514
515    //append the converted polynomial to the CFFList
516    result.append(CFFactor(bigone,exponent));
517  }
518  return result;
519}
520
521////////////////////////////////////////////////////////////////////////////////
522// NAME: convertZZ2CF                                                         //
523//                                                                            //
524// DESCRIPTION:                                                               //
525// Routine for conversion of integers represented in NTL as Type ZZ to        //
526// integers in Factory represented as canonicalform.                          //
527// To guarantee the correct execution of the algorithm the characteristic     //
528// has to equal zero.                                                         //
529//                                                                            //
530// INPUT:  The value coefficient of type ZZ that has to be converted          //
531// OUTPUT: The converted Factory-integer of type canonicalform                //
532////////////////////////////////////////////////////////////////////////////////
533
534static char *cf_stringtemp;
535static char *cf_stringtemp2;
536static int cf_stringtemp_l=0;
537CanonicalForm convertZZ2CF(ZZ coefficient)
538{
539  long coeff_long;
540  //CanonicalForm tmp=0;
541  char dummy[2];
542  int minusremainder=0;
543  char numbers[]="0123456789abcdef";
544
545  coeff_long=to_long(coefficient);
546
547  //Test whether coefficient can be represented as an immediate integer in Factory
548  if ( (NumBits(coefficient)<((long)NTL_ZZ_NBITS))
549  && (coeff_long>((long)MINIMMEDIATE))
550  && (coeff_long<((long)MAXIMMEDIATE)))
551  {
552    // coefficient is immediate --> return the coefficient as canonicalform
553    return CanonicalForm(coeff_long);
554  }
555  else
556  {
557    // coefficient is not immediate (gmp-number)
558    if (cf_stringtemp_l==0)
559    {
560      cf_stringtemp=(char *)Alloc(1023);
561      cf_stringtemp2=(char *)Alloc(1023);
562      cf_stringtemp[0]='\0';
563      cf_stringtemp2[0]='\0';
564      cf_stringtemp_l=1023;
565    }
566
567    // convert coefficient to char* (input for gmp)
568    dummy[1]='\0';
569
570    if (coefficient<0)
571    {
572      // negate coefficient, but store the sign in minusremainder
573      minusremainder=1;
574      coefficient=-coefficient;
575    }
576
577    int l=0;
578    while (coefficient>15)
579    {
580      ZZ quotient,remaind;
581      ZZ ten;ten=16;
582      DivRem(quotient,remaind,coefficient,ten);
583      dummy[0]=numbers[to_long(remaind)];
584      //tmp*=10; tmp+=to_long(remaind);
585
586      l++;
587      if (l>=cf_stringtemp_l-2)
588      {
589        Free(cf_stringtemp2,cf_stringtemp_l);
590        char *p=(char *)Alloc(cf_stringtemp_l*2);
591        //NTL_SNS
592        memcpy(p,cf_stringtemp,cf_stringtemp_l);
593        Free(cf_stringtemp,cf_stringtemp_l);
594        cf_stringtemp_l*=2;
595        cf_stringtemp=p;
596        cf_stringtemp2=(char *)Alloc(cf_stringtemp_l);
597      }
598      cf_stringtemp[l-1]=dummy[0];
599      cf_stringtemp[l]='\0';
600      //strcat(stringtemp,dummy);
601
602      coefficient=quotient;
603    }
604    //built up the string in dummy[0]
605    dummy[0]=numbers[to_long(coefficient)];
606    //NTL_SNS
607    l++;
608    cf_stringtemp[l-1]=dummy[0];
609    cf_stringtemp[l]='\0';
610    //tmp*=10; tmp+=to_long(coefficient);
611
612    if (minusremainder==1)
613    {
614      //Check whether coefficient has been negative at the start of the procedure
615      cf_stringtemp2[0]='-';
616      //tmp*=(-1);
617    }
618
619    //reverse the list to obtain the correct string
620    //NTL_SNS
621    for (int i=l-1;i>=0;i--) // l ist the position of \0
622    {
623      cf_stringtemp2[l-i-1+minusremainder]=cf_stringtemp[i];
624    }
625    cf_stringtemp2[l+minusremainder]='\0';
626  }
627
628  //convert the string to canonicalform using the char*-Constructor
629  return CanonicalForm(cf_stringtemp2,16);
630  //return tmp;
631}
632
633////////////////////////////////////////////////////////////////////////////////
634// NAME: convertFacCF2NTLZZX                                                  //
635//                                                                            //
636// DESCRIPTION:                                                               //
637// Routine for conversion of canonicalforms in Factory to polynomials         //
638// of type ZZX of NTL. To guarantee the correct execution of the              //
639// algorithm the characteristic has to equal zero.                            //
640//                                                                            //
641// INPUT:  The canonicalform that has to be converted                         //
642// OUTPUT: The converted NTL-polynom of type ZZX                              //
643////////////////////////////////////////////////////////////////////////////////
644
645ZZ convertFacCF2NTLZZ(const CanonicalForm f)
646{
647  ZZ temp;
648  if (f.isImm()) temp=f.intval();
649  else
650  {
651    //Coefficient is a gmp-number
652    mpz_t gmp_val;
653    char* stringtemp;
654
655    gmp_val[0]=*getmpi(f.getval());
656    int l=mpz_sizeinbase(gmp_val,10)+2;
657    stringtemp=(char*)Alloc(l);
658    stringtemp=mpz_get_str(stringtemp,10,gmp_val);
659    mpz_clear(gmp_val);
660    conv(temp,stringtemp);
661    Free(stringtemp,l);
662  }
663  return temp;
664}
665
666ZZX convertFacCF2NTLZZX(CanonicalForm f)
667{
668    ZZX ntl_poly;
669
670    CFIterator i;
671    i=f;
672
673    int NTLcurrentExp=i.exp();
674    int largestExp=i.exp();
675    int k;
676
677    //set the length of the NTL-polynomial
678    ntl_poly.SetMaxLength(largestExp+1);
679
680    //Go through the coefficients of the canonicalform and build up the NTL-polynomial
681    for (;i.hasTerms();i++)
682    {
683      for (k=NTLcurrentExp;k>i.exp();k--)
684      {
685        SetCoeff(ntl_poly,k,0);
686      }
687      NTLcurrentExp=i.exp();
688
689      //Coefficient is a gmp-number
690      ZZ temp=convertFacCF2NTLZZ(i.coeff());
691
692      //set the computed coefficient
693      SetCoeff(ntl_poly,NTLcurrentExp,temp);
694
695      NTLcurrentExp--;
696    }
697    for (k=NTLcurrentExp;k>=0;k--)
698    {
699      SetCoeff(ntl_poly,k,0);
700    }
701
702    //normalize the polynomial
703    ntl_poly.normalize();
704
705    return ntl_poly;
706}
707
708////////////////////////////////////////////////////////////////////////////////
709// NAME: convertNTLvec_pair_ZZX_long2FacCFFList                               //
710//                                                                            //
711// DESCRIPTION:                                                               //
712// Routine for converting a vector of polynomials from ZZ to a list           //
713// CFFList of Factory. This routine will be used after a successful           //
714// factorization of NTL to convert the result back to Factory.                //
715// Additionally a variable x and the computed multiplicity, as a type         //
716// ZZ of NTL, is needed as parameters indicating the main variable of the     //
717// computed canonicalform and the multiplicity of the original polynomial.    //
718// To guarantee the correct execution of the algorithm the characteristic     //
719// has to equal zero.                                                         //
720//                                                                            //
721// INPUT:  A vector of polynomials over ZZ of type vec_pair_ZZX_long and      //
722//         a variable x and a multiplicity of type ZZ                         //
723// OUTPUT: The converted list of polynomials of type CFFList, all             //
724//         have x as their main variable                                      //
725////////////////////////////////////////////////////////////////////////////////
726
727CFFList convertNTLvec_pair_ZZX_long2FacCFFList(vec_pair_ZZX_long e,ZZ multi,Variable x)
728{
729  CFFList result;
730  ZZX polynom;
731  long exponent;
732  CanonicalForm bigone;
733
734  // Go through the vector e and build up the CFFList
735  // As usual bigone summarizes the result
736  for (int i=e.length()-1;i>=0;i--)
737  {
738    ZZ coefficient;
739    polynom=e[i].a;
740    exponent=e[i].b;
741    bigone=convertNTLZZX2CF(polynom,x);
742    //append the converted polynomial to the list
743    result.append(CFFactor(bigone,exponent));
744  }
745  // the multiplicity at pos 1
746  //if (!IsOne(multi))
747    result.insert(CFFactor(convertZZ2CF(multi),1));
748
749  //return the converted list
750  return result;
751}
752
753
754////////////////////////////////////////////////////////////////////////////////
755// NAME: convertNTLZZpX2CF                                                    //
756//                                                                            //
757// DESCRIPTION:                                                               //
758// Routine for conversion of elements of arbitrary extensions of ZZp,         //
759// having type ZZpE, of NTL to their corresponding values of type             //
760// canonicalform in Factory.                                                  //
761// To guarantee the correct execution of the algorithm the characteristic     //
762// has to be an arbitrary prime number and Factory has to compute in an       //
763// extension of F_p.                                                          //
764//                                                                            //
765// INPUT:  The coefficient of type ZZpE and the variable x indicating the main//
766//         variable of the computed canonicalform                             //
767// OUTPUT: The converted value of coefficient as type canonicalform           //
768////////////////////////////////////////////////////////////////////////////////
769
770CanonicalForm convertNTLZZpE2CF(ZZ_pE coefficient,Variable x)
771{
772  return convertNTLZZpX2CF(rep(coefficient),x);
773}
774CanonicalForm convertNTLzzpE2CF(zz_pE coefficient,Variable x)
775{
776  return convertNTLzzpX2CF(rep(coefficient),x);
777}
778
779////////////////////////////////////////////////////////////////////////////////
780// NAME: convertNTLvec_pair_ZZpEX_long2FacCFFList                             //
781//                                                                            //
782// DESCRIPTION:                                                               //
783// Routine for converting a vector of polynomials from ZZpEX to a CFFList     //
784// of Factory. This routine will be used after a successful factorization     //
785// of NTL to convert the result back to Factory.                              //
786// Additionally a variable x and the computed multiplicity, as a type         //
787// ZZpE of NTL, is needed as parameters indicating the main variable of the   //
788// computed canonicalform and the multiplicity of the original polynomial.    //
789// To guarantee the correct execution of the algorithm the characteristic     //
790// has a be an arbitrary prime number p and computations have to be done      //
791// in an extention of F_p.                                                    //
792//                                                                            //
793// INPUT:  A vector of polynomials over ZZpE of type vec_pair_ZZ_pEX_long and //
794//         a variable x and a multiplicity of type ZZpE                       //
795// OUTPUT: The converted list of polynomials of type CFFList, all polynomials //
796//         have x as their main variable                                      //
797////////////////////////////////////////////////////////////////////////////////
798
799CFFList convertNTLvec_pair_ZZpEX_long2FacCFFList(vec_pair_ZZ_pEX_long e,ZZ_pE multi,Variable x,Variable alpha)
800{
801  CFFList result;
802  ZZ_pEX polynom;
803  long exponent;
804  CanonicalForm bigone;
805
806  // Maybe, e may additionally be sorted with respect to increasing degree of x, but this is not
807  //important for the factorization, but nevertheless would take computing time, so it is omitted
808
809  // Go through the vector e and build up the CFFList
810  // As usual bigone summarizes the result during every loop
811  for (int i=e.length()-1;i>=0;i--)
812  {
813    bigone=0;
814
815    polynom=e[i].a;
816    exponent=e[i].b;
817
818    for (int j=0;j<=deg(polynom);j++)
819    {
820      if (IsOne(coeff(polynom,j)))
821      {
822        bigone+=power(x,j);
823      }
824      else
825      {
826        CanonicalForm coefficient=convertNTLZZpE2CF(coeff(polynom,j),alpha);
827        if (coeff(polynom,j)!=0)
828        {
829          bigone += (power(x,j)*coefficient);
830        }
831      }
832    }
833    //append the computed polynomials together with its exponent to the CFFList
834    result.append(CFFactor(bigone,exponent));
835  }
836  // Start by appending the multiplicity
837  if (!IsOne(multi))
838    result.insert(CFFactor(convertNTLZZpE2CF(multi,alpha),1));
839
840  //return the computed CFFList
841  return result;
842}
843CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(vec_pair_zz_pEX_long e,zz_pE multi,Variable x,Variable alpha)
844{
845  CFFList result;
846  zz_pEX polynom;
847  long exponent;
848  CanonicalForm bigone;
849
850  // Maybe, e may additionally be sorted with respect to increasing degree of x, but this is not
851  //important for the factorization, but nevertheless would take computing time, so it is omitted
852
853  // Go through the vector e and build up the CFFList
854  // As usual bigone summarizes the result during every loop
855  for (int i=e.length()-1;i>=0;i--)
856  {
857    bigone=0;
858
859    polynom=e[i].a;
860    exponent=e[i].b;
861
862    for (int j=0;j<=deg(polynom);j++)
863    {
864      if (IsOne(coeff(polynom,j)))
865      {
866        bigone+=power(x,j);
867      }
868      else
869      {
870        CanonicalForm coefficient=convertNTLzzpE2CF(coeff(polynom,j),alpha);
871        if (coeff(polynom,j)!=0)
872        {
873          bigone += (power(x,j)*coefficient);
874        }
875      }
876    }
877    //append the computed polynomials together with its exponent to the CFFList
878    result.append(CFFactor(bigone,exponent));
879  }
880  // Start by appending the multiplicity
881  if (!IsOne(multi))
882    result.insert(CFFactor(convertNTLzzpE2CF(multi,alpha),1));
883
884  //return the computed CFFList
885  return result;
886}
887
888////////////////////////////////////////////////////////////////////////////////
889// NAME: convertNTLGF2E2CF                                                    //
890//                                                                            //
891// DESCRIPTION:                                                               //
892// Routine for conversion of elements of extensions of GF2, having type       //
893// GF2E, of NTL to their corresponding values of type canonicalform in        //
894// Factory.                                                                   //
895// To guarantee the correct execution of the algorithm, the characteristic    //
896// must equal two and Factory has to compute in an extension of F_2.          //
897// As usual this is an optimized special case of the more general conversion  //
898// routine from ZZpE to Factory.                                              //
899//                                                                            //
900// INPUT:  The coefficient of type GF2E and the variable x indicating the     //
901//         main variable of the computed canonicalform                        //
902// OUTPUT: The converted value of coefficient as type canonicalform           //
903////////////////////////////////////////////////////////////////////////////////
904
905CanonicalForm convertNTLGF2E2CF(GF2E coefficient,Variable x)
906{
907  return convertNTLGF2X2CF(rep(coefficient),x);
908}
909
910////////////////////////////////////////////////////////////////////////////////
911// NAME: convertNTLvec_pair_GF2EX_long2FacCFFList                             //
912//                                                                            //
913// DESCRIPTION:                                                               //
914// Routine for converting a vector of polynomials from GF2EX to a CFFList     //
915// of Factory. This routine will be used after a successful factorization     //
916// of NTL to convert the result back to Factory.                              //
917// This is a special, but optimized case of the more general conversion       //
918// from ZZpE to canonicalform.                                                //
919// Additionally a variable x and the computed multiplicity, as a type GF2E    //
920// of NTL, is needed as parameters indicating the main variable of the        //
921// computed canonicalform and the multiplicity of the original polynomial.    //
922// To guarantee the correct execution of the algorithm the characteristic     //
923// has to equal two and computations have to be done in an extention of F_2.  //
924//                                                                            //
925// INPUT:  A vector of polynomials over GF2E of type vec_pair_GF2EX_long and  //
926//         a variable x and a multiplicity of type GF2E                       //
927// OUTPUT: The converted list of polynomials of type CFFList, all polynomials //
928//         have x as their main variable                                      //
929////////////////////////////////////////////////////////////////////////////////
930
931CFFList convertNTLvec_pair_GF2EX_long2FacCFFList
932    (vec_pair_GF2EX_long e, GF2E /*multi*/, Variable x, Variable alpha)
933{
934  CFFList result;
935  GF2EX polynom;
936  long exponent;
937  CanonicalForm bigone;
938
939  // Maybe, e may additionally be sorted with respect to increasing degree of x, but this is not
940  //important for the factorization, but nevertheless would take computing time, so it is omitted
941
942  // multiplicity is always one, so we do not have to worry about that
943
944  // Go through the vector e and build up the CFFList
945  // As usual bigone summarizes the result during every loop
946  for (int i=e.length()-1;i>=0;i--)
947  {
948    bigone=0;
949
950    polynom=e[i].a;
951    exponent=e[i].b;
952
953    for (int j=0;j<=deg(polynom);j++)
954    {
955      if (IsOne(coeff(polynom,j)))
956      {
957        bigone+=power(x,j);
958      }
959      else
960      {
961        CanonicalForm coefficient=convertNTLGF2E2CF(coeff(polynom,j),alpha);
962        if (coeff(polynom,j)!=0)
963        {
964          bigone += (power(x,j)*coefficient);
965        }
966      }
967    }
968
969    // append the computed polynomial together with its multiplicity
970    result.append(CFFactor(bigone,exponent));
971
972  }
973  // return the computed CFFList
974  return result;
975}
976
977////////////////////////////////////////////////////
978// CanonicalForm in Z_2(a)[X] to NTL GF2EX        //
979////////////////////////////////////////////////////
980GF2EX convertFacCF2NTLGF2EX(CanonicalForm f,GF2X mipo)
981{
982  GF2E::init(mipo);
983  GF2EX result;
984  CFIterator i;
985  i=f;
986
987  int NTLcurrentExp=i.exp();
988  int largestExp=i.exp();
989  int k;
990
991  result.SetMaxLength(largestExp+1);
992  for(;i.hasTerms();i++)
993  {
994    for(k=NTLcurrentExp;k>i.exp();k--) SetCoeff(result,k,0);
995    NTLcurrentExp=i.exp();
996    CanonicalForm c=i.coeff();
997    GF2X cc=convertFacCF2NTLGF2X(c);
998    //ZZ_pE ccc;
999    //conv(ccc,cc);
1000    SetCoeff(result,NTLcurrentExp,to_GF2E(cc));
1001    NTLcurrentExp--;
1002  }
1003  for(k=NTLcurrentExp;k>=0;k--) SetCoeff(result,k,0);
1004  result.normalize();
1005  return result;
1006}
1007////////////////////////////////////////////////////
1008// CanonicalForm in Z_p(a)[X] to NTL ZZ_pEX       //
1009////////////////////////////////////////////////////
1010ZZ_pEX convertFacCF2NTLZZ_pEX(CanonicalForm f, ZZ_pX mipo)
1011{
1012  ZZ_pE::init(mipo);
1013  ZZ_pEX result;
1014  CFIterator i;
1015  i=f;
1016
1017  int NTLcurrentExp=i.exp();
1018  int largestExp=i.exp();
1019  int k;
1020
1021  result.SetMaxLength(largestExp+1);
1022  for(;i.hasTerms();i++)
1023  {
1024    for(k=NTLcurrentExp;k>i.exp();k--) SetCoeff(result,k,0);
1025    NTLcurrentExp=i.exp();
1026    CanonicalForm c=i.coeff();
1027    ZZ_pX cc=convertFacCF2NTLZZpX(c);
1028    //ZZ_pE ccc;
1029    //conv(ccc,cc);
1030    SetCoeff(result,NTLcurrentExp,to_ZZ_pE(cc));
1031    NTLcurrentExp--;
1032  }
1033  for(k=NTLcurrentExp;k>=0;k--) SetCoeff(result,k,0);
1034  result.normalize();
1035  return result;
1036}
1037zz_pEX convertFacCF2NTLzz_pEX(CanonicalForm f, zz_pX mipo)
1038{
1039  zz_pE::init(mipo);
1040  zz_pEX result;
1041  CFIterator i;
1042  i=f;
1043
1044  int NTLcurrentExp=i.exp();
1045  int largestExp=i.exp();
1046  int k;
1047
1048  result.SetMaxLength(largestExp+1);
1049  for(;i.hasTerms();i++)
1050  {
1051    for(k=NTLcurrentExp;k>i.exp();k--) SetCoeff(result,k,0);
1052    NTLcurrentExp=i.exp();
1053    CanonicalForm c=i.coeff();
1054    zz_pX cc=convertFacCF2NTLzzpX(c);
1055    //ZZ_pE ccc;
1056    //conv(ccc,cc);
1057    SetCoeff(result,NTLcurrentExp,to_zz_pE(cc));
1058    NTLcurrentExp--;
1059  }
1060  for(k=NTLcurrentExp;k>=0;k--) SetCoeff(result,k,0);
1061  result.normalize();
1062  return result;
1063}
1064
1065CanonicalForm convertNTLzz_pEX2CF (zz_pEX f, Variable x, Variable alpha)
1066{
1067  CanonicalForm bigone;
1068  if (deg (f) > 0)
1069  {
1070    bigone= 0;
1071    bigone.mapinto();
1072    for (int j=0;j<deg(f)+1;j++)
1073    {
1074      if (coeff(f,j)!=0)
1075      {
1076        bigone+=(power(x,j)*convertNTLzzpE2CF(coeff(f,j),alpha));
1077      }
1078    }
1079  }
1080  else
1081  {
1082    bigone= convertNTLzzpE2CF(coeff(f,0),alpha);
1083    bigone.mapinto();
1084  }
1085  return bigone;
1086}
1087//----------------------------------------------------------------------
1088mat_ZZ* convertFacCFMatrix2NTLmat_ZZ(CFMatrix &m)
1089{
1090  mat_ZZ *res=new mat_ZZ;
1091  res->SetDims(m.rows(),m.columns());
1092
1093  int i,j;
1094  for(i=m.rows();i>0;i--)
1095  {
1096    for(j=m.columns();j>0;j--)
1097    {
1098      (*res)(i,j)=convertFacCF2NTLZZ(m(i,j));
1099    }
1100  }
1101  return res;
1102}
1103CFMatrix* convertNTLmat_ZZ2FacCFMatrix(mat_ZZ &m)
1104{
1105  CFMatrix *res=new CFMatrix(m.NumRows(),m.NumCols());
1106  int i,j;
1107  for(i=res->rows();i>0;i--)
1108  {
1109    for(j=res->columns();j>0;j--)
1110    {
1111      (*res)(i,j)=convertZZ2CF(m(i,j));
1112    }
1113  }
1114  return res;
1115}
1116
1117mat_zz_p* convertFacCFMatrix2NTLmat_zz_p(CFMatrix &m)
1118{
1119  mat_zz_p *res=new mat_zz_p;
1120  res->SetDims(m.rows(),m.columns());
1121
1122  int i,j;
1123  for(i=m.rows();i>0;i--)
1124  {
1125    for(j=m.columns();j>0;j--)
1126    {
1127      if(!(m(i,j)).isImm()) printf("convertFacCFMatrix2NTLmat_zz_p: not imm.\n");
1128      (*res)(i,j)=(m(i,j)).intval();
1129    }
1130  }
1131  return res;
1132}
1133CFMatrix* convertNTLmat_zz_p2FacCFMatrix(mat_zz_p &m)
1134{
1135  CFMatrix *res=new CFMatrix(m.NumRows(),m.NumCols());
1136  int i,j;
1137  for(i=res->rows();i>0;i--)
1138  {
1139    for(j=res->columns();j>0;j--)
1140    {
1141      (*res)(i,j)=CanonicalForm(to_long(rep(m(i,j))));
1142    }
1143  }
1144  return res;
1145}
1146mat_zz_pE* convertFacCFMatrix2NTLmat_zz_pE(CFMatrix &m)
1147{
1148  mat_zz_pE *res=new mat_zz_pE;
1149  res->SetDims(m.rows(),m.columns());
1150
1151  int i,j;
1152  for(i=m.rows();i>0;i--)
1153  {
1154    for(j=m.columns();j>0;j--)
1155    {
1156      zz_pX cc=convertFacCF2NTLzzpX(m(i,j));
1157      (*res)(i,j)=to_zz_pE(cc);
1158    }
1159  }
1160  return res;
1161}
1162CFMatrix* convertNTLmat_zz_pE2FacCFMatrix(mat_zz_pE &m, Variable alpha)
1163{
1164  CFMatrix *res=new CFMatrix(m.NumRows(),m.NumCols());
1165  int i,j;
1166  for(i=res->rows();i>0;i--)
1167  {
1168    for(j=res->columns();j>0;j--)
1169    {
1170      (*res)(i,j)=convertNTLzzpE2CF(m(i,j), alpha);
1171    }
1172  }
1173  return res;
1174}
1175#endif
Note: See TracBrowser for help on using the repository browser.