Context Navigation

source: git/factory/NTLconvert.cc @ a99e31

spielwiese

Last change on this file since a99e31 was a99e31, checked in by Hans Schönemann <hannes@…>, 22 years ago
*hannes: NTL -inactive git-svn-id: file:///usr/local/Singular/svn/trunk@5981 2c84dea3-7e68-4137-9b89-c4e89433aadc
Property mode set to `100644`
File size: 29.5 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: