source: git/factory/NTLconvert.cc @ ceaa04

spielwiese
Last change on this file since ceaa04 was ceaa04, checked in by Hans Schönemann <hannes@…>, 14 years ago
*hannes: code cleanup git-svn-id: file:///usr/local/Singular/svn/trunk@12320 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 37.4 KB
Line 
1/* $Id$ */
2#include <config.h>
3
4#ifdef HAVE_SINGULAR
5#ifndef OM_NDEBUG
6#define OM_NDEBUG
7#endif
8#endif
9
10#include "cf_gmp.h"
11
12#include "assert.h"
13
14#include "cf_defs.h"
15#include "canonicalform.h"
16#include "cf_iter.h"
17#include "fac_berlekamp.h"
18#include "fac_cantzass.h"
19#include "fac_univar.h"
20#include "fac_multivar.h"
21#include "fac_sqrfree.h"
22#include "cf_algorithm.h"
23
24#ifdef HAVE_NTL
25#ifdef HAVE_CSTDIO
26#include <cstdio>
27#else
28#include <stdio.h>
29#endif
30#include <string.h>
31#include <NTL/ZZXFactoring.h>
32#include <NTL/ZZ_pXFactoring.h>
33#include <NTL/lzz_pXFactoring.h>
34#include <NTL/GF2XFactoring.h>
35#include <NTL/ZZ_pEXFactoring.h>
36#include <NTL/lzz_pEXFactoring.h>
37#include <NTL/GF2EXFactoring.h>
38#include <NTL/tools.h>
39#include "int_int.h"
40#include <limits.h>
41#include "NTLconvert.h"
42
43#ifdef HAVE_OMALLOC
44#define Alloc(L) omAlloc(L)
45#define Free(A,L) omFreeSize(A,L)
46#elif defined(USE_MEMUTIL)
47#include "memutil.h"
48#define Alloc(L) getBlock(L)
49#define Free(A,L) freeBlock(A,L)
50#else
51#define Alloc(L) malloc(L)
52#define Free(A,L) free(A)
53#endif
54 
55void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
56       
57
58int fac_NTL_char=-1;            // the current characterstic for NTL calls
59                                // -1: undefined
60#ifdef NTL_CLIENT               // in <NTL/tools.h>: using of name space NTL
61NTL_CLIENT
62#endif
63
64////////////////////////////////////////////////////////////////////////////////
65// NAME: convertFacCF2NTLZZpX                                                 //
66//                                                                            //
67// DESCRIPTION:                                                               //
68// Conversion routine for Factory-type canonicalform into ZZpX of NTL,        //
69// i.e. polynomials over F_p. As a precondition for correct execution,        //
70// the characteristic has to a a prime number.                                //
71//                                                                            //
72// INPUT:  A canonicalform f                                                  //
73// OUTPUT: The converted NTL-polynomial over F_p of type ZZpX                 //
74////////////////////////////////////////////////////////////////////////////////
75
76ZZ_pX convertFacCF2NTLZZpX(CanonicalForm f)
77{
78  ZZ_pX ntl_poly;
79
80  CFIterator i;
81  i=f;
82
83  int NTLcurrentExp=i.exp();
84  int largestExp=i.exp();
85  int k;
86
87  // we now build up the NTL-polynomial
88  ntl_poly.SetMaxLength(largestExp+1);
89
90  for (;i.hasTerms();i++)
91  {
92    for (k=NTLcurrentExp;k>i.exp();k--)
93    {
94      SetCoeff(ntl_poly,k,0);
95    }
96    NTLcurrentExp=i.exp();
97
98    CanonicalForm c=i.coeff();
99    if (!c.isImm()) c=c.mapinto(); //c%= getCharacteristic();
100    if (!c.isImm())
101    {  //This case will never happen if the characteristic is in fact a prime
102       // number, since all coefficients are represented as immediates
103       #ifndef NOSTREAMIO
104       cout<<"convertFacCF2NTLZZ_pX: coefficient not immediate! : "<<f<<"\n";
105       #else
106       //NTL_SNS
107       printf("convertFacCF2NTLZZ_pX: coefficient not immediate!, char=%d\n",
108              getCharacteristic());
109       #endif
110       NTL_SNS exit(1);
111    }
112    else
113    {
114      SetCoeff(ntl_poly,NTLcurrentExp,c.intval());
115    }
116    NTLcurrentExp--;
117  }
118
119  //Set the remaining coefficients of ntl_poly to zero.
120  // This is necessary, because NTL internally
121  // also stores powers with zero coefficient,
122  // whereas factory stores tuples of degree and coefficient
123  //leaving out tuples if the coefficient equals zero
124  for (k=NTLcurrentExp;k>=0;k--)
125  {
126    SetCoeff(ntl_poly,k,0);
127  }
128
129  //normalize the polynomial and return it
130  ntl_poly.normalize();
131
132  return ntl_poly;
133}
134zz_pX convertFacCF2NTLzzpX(CanonicalForm f)
135{
136  zz_pX ntl_poly;
137
138  CFIterator i;
139  i=f;
140
141  int NTLcurrentExp=i.exp();
142  int largestExp=i.exp();
143  int k;
144
145  // we now build up the NTL-polynomial
146  ntl_poly.SetMaxLength(largestExp+1);
147
148  for (;i.hasTerms();i++)
149  {
150    for (k=NTLcurrentExp;k>i.exp();k--)
151    {
152      SetCoeff(ntl_poly,k,0);
153    }
154    NTLcurrentExp=i.exp();
155
156    CanonicalForm c=i.coeff();
157    if (!c.isImm()) c.mapinto(); //c%= getCharacteristic();
158    if (!c.isImm())
159    {  //This case will never happen if the characteristic is in fact a prime
160       // number, since all coefficients are represented as immediates
161       #ifndef NOSTREAMIO
162       cout<<"convertFacCF2NTLzz_pX: coefficient not immediate! : "<<f<<"\n";
163       #else
164       //NTL_SNS
165       printf("convertFacCF2NTLzz_pX: coefficient not immediate!, char=%d\n",
166              getCharacteristic());
167       #endif
168       NTL_SNS exit(1);
169    }
170    else
171    {
172      SetCoeff(ntl_poly,NTLcurrentExp,c.intval());
173    }
174    NTLcurrentExp--;
175  }
176
177  //Set the remaining coefficients of ntl_poly to zero.
178  // This is necessary, because NTL internally
179  // also stores powers with zero coefficient,
180  // whereas factory stores tuples of degree and coefficient
181  //leaving out tuples if the coefficient equals zero
182  for (k=NTLcurrentExp;k>=0;k--)
183  {
184    SetCoeff(ntl_poly,k,0);
185  }
186
187  //normalize the polynomial and return it
188  ntl_poly.normalize();
189
190  return ntl_poly;
191}
192
193////////////////////////////////////////////////////////////////////////////////
194// NAME: convertFacCF2NTLGF2X                                                 //
195//                                                                            //
196// DESCRIPTION:                                                               //
197// Conversion routine for Factory-type canonicalform into GF2X of NTL,        //
198// i.e. polynomials over F_2. As precondition for correct execution,          //
199// the characteristic must equal two.                                         //
200// This is a special case of the more general conversion routine for          //
201// canonicalform to ZZpX. It is included because NTL provides additional      //
202// support and faster algorithms over F_2, moreover the conversion code       //
203// can be optimized, because certain steps are either completely obsolent     //
204// (like normalizing the polynomial) or they can be made significantly        //
205// faster (like building up the NTL-polynomial).                              //
206//                                                                            //
207// INPUT:  A canonicalform f                                                  //
208// OUTPUT: The converted NTL-polynomial over F_2 of type GF2X                 //
209////////////////////////////////////////////////////////////////////////////////
210
211GF2X convertFacCF2NTLGF2X(CanonicalForm f)
212{
213  //printf("convertFacCF2NTLGF2X\n");
214  GF2X ntl_poly;
215
216  CFIterator i;
217  i=f;
218
219  int NTLcurrentExp=i.exp();
220  int largestExp=i.exp();
221  int k;
222
223  //building the NTL-polynomial
224  ntl_poly.SetMaxLength(largestExp+1);
225
226  for (;i.hasTerms();i++)
227  {
228
229    for (k=NTLcurrentExp;k>i.exp();k--)
230    {
231      SetCoeff(ntl_poly,k,0);
232    }
233    NTLcurrentExp=i.exp();
234
235    if (!i.coeff().isImm()) i.coeff()=i.coeff().mapinto();
236    if (!i.coeff().isImm())
237    {
238      #ifndef NOSTREAMIO
239      cout<<"convertFacCF2NTLGF2X: coefficient not immidiate! : " << f << "\n";
240      #else
241      //NTL_SNS
242      printf("convertFacCF2NTLGF2X: coefficient not immidiate!");
243      #endif
244      NTL_SNS exit(1);
245    }
246    else
247    {
248      SetCoeff(ntl_poly,NTLcurrentExp,i.coeff().intval());
249    }
250    NTLcurrentExp--;
251  }
252  for (k=NTLcurrentExp;k>=0;k--)
253  {
254    SetCoeff(ntl_poly,k,0);
255  }
256  //normalization is not necessary of F_2
257
258  return ntl_poly;
259}
260
261
262////////////////////////////////////////////////////////////////////////////////
263// NAME: convertNTLZZpX2CF                                                    //
264//                                                                            //
265// DESCRIPTION:                                                               //
266// Conversion routine for NTL-Type ZZpX to Factory-Type canonicalform.        //
267// Additionally a variable x is needed as a parameter indicating the          //
268// main variable of the computed canonicalform. To guarantee the correct      //
269// execution of the algorithm, the characteristic has a be an arbitrary       //
270// prime number.                                                              //
271//                                                                            //
272// INPUT:  A canonicalform f, a variable x                                    //
273// OUTPUT: The converted Factory-polynomial of type canonicalform,            //
274//         built by the main variable x                                       //
275////////////////////////////////////////////////////////////////////////////////
276
277CanonicalForm convertNTLZZpX2CF(ZZ_pX poly,Variable x)
278{
279  //printf("convertNTLZZpX2CF\n");
280  CanonicalForm bigone;
281
282
283  if (deg(poly)>0)
284  {
285    // poly is non-constant
286    bigone=0;
287    bigone.mapinto();
288    // Compute the canonicalform coefficient by coefficient,
289    // bigone summarizes the result.
290    for (int j=0;j<=deg(poly);j++)
291    {
292      if (coeff(poly,j)!=0)
293      {
294        bigone+=(power(x,j)*CanonicalForm(to_long(rep(coeff(poly,j)))));
295      }
296    }
297  }
298  else
299  {
300    // poly is immediate
301    bigone=CanonicalForm(to_long(rep(coeff(poly,0))));
302    bigone.mapinto();
303  }
304  return bigone;
305}
306
307CanonicalForm convertNTLzzpX2CF(zz_pX poly,Variable x)
308{
309  //printf("convertNTLzzpX2CF\n");
310  CanonicalForm bigone;
311
312
313  if (deg(poly)>0)
314  {
315    // poly is non-constant
316    bigone=0;
317    bigone.mapinto();
318    // Compute the canonicalform coefficient by coefficient,
319    // bigone summarizes the result.
320    for (int j=0;j<=deg(poly);j++)
321    {
322      if (coeff(poly,j)!=0)
323      {
324        bigone+=(power(x,j)*CanonicalForm(to_long(rep(coeff(poly,j)))));
325      }
326    }
327  }
328  else
329  {
330    // poly is immediate
331    bigone=CanonicalForm(to_long(rep(coeff(poly,0))));
332    bigone.mapinto();
333  }
334  return bigone;
335}
336
337CanonicalForm convertNTLZZX2CF(ZZX polynom,Variable x)
338{
339  //printf("convertNTLZZX2CF\n");
340  CanonicalForm bigone;
341
342  // Go through the vector e and build up the CFFList
343  // As usual bigone summarizes the result
344  bigone=0;
345  ZZ coefficient;
346
347  for (int j=0;j<=deg(polynom);j++)
348  {
349    coefficient=coeff(polynom,j);
350    if (!IsZero(coefficient))
351    {
352      bigone += (power(x,j)*convertZZ2CF(coefficient));
353    }
354  }
355  return bigone;
356}
357
358////////////////////////////////////////////////////////////////////////////////
359// NAME: convertNTLGF2X2CF                                                    //
360//                                                                            //
361// DESCRIPTION:                                                               //
362// Conversion routine for NTL-Type GF2X to Factory-Type canonicalform,        //
363// the routine is again an optimized special case of the more general         //
364// conversion to ZZpX. Additionally a variable x is needed as a               //
365// parameter indicating the main variable of the computed canonicalform.      //
366// To guarantee the correct execution of the algorithm the characteristic     //
367// has a be an arbitrary prime number.                                        //
368//                                                                            //
369// INPUT:  A canonicalform f, a variable x                                    //
370// OUTPUT: The converted Factory-polynomial of type canonicalform,            //
371//         built by the main variable x                                       //
372////////////////////////////////////////////////////////////////////////////////
373
374CanonicalForm convertNTLGF2X2CF(GF2X poly,Variable x)
375{
376  //printf("convertNTLGF2X2CF\n");
377  CanonicalForm bigone;
378
379  if (deg(poly)>0)
380  {
381    // poly is non-constant
382    bigone=0;
383    bigone.mapinto();
384    // Compute the canonicalform coefficient by coefficient,
385    // bigone summarizes the result.
386    // In constrast to the more general conversion to ZZpX
387    // the only possible coefficients are zero
388    // and one yielding the following simplified loop
389    for (int j=0;j<=deg(poly);j++)
390    {
391      if (coeff(poly,j)!=0) bigone+=power(x,j);
392     // *CanonicalForm(to_long(rep(coeff(poly,j))))) is not necessary any more;
393    }
394  }
395  else
396  {
397    // poly is immediate
398    bigone=CanonicalForm(to_long(rep(coeff(poly,0))));
399    bigone.mapinto();
400  }
401
402  return bigone;
403}
404
405////////////////////////////////////////////////////////////////////////////////
406// NAME: convertNTLvec_pair_ZZpX_long2FacCFFList                              //
407//                                                                            //
408// DESCRIPTION:                                                               //
409// Routine for converting a vector of polynomials from ZZpX to                //
410// a CFFList of Factory. This routine will be used after a successful         //
411// factorization of NTL to convert the result back to Factory.                //
412//                                                                            //
413// Additionally a variable x and the computed multiplicity, as a type ZZp     //
414// of NTL, is needed as parameters indicating the main variable of the        //
415// computed canonicalform and the multiplicity of the original polynomial.    //
416// To guarantee the correct execution of the algorithm the characteristic     //
417// has a be an arbitrary prime number.                                        //
418//                                                                            //
419// INPUT:  A vector of polynomials over ZZp of type vec_pair_ZZ_pX_long and   //
420//         a variable x and a multiplicity of type ZZp                        //
421// OUTPUT: The converted list of polynomials of type CFFList, all polynomials //
422//         have x as their main variable                                      //
423////////////////////////////////////////////////////////////////////////////////
424
425CFFList convertNTLvec_pair_ZZpX_long2FacCFFList
426                                  (vec_pair_ZZ_pX_long e,ZZ_p multi,Variable x)
427{
428  //printf("convertNTLvec_pair_ZZpX_long2FacCFFList\n");
429  CFFList rueckgabe;
430  ZZ_pX polynom;
431  CanonicalForm bigone;
432
433  // Maybe, e may additionally be sorted with respect to increasing degree of x
434  // but this is not
435  //important for the factorization, but nevertheless would take computing time,
436  // so it is omitted
437
438
439  // Go through the vector e and compute the CFFList
440  // again bigone summarizes the result
441  for (int i=e.length()-1;i>=0;i--)
442  {
443    rueckgabe.append(CFFactor(convertNTLZZpX2CF(e[i].a,x),e[i].b));
444  }
445  // the multiplicity at pos 1
446  if (!IsOne(multi))
447    rueckgabe.insert(CFFactor(CanonicalForm(to_long(rep(multi))),1));
448  return rueckgabe;
449}
450CFFList convertNTLvec_pair_zzpX_long2FacCFFList
451                                  (vec_pair_zz_pX_long e,zz_p multi,Variable x)
452{
453  //printf("convertNTLvec_pair_zzpX_long2FacCFFList\n");
454  CFFList rueckgabe;
455  zz_pX polynom;
456  CanonicalForm bigone;
457
458  // Maybe, e may additionally be sorted with respect to increasing degree of x
459  // but this is not
460  //important for the factorization, but nevertheless would take computing time,
461  // so it is omitted
462
463
464  // Go through the vector e and compute the CFFList
465  // again bigone summarizes the result
466  for (int i=e.length()-1;i>=0;i--)
467  {
468    rueckgabe.append(CFFactor(convertNTLzzpX2CF(e[i].a,x),e[i].b));
469  }
470  // the multiplicity at pos 1
471  if (!IsOne(multi))
472    rueckgabe.insert(CFFactor(CanonicalForm(to_long(rep(multi))),1));
473  return rueckgabe;
474}
475
476////////////////////////////////////////////////////////////////////////////////
477// NAME: convertNTLvec_pair_GF2X_long2FacCFFList                              //
478//                                                                            //
479// DESCRIPTION:                                                               //
480// Routine for converting a vector of polynomials of type GF2X from           //
481// NTL to a list CFFList of Factory. This routine will be used after a        //
482// successful factorization of NTL to convert the result back to Factory.     //
483// As usual this is simply a special case of the more general conversion      //
484// routine but again speeded up by leaving out unnecessary steps.             //
485// Additionally a variable x and the computed multiplicity, as type           //
486// GF2 of NTL, are needed as parameters indicating the main variable of the   //
487// computed canonicalform and the multiplicity of the original polynomial.    //
488// To guarantee the correct execution of the algorithm the characteristic     //
489// has a be an arbitrary prime number.                                        //
490//                                                                            //
491// INPUT:  A vector of polynomials over GF2 of type vec_pair_GF2X_long and    //
492//         a variable x and a multiplicity of type GF2                        //
493// OUTPUT: The converted list of polynomials of type CFFList, all             //
494//         polynomials have x as their main variable                          //
495////////////////////////////////////////////////////////////////////////////////
496
497CFFList convertNTLvec_pair_GF2X_long2FacCFFList
498                               (vec_pair_GF2X_long e,GF2 multi,Variable x)
499{
500  //printf("convertNTLvec_pair_GF2X_long2FacCFFList\n");
501  CFFList rueckgabe;
502  GF2X polynom;
503  long exponent;
504  CanonicalForm bigone;
505
506  // Maybe, e may additionally be sorted with respect to increasing degree of x
507  // but this is not
508  //important for the factorization, but nevertheless would take computing time
509  // so it is omitted.
510
511  //We do not have to worry about the multiplicity in GF2 since it equals one.
512
513  // Go through the vector e and compute the CFFList
514  // bigone summarizes the result again
515  for (int i=e.length()-1;i>=0;i--)
516  {
517    bigone=0;
518
519    polynom=e[i].a;
520    exponent=e[i].b;
521    for (int j=0;j<=deg(polynom);j++)
522    {
523      if (coeff(polynom,j)!=0)
524        bigone += (power(x,j)*CanonicalForm(to_long(rep(coeff(polynom,j)))));
525    }
526
527    //append the converted polynomial to the CFFList
528    rueckgabe.append(CFFactor(bigone,exponent));
529  }
530  return rueckgabe;
531}
532
533////////////////////////////////////////////////////////////////////////////////
534// NAME: convertZZ2CF                                                         //
535//                                                                            //
536// DESCRIPTION:                                                               //
537// Routine for conversion of integers represented in NTL as Type ZZ to        //
538// integers in Factory represented as canonicalform.                          //
539// To guarantee the correct execution of the algorithm the characteristic     //
540// has to equal zero.                                                         //
541//                                                                            //
542// INPUT:  The value coefficient of type ZZ that has to be converted          //
543// OUTPUT: The converted Factory-integer of type canonicalform                //
544////////////////////////////////////////////////////////////////////////////////
545
546static char *cf_stringtemp;
547static char *cf_stringtemp2;
548static int cf_stringtemp_l=0;
549CanonicalForm convertZZ2CF(ZZ coefficient)
550{
551  long coeff_long;
552  //CanonicalForm tmp=0;
553  char dummy[2];
554  int minusremainder=0;
555  char numbers[]="0123456789abcdef";
556
557  coeff_long=to_long(coefficient);
558
559  //Test whether coefficient can be represented as an immediate integer in Factory
560  if ( (NumBits(coefficient)<((long)NTL_ZZ_NBITS))
561  && (coeff_long>((long)MINIMMEDIATE))
562  && (coeff_long<((long)MAXIMMEDIATE)))
563  {
564    // coefficient is immediate --> return the coefficient as canonicalform
565    return CanonicalForm(coeff_long);
566  }
567  else
568  {
569    // coefficient is not immediate (gmp-number)
570    if (cf_stringtemp_l==0)
571    {
572      cf_stringtemp=(char *)Alloc(1023);
573      cf_stringtemp2=(char *)Alloc(1023);
574      cf_stringtemp[0]='\0';
575      cf_stringtemp2[0]='\0';
576      cf_stringtemp_l=1023;
577    }
578
579    // convert coefficient to char* (input for gmp)
580    dummy[1]='\0';
581
582    if (coefficient<0)
583    {
584      // negate coefficient, but store the sign in minusremainder
585      minusremainder=1;
586      coefficient=-coefficient;
587    }
588
589    int l=0;
590    while (coefficient>15)
591    {
592      ZZ quotient,remaind;
593      ZZ ten;ten=16;
594      DivRem(quotient,remaind,coefficient,ten);
595      dummy[0]=numbers[to_long(remaind)];
596      //tmp*=10; tmp+=to_long(remaind);
597
598      l++;
599      if (l>=cf_stringtemp_l-2)
600      {
601        Free(cf_stringtemp2,cf_stringtemp_l);
602        char *p=(char *)Alloc(cf_stringtemp_l*2);
603        //NTL_SNS
604        memcpy(p,cf_stringtemp,cf_stringtemp_l);
605        Free(cf_stringtemp,cf_stringtemp_l);
606        cf_stringtemp_l*=2;
607        cf_stringtemp=p;
608        cf_stringtemp2=(char *)Alloc(cf_stringtemp_l);
609      }
610      cf_stringtemp[l-1]=dummy[0];
611      cf_stringtemp[l]='\0';
612      //strcat(stringtemp,dummy);
613
614      coefficient=quotient;
615    }
616    //built up the string in dummy[0]
617    dummy[0]=numbers[to_long(coefficient)];
618    //NTL_SNS
619    l++;
620    cf_stringtemp[l-1]=dummy[0];
621    cf_stringtemp[l]='\0';
622    //tmp*=10; tmp+=to_long(coefficient);
623
624    if (minusremainder==1)
625    {
626      //Check whether coefficient has been negative at the start of the procedure
627      cf_stringtemp2[0]='-';
628      //tmp*=(-1);
629    }
630
631    //reverse the list to obtain the correct string
632    //NTL_SNS
633    for (int i=l-1;i>=0;i--) // l ist the position of \0
634    {
635      cf_stringtemp2[l-i-1+minusremainder]=cf_stringtemp[i];
636    }
637    cf_stringtemp2[l+minusremainder]='\0';
638  }
639
640  //convert the string to canonicalform using the char*-Constructor
641  return CanonicalForm(cf_stringtemp2,16);
642  //return tmp;
643}
644
645////////////////////////////////////////////////////////////////////////////////
646// NAME: convertFacCF2NTLZZX                                                  //
647//                                                                            //
648// DESCRIPTION:                                                               //
649// Routine for conversion of canonicalforms in Factory to polynomials         //
650// of type ZZX of NTL. To guarantee the correct execution of the              //
651// algorithm the characteristic has to equal zero.                            //
652//                                                                            //
653// INPUT:  The canonicalform that has to be converted                         //
654// OUTPUT: The converted NTL-polynom of type ZZX                              //
655////////////////////////////////////////////////////////////////////////////////
656
657ZZX convertFacCF2NTLZZX(CanonicalForm f)
658{
659    ZZX ntl_poly;
660
661    CFIterator i;
662    i=f;
663
664    int NTLcurrentExp=i.exp();
665    int largestExp=i.exp();
666    int k;
667
668    //set the length of the NTL-polynomial
669    ntl_poly.SetMaxLength(largestExp+1);
670
671    //Go through the coefficients of the canonicalform and build up the NTL-polynomial
672    for (;i.hasTerms();i++)
673    {
674      for (k=NTLcurrentExp;k>i.exp();k--)
675      {
676        SetCoeff(ntl_poly,k,0);
677      }
678      NTLcurrentExp=i.exp();
679
680      if (!i.coeff().isImm())
681      {
682        //Coefficient is a gmp-number
683        mpz_t gmp_val;
684        ZZ temp;
685        char* stringtemp;
686
687        gmp_val[0]=getmpi(i.coeff().getval());
688        int l=mpz_sizeinbase(gmp_val,10)+2;
689        stringtemp=(char*)Alloc(l);
690        stringtemp=mpz_get_str(stringtemp,10,gmp_val);
691        mpz_clear(gmp_val);
692        conv(temp,stringtemp);
693        Free(stringtemp,l);
694
695        //set the computed coefficient
696        SetCoeff(ntl_poly,NTLcurrentExp,temp);
697      }
698      else
699      {
700        //Coefficient is immediate --> use its value
701        SetCoeff(ntl_poly,NTLcurrentExp,i.coeff().intval());
702      }
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= 0;
1076  for (int j=0;j<=deg(f);j++)
1077  {
1078    if (IsOne(coeff(f,j)))
1079      bigone+=power(x,j);
1080      else
1081      {
1082        //cout << "hier doof" << "\n";
1083        CanonicalForm coefficient=convertNTLzzpE2CF(coeff(f,j),alpha);
1084        //cout << "ja" << "\n";
1085        if (coeff(f,j)!=0)
1086          bigone += (power(x,j)*coefficient);
1087      }
1088  }
1089}
1090#endif
Note: See TracBrowser for help on using the repository browser.