Context Navigation

source: git/factory/facAbsBiFact.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: 21.8 KB

Line
1	/*****************************************************************************\
2	* Computer Algebra System SINGULAR
3	\*****************************************************************************/
4	/** @file facAbsBiFact.cc
5	*
6	* @author Martin Lee
7	*
8	**/
9	/*****************************************************************************/
10
11
12	#include "config.h"
13
14
15	#include "timing.h"
16	#include "debug.h"
17
18	#include "facAbsBiFact.h"
19	#include "facBivar.h"
20	#include "facFqBivar.h"
21	#include "cf_reval.h"
22	#include "cf_primes.h"
23	#include "cf_algorithm.h"
24	#ifdef HAVE_FLINT
25	#include "FLINTconvert.h"
26	#include "flint/nmod_poly_factor.h"
27	#include <flint/fmpz_poly_factor.h>
28	#endif
29	#ifdef HAVE_NTL
30	#include "NTLconvert.h"
31	#include <NTL/LLL.h>
32	#endif
33
34	#if defined(HAVE_NTL) \|\| defined(HAVE_FLINT)
35	TIMING_DEFINE_PRINT(fac_Qa_factorize)
36	TIMING_DEFINE_PRINT(fac_evalpoint)
37
38	CFAFList uniAbsFactorize (const CanonicalForm& F, bool full)
39	{
40	CFAFList result;
41	if (degree (F) == 1)
42	{
43	bool isRat= isOn (SW_RATIONAL);
44	On (SW_RATIONAL);
45	result= CFAFList (CFAFactor (F/Lc(F), 1, 1));
46	result.insert (CFAFactor (Lc (F), 1, 1));
47	if (!isRat)
48	Off (SW_RATIONAL);
49	return result;
50	}
51	CanonicalForm LcF= 1;
52	Variable alpha;
53	CFFList QaFactors;
54	CFFListIterator iter;
55	alpha= rootOf (F);
56	QaFactors= factorize (F, alpha);
57	iter= QaFactors;
58	if (iter.getItem().factor().inCoeffDomain())
59	{
60	LcF = iter.getItem().factor();
61	iter++;
62	}
63	for (;iter.hasItem(); iter++)
64	{
65	if (full)
66	result.append (CFAFactor (iter.getItem().factor(), getMipo (alpha),
67	iter.getItem().exp()));
68	if (!full && degree (iter.getItem().factor()) == 1)
69	{
70	result.append (CFAFactor (iter.getItem().factor(), getMipo (alpha),
71	iter.getItem().exp()));
72	break;
73	}
74	}
75	result.insert (CFAFactor (LcF, 1, 1));
76	return result;
77	}
78
79	//TODO optimize choice of p -> choose p as large as possible (better than small p since factorization mod p does not require field extension, also less lifting)
80	int
81	choosePoint (const CanonicalForm& F, int tdegF, CFArray& eval, bool rec,
82	int absValue)
83	{
84	REvaluation E1 (1, 1, IntRandom (absValue));
85	REvaluation E2 (2, 2, IntRandom (absValue));
86	if (rec)
87	{
88	E1.nextpoint();
89	E2.nextpoint();
90	}
91
92	CanonicalForm f, f1, f2, Fp;
93	int i, p;
94	CFFList f1Factors, f2Factors;
95	CFFListIterator iter;
96	int count= 0;
97	while (1)
98	{
99	count++;
100	f1= E1 (F);
101	if (!f1.isZero() && degree (f1) == degree (F,2))
102	{
103	f1Factors= factorize (f1);
104	if (f1Factors.getFirst().factor().inCoeffDomain())
105	f1Factors.removeFirst();
106	if (f1Factors.length() == 1 && f1Factors.getFirst().exp() == 1)
107	{
108	f= E2(f1);
109	f2= E2 (F);
110	f2Factors= factorize (f2);
111	Off (SW_RATIONAL);
112	if (f2Factors.getFirst().factor().inCoeffDomain())
113	f2Factors.removeFirst();
114	if (f2Factors.length() == 1 && f2Factors.getFirst().exp() == 1)
115	{
116	#ifdef HAVE_FLINT
117	// init
118	fmpz_t FLINTD1,FLINTD2;
119	fmpz_init(FLINTD1);
120	fmpz_init(FLINTD2);
121	fmpz_poly_t FLINTf1;
122	fmpz_poly_t FLINTf2;
123	// conversion
124	convertFacCF2Fmpz_poly_t(FLINTf1,f1);
125	convertFacCF2Fmpz_poly_t(FLINTf2,f2);
126	// discriminant
127	fmpz_poly_discriminant(FLINTD1,FLINTf1);
128	fmpz_poly_discriminant(FLINTD2,FLINTf2);
129	// conversion
130	CanonicalForm D1= convertFmpz2CF(FLINTD1);
131	CanonicalForm D2= convertFmpz2CF(FLINTD2);
132	// clean up
133	fmpz_poly_clear(FLINTf1);
134	fmpz_poly_clear(FLINTf2);
135	fmpz_clear(FLINTD1);
136	fmpz_clear(FLINTD2);
137	#elif defined(HAVE_NTL)
138	ZZX NTLf1= convertFacCF2NTLZZX (f1);
139	ZZX NTLf2= convertFacCF2NTLZZX (f2);
140	ZZ NTLD1= discriminant (NTLf1);
141	ZZ NTLD2= discriminant (NTLf2);
142	CanonicalForm D1= convertZZ2CF (NTLD1);
143	CanonicalForm D2= convertZZ2CF (NTLD2);
144	#else
145	factoryError("NTL/FLINT missing: choosePoint");
146	#endif
147	if ((!f.isZero()) &&
148	(abs(f)>cf_getSmallPrime (cf_getNumSmallPrimes()-1)))
149	{
150	for (i= cf_getNumPrimes()-1; i >= 0; i--)
151	{
152	if (f % CanonicalForm (cf_getPrime (i)) == 0)
153	{
154	p= cf_getPrime(i);
155	Fp= mod (F,p);
156	if (totaldegree (Fp) == tdegF &&
157	degree (mod (f2,p), 1) == degree (F,1) &&
158	degree (mod (f1, p),2) == degree (F,2))
159	{
160	if (mod (D1, p) != 0 && mod (D2, p) != 0)
161	{
162	eval[0]= E1[1];
163	eval[1]= E2[2];
164	return p;
165	}
166	}
167	}
168	}
169	}
170	else if (!f.isZero())
171	{
172	for (i= cf_getNumSmallPrimes()-1; i >= 0; i--)
173	{
174	if (f % CanonicalForm (cf_getSmallPrime (i)) == 0)
175	{
176	p= cf_getSmallPrime (i);
177	Fp= mod (F,p);
178	if (totaldegree (Fp) == tdegF &&
179	degree (mod (f2, p),1) == degree (F,1) &&
180	degree (mod (f1,p),2) == degree (F,2))
181	{
182	if (mod (D1, p) != 0 && mod (D2, p) != 0)
183	{
184	eval[0]= E1[1];
185	eval[1]= E2[2];
186	return p;
187	}
188	}
189	}
190	}
191	}
192	}
193	E2.nextpoint();
194	On (SW_RATIONAL);
195	}
196	}
197	E1.nextpoint();
198	if (count == 2)
199	{
200	count= 0;
201	absValue++;
202	E1=REvaluation (1, 1, IntRandom (absValue));
203	E2=REvaluation (2, 2, IntRandom (absValue));
204	E1.nextpoint();
205	E2.nextpoint();
206	}
207	}
208	return 0;
209	}
210
211	//G is assumed to be bivariate, irreducible over Q, primitive wrt x and y, compressed
212	CFAFList absBiFactorizeMain (const CanonicalForm& G, bool full)
213	{
214	CanonicalForm F= bCommonDen (G)*G;
215	bool isRat= isOn (SW_RATIONAL);
216	Off (SW_RATIONAL);
217	F /= icontent (F);
218	On (SW_RATIONAL);
219
220	mpz_t * M=new mpz_t [4];
221	mpz_init (M[0]);
222	mpz_init (M[1]);
223	mpz_init (M[2]);
224	mpz_init (M[3]);
225
226	mpz_t * S=new mpz_t [2];
227	mpz_init (S[0]);
228	mpz_init (S[1]);
229
230	F= compress (F, M, S);
231
232	if (F.isUnivariate())
233	{
234	if (degree (F) == 1)
235	{
236	mpz_clear (M[0]);
237	mpz_clear (M[1]);
238	mpz_clear (M[2]);
239	mpz_clear (M[3]);
240	delete [] M;
241
242	mpz_clear (S[0]);
243	mpz_clear (S[1]);
244	delete [] S;
245	if (!isRat)
246	Off (SW_RATIONAL);
247	return CFAFList (CFAFactor (G, 1, 1));
248	}
249	CFAFList result= uniAbsFactorize (F, full);
250	if (result.getFirst().factor().inCoeffDomain())
251	result.removeFirst();
252	for (CFAFListIterator iter=result; iter.hasItem(); iter++)
253	iter.getItem()= CFAFactor (decompress (iter.getItem().factor(), M, S),
254	iter.getItem().minpoly(),iter.getItem().exp());
255	mpz_clear (M[0]);
256	mpz_clear (M[1]);
257	mpz_clear (M[2]);
258	mpz_clear (M[3]);
259	delete [] M;
260
261	mpz_clear (S[0]);
262	mpz_clear (S[1]);
263	delete [] S;
264	if (!isRat)
265	Off (SW_RATIONAL);
266	return result;
267	}
268
269	if (degree (F, 1) == 1 \|\| degree (F, 2) == 1)
270	{
271	mpz_clear (M[0]);
272	mpz_clear (M[1]);
273	mpz_clear (M[2]);
274	mpz_clear (M[3]);
275	delete [] M;
276
277	mpz_clear (S[0]);
278	mpz_clear (S[1]);
279	delete [] S;
280	if (!isRat)
281	Off (SW_RATIONAL);
282	return CFAFList (CFAFactor (G, 1, 1));
283	}
284	int minTdeg, tdegF= totaldegree (F);
285	CanonicalForm Fp, smallestFactor;
286	int p;
287	CFFList factors;
288	Variable alpha;
289	bool rec= false;
290	Variable x= Variable (1);
291	Variable y= Variable (2);
292	CanonicalForm bufF= F;
293	CFFListIterator iter;
294	CFArray eval= CFArray (2);
295	int absValue= 1;
296	differentevalpoint:
297	while (1)
298	{
299	TIMING_START (fac_evalpoint);
300	p= choosePoint (F, tdegF, eval, rec, absValue);
301	TIMING_END_AND_PRINT (fac_evalpoint, "time to find eval point: ");
302
303	//after here isOn (SW_RATIONAL)==false
304	setCharacteristic (p);
305	Fp=F.mapinto();
306	factors= factorize (Fp);
307
308	if (factors.getFirst().factor().inCoeffDomain())
309	factors.removeFirst();
310
311	if (factors.length() == 1 && factors.getFirst().exp() == 1)
312	{
313	if (absIrredTest (Fp))
314	{
315	if (isRat)
316	On (SW_RATIONAL);
317	setCharacteristic(0);
318	mpz_clear (M[0]);
319	mpz_clear (M[1]);
320	mpz_clear (M[2]);
321	mpz_clear (M[3]);
322	delete [] M;
323
324	mpz_clear (S[0]);
325	mpz_clear (S[1]);
326	delete [] S;
327	return CFAFList (CFAFactor (G, 1, 1));
328	}
329	else
330	{
331	setCharacteristic (0);
332	if (modularIrredTestWithShift (F))
333	{
334	if (isRat)
335	On (SW_RATIONAL);
336	mpz_clear (M[0]);
337	mpz_clear (M[1]);
338	mpz_clear (M[2]);
339	mpz_clear (M[3]);
340	delete [] M;
341
342	mpz_clear (S[0]);
343	mpz_clear (S[1]);
344	delete [] S;
345	return CFAFList (CFAFactor (G, 1, 1));
346	}
347	rec= true;
348	continue;
349	}
350	}
351	iter= factors;
352	smallestFactor= iter.getItem().factor();
353	while (smallestFactor.isUnivariate() && iter.hasItem())
354	{
355	iter++;
356	if (!iter.hasItem())
357	break;
358	smallestFactor= iter.getItem().factor();
359	}
360
361	minTdeg= totaldegree (smallestFactor);
362	if (iter.hasItem())
363	iter++;
364	for (; iter.hasItem(); iter++)
365	{
366	if (!iter.getItem().factor().isUnivariate() &&
367	(totaldegree (iter.getItem().factor()) < minTdeg))
368	{
369	smallestFactor= iter.getItem().factor();
370	minTdeg= totaldegree (smallestFactor);
371	}
372	}
373	if (tdegF % minTdeg == 0)
374	break;
375	setCharacteristic(0);
376	rec=true;
377	}
378	CanonicalForm Gp= Fp/smallestFactor;
379	Gp= Gp /Lc (Gp);
380
381	CanonicalForm Gpy= Gp (eval[0].mapinto(), 1);
382	CanonicalForm smallestFactorEvaly= smallestFactor (eval[0].mapinto(),1);
383	CanonicalForm Gpx= Gp (eval[1].mapinto(), 2);
384	CanonicalForm smallestFactorEvalx= smallestFactor (eval[1].mapinto(),2);
385
386	bool xValid= !(Gpx.inCoeffDomain() \|\| smallestFactorEvalx.inCoeffDomain() \|\|
387	!gcd (Gpx, smallestFactorEvalx).inCoeffDomain());
388	bool yValid= !(Gpy.inCoeffDomain() \|\| smallestFactorEvaly.inCoeffDomain() \|\|
389	!gcd (Gpy, smallestFactorEvaly).inCoeffDomain());
390	if (!xValid \|\| !yValid)
391	{
392	rec= true;
393	setCharacteristic (0);
394	goto differentevalpoint;
395	}
396
397	setCharacteristic (0);
398
399	CanonicalForm mipo;
400
401	CFArray mipos= CFArray (2);
402	CFFList mipoFactors;
403	for (int i= 1; i < 3; i++)
404	{
405	CanonicalForm Fi= F(eval[i-1],i);
406
407	int s= tdegF/minTdeg + 1;
408	CanonicalForm bound= power (maxNorm (Fi), 2*(s-1));
409	bound *= power (CanonicalForm (s),s-1);
410	bound = power (CanonicalForm (2), ((s-1)(s-1))/2); //possible int overflow
411
412	CanonicalForm B = p;
413	long k = 1L;
414	while ( B < bound ) {
415	B *= p;
416	k++;
417	}
418
419	//TODO take floor (log2(k))
420	k= k+1;
421	#ifdef HAVE_FLINT
422	fmpz_poly_t FLINTFi;
423	convertFacCF2Fmpz_poly_t (FLINTFi, Fi);
424	setCharacteristic (p);
425	nmod_poly_t FLINTFpi, FLINTGpi;
426	if (i == 2)
427	{
428	convertFacCF2nmod_poly_t (FLINTFpi,
429	smallestFactorEvalx/lc (smallestFactorEvalx));
430	convertFacCF2nmod_poly_t (FLINTGpi, Gpx/lc (Gpx));
431	}
432	else
433	{
434	convertFacCF2nmod_poly_t (FLINTFpi,
435	smallestFactorEvaly/lc (smallestFactorEvaly));
436	convertFacCF2nmod_poly_t (FLINTGpi, Gpy/lc (Gpy));
437	}
438	nmod_poly_factor_t nmodFactors;
439	nmod_poly_factor_init (nmodFactors);
440	nmod_poly_factor_insert (nmodFactors, FLINTFpi, 1L);
441	nmod_poly_factor_insert (nmodFactors, FLINTGpi, 1L);
442
443	// the following fix is due to interface changes from FLINT 2.3 -> FLINT 2.4
444	# ifndef slong
445	# define slong long
446	# endif
447
448	slong * link= new slong [2];
449	fmpz_poly_t *v= new fmpz_poly_t[2];
450	fmpz_poly_t *w= new fmpz_poly_t[2];
451	fmpz_poly_init(v[0]);
452	fmpz_poly_init(v[1]);
453	fmpz_poly_init(w[0]);
454	fmpz_poly_init(w[1]);
455
456	fmpz_poly_factor_t liftedFactors;
457	fmpz_poly_factor_init (liftedFactors);
458	_fmpz_poly_hensel_start_lift (liftedFactors, link, v, w, FLINTFi,
459	nmodFactors, k);
460
461	nmod_poly_factor_clear (nmodFactors);
462	nmod_poly_clear (FLINTFpi);
463	nmod_poly_clear (FLINTGpi);
464
465	setCharacteristic(0);
466	CanonicalForm liftedSmallestFactor=
467	convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[0],x);
468
469	CanonicalForm otherFactor=
470	convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[1],x);
471	modpk pk= modpk (p, k);
472	#elif defined(HAVE_NTL)
473	modpk pk= modpk (p, k);
474	ZZX NTLFi=convertFacCF2NTLZZX (pk (Fi*pk.inverse (lc(Fi))));
475	setCharacteristic (p);
476
477	if (fac_NTL_char != p)
478	{
479	fac_NTL_char= p;
480	zz_p::init (p);
481	}
482	zz_pX NTLFpi, NTLGpi;
483	if (i == 2)
484	{
485	NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvalx/lc(smallestFactorEvalx));
486	NTLGpi=convertFacCF2NTLzzpX (Gpx/lc (Gpx));
487	}
488	else
489	{
490	NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvaly/lc(smallestFactorEvaly));
491	NTLGpi=convertFacCF2NTLzzpX (Gpy/lc (Gpy));
492	}
493	vec_zz_pX modFactors;
494	modFactors.SetLength(2);
495	modFactors[0]= NTLFpi;
496	modFactors[1]= NTLGpi;
497	vec_ZZX liftedFactors;
498	MultiLift (liftedFactors, modFactors, NTLFi, (long) k);
499	setCharacteristic(0);
500	CanonicalForm liftedSmallestFactor=
501	convertNTLZZX2CF (liftedFactors[0], x);
502
503	CanonicalForm otherFactor=
504	convertNTLZZX2CF (liftedFactors[1], x);
505	#else
506	factoryError("absBiFactorizeMain: NTL/FLINT missing");
507	#endif
508
509	Off (SW_SYMMETRIC_FF);
510	liftedSmallestFactor= pk (liftedSmallestFactor);
511	if (i == 2)
512	liftedSmallestFactor= liftedSmallestFactor (eval[0],1);
513	else
514	liftedSmallestFactor= liftedSmallestFactor (eval[1],1);
515
516	On (SW_SYMMETRIC_FF);
517	CFMatrix *M= new CFMatrix (s, s);
518	(*M)(s,s)= power (CanonicalForm (p), k);
519	for (int j= 1; j < s; j++)
520	{
521	(*M) (j,j)= 1;
522	(*M) (j+1,j)= -liftedSmallestFactor;
523	}
524
525	#ifdef HAVE_FLINT
526	fmpz_mat_t FLINTM;
527	convertFacCFMatrix2Fmpz_mat_t(FLINTM,*M);
528	fmpq_t delta,eta;
529	fmpq_init(delta); fmpq_set_si(delta,1,1);
530	fmpq_init(eta); fmpq_set_si(eta,3,4);
531	fmpz_mat_transpose(FLINTM,FLINTM);
532	fmpz_mat_lll_storjohann(FLINTM,delta,eta);
533	fmpz_mat_transpose(FLINTM,FLINTM);
534	delete M;
535	M=convertFmpz_mat_t2FacCFMatrix(FLINTM);
536	fmpz_mat_clear(FLINTM);
537	#elif defined(HAVE_NTL)
538	mat_ZZ * NTLM= convertFacCFMatrix2NTLmat_ZZ (*M);
539
540	ZZ det;
541
542	transpose (NTLM, NTLM);
543	(void) LLL (det, *NTLM, 1L, 1L); //use floating point LLL ?
544	transpose (NTLM, NTLM);
545	delete M;
546	M= convertNTLmat_ZZ2FacCFMatrix (*NTLM);
547	delete NTLM;
548	#else
549	factoryError("NTL/FLINT missing: absBiFactorizeMain");
550	#endif
551
552	mipo= 0;
553	for (int j= 1; j <= s; j++)
554	mipo += (M) (j,1)power (x,s-j);
555
556	delete M;
557	mipoFactors= factorize (mipo);
558	if (mipoFactors.getFirst().factor().inCoeffDomain())
559	mipoFactors.removeFirst();
560
561	#ifdef HAVE_FLINT
562	fmpz_poly_clear (v[0]);
563	fmpz_poly_clear (v[1]);
564	fmpz_poly_clear (w[0]);
565	fmpz_poly_clear (w[1]);
566	delete [] v;
567	delete [] w;
568	delete [] link;
569	fmpz_poly_factor_clear (liftedFactors);
570	#endif
571
572	if (mipoFactors.length() > 1 \|\|
573	(mipoFactors.length() == 1 && mipoFactors.getFirst().exp() > 1) \|\|
574	mipo.inCoeffDomain())
575	{
576	rec=true;
577	goto differentevalpoint;
578	}
579	else
580	mipos[i-1]= mipo;
581	}
582
583	if (degree (mipos[0]) != degree (mipos[1]))
584	{
585	rec=true;
586	goto differentevalpoint;
587	}
588
589	On (SW_RATIONAL);
590	if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
591	alpha= rootOf (mipos[0]);
592	else
593	alpha= rootOf (mipos[1]);
594
595	int wrongMipo= 0;
596
597	Variable beta;
598	if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
599	{
600	mipoFactors= factorize (mipos[1], alpha);
601	if (mipoFactors.getFirst().factor().inCoeffDomain())
602	mipoFactors.removeFirst();
603	for (iter= mipoFactors; iter.hasItem(); iter++)
604	{
605	if (degree (iter.getItem().factor()) > 1)
606	wrongMipo++;
607	}
608	if (wrongMipo == mipoFactors.length())
609	{
610	rec=true;
611	goto differentevalpoint;
612	}
613	wrongMipo= 0;
614	beta= rootOf (mipos[1]);
615	mipoFactors= factorize (mipos[0], beta);
616	if (mipoFactors.getFirst().factor().inCoeffDomain())
617	mipoFactors.removeFirst();
618	for (iter= mipoFactors; iter.hasItem(); iter++)
619	{
620	if (degree (iter.getItem().factor()) > 1)
621	wrongMipo++;
622	}
623	if (wrongMipo == mipoFactors.length())
624	{
625	rec=true;
626	goto differentevalpoint;
627	}
628	}
629	else
630	{
631	mipoFactors= factorize (mipos[0], alpha);
632	if (mipoFactors.getFirst().factor().inCoeffDomain())
633	mipoFactors.removeFirst();
634	for (iter= mipoFactors; iter.hasItem(); iter++)
635	{
636	if (degree (iter.getItem().factor()) > 1)
637	wrongMipo++;
638	}
639	if (wrongMipo == mipoFactors.length())
640	{
641	rec=true;
642	goto differentevalpoint;
643	}
644	wrongMipo= 0;
645	beta= rootOf (mipos[0]);
646	mipoFactors= factorize (mipos[1], beta);
647	if (mipoFactors.getFirst().factor().inCoeffDomain())
648	mipoFactors.removeFirst();
649	for (iter= mipoFactors; iter.hasItem(); iter++)
650	{
651	if (degree (iter.getItem().factor()) > 1)
652	wrongMipo++;
653	}
654	if (wrongMipo == mipoFactors.length())
655	{
656	rec=true;
657	goto differentevalpoint;
658	}
659	}
660
661
662	CanonicalForm F1;
663	if (degree (F,1) > minTdeg)
664	F1= F (eval[1], 2);
665	else
666	F1= F (eval[0], 1);
667
668	CFFList QaF1Factors;
669	bool swap= false;
670	if (F1.level() == 2)
671	{
672	swap= true;
673	F1=swapvar (F1, x, y);
674	F= swapvar (F, x, y);
675	}
676
677	wrongMipo= 0;
678	QaF1Factors= factorize (F1, alpha);
679	if (QaF1Factors.getFirst().factor().inCoeffDomain())
680	QaF1Factors.removeFirst();
681	for (iter= QaF1Factors; iter.hasItem(); iter++)
682	{
683	if (degree (iter.getItem().factor()) > minTdeg)
684	wrongMipo++;
685	}
686
687	if (wrongMipo == QaF1Factors.length())
688	{
689	rec= true;
690	F= bufF;
691	goto differentevalpoint;
692	}
693
694	CanonicalForm evaluation;
695	if (swap)
696	evaluation= eval[0];
697	else
698	evaluation= eval[1];
699
700	F *= bCommonDen (F);
701	F= F (y + evaluation, y);
702
703	int liftBound= degree (F,y) + 1;
704
705	modpk b= modpk();
706
707	CanonicalForm den= 1;
708
709	mipo= getMipo (alpha);
710
711	CFList uniFactors;
712	for (iter=QaF1Factors; iter.hasItem(); iter++)
713	uniFactors.append (iter.getItem().factor());
714
715	F /= Lc (F1);
716	#ifdef HAVE_FLINT
717	// init
718	fmpz_t FLINTf,FLINTD;
719	fmpz_init(FLINTf);
720	fmpz_init(FLINTD);
721	fmpz_poly_t FLINTmipo;
722	fmpz_poly_t FLINTLcf;
723	//conversion
724	convertFacCF2Fmpz_poly_t(FLINTmipo,mipo);
725	convertFacCF2Fmpz_poly_t(FLINTLcf,Lc (F*bCommonDen (F)));
726	// resultant, discriminant
727	fmpz_poly_resultant(FLINTf,FLINTmipo,FLINTLcf);
728	fmpz_poly_discriminant(FLINTD,FLINTmipo);
729	fmpz_mul(FLINTf,FLINTD,FLINTf);
730	den= abs (convertFmpz2CF(FLINTf));
731	// clean up
732	fmpz_clear(FLINTf);
733	// FLINTD is used below
734	fmpz_poly_clear(FLINTLcf);
735	fmpz_poly_clear(FLINTmipo);
736	#elif defined(HAVE_NTL)
737	ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
738	ZZX NTLLcf= convertFacCF2NTLZZX (Lc (F*bCommonDen (F)));
739	ZZ NTLf= resultant (NTLmipo, NTLLcf);
740	ZZ NTLD= discriminant (NTLmipo);
741	den= abs (convertZZ2CF (NTLD*NTLf));
742	#else
743	factoryError("NTL/FLINT missing: absBiFactorizeMain");
744	#endif
745
746	// make factors elements of Z(a)[x] disable for modularDiophant
747	CanonicalForm multiplier= 1;
748	for (CFListIterator i= uniFactors; i.hasItem(); i++)
749	{
750	multiplier *= bCommonDen (i.getItem());
751	i.getItem()= i.getItem()*bCommonDen(i.getItem());
752	}
753	F *= multiplier;
754	F *= bCommonDen (F);
755
756	Off (SW_RATIONAL);
757	int ii= 0;
758	#ifdef HAVE_FLINT
759	CanonicalForm discMipo= convertFmpz2CF(FLINTD);
760	fmpz_clear(FLINTD);
761	#elif defined(HAVE_NTL)
762	CanonicalForm discMipo= convertZZ2CF (NTLD);
763	#endif
764	findGoodPrime (bufF*discMipo,ii);
765	findGoodPrime (F1*discMipo,ii);
766	findGoodPrime (F*discMipo,ii);
767
768	int pp=cf_getBigPrime(ii);
769	b = coeffBound( F, pp, mipo );
770	modpk bb= coeffBound (F1, pp, mipo);
771	if (bb.getk() > b.getk() ) b=bb;
772	bb= coeffBound (F, pp, mipo);
773	if (bb.getk() > b.getk() ) b=bb;
774
775	ExtensionInfo dummy= ExtensionInfo (alpha, false);
776	DegreePattern degs= DegreePattern (uniFactors);
777
778	bool earlySuccess= false;
779	CFList earlyFactors;
780	uniFactors= henselLiftAndEarly
781	(F, earlySuccess, earlyFactors, degs, liftBound,
782	uniFactors, dummy, evaluation, b, den);
783
784	DEBOUTLN (cerr, "lifted factors= " << uniFactors);
785
786	CanonicalForm MODl= power (y, liftBound);
787
788	On (SW_RATIONAL);
789	F *= bCommonDen (F);
790	Off (SW_RATIONAL);
791
792	CFList biFactors;
793
794	biFactors= factorRecombination (uniFactors, F, MODl, degs, evaluation, 1,
795	uniFactors.length()/2, b, den);
796
797	On (SW_RATIONAL);
798
799	if (earlySuccess)
800	biFactors= Union (earlyFactors, biFactors);
801	else if (!earlySuccess && degs.getLength() == 1)
802	biFactors= earlyFactors;
803
804	bool swap2= false;
805	appendSwapDecompress (biFactors, CFList(), CFList(), swap, swap2, CFMap());
806	if (isOn (SW_RATIONAL))
807	normalize (biFactors);
808
809	CFAFList result;
810	bool found= false;
811
812	for (CFListIterator i= biFactors; i.hasItem(); i++)
813	{
814	if (full)
815	result.append (CFAFactor (decompress (i.getItem(), M, S),
816	getMipo (alpha), 1));
817
818	if (totaldegree (i.getItem()) == minTdeg)
819	{
820	if (!full)
821	result= CFAFList (CFAFactor (decompress (i.getItem(), M, S),
822	getMipo (alpha), 1));
823	found= true;
824
825	if (!full)
826	break;
827	}
828	}
829
830	if (!found)
831	{
832	rec= true;
833	F= bufF;
834	goto differentevalpoint;
835	}
836
837	if (isRat)
838	On (SW_RATIONAL);
839	else
840	Off (SW_RATIONAL);
841
842	mpz_clear (M[0]);
843	mpz_clear (M[1]);
844	mpz_clear (M[2]);
845	mpz_clear (M[3]);
846	delete [] M;
847
848	mpz_clear (S[0]);
849	mpz_clear (S[1]);
850	delete [] S;
851
852	return result;
853	}
854	#endif

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

Download in other formats: