source: git/factory/NTLconvert.cc @ 362fc67

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