source: git/factory/NTLconvert.cc @ c729f2

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