Context Navigation

source: git/factory/cf_factor.cc

spielwiese

Last change on this file was 55b50e3, checked in by Marc Mezzarobba <marc@…>, 10 months ago
make Singular build with flint3 (#1177)
Property mode set to `100644`
File size: 25.5 KB

Line
1	/* emacs edit mode for this file is -- C++ -- */
2
3	/**
4	*
5	* @file cf_factor.cc
6	*
7	* Interface to factorization and square free factorization algorithms.
8	*
9	* Used by: cf_irred.cc
10	*
11	* Header file: cf_algorithm.h
12	*
13	**/
14
15
16	#include "config.h"
17
18
19	#include "cf_assert.h"
20
21	#include "cf_defs.h"
22	#include "canonicalform.h"
23	#include "cf_iter.h"
24	#include "fac_sqrfree.h"
25	#include "cf_algorithm.h"
26	#include "facFqFactorize.h"
27	#include "facFqSquarefree.h"
28	#include "cf_map.h"
29	#include "facAlgExt.h"
30	#include "facFactorize.h"
31	#include "singext.h"
32	#include "cf_util.h"
33	#include "fac_berlekamp.h"
34	#include "fac_cantzass.h"
35	#include "fac_univar.h"
36	#include "fac_multivar.h"
37
38	#include "int_int.h"
39	#ifdef HAVE_NTL
40	#include "NTLconvert.h"
41	#endif
42
43	#include "factory/cf_gmp.h"
44	#ifdef HAVE_FLINT
45	#include "FLINTconvert.h"
46	#if (__FLINT_RELEASE >= 20700)
47	#include <flint/nmod_mpoly_factor.h>
48	#include <flint/fmpq_mpoly_factor.h>
49	#include <flint/fq_nmod_mpoly_factor.h>
50	#include <flint/nmod_poly_factor.h>
51	#include <flint/fmpz_poly_factor.h>
52	#include <flint/fmpz_mpoly_factor.h>
53	#include <flint/fq_nmod_poly_factor.h>
54	#endif
55	#endif
56
57	//static bool isUnivariateBaseDomain( const CanonicalForm & f )
58	//{
59	// CFIterator i = f;
60	// bool ok = i.coeff().inBaseDomain();
61	// i++;
62	// while ( i.hasTerms() && ( ok = ok && i.coeff().inBaseDomain() ) ) i++;
63	// return ok;
64	//}
65
66	void find_exp(const CanonicalForm & f, int * exp_f)
67	{
68	if ( ! f.inCoeffDomain() )
69	{
70	int e=f.level();
71	CFIterator i = f;
72	if (e>=0)
73	{
74	if (i.exp() > exp_f[e]) exp_f[e]=i.exp();
75	}
76	for (; i.hasTerms(); i++ )
77	{
78	find_exp(i.coeff(), exp_f);
79	}
80	}
81	}
82
83	int find_mvar(const CanonicalForm & f)
84	{
85	int mv=f.level();
86	int *exp_f=NEW_ARRAY(int,mv+1);
87	int i;
88	for(i=mv;i>0;i--) exp_f[i]=0;
89	find_exp(f,exp_f);
90	for(i=mv;i>0;i--)
91	{
92	if ((exp_f[i]>0) && (exp_f[i]<exp_f[mv]))
93	{
94	mv=i;
95	}
96	}
97	DELETE_ARRAY(exp_f);
98	return mv;
99	}
100
101	#if 1
102	//#ifndef NOSTREAMIO
103	void out_cf(const char s1,const CanonicalForm &f,const char s2)
104	{
105	printf("%s",s1);
106	if (f.isZero()) printf("+0");
107	//else if (! f.inCoeffDomain() )
108	else if (! f.inBaseDomain() )
109	{
110	int l = f.level();
111	for ( CFIterator i = f; i.hasTerms(); i++ )
112	{
113	int e=i.exp();
114	if (i.coeff().isOne())
115	{
116	printf("+");
117	if (e==0) printf("1");
118	else
119	{
120	printf("%c",'a'+l-1);
121	if (e!=1) printf("^%d",e);
122	}
123	}
124	else
125	{
126	out_cf("+(",i.coeff(),")");
127	if (e!=0)
128	{
129	printf("*%c",'a'+l-1);
130	if (e!=1) printf("^%d",e);
131	}
132	}
133	}
134	}
135	else
136	{
137	if ( f.isImm() )
138	{
139	if (CFFactory::gettype()==GaloisFieldDomain)
140	{
141	long a= imm2int (f.getval());
142	if ( a == gf_q )
143	printf ("+%ld", a);
144	else if ( a == 0L )
145	printf ("+1");
146	else if ( a == 1L )
147	printf ("+%c",gf_name);
148	else
149	{
150	printf ("+%c",gf_name);
151	printf ("^%ld",a);
152	}
153	}
154	else
155	{
156	long l=f.intval();
157	if (l<0) printf("%ld",l);
158	else printf("+%ld",l);
159	}
160	}
161	else
162	{
163	#ifdef NOSTREAMIO
164	if (f.inZ())
165	{
166	mpz_t m;
167	gmp_numerator(f,m);
168	char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
169	str = mpz_get_str( str, 10, m );
170	puts(str);
171	delete[] str;
172	mpz_clear(m);
173	}
174	else if (f.inQ())
175	{
176	mpz_t m;
177	gmp_numerator(f,m);
178	char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
179	str = mpz_get_str( str, 10, m );
180	while(str[strlen(str)]<' ') { str[strlen(str)]='\0'; }
181	puts(str);putchar('/');
182	delete[] str;
183	mpz_clear(m);
184	gmp_denominator(f,m);
185	str = new char[mpz_sizeinbase( m, 10 ) + 2];
186	str = mpz_get_str( str, 10, m );
187	while(str[strlen(str)]<' ') { str[strlen(str)]='\0'; }
188	puts(str);
189	delete[] str;
190	mpz_clear(m);
191	}
192	#else
193	std::cout << f;
194	#endif
195	}
196	//if (f.inZ()) printf("(Z)");
197	//else if (f.inQ()) printf("(Q)");
198	//else if (f.inFF()) printf("(FF)");
199	//else if (f.inPP()) printf("(PP)");
200	//else if (f.inGF()) printf("(PP)");
201	//else
202	if (f.inExtension()) printf("E(%d)",f.level());
203	}
204	printf("%s",s2);
205	}
206	void out_cff(CFFList &L)
207	{
208	//int n = L.length();
209	CFFListIterator J=L;
210	int j=0;
211	for ( ; J.hasItem(); J++, j++ )
212	{
213	printf("F%d",j);out_cf(":",J.getItem().factor()," ^ ");
214	printf("%d\n", J.getItem().exp());
215	}
216	}
217	void test_cff(CFFList &L,const CanonicalForm & f)
218	{
219	//int n = L.length();
220	CFFListIterator J=L;
221	CanonicalForm t=1;
222	int j=0;
223	if (!(L.getFirst().factor().inCoeffDomain()))
224	printf("first entry is not const\n");
225	for ( ; J.hasItem(); J++, j++ )
226	{
227	CanonicalForm tt=J.getItem().factor();
228	if (tt.inCoeffDomain() && (j!=0))
229	printf("other entry is const\n");
230	j=J.getItem().exp();
231	while(j>0) { t*=tt; j--; }
232	}
233	if (!(f-t).isZero()) { printf("problem:\n");out_cf("factor:",f," has problems\n");}
234	}
235	//#endif
236	#endif
237
238	bool isPurePoly_m(const CanonicalForm & f)
239	{
240	if (f.inBaseDomain()) return true;
241	if (f.level()<0) return false;
242	for (CFIterator i=f;i.hasTerms();i++)
243	{
244	if (!isPurePoly_m(i.coeff())) return false;
245	}
246	return true;
247	}
248	bool isPurePoly(const CanonicalForm & f)
249	{
250	if (f.level()<=0) return false;
251	for (CFIterator i=f;i.hasTerms();i++)
252	{
253	if (!(i.coeff().inBaseDomain())) return false;
254	}
255	return true;
256	}
257
258
259	/**
260	* get_max_degree_Variable returns Variable with
261	* highest degree. We assume f is not a constant!
262	**/
263	Variable
264	get_max_degree_Variable(const CanonicalForm & f)
265	{
266	ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
267	int max=0, maxlevel=0, n=level(f);
268	for ( int i=1; i<=n; i++ )
269	{
270	if (degree(f,Variable(i)) >= max)
271	{
272	max= degree(f,Variable(i)); maxlevel= i;
273	}
274	}
275	return Variable(maxlevel);
276	}
277
278	/**
279	* get_Terms: Split the polynomial in the containing terms.
280	* getTerms: the real work is done here.
281	**/
282	void
283	getTerms( const CanonicalForm & f, const CanonicalForm & t, CFList & result )
284	{
285	if ( getNumVars(f) == 0 ) result.append(f*t);
286	else{
287	Variable x(level(f));
288	for ( CFIterator i=f; i.hasTerms(); i++ )
289	getTerms( i.coeff(), t*power(x,i.exp()), result);
290	}
291	}
292	CFList
293	get_Terms( const CanonicalForm & f ){
294	CFList result,dummy,dummy2;
295	CFIterator i;
296	CFListIterator j;
297
298	if ( getNumVars(f) == 0 ) result.append(f);
299	else{
300	Variable _x(level(f));
301	for ( i=f; i.hasTerms(); i++ ){
302	getTerms(i.coeff(), 1, dummy);
303	for ( j=dummy; j.hasItem(); j++ )
304	result.append(j.getItem() * power(_x, i.exp()));
305
306	dummy= dummy2; // have to initalize new
307	}
308	}
309	return result;
310	}
311
312
313	/**
314	* homogenize homogenizes f with Variable x
315	**/
316	CanonicalForm
317	homogenize( const CanonicalForm & f, const Variable & x)
318	{
319	#if 0
320	int maxdeg=totaldegree(f), deg;
321	CFIterator i;
322	CanonicalForm elem, result(0);
323
324	for (i=f; i.hasTerms(); i++)
325	{
326	elem= i.coeff()*power(f.mvar(),i.exp());
327	deg = totaldegree(elem);
328	if ( deg < maxdeg )
329	result += elem * power(x,maxdeg-deg);
330	else
331	result+=elem;
332	}
333	return result;
334	#else
335	CFList Newlist, Termlist= get_Terms(f);
336	int maxdeg=totaldegree(f), deg;
337	CFListIterator i;
338	CanonicalForm elem, result(0);
339
340	for (i=Termlist; i.hasItem(); i++)
341	{
342	elem= i.getItem();
343	deg = totaldegree(elem);
344	if ( deg < maxdeg )
345	Newlist.append(elem * power(x,maxdeg-deg));
346	else
347	Newlist.append(elem);
348	}
349	for (i=Newlist; i.hasItem(); i++) // rebuild
350	result += i.getItem();
351
352	return result;
353	#endif
354	}
355
356	CanonicalForm
357	homogenize( const CanonicalForm & f, const Variable & x, const Variable & v1, const Variable & v2)
358	{
359	#if 0
360	int maxdeg=totaldegree(f), deg;
361	CFIterator i;
362	CanonicalForm elem, result(0);
363
364	for (i=f; i.hasTerms(); i++)
365	{
366	elem= i.coeff()*power(f.mvar(),i.exp());
367	deg = totaldegree(elem);
368	if ( deg < maxdeg )
369	result += elem * power(x,maxdeg-deg);
370	else
371	result+=elem;
372	}
373	return result;
374	#else
375	CFList Newlist, Termlist= get_Terms(f);
376	int maxdeg=totaldegree(f), deg;
377	CFListIterator i;
378	CanonicalForm elem, result(0);
379
380	for (i=Termlist; i.hasItem(); i++)
381	{
382	elem= i.getItem();
383	deg = totaldegree(elem,v1,v2);
384	if ( deg < maxdeg )
385	Newlist.append(elem * power(x,maxdeg-deg));
386	else
387	Newlist.append(elem);
388	}
389	for (i=Newlist; i.hasItem(); i++) // rebuild
390	result += i.getItem();
391
392	return result;
393	#endif
394	}
395
396	VAR int singular_homog_flag=1;
397
398	int cmpCF( const CFFactor & f, const CFFactor & g )
399	{
400	if (f.exp() > g.exp()) return 1;
401	if (f.exp() < g.exp()) return 0;
402	if (f.factor() > g.factor()) return 1;
403	return 0;
404	}
405
406	/**
407	* factorization over \f$ F_p \f$ or \f$ Q \f$
408	**/
409	CFFList factorize ( const CanonicalForm & f, bool issqrfree )
410	{
411	if ( f.inCoeffDomain() )
412	return CFFList( f );
413	#ifndef NOASSERT
414	Variable a;
415	ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
416	( const CanonicalForm & f, const Variable & alpha ) instead");
417	#endif
418	//out_cf("factorize:",f,"==================================\n");
419	if (! f.isUnivariate() ) // preprocess homog. polys
420	{
421	if ( singular_homog_flag && f.isHomogeneous())
422	{
423	Variable xn = get_max_degree_Variable(f);
424	int d_xn = degree(f,xn);
425	CFMap n;
426	CanonicalForm F = compress(f(1,xn),n);
427	CFFList Intermediatelist;
428	Intermediatelist = factorize(F);
429	CFFList Homoglist;
430	CFFListIterator j;
431	for ( j=Intermediatelist; j.hasItem(); j++ )
432	{
433	Homoglist.append(
434	CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
435	}
436	CFFList Unhomoglist;
437	CanonicalForm unhomogelem;
438	for ( j=Homoglist; j.hasItem(); j++ )
439	{
440	unhomogelem= homogenize(j.getItem().factor(),xn);
441	Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
442	d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
443	}
444	if ( d_xn != 0 ) // have to append xn^(d_xn)
445	Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
446	if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
447	return Unhomoglist;
448	}
449	}
450	CFFList F;
451	if ( getCharacteristic() > 0 )
452	{
453	if (f.isUnivariate())
454	{
455	#ifdef HAVE_FLINT
456	#ifdef HAVE_NTL
457	if (degree (f) < 300)
458	#endif
459	{
460	// use FLINT: char p, univariate
461	nmod_poly_t f1;
462	convertFacCF2nmod_poly_t (f1, f);
463	nmod_poly_factor_t result;
464	nmod_poly_factor_init (result);
465	mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
466	F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
467	nmod_poly_factor_clear (result);
468	nmod_poly_clear (f1);
469	if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
470	return F;
471	}
472	#endif
473	#ifdef HAVE_NTL
474	{ // NTL char 2, univariate
475	if (getCharacteristic()==2)
476	{
477	// Specialcase characteristic==2
478	if (fac_NTL_char != 2)
479	{
480	fac_NTL_char = 2;
481	zz_p::init(2);
482	}
483	// convert to NTL using the faster conversion routine for characteristic 2
484	GF2X f1=convertFacCF2NTLGF2X(f);
485	// no make monic necessary in GF2
486	//factorize
487	vec_pair_GF2X_long factors;
488	CanZass(factors,f1);
489
490	// convert back to factory again using the faster conversion routine for vectors over GF2X
491	F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
492	if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
493	return F;
494	}
495	}
496	#endif
497	#ifdef HAVE_NTL
498	{
499	// use NTL char p, univariate
500	if (fac_NTL_char != getCharacteristic())
501	{
502	fac_NTL_char = getCharacteristic();
503	zz_p::init(getCharacteristic());
504	}
505
506	// convert to NTL
507	zz_pX f1=convertFacCF2NTLzzpX(f);
508	zz_p leadcoeff = LeadCoeff(f1);
509
510	//make monic
511	f1=f1 / LeadCoeff(f1);
512	// factorize
513	vec_pair_zz_pX_long factors;
514	CanZass(factors,f1);
515
516	F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
517	//test_cff(F,f);
518	if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
519	return F;
520	}
521	#endif
522	#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
523	// Use Factory without NTL and without FLINT: char p, univariate
524	{
525	if ( isOn( SW_BERLEKAMP ) )
526	F=FpFactorizeUnivariateB( f, issqrfree );
527	else
528	F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
529	return F;
530	}
531	#endif
532	}
533	else // char p, multivariate
534	{
535	if (CFFactory::gettype() == GaloisFieldDomain)
536	{
537	#if defined(HAVE_NTL)
538	if (issqrfree)
539	{
540	CFList factors;
541	Variable alpha;
542	factors= GFSqrfFactorize (f);
543	for (CFListIterator i= factors; i.hasItem(); i++)
544	F.append (CFFactor (i.getItem(), 1));
545	}
546	else
547	{
548	Variable alpha;
549	F= GFFactorize (f);
550	}
551	#else
552	factoryError ("multivariate factorization over GF depends on NTL(missing)");
553	return CFFList (CFFactor (f, 1));
554	#endif
555	}
556	else
557	{
558	#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
559	if (!isOn(SW_USE_FL_FAC_P))
560	{
561	#endif
562	#if defined(HAVE_NTL)
563	if (issqrfree)
564	{
565	CFList factors;
566	Variable alpha;
567	factors= FpSqrfFactorize (f);
568	for (CFListIterator i= factors; i.hasItem(); i++)
569	F.append (CFFactor (i.getItem(), 1));
570	goto end_charp;
571	}
572	else
573	{
574	Variable alpha;
575	F= FpFactorize (f);
576	goto end_charp;
577	}
578	#endif
579	#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
580	}
581	#endif
582	#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
583	nmod_mpoly_ctx_t ctx;
584	nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,getCharacteristic());
585	nmod_mpoly_t Flint_f;
586	nmod_mpoly_init(Flint_f,ctx);
587	convFactoryPFlintMP(f,Flint_f,ctx,f.level());
588	nmod_mpoly_factor_t factors;
589	nmod_mpoly_factor_init(factors,ctx);
590	int okay;
591	if (issqrfree) okay=nmod_mpoly_factor_squarefree(factors,Flint_f,ctx);
592	else okay=nmod_mpoly_factor(factors,Flint_f,ctx);
593	nmod_mpoly_t fac;
594	nmod_mpoly_init(fac,ctx);
595	CanonicalForm cf_fac;
596	int cf_exp;
597	cf_fac=nmod_mpoly_factor_get_constant_ui(factors,ctx);
598	F.append(CFFactor(cf_fac,1));
599	for(int i=nmod_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
600	{
601	nmod_mpoly_factor_get_base(fac,factors,i,ctx);
602	cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
603	cf_exp=nmod_mpoly_factor_get_exp_si(factors,i,ctx);
604	F.append(CFFactor(cf_fac,cf_exp));
605	}
606	nmod_mpoly_factor_clear(factors,ctx);
607	nmod_mpoly_clear(Flint_f,ctx);
608	nmod_mpoly_ctx_clear(ctx);
609	if (okay==0)
610	{
611	Off(SW_USE_FL_GCD_P);
612	Off(SW_USE_FL_FAC_P);
613	F=factorize(f,issqrfree);
614	On(SW_USE_FL_GCD_P);
615	On(SW_USE_FL_FAC_P);
616	}
617	#endif
618	#if !defined(HAVE_FLINT) \|\| (__FLINT_RELEASE < 20700)
619	#ifndef HAVE_NTL
620	factoryError ("multivariate factorization depends on NTL/FLINT(missing)");
621	return CFFList (CFFactor (f, 1));
622	#endif
623	#endif
624	}
625	}
626	}
627	else // char 0
628	{
629	bool on_rational = isOn(SW_RATIONAL);
630	On(SW_RATIONAL);
631	CanonicalForm cd = bCommonDen( f );
632	CanonicalForm fz = f * cd;
633	Off(SW_RATIONAL);
634	if ( f.isUnivariate() )
635	{
636	CanonicalForm ic=icontent(fz);
637	fz/=ic;
638	if (fz.degree()==1)
639	{
640	F=CFFList(CFFactor(fz,1));
641	F.insert(CFFactor(ic,1));
642	}
643	else
644	#if defined(HAVE_FLINT) && (__FLINT_RELEASE>=20503) && (__FLINT_RELEASE!= 20600)
645	{
646	// FLINT 2.6.0 has a bug:
647	// factorize x^12-13x^10-13x^8+13x^4+13x^2-1 runs forever
648	// use FLINT: char 0, univariate
649	fmpz_poly_t f1;
650	convertFacCF2Fmpz_poly_t (f1, fz);
651	fmpz_poly_factor_t result;
652	fmpz_poly_factor_init (result);
653	fmpz_poly_factor(result, f1);
654	F= convertFLINTfmpz_poly_factor2FacCFFList (result, fz.mvar());
655	fmpz_poly_factor_clear (result);
656	fmpz_poly_clear (f1);
657	if ( ! ic.isOne() )
658	{
659	// according to convertFLINTfmpz_polyfactor2FcaCFFlist,
660	// first entry is in CoeffDomain
661	CFFactor new_first( F.getFirst().factor() * ic );
662	F.removeFirst();
663	F.insert( new_first );
664	}
665	}
666	goto end_char0;
667	#elif defined(HAVE_NTL)
668	{
669	//use NTL
670	ZZ c;
671	vec_pair_ZZX_long factors;
672	//factorize the converted polynomial
673	factor(c,factors,convertFacCF2NTLZZX(fz));
674
675	//convert the result back to Factory
676	F=convertNTLvec_pair_ZZX_long2FacCFFList(factors,c,fz.mvar());
677	if ( ! ic.isOne() )
678	{
679	// according to convertNTLvec_pair_ZZX_long2FacCFFList
680	// first entry is in CoeffDomain
681	CFFactor new_first( F.getFirst().factor() * ic );
682	F.removeFirst();
683	F.insert( new_first );
684	}
685	}
686	goto end_char0;
687	#else
688	{
689	//Use Factory without NTL: char 0, univariate
690	F = ZFactorizeUnivariate( fz, issqrfree );
691	goto end_char0;
692	}
693	#endif
694	}
695	else // multivariate, char 0
696	{
697	#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
698	if (isOn(SW_USE_FL_FAC_0))
699	{
700	On (SW_RATIONAL);
701	fmpz_mpoly_ctx_t ctx;
702	fmpz_mpoly_ctx_init(ctx,f.level(),ORD_LEX);
703	fmpz_mpoly_t Flint_f;
704	fmpz_mpoly_init(Flint_f,ctx);
705	convFactoryPFlintMP(fz,Flint_f,ctx,fz.level());
706	fmpz_mpoly_factor_t factors;
707	fmpz_mpoly_factor_init(factors,ctx);
708	int rr;
709	if (issqrfree) rr=fmpz_mpoly_factor_squarefree(factors,Flint_f,ctx);
710	else rr=fmpz_mpoly_factor(factors,Flint_f,ctx);
711	if (rr==0) printf("fail\n");
712	fmpz_mpoly_t fac;
713	fmpz_mpoly_init(fac,ctx);
714	CanonicalForm cf_fac;
715	int cf_exp;
716	fmpz_t c;
717	fmpz_init(c);
718	fmpz_mpoly_factor_get_constant_fmpz(c,factors,ctx);
719	cf_fac=convertFmpz2CF(c);
720	fmpz_clear(c);
721	F.append(CFFactor(cf_fac,1));
722	for(int i=fmpz_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
723	{
724	fmpz_mpoly_factor_get_base(fac,factors,i,ctx);
725	cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
726	cf_exp=fmpz_mpoly_factor_get_exp_si(factors,i,ctx);
727	F.append(CFFactor(cf_fac,cf_exp));
728	}
729	fmpz_mpoly_factor_clear(factors,ctx);
730	fmpz_mpoly_clear(Flint_f,ctx);
731	fmpz_mpoly_ctx_clear(ctx);
732	goto end_char0;
733	}
734	#endif
735	#if defined(HAVE_NTL)
736	On (SW_RATIONAL);
737	if (issqrfree)
738	{
739	CFList factors= ratSqrfFactorize (fz);
740	for (CFListIterator i= factors; i.hasItem(); i++)
741	F.append (CFFactor (i.getItem(), 1));
742	}
743	else
744	{
745	F = ratFactorize (fz);
746	}
747	#endif
748	#if !defined(HAVE_FLINT) \|\| (__FLINT_RELEASE < 20700)
749	#ifndef HAVE_NTL
750	F=ZFactorizeMultivariate(fz, issqrfree);
751	#endif
752	#endif
753	}
754
755	end_char0:
756	if ( on_rational )
757	On(SW_RATIONAL);
758	else
759	Off(SW_RATIONAL);
760	if ( ! cd.isOne() )
761	{
762	CFFactor new_first( F.getFirst().factor() / cd );
763	F.removeFirst();
764	F.insert( new_first );
765	}
766	}
767
768	#if defined(HAVE_NTL)
769	end_charp:
770	#endif
771	if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
772	return F;
773	}
774
775	/**
776	* factorization over \f$ F_p(\alpha) \f$ or \f$ Q(\alpha) \f$
777	**/
778	CFFList factorize ( const CanonicalForm & f, const Variable & alpha )
779	{
780	if ( f.inCoeffDomain() )
781	return CFFList( f );
782	//out_cf("factorize:",f,"==================================\n");
783	//out_cf("mipo:",getMipo(alpha),"\n");
784
785	CFFList F;
786	ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
787	#ifndef NOASSERT
788	Variable beta;
789	if (hasFirstAlgVar(f, beta))
790	ASSERT (beta == alpha, "f has an algebraic variable that \
791	does not coincide with alpha");
792	#endif
793	int ch=getCharacteristic();
794	if (ch>0)
795	{
796	if (f.isUnivariate())
797	{
798	#ifdef HAVE_NTL
799	if (/getCharacteristic()/ch==2)
800	{
801	// special case : GF2
802
803	// remainder is two ==> nothing to do
804
805	// set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
806	GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
807	GF2E::init (minPo);
808
809	// convert to NTL again using the faster conversion routines
810	GF2EX f1;
811	if (isPurePoly(f))
812	{
813	GF2X f_tmp=convertFacCF2NTLGF2X(f);
814	f1=to_GF2EX(f_tmp);
815	}
816	else
817	f1=convertFacCF2NTLGF2EX(f,minPo);
818
819	// make monic (in Z/2(a))
820	GF2E f1_coef=LeadCoeff(f1);
821	MakeMonic(f1);
822
823	// factorize using NTL
824	vec_pair_GF2EX_long factors;
825	CanZass(factors,f1);
826
827	// return converted result
828	F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
829	if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
830	return F;
831	}
832	#endif
833	#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
834	{
835	// use FLINT
836	nmod_poly_t FLINTmipo, leadingCoeff;
837	fq_nmod_ctx_t fq_con;
838
839	nmod_poly_init (FLINTmipo, ch);
840	nmod_poly_init (leadingCoeff, ch);
841	convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
842
843	fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
844	fq_nmod_poly_t FLINTF;
845	convertFacCF2Fq_nmod_poly_t (FLINTF, f, fq_con);
846	fq_nmod_poly_factor_t res;
847	fq_nmod_poly_factor_init (res, fq_con);
848	fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
849	F= convertFLINTFq_nmod_poly_factor2FacCFFList (res, f.mvar(), alpha, fq_con);
850	F.insert (CFFactor (Lc (f), 1));
851
852	fq_nmod_poly_factor_clear (res, fq_con);
853	fq_nmod_poly_clear (FLINTF, fq_con);
854	nmod_poly_clear (FLINTmipo);
855	nmod_poly_clear (leadingCoeff);
856	fq_nmod_ctx_clear (fq_con);
857	if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
858	return F;
859	}
860	#endif
861	#ifdef HAVE_NTL
862	{
863	// use NTL
864	if (fac_NTL_char != ch)
865	{
866	fac_NTL_char = ch;
867	zz_p::init(ch);
868	}
869
870	// set minimal polynomial in NTL
871	zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
872	zz_pE::init (minPo);
873
874	// convert to NTL
875	zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
876	zz_pE leadcoeff= LeadCoeff(f1);
877
878	//make monic
879	f1=f1 / leadcoeff; //leadcoeff==LeadCoeff(f1);
880
881	// factorize
882	vec_pair_zz_pEX_long factors;
883	CanZass(factors,f1);
884
885	// return converted result
886	F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
887	//test_cff(F,f);
888	if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
889	return F;
890	}
891	#endif
892	#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
893	// char p, extension, univariate
894	CanonicalForm c=Lc(f);
895	CanonicalForm fc=f/c;
896	F=FpFactorizeUnivariateCZ( fc, false, 1, alpha, Variable() );
897	F.insert (CFFactor (c, 1));
898	#endif
899	}
900	else // char p, multivariate
901	{
902	#if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
903	// use FLINT
904	nmod_poly_t FLINTmipo;
905	fq_nmod_ctx_t fq_con;
906	fq_nmod_mpoly_ctx_t ctx;
907
908	nmod_poly_init (FLINTmipo, ch);
909	convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
910
911	fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
912	fq_nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,fq_con);
913
914	fq_nmod_mpoly_t FLINTF;
915	fq_nmod_mpoly_init(FLINTF,ctx);
916	convertFacCF2Fq_nmod_mpoly_t(FLINTF,f,ctx,f.level(),fq_con);
917	fq_nmod_mpoly_factor_t res;
918	fq_nmod_mpoly_factor_init (res, ctx);
919	fq_nmod_mpoly_factor (res, FLINTF, ctx);
920	F= convertFLINTFq_nmod_mpoly_factor2FacCFFList (res, ctx,f.level(),fq_con,alpha);
921	//F.insert (CFFactor (Lc (f), 1));
922
923	fq_nmod_mpoly_factor_clear (res, ctx);
924	fq_nmod_mpoly_clear (FLINTF, ctx);
925	nmod_poly_clear (FLINTmipo);
926	fq_nmod_mpoly_ctx_clear (ctx);
927	fq_nmod_ctx_clear (fq_con);
928	if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
929	return F;
930	#elif defined(HAVE_NTL)
931	F= FqFactorize (f, alpha);
932	#else
933	factoryError ("multivariate factorization over Z/pZ(alpha) depends on NTL/Flint(missing)");
934	return CFFList (CFFactor (f, 1));
935	#endif
936	}
937	}
938	else // Q(a)[x]
939	{
940	if (f.isUnivariate())
941	{
942	F= AlgExtFactorize (f, alpha);
943	}
944	else //Q(a)[x1,...,xn]
945	{
946	#if defined(HAVE_NTL) \|\| defined(HAVE_FLINT)
947	F= ratFactorize (f, alpha);
948	#else
949	factoryError ("multivariate factorization over Q(alpha) depends on NTL or FLINT (missing)");
950	return CFFList (CFFactor (f, 1));
951	#endif
952	}
953	}
954	if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
955	return F;
956	}
957
958	/**
959	* squarefree factorization
960	**/
961	CFFList sqrFree ( const CanonicalForm & f, bool sort )
962	{
963	// ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
964	CFFList result;
965
966	if ( getCharacteristic() == 0 )
967	result = sqrFreeZ( f );
968	else
969	{
970	Variable alpha;
971	if (hasFirstAlgVar (f, alpha))
972	result = FqSqrf( f, alpha );
973	else
974	result= FpSqrf (f);
975	}
976	if (sort)
977	{
978	CFFactor buf= result.getFirst();
979	result.removeFirst();
980	result= sortCFFList (result);
981	result.insert (buf);
982	}
983	return result;
984	}
985

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

Download in other formats: