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