source: git/factory/NTLconvert.cc @ 16f511

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