source: git/factory/NTLconvert.cc @ fbb0173

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