Context Navigation

source: git/factory/facFqBivar.cc @ 49660c

spielwiese

Last change on this file since 49660c was 49660c, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: use FLINT linear algebra in bivariate factorization over finite fields
Property mode set to `100644`
File size: 219.6 KB

Line
1	/*****************************************************************************\
2	* Computer Algebra System SINGULAR
3	\*****************************************************************************/
4	/** @file facFqBivar.cc
5	*
6	* This file provides functions for factorizing a bivariate polynomial over
7	* \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF, based on "Modern Computer
8	* Algebra, Chapter 15" by J. von zur Gathen & J. Gerhard and "Factoring
9	* multivariate polynomials over a finite field" by L. Bernardin.
10	* Factor Recombination is described in "Factoring polynomials over global
11	* fields" by K. Belabas, M. van Hoeij, J. Klueners, A. Steel
12	*
13	*
14	* @author Martin Lee
15	*
16	**/
17	/*****************************************************************************/
18
19	#include "config.h"
20
21	#include "cf_assert.h"
22	#include "debug.h"
23	#include "timing.h"
24
25	#include "canonicalform.h"
26	#include "cf_defs.h"
27	#include "cf_map_ext.h"
28	#include "cf_random.h"
29	#include "facHensel.h"
30	#include "facMul.h"
31	#include "cf_map.h"
32	#include "cf_gcd_smallp.h"
33	#include "facFqBivarUtil.h"
34	#include "facFqBivar.h"
35	#include "cfNewtonPolygon.h"
36	#include "algext.h"
37
38	#ifdef HAVE_NTL
39	#include "NTLconvert.h"
40
41	#ifdef HAVE_FLINT
42	#include "FLINTconvert.h"
43	#endif
44
45	TIMING_DEFINE_PRINT(fac_fq_uni_factorizer)
46	TIMING_DEFINE_PRINT(fac_fq_bi_hensel_lift)
47	TIMING_DEFINE_PRINT(fac_fq_bi_factor_recombination)
48	TIMING_DEFINE_PRINT(fac_fq_bi_evaluation)
49	TIMING_DEFINE_PRINT(fac_fq_bi_shift_to_zero)
50
51	CanonicalForm prodMod0 (const CFList& L, const CanonicalForm& M, const modpk& b)
52	{
53	if (L.isEmpty())
54	return 1;
55	else if (L.length() == 1)
56	return mod (L.getFirst()(0, 1) , M);
57	else if (L.length() == 2)
58	return mod (mulNTL (L.getFirst()(0, 1),L.getLast()(0, 1), b), M);
59	else
60	{
61	int l= L.length()/2;
62	CFListIterator i= L;
63	CFList tmp1, tmp2;
64	CanonicalForm buf1, buf2;
65	for (int j= 1; j <= l; j++, i++)
66	tmp1.append (i.getItem());
67	tmp2= Difference (L, tmp1);
68	buf1= prodMod0 (tmp1, M, b);
69	buf2= prodMod0 (tmp2, M, b);
70	return mod (mulNTL (buf1,buf2, b), M);
71	}
72	}
73
74	CanonicalForm evalPoint (const CanonicalForm& F, CanonicalForm & eval,
75	const Variable& alpha, CFList& list, const bool& GF,
76	bool& fail)
77	{
78	fail= false;
79	Variable x= Variable(2);
80	Variable y= Variable(1);
81	FFRandom genFF;
82	GFRandom genGF;
83	CanonicalForm random, mipo;
84	double bound;
85	int p= getCharacteristic ();
86	if (alpha.level() != 1)
87	{
88	mipo= getMipo (alpha);
89	int d= degree (mipo);
90	bound= ipower (p, d);
91	}
92	else if (GF)
93	{
94	int d= getGFDegree();
95	bound= ipower (p, d);
96	}
97	else
98	bound= p;
99
100	random= 0;
101	do
102	{
103	if (list.length() >= bound)
104	{
105	fail= true;
106	break;
107	}
108	if (list.isEmpty())
109	random= 0;
110	else if (GF)
111	{
112	if (list.length() == 1)
113	random= getGFGenerator();
114	else
115	random= genGF.generate();
116	}
117	else if (list.length() < p \|\| alpha.level() == 1)
118	random= genFF.generate();
119	else if (alpha != x && list.length() >= p)
120	{
121	if (list.length() == p)
122	random= alpha;
123	else
124	{
125	AlgExtRandomF genAlgExt (alpha);
126	random= genAlgExt.generate();
127	}
128	}
129	if (find (list, random)) continue;
130	eval= F (random, x);
131	if (degree (eval) != degree (F, y))
132	{ //leading coeff vanishes
133	if (!find (list, random))
134	list.append (random);
135	continue;
136	}
137	if (degree (gcd (deriv (eval, eval.mvar()), eval), eval.mvar()) > 0)
138	{ //evaluated polynomial is not squarefree
139	if (!find (list, random))
140	list.append (random);
141	continue;
142	}
143	} while (find (list, random));
144
145	return random;
146	}
147
148	CFList
149	uniFactorizer (const CanonicalForm& A, const Variable& alpha, const bool& GF)
150	{
151	Variable x= A.mvar();
152	if (A.inCoeffDomain())
153	return CFList();
154	ASSERT (A.isUnivariate(),
155	"univariate polynomial expected or constant expected");
156	CFFList factorsA;
157	zz_p::init (getCharacteristic());
158	if (GF)
159	{
160	int k= getGFDegree();
161	char cGFName= gf_name;
162	CanonicalForm mipo= gf_mipo;
163	setCharacteristic (getCharacteristic());
164	Variable beta= rootOf (mipo.mapinto());
165	CanonicalForm buf= GF2FalphaRep (A, beta);
166	if (getCharacteristic() > 2)
167	{
168	zz_pX NTLMipo= convertFacCF2NTLzzpX (mipo.mapinto());
169	zz_pE::init (NTLMipo);
170	zz_pEX NTLA= convertFacCF2NTLzz_pEX (buf, NTLMipo);
171	MakeMonic (NTLA);
172	vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
173	zz_pE multi= to_zz_pE (1);
174	factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
175	x, beta);
176	}
177	else
178	{
179	GF2X NTLMipo= convertFacCF2NTLGF2X (mipo.mapinto());
180	GF2E::init (NTLMipo);
181	GF2EX NTLA= convertFacCF2NTLGF2EX (buf, NTLMipo);
182	MakeMonic (NTLA);
183	vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
184	GF2E multi= to_GF2E (1);
185	factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
186	x, beta);
187	}
188	setCharacteristic (getCharacteristic(), k, cGFName);
189	for (CFFListIterator i= factorsA; i.hasItem(); i++)
190	{
191	buf= i.getItem().factor();
192	buf= Falpha2GFRep (buf);
193	i.getItem()= CFFactor (buf, i.getItem().exp());
194	}
195	}
196	else if (alpha.level() != 1)
197	{
198	if (getCharacteristic() > 2)
199	{
200	zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
201	zz_pE::init (NTLMipo);
202	zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
203	MakeMonic (NTLA);
204	vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
205	zz_pE multi= to_zz_pE (1);
206	factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
207	x, alpha);
208	}
209	else
210	{
211	GF2X NTLMipo= convertFacCF2NTLGF2X (getMipo (alpha));
212	GF2E::init (NTLMipo);
213	GF2EX NTLA= convertFacCF2NTLGF2EX (A, NTLMipo);
214	MakeMonic (NTLA);
215	vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
216	GF2E multi= to_GF2E (1);
217	factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
218	x, alpha);
219	}
220	}
221	else
222	{
223	#ifdef HAVE_FLINT
224	nmod_poly_t FLINTA;
225	convertFacCF2nmod_poly_t (FLINTA, A);
226	nmod_poly_factor_t result;
227	nmod_poly_factor_init (result);
228	mp_limb_t leadingCoeff= nmod_poly_factor (result, FLINTA);
229	factorsA= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, x);
230	if (factorsA.getFirst().factor().inCoeffDomain())
231	factorsA.removeFirst();
232	nmod_poly_factor_clear (result);
233	nmod_poly_clear (FLINTA);
234	#else
235	if (getCharacteristic() > 2)
236	{
237	zz_pX NTLA= convertFacCF2NTLzzpX (A);
238	MakeMonic (NTLA);
239	vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
240	zz_p multi= to_zz_p (1);
241	factorsA= convertNTLvec_pair_zzpX_long2FacCFFList (NTLFactorsA, multi,
242	x);
243	}
244	else
245	{
246	GF2X NTLA= convertFacCF2NTLGF2X (A);
247	vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
248	GF2 multi= to_GF2 (1);
249	factorsA= convertNTLvec_pair_GF2X_long2FacCFFList (NTLFactorsA, multi,
250	x);
251	}
252	#endif
253	}
254	CFList uniFactors;
255	for (CFFListIterator i= factorsA; i.hasItem(); i++)
256	uniFactors.append (i.getItem().factor());
257	return uniFactors;
258	}
259
260	/// naive factor recombination as decribed in "Factoring
261	/// multivariate polynomials over a finite field" by L Bernardin.
262	CFList
263	extFactorRecombination (CFList& factors, CanonicalForm& F,
264	const CanonicalForm& N, const ExtensionInfo& info,
265	DegreePattern& degs, const CanonicalForm& eval, int s,
266	int thres)
267	{
268	if (factors.length() == 0)
269	{
270	F= 1;
271	return CFList();
272	}
273	if (F.inCoeffDomain())
274	return CFList();
275
276	Variable alpha= info.getAlpha();
277	Variable beta= info.getBeta();
278	CanonicalForm gamma= info.getGamma();
279	CanonicalForm delta= info.getDelta();
280	int k= info.getGFDegree();
281
282	CanonicalForm M= N;
283	int l= degree (N);
284	Variable y= F.mvar();
285	Variable x= Variable (1);
286	CFList source, dest;
287	if (degs.getLength() <= 1 \|\| factors.length() == 1)
288	{
289	CFList result= CFList(mapDown (F(y-eval, y), info, source, dest));
290	F= 1;
291	return result;
292	}
293
294	DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, M) == F " <<
295	(mod (LC (F, 1)prodMod (factors, M), M)/Lc (mod (LC (F, 1)prodMod (factors, M), M)) == F/Lc (F)));
296	int degMipoBeta= 1;
297	if (!k && beta.level() != 1)
298	degMipoBeta= degree (getMipo (beta));
299
300	CFList T, S, Diff;
301	T= factors;
302
303	CFList result;
304	CanonicalForm buf, buf2, quot;
305
306	buf= F;
307
308	CanonicalForm g, LCBuf= LC (buf, x);
309	int * v= new int [T.length()];
310	for (int i= 0; i < T.length(); i++)
311	v[i]= 0;
312
313	CFArray TT;
314	DegreePattern bufDegs1, bufDegs2;
315	bufDegs1= degs;
316	int subsetDeg;
317	TT= copy (factors);
318	bool nosubset= false;
319	bool recombination= false;
320	bool trueFactor= false;
321	CanonicalForm test;
322	CanonicalForm buf0= buf (0, x)*LCBuf;
323	while (T.length() >= 2*s && s <= thres)
324	{
325	while (nosubset == false)
326	{
327	if (T.length() == s)
328	{
329	delete [] v;
330	if (recombination)
331	{
332	T.insert (LCBuf);
333	g= prodMod (T, M);
334	T.removeFirst();
335	g /= content(g);
336	g= g (y - eval, y);
337	g /= Lc (g);
338	appendTestMapDown (result, g, info, source, dest);
339	F= 1;
340	return result;
341	}
342	else
343	{
344	appendMapDown (result, F (y - eval, y), info, source, dest);
345	F= 1;
346	return result;
347	}
348	}
349	S= subset (v, s, TT, nosubset);
350	if (nosubset) break;
351	subsetDeg= subsetDegree (S);
352	// skip those combinations that are not possible
353	if (!degs.find (subsetDeg))
354	continue;
355	else
356	{
357	test= prodMod0 (S, M);
358	test *= LCBuf;
359	test = mod (test, M);
360	if (fdivides (test, buf0))
361	{
362	S.insert (LCBuf);
363	g= prodMod (S, M);
364	S.removeFirst();
365	g /= content (g, x);
366	if (fdivides (g, buf, quot))
367	{
368	buf2= g (y - eval, y);
369	buf2 /= Lc (buf2);
370
371	if (!k && beta.level() == 1)
372	{
373	if (degree (buf2, alpha) < degMipoBeta)
374	{
375	buf= quot;
376	LCBuf= LC (buf, x);
377	recombination= true;
378	appendTestMapDown (result, buf2, info, source, dest);
379	trueFactor= true;
380	}
381	}
382	else
383	{
384	if (!isInExtension (buf2, gamma, k, delta, source, dest))
385	{
386	buf= quot;
387	LCBuf= LC (buf, x);
388	recombination= true;
389	appendTestMapDown (result, buf2, info, source, dest);
390	trueFactor= true;
391	}
392	}
393	if (trueFactor)
394	{
395	T= Difference (T, S);
396	l -= degree (g);
397	M= power (y, l);
398	buf0= buf (0, x)*LCBuf;
399
400	// compute new possible degree pattern
401	bufDegs2= DegreePattern (T);
402	bufDegs1.intersect (bufDegs2);
403	bufDegs1.refine ();
404	if (T.length() < 2*s \|\| T.length() == s \|\|
405	bufDegs1.getLength() == 1)
406	{
407	delete [] v;
408	if (recombination)
409	{
410	appendTestMapDown (result, buf (y - eval, y), info, source,
411	dest);
412	F= 1;
413	return result;
414	}
415	else
416	{
417	appendMapDown (result, F (y - eval, y), info, source, dest);
418	F= 1;
419	return result;
420	}
421	}
422	trueFactor= false;
423	TT= copy (T);
424	indexUpdate (v, s, T.length(), nosubset);
425	if (nosubset) break;
426	}
427	}
428	}
429	}
430	}
431	s++;
432	if (T.length() < 2*s \|\| T.length() == s)
433	{
434	delete [] v;
435	if (recombination)
436	{
437	appendTestMapDown (result, buf (y - eval, y), info, source, dest);
438	F= 1;
439	return result;
440	}
441	else
442	{
443	appendMapDown (result, F (y - eval, y), info, source, dest);
444	F= 1;
445	return result;
446	}
447	}
448	for (int i= 0; i < T.length(); i++)
449	v[i]= 0;
450	nosubset= false;
451	}
452	if (T.length() < 2*s)
453	{
454	appendMapDown (result, F (y - eval, y), info, source, dest);
455	F= 1;
456	delete [] v;
457	return result;
458	}
459
460	if (s > thres)
461	{
462	factors= T;
463	F= buf;
464	degs= bufDegs1;
465	}
466
467	delete [] v;
468	return result;
469	}
470
471	/// naive factor recombination as decribed in "Factoring
472	/// multivariate polynomials over a finite field" by L Bernardin.
473	CFList
474	factorRecombination (CFList& factors, CanonicalForm& F,
475	const CanonicalForm& N, DegreePattern& degs, int s,
476	int thres, const modpk& b
477	)
478	{
479	if (factors.length() == 0)
480	{
481	F= 1;
482	return CFList ();
483	}
484	if (F.inCoeffDomain())
485	return CFList();
486	if (degs.getLength() <= 1 \|\| factors.length() == 1)
487	{
488	CFList result= CFList (F);
489	F= 1;
490	return result;
491	}
492	#ifdef DEBUGOUTPUT
493	if (b.getp() == 0)
494	DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
495	(mod (LC (F, 1)prodMod (factors, N),N)/Lc (mod (LC (F, 1)prodMod (factors, N),N)) == F/Lc(F)));
496	else
497	DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
498	(mod (b(LC (F, 1)prodMod (factors, N)),N)/Lc (mod (b(LC (F, 1)prodMod (factors, N)),N)) == F/Lc(F)));
499	#endif
500
501	CFList T, S;
502
503	CanonicalForm M= N;
504	int l= degree (N);
505	T= factors;
506	CFList result;
507	Variable y= Variable (2);
508	Variable x= Variable (1);
509	CanonicalForm LCBuf= LC (F, x);
510	CanonicalForm g, quot, buf= F;
511	int * v= new int [T.length()];
512	for (int i= 0; i < T.length(); i++)
513	v[i]= 0;
514	bool nosubset= false;
515	CFArray TT;
516	DegreePattern bufDegs1, bufDegs2;
517	bufDegs1= degs;
518	int subsetDeg;
519	TT= copy (factors);
520	bool recombination= false;
521	CanonicalForm test;
522	bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) \|\|
523	getCharacteristic() > 0;
524	if (!isRat)
525	On (SW_RATIONAL);
526	CanonicalForm buf0= mulNTL (buf (0, x), LCBuf);
527	if (!isRat)
528	Off (SW_RATIONAL);
529	while (T.length() >= 2*s && s <= thres)
530	{
531	while (nosubset == false)
532	{
533	if (T.length() == s)
534	{
535	delete [] v;
536	if (recombination)
537	{
538	T.insert (LCBuf);
539	g= prodMod (T, M);
540	if (b.getp() != 0)
541	g= b(g);
542	T.removeFirst();
543	result.append (g/content (g, x));
544	F= 1;
545	return result;
546	}
547	else
548	{
549	result= CFList (F);
550	F= 1;
551	return result;
552	}
553	}
554	S= subset (v, s, TT, nosubset);
555	if (nosubset) break;
556	subsetDeg= subsetDegree (S);
557	// skip those combinations that are not possible
558	if (!degs.find (subsetDeg))
559	continue;
560	else
561	{
562	if (!isRat)
563	On (SW_RATIONAL);
564	test= prodMod0 (S, M);
565	if (!isRat)
566	{
567	test *= bCommonDen (test);
568	Off (SW_RATIONAL);
569	}
570	test= mulNTL (test, LCBuf, b);
571	test= mod (test, M);
572	if (uniFdivides (test, buf0))
573	{
574	if (!isRat)
575	On (SW_RATIONAL);
576	S.insert (LCBuf);
577	g= prodMod (S, M);
578	S.removeFirst();
579	if (!isRat)
580	{
581	g *= bCommonDen(g);
582	Off (SW_RATIONAL);
583	}
584	if (b.getp() != 0)
585	g= b(g);
586	if (!isRat)
587	On (SW_RATIONAL);
588	g /= content (g, x);
589	if (fdivides (g, buf, quot))
590	{
591	recombination= true;
592	result.append (g);
593	if (b.getp() != 0)
594	buf= quot*bCommonDen (quot);
595	else
596	buf= quot;
597	LCBuf= LC (buf, x);
598	T= Difference (T, S);
599	l -= degree (g);
600	M= power (y, l);
601	buf0= mulNTL (buf (0, x), LCBuf);
602	if (!isRat)
603	Off (SW_RATIONAL);
604	// compute new possible degree pattern
605	bufDegs2= DegreePattern (T);
606	bufDegs1.intersect (bufDegs2);
607	bufDegs1.refine ();
608	if (T.length() < 2*s \|\| T.length() == s \|\|
609	bufDegs1.getLength() == 1)
610	{
611	delete [] v;
612	if (recombination)
613	{
614	result.append (buf);
615	F= 1;
616	return result;
617	}
618	else
619	{
620	result= CFList (F);
621	F= 1;
622	return result;
623	}
624	}
625	TT= copy (T);
626	indexUpdate (v, s, T.length(), nosubset);
627	if (nosubset) break;
628	}
629	if (!isRat)
630	Off (SW_RATIONAL);
631	}
632	}
633	}
634	s++;
635	if (T.length() < 2*s \|\| T.length() == s)
636	{
637	delete [] v;
638	if (recombination)
639	{
640	result.append (buf);
641	F= 1;
642	return result;
643	}
644	else
645	{
646	result= CFList (F);
647	F= 1;
648	return result;
649	}
650	}
651	for (int i= 0; i < T.length(); i++)
652	v[i]= 0;
653	nosubset= false;
654	}
655	delete [] v;
656	if (T.length() < 2*s)
657	{
658	result.append (F);
659	F= 1;
660	return result;
661	}
662
663	if (s > thres)
664	{
665	factors= T;
666	F= buf;
667	degs= bufDegs1;
668	}
669
670	return result;
671	}
672
673	Variable chooseExtension (const Variable & alpha, const Variable& beta, int k)
674	{
675	zz_p::init (getCharacteristic());
676	zz_pX NTLIrredpoly;
677	int i=1, m= 2;
678	// extension of F_p needed
679	if (alpha.level() == 1 && beta.level() == 1 && k == 1)
680	{
681	i= 1;
682	m= 2;
683	} //extension of F_p(alpha) needed but want to factorize over F_p
684	else if (alpha.level() != 1 && beta.level() == 1 && k == 1)
685	{
686	i= 1;
687	m= degree (getMipo (alpha)) + 1;
688	} //extension of F_p(alpha) needed for first time
689	else if (alpha.level() != 1 && beta.level() == 1 && k != 1)
690	{
691	i= 2;
692	m= degree (getMipo (alpha));
693	}
694	else if (alpha.level() != 1 && beta.level() != 1 && k != 1)
695	{
696	m= degree (getMipo (beta));
697	i= degree (getMipo (alpha))/m + 1;
698	}
699	BuildIrred (NTLIrredpoly, i*m);
700	CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
701	return rootOf (newMipo);
702	}
703
704	void
705	earlyFactorDetection (CFList& reconstructedFactors, CanonicalForm& F, CFList&
706	factors, int& adaptedLiftBound, int*& factorsFoundIndex,
707	DegreePattern& degs, bool& success, int deg,
708	const modpk& b)
709	{
710	DegreePattern bufDegs1= degs;
711	DegreePattern bufDegs2;
712	CFList T= factors;
713	CanonicalForm buf= F;
714	Variable x= Variable (1);
715	CanonicalForm g, quot;
716	CanonicalForm M= power (F.mvar(), deg);
717	adaptedLiftBound= 0;
718	int d= degree (F), l= 0;
719	bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) \|\| getCharacteristic() > 0;
720	if (!isRat)
721	On (SW_RATIONAL);
722	if (b.getp() != 0)
723	buf *= bCommonDen (buf);
724	CanonicalForm LCBuf= LC (buf, x);
725	CanonicalForm buf0= mulNTL (buf (0,x), LCBuf);
726	CanonicalForm buf1= mulNTL (buf (1,x), LCBuf);
727	if (!isRat)
728	Off (SW_RATIONAL);
729	CanonicalForm test0, test1;
730
731	for (CFListIterator i= factors; i.hasItem(); i++, l++)
732	{
733	if (!bufDegs1.find (degree (i.getItem(), 1)) \|\| factorsFoundIndex[l] == 1)
734	continue;
735	else
736	{
737	test1= mod (mulNTL (i.getItem() (1,x), LCBuf, b), M);
738	if (uniFdivides (test1, buf1))
739	{
740	test0= mod (mulNTL (i.getItem() (0,x), LCBuf, b), M);
741	if (uniFdivides (test0, buf0))
742	{
743	if (!isRat)
744	On (SW_RATIONAL);
745	g= mulMod2 (i.getItem(), LCBuf, M);
746	if (!isRat)
747	{
748	g *= bCommonDen(g);
749	Off (SW_RATIONAL);
750	}
751	if (b.getp() != 0)
752	g= b(g);
753	if (!isRat)
754	On (SW_RATIONAL);
755	g /= content (g, x);
756	if (fdivides (g, buf, quot))
757	{
758	reconstructedFactors.append (g);
759	factorsFoundIndex[l]= 1;
760	if (b.getp() != 0)
761	buf= quot*bCommonDen(quot);
762	else
763	buf= quot;
764	d -= degree (g);
765	LCBuf= LC (buf, x);
766	buf0= mulNTL (buf (0,x), LCBuf);
767	buf1= mulNTL (buf (1,x), LCBuf);
768	if (!isRat)
769	Off (SW_RATIONAL);
770	T= Difference (T, CFList (i.getItem()));
771	F= buf;
772
773	// compute new possible degree pattern
774	bufDegs2= DegreePattern (T);
775	bufDegs1.intersect (bufDegs2);
776	bufDegs1.refine ();
777	if (bufDegs1.getLength() <= 1)
778	{
779	if (!buf.inCoeffDomain())
780	{
781	reconstructedFactors.append (buf);
782	F= 1;
783	}
784	break;
785	}
786	}
787	if (!isRat)
788	Off (SW_RATIONAL);
789	}
790	}
791	}
792	}
793	adaptedLiftBound= d + 1;
794	if (adaptedLiftBound < deg)
795	{
796	degs= bufDegs1;
797	success= true;
798	}
799	if (bufDegs1.getLength() <= 1)
800	degs= bufDegs1;
801	}
802
803	void
804	extEarlyFactorDetection (CFList& reconstructedFactors, CanonicalForm& F, CFList&
805	factors,int& adaptedLiftBound, int*& factorsFoundIndex,
806	DegreePattern& degs, bool& success, const
807	ExtensionInfo& info, const CanonicalForm& eval, int deg
808	)
809	{
810	Variable alpha= info.getAlpha();
811	Variable beta= info.getBeta();
812	CanonicalForm gamma= info.getGamma();
813	CanonicalForm delta= info.getDelta();
814	int k= info.getGFDegree();
815	DegreePattern bufDegs1= degs, bufDegs2;
816	CFList result;
817	CFList T= factors;
818	Variable y= F.mvar();
819	Variable x= Variable (1);
820	CanonicalForm buf= F, LCBuf= LC (buf, x), g, buf2;
821	CanonicalForm M= power (y, deg);
822	adaptedLiftBound= 0;
823	bool trueFactor= false;
824	int d= degree (F), l= 0;
825	CFList source, dest;
826	int degMipoBeta= 1;
827	if (!k && beta.level() != 1)
828	degMipoBeta= degree (getMipo (beta));
829	CanonicalForm quot;
830	for (CFListIterator i= factors; i.hasItem(); i++, l++)
831	{
832	if (!bufDegs1.find (degree (i.getItem(), 1)) \|\| factorsFoundIndex[l] == 1)
833	continue;
834	else
835	{
836	g= mulMod2 (i.getItem(), LCBuf, M);
837	g /= content (g, x);
838	if (fdivides (g, buf, quot))
839	{
840	buf2= g (y - eval, y);
841	buf2 /= Lc (buf2);
842
843	if (!k && beta == x)
844	{
845	if (degree (buf2, alpha) < degMipoBeta)
846	{
847	appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
848	factorsFoundIndex[l]= 1;
849	buf= quot;
850	d -= degree (g);
851	LCBuf= LC (buf, x);
852	trueFactor= true;
853	}
854	}
855	else
856	{
857	if (!isInExtension (buf2, gamma, k, delta, source, dest))
858	{
859	appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
860	factorsFoundIndex[l]= 1;
861	buf= quot;
862	d -= degree (g);
863	LCBuf= LC (buf, x);
864	trueFactor= true;
865	}
866	}
867	if (trueFactor)
868	{
869	T= Difference (T, CFList (i.getItem()));
870	F= buf;
871
872	// compute new possible degree pattern
873	bufDegs2= DegreePattern (T);
874	bufDegs1.intersect (bufDegs2);
875	bufDegs1.refine ();
876	trueFactor= false;
877	if (bufDegs1.getLength() <= 1)
878	{
879	if (!buf.inCoeffDomain())
880	{
881	buf= buf (y - eval, y);
882	buf /= Lc (buf);
883	appendMapDown (reconstructedFactors, buf, info, source, dest);
884	F= 1;
885	}
886	break;
887	}
888	}
889	}
890	}
891	}
892	adaptedLiftBound= d + 1;
893	if (adaptedLiftBound < deg)
894	{
895	degs= bufDegs1;
896	success= true;
897	}
898	if (bufDegs1.getLength() <= 1)
899	degs= bufDegs1;
900	}
901
902	int*
903	getCombinations (int * rightSide, int sizeOfRightSide, int& sizeOfOutput,
904	int degreeLC)
905	{
906	Variable x= Variable (1);
907	int p= getCharacteristic();
908	int d= getGFDegree();
909	char cGFName= gf_name;
910	setCharacteristic(0);
911	CanonicalForm buf= 1;
912	for (int i= 0; i < sizeOfRightSide; i++)
913	buf *= (power (x, rightSide [i]) + 1);
914
915	int j= 0;
916	for (CFIterator i= buf; i.hasTerms(); i++, j++)
917	{
918	if (i.exp() < degreeLC)
919	{
920	j++;
921	break;
922	}
923	}
924
925	ASSERT ( j > 1, "j > 1 expected" );
926
927	int* result = new int [j - 1];
928	sizeOfOutput= j - 1;
929
930	int i= 0;
931	for (CFIterator m = buf; i < j - 1; i++, m++)
932	result [i]= m.exp();
933
934	if (d > 1)
935	setCharacteristic (p, d, cGFName);
936	else
937	setCharacteristic (p);
938	return result;
939	}
940
941	int *
942	getLiftPrecisions (const CanonicalForm& F, int& sizeOfOutput, int degreeLC)
943	{
944	int sizeOfNewtonPoly;
945	int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPoly);
946	int sizeOfRightSide;
947	int * rightSide= getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
948	int * result= getCombinations(rightSide, sizeOfRightSide, sizeOfOutput,
949	degreeLC);
950	delete [] rightSide;
951	for (int i= 0; i < sizeOfNewtonPoly; i++)
952	delete [] newtonPolyg[i];
953	delete [] newtonPolyg;
954	return result;
955	}
956
957	void
958	deleteFactors (CFList& factors, int* factorsFoundIndex)
959	{
960	CFList result;
961	int i= 0;
962	for (CFListIterator iter= factors; iter.hasItem(); iter++, i++)
963	{
964	if (factorsFoundIndex[i] == 1)
965	continue;
966	else
967	result.append (iter.getItem());
968	}
969	factors= result;
970	}
971
972	CFList
973	henselLiftAndEarly (CanonicalForm& A, bool& earlySuccess, CFList&
974	earlyFactors, DegreePattern& degs, int& liftBound,
975	const CFList& uniFactors, const ExtensionInfo& info,
976	const CanonicalForm& eval, modpk& b)
977	{
978	Variable alpha= info.getAlpha();
979	Variable beta= info.getBeta();
980	CanonicalForm gamma= info.getGamma();
981	CanonicalForm delta= info.getDelta();
982	bool extension= info.isInExtension();
983
984	int sizeOfLiftPre;
985	int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
986
987	Variable x= Variable (1);
988	Variable y= Variable (2);
989	CFArray Pi;
990	CFList diophant;
991	CFList bufUniFactors= uniFactors;
992	CanonicalForm bufA= A;
993	CanonicalForm lcA0= 0;
994	bool mipoHasDen= false;
995	if (getCharacteristic() == 0 && b.getp() != 0)
996	{
997	if (alpha.level() == 1)
998	{
999	lcA0= lc (A (0, 2));
1000	A *= b.inverse (lcA0);
1001	A= b (A);
1002	for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
1003	i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1004	}
1005	else
1006	{
1007	lcA0= Lc (A (0,2));
1008	On (SW_RATIONAL);
1009	mipoHasDen= !bCommonDen(getMipo(alpha)).isOne();
1010	Off (SW_RATIONAL);
1011	CanonicalForm lcA0inverse= b.inverse (lcA0);
1012	A *= lcA0inverse;
1013	A= b (A);
1014	// Lc of bufUniFactors is in Z
1015	for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
1016	i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1017	}
1018	}
1019	bufUniFactors.insert (LC (A, x));
1020	CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1);
1021	earlySuccess= false;
1022	int newLiftBound= 0;
1023
1024	int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
1025	int dummy;
1026	int * factorsFoundIndex= new int [uniFactors.length()];
1027	for (int i= 0; i < uniFactors.length(); i++)
1028	factorsFoundIndex [i]= 0;
1029
1030	CFList bufBufUniFactors;
1031	Variable v= alpha;
1032	if (smallFactorDeg >= liftBound \|\| degree (A,y) <= 4)
1033	henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M, b, true);
1034	else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1035	{
1036	henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
1037	if (mipoHasDen)
1038	{
1039	for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1040	if (hasFirstAlgVar (iter.getItem(), v))
1041	break;
1042	if (v != alpha)
1043	{
1044	bufBufUniFactors= bufUniFactors;
1045	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1046	iter.getItem()= replacevar (iter.getItem(), v, alpha);
1047	A= replacevar (A, alpha, v);
1048	}
1049	}
1050
1051	if (!extension)
1052	{
1053	if (v==alpha)
1054	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1055	factorsFoundIndex, degs, earlySuccess,
1056	smallFactorDeg, b);
1057	else
1058	earlyFactorDetection(earlyFactors, bufA, bufBufUniFactors, newLiftBound,
1059	factorsFoundIndex, degs, earlySuccess,
1060	smallFactorDeg, b);
1061	}
1062	else
1063	extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1064	factorsFoundIndex, degs, earlySuccess, info,
1065	eval, smallFactorDeg);
1066	if (degs.getLength() > 1 && !earlySuccess &&
1067	smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
1068	{
1069	if (newLiftBound >= liftPre[sizeOfLiftPre-1]+1)
1070	{
1071	bufUniFactors.insert (LC (A, x));
1072	henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
1073	liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M, b);
1074	if (v!=alpha)
1075	{
1076	bufBufUniFactors= bufUniFactors;
1077	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1078	iter.getItem()= replacevar (iter.getItem(), v, alpha);
1079	}
1080	if (!extension)
1081	{
1082	if (v==alpha)
1083	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1084	factorsFoundIndex, degs, earlySuccess,
1085	liftPre[sizeOfLiftPre-1] + 1, b);
1086	else
1087	earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1088	factorsFoundIndex, degs, earlySuccess,
1089	liftPre[sizeOfLiftPre-1] + 1, b);
1090	}
1091	else
1092	extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1093	factorsFoundIndex, degs, earlySuccess, info,
1094	eval, liftPre[sizeOfLiftPre-1] + 1);
1095	}
1096	}
1097	else if (earlySuccess)
1098	liftBound= newLiftBound;
1099
1100	int i= sizeOfLiftPre - 1;
1101	while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
1102	{
1103	if (newLiftBound >= liftPre[i] + 1)
1104	{
1105	bufUniFactors.insert (LC (A, x));
1106	henselLiftResume12 (A, bufUniFactors, liftPre[i] + 1,
1107	liftPre[i-1] + 1, Pi, diophant, M, b);
1108	if (v!=alpha)
1109	{
1110	bufBufUniFactors= bufUniFactors;
1111	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1112	iter.getItem()= replacevar (iter.getItem(), v, alpha);
1113	}
1114	if (!extension)
1115	{
1116	if (v==alpha)
1117	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1118	factorsFoundIndex, degs, earlySuccess,
1119	liftPre[i-1] + 1, b);
1120	else
1121	earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1122	factorsFoundIndex, degs, earlySuccess,
1123	liftPre[i-1] + 1, b);
1124	}
1125	else
1126	extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1127	factorsFoundIndex, degs, earlySuccess, info,
1128	eval, liftPre[i-1] + 1);
1129	}
1130	else
1131	{
1132	liftBound= newLiftBound;
1133	break;
1134	}
1135	i--;
1136	}
1137	if (earlySuccess)
1138	liftBound= newLiftBound;
1139	//after here all factors are lifted to liftPre[sizeOfLiftPre-1]
1140	}
1141	else
1142	{
1143	henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
1144	if (mipoHasDen)
1145	{
1146	for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1147	if (hasFirstAlgVar (iter.getItem(), v))
1148	break;
1149	if (v != alpha)
1150	{
1151	bufBufUniFactors= bufUniFactors;
1152	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1153	iter.getItem()= replacevar (iter.getItem(), v, alpha);
1154	A= replacevar (A, alpha, v);
1155	}
1156	}
1157	if (!extension)
1158	{
1159	if (v==alpha)
1160	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1161	factorsFoundIndex, degs, earlySuccess,
1162	smallFactorDeg, b);
1163	else
1164	earlyFactorDetection (earlyFactors, bufA, bufBufUniFactors, newLiftBound,
1165	factorsFoundIndex, degs, earlySuccess,
1166	smallFactorDeg, b);
1167	}
1168	else
1169	extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1170	factorsFoundIndex, degs, earlySuccess, info,
1171	eval, smallFactorDeg);
1172	int i= 1;
1173	while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
1174	i++;
1175	dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
1176	if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1177	{
1178	bufUniFactors.insert (LC (A, x));
1179	henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
1180	dummy, Pi, diophant, M, b);
1181	if (v!=alpha)
1182	{
1183	bufBufUniFactors= bufUniFactors;
1184	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1185	iter.getItem()= replacevar (iter.getItem(), v, alpha);
1186	}
1187	if (!extension)
1188	{
1189	if (v==alpha)
1190	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1191	factorsFoundIndex, degs, earlySuccess, dummy, b);
1192	else
1193	earlyFactorDetection (earlyFactors, bufA,bufBufUniFactors, newLiftBound,
1194	factorsFoundIndex, degs, earlySuccess, dummy, b);
1195	}
1196	else
1197	extEarlyFactorDetection (earlyFactors, bufA,bufUniFactors, newLiftBound,
1198	factorsFoundIndex, degs, earlySuccess, info,
1199	eval, dummy);
1200	}
1201	while (degs.getLength() > 1 && !earlySuccess && i < 4)
1202	{
1203	if (newLiftBound >= dummy)
1204	{
1205	bufUniFactors.insert (LC (A, x));
1206	dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
1207	henselLiftResume12 (A, bufUniFactors, (degree (A,y)/4)*i + 4,
1208	dummy, Pi, diophant, M, b);
1209	if (v!=alpha)
1210	{
1211	bufBufUniFactors= bufUniFactors;
1212	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1213	iter.getItem()= replacevar (iter.getItem(), v, alpha);
1214	}
1215	if (!extension)
1216	{
1217	if (v==alpha)
1218	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1219	factorsFoundIndex, degs, earlySuccess, dummy,b);
1220	else
1221	earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1222	factorsFoundIndex, degs, earlySuccess, dummy,b);
1223	}
1224	else
1225	extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1226	factorsFoundIndex, degs, earlySuccess, info,
1227	eval, dummy);
1228	}
1229	else
1230	{
1231	liftBound= newLiftBound;
1232	break;
1233	}
1234	i++;
1235	}
1236	if (earlySuccess)
1237	liftBound= newLiftBound;
1238	}
1239
1240	A= bufA;
1241	if (earlyFactors.length() > 0 && degs.getLength() > 1)
1242	{
1243	liftBound= degree (A,y) + 1;
1244	earlySuccess= true;
1245	deleteFactors (bufUniFactors, factorsFoundIndex);
1246	}
1247
1248	delete [] factorsFoundIndex;
1249	delete [] liftPre;
1250
1251	return bufUniFactors;
1252	}
1253
1254	CFList
1255	henselLiftAndEarly (CanonicalForm& A, bool& earlySuccess, CFList&
1256	earlyFactors, DegreePattern& degs, int& liftBound,
1257	const CFList& uniFactors, const ExtensionInfo& info,
1258	const CanonicalForm& eval)
1259	{
1260	modpk dummy= modpk();
1261	return henselLiftAndEarly (A, earlySuccess, earlyFactors, degs, liftBound,
1262	uniFactors, info, eval, dummy);
1263	}
1264
1265	long isReduced (const mat_zz_p& M)
1266	{
1267	long i, j, nonZero;
1268	for (i = 1; i <= M.NumRows(); i++)
1269	{
1270	nonZero= 0;
1271	for (j = 1; j <= M.NumCols(); j++)
1272	{
1273	if (!IsZero (M (i,j)))
1274	nonZero++;
1275	}
1276	if (nonZero != 1)
1277	return 0;
1278	}
1279	return 1;
1280	}
1281
1282	#ifdef HAVE_FLINT
1283	long isReduced (const nmod_mat_t M)
1284	{
1285	long i, j, nonZero;
1286	for (i = 1; i <= nmod_mat_nrows(M); i++)
1287	{
1288	nonZero= 0;
1289	for (j = 1; j <= nmod_mat_ncols (M); j++)
1290	{
1291	if (!(nmod_mat_entry (M, i-1, j-1)==0))
1292	nonZero++;
1293	}
1294	if (nonZero != 1)
1295	return 0;
1296	}
1297	return 1;
1298	}
1299	#endif
1300
1301	long isReduced (const mat_zz_pE& M)
1302	{
1303	long i, j, nonZero;
1304	for (i = 1; i <= M.NumRows(); i++)
1305	{
1306	nonZero= 0;
1307	for (j = 1; j <= M.NumCols(); j++)
1308	{
1309	if (!IsZero (M (i,j)))
1310	nonZero++;
1311	}
1312	if (nonZero != 1)
1313	return 0;
1314	}
1315	return 1;
1316	}
1317
1318	int * extractZeroOneVecs (const mat_zz_p& M)
1319	{
1320	long i, j;
1321	bool nonZeroOne= false;
1322	int * result= new int [M.NumCols()];
1323	for (i = 1; i <= M.NumCols(); i++)
1324	{
1325	for (j = 1; j <= M.NumRows(); j++)
1326	{
1327	if (!(IsOne (M (j,i)) \|\| IsZero (M (j,i))))
1328	{
1329	nonZeroOne= true;
1330	break;
1331	}
1332	}
1333	if (!nonZeroOne)
1334	result [i - 1]= 1;
1335	else
1336	result [i - 1]= 0;
1337	nonZeroOne= false;
1338	}
1339	return result;
1340	}
1341
1342	#ifdef HAVE_FLINT
1343	int * extractZeroOneVecs (const nmod_mat_t M)
1344	{
1345	long i, j;
1346	bool nonZeroOne= false;
1347	int * result= new int [nmod_mat_ncols (M)];
1348	for (i = 0; i < nmod_mat_ncols (M); i++)
1349	{
1350	for (j = 0; j < nmod_mat_nrows (M); j++)
1351	{
1352	if (!((nmod_mat_entry (M, j, i) == 1) \|\| (nmod_mat_entry (M, j,i) == 0)))
1353	{
1354	nonZeroOne= true;
1355	break;
1356	}
1357	}
1358	if (!nonZeroOne)
1359	result [i]= 1;
1360	else
1361	result [i]= 0;
1362	nonZeroOne= false;
1363	}
1364	return result;
1365	}
1366	#endif
1367
1368	int * extractZeroOneVecs (const mat_zz_pE& M)
1369	{
1370	long i, j;
1371	bool nonZeroOne= false;
1372	int * result= new int [M.NumCols()];
1373	for (i = 1; i <= M.NumCols(); i++)
1374	{
1375	for (j = 1; j <= M.NumRows(); j++)
1376	{
1377	if (!(IsOne (M (j,i)) \|\| IsZero (M (j,i))))
1378	{
1379	nonZeroOne= true;
1380	break;
1381	}
1382	}
1383	if (!nonZeroOne)
1384	result [i - 1]= 1;
1385	else
1386	result [i - 1]= 0;
1387	nonZeroOne= false;
1388	}
1389	return result;
1390	}
1391
1392	void
1393	reconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const CFList&
1394	factors, const int liftBound, int& factorsFound, int*&
1395	factorsFoundIndex, mat_zz_pE& N, bool beenInThres
1396	)
1397	{
1398	Variable y= Variable (2);
1399	Variable x= Variable (1);
1400	CanonicalForm yToL= power (y, liftBound);
1401	if (factors.length() == 2)
1402	{
1403	CanonicalForm tmp1, tmp2, tmp3;
1404	tmp1= factors.getFirst();
1405	tmp2= factors.getLast();
1406	tmp1 *= LC (F, x);
1407	tmp1= mod (tmp1, yToL);
1408	tmp1 /= content (tmp1, x);
1409	tmp2 *= LC (F, x);
1410	tmp2= mod (tmp2, yToL);
1411	tmp2 /= content (tmp2, x);
1412	tmp3 = tmp1*tmp2;
1413	if (tmp3/Lc (tmp3) == F/Lc (F))
1414	{
1415	factorsFound++;
1416	F= 1;
1417	reconstructedFactors.append (tmp1);
1418	reconstructedFactors.append (tmp2);
1419	return;
1420	}
1421	}
1422	CanonicalForm quot, buf;
1423	CFListIterator iter;
1424	for (long i= 1; i <= N.NumCols(); i++)
1425	{
1426	if (factorsFoundIndex [i - 1] == 1)
1427	continue;
1428	iter= factors;
1429	if (beenInThres)
1430	{
1431	int count= 1;
1432	while (count < i)
1433	{
1434	count++;
1435	iter++;
1436	}
1437	buf= iter.getItem();
1438	}
1439	else
1440	{
1441	buf= 1;
1442	for (long j= 1; j <= N.NumRows(); j++, iter++)
1443	{
1444	if (!IsZero (N (j,i)))
1445	buf= mulMod2 (buf, iter.getItem(), yToL);
1446	}
1447	}
1448	buf *= LC (F, x);
1449	buf= mod (buf, yToL);
1450	buf /= content (buf, x);
1451	if (fdivides (buf, F, quot))
1452	{
1453	factorsFoundIndex[i - 1]= 1;
1454	factorsFound++;
1455	F= quot;
1456	F /= Lc (F);
1457	reconstructedFactors.append (buf);
1458	}
1459	if (degree (F) <= 0)
1460	return;
1461	if (factorsFound + 1 == N.NumCols())
1462	{
1463	reconstructedFactors.append (F);
1464	return;
1465	}
1466	}
1467	}
1468
1469	void
1470	reconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const CFList&
1471	factors, const int liftBound, int& factorsFound, int*&
1472	factorsFoundIndex, mat_zz_p& N, bool beenInThres
1473	)
1474	{
1475	Variable y= Variable (2);
1476	Variable x= Variable (1);
1477	CanonicalForm yToL= power (y, liftBound);
1478	if (factors.length() == 2)
1479	{
1480	CanonicalForm tmp1, tmp2, tmp3;
1481	tmp1= factors.getFirst();
1482	tmp2= factors.getLast();
1483	tmp1 *= LC (F, x);
1484	tmp1= mod (tmp1, yToL);
1485	tmp1 /= content (tmp1, x);
1486	tmp2 *= LC (F, x);
1487	tmp2= mod (tmp2, yToL);
1488	tmp2 /= content (tmp2, x);
1489	tmp3 = tmp1*tmp2;
1490	if (tmp3/Lc (tmp3) == F/Lc (F))
1491	{
1492	factorsFound++;
1493	F= 1;
1494	reconstructedFactors.append (tmp1);
1495	reconstructedFactors.append (tmp2);
1496	return;
1497	}
1498	}
1499	CanonicalForm quot, buf;
1500	CFListIterator iter;
1501	for (long i= 1; i <= N.NumCols(); i++)
1502	{
1503	if (factorsFoundIndex [i - 1] == 1)
1504	continue;
1505	iter= factors;
1506	if (beenInThres)
1507	{
1508	int count= 1;
1509	while (count < i)
1510	{
1511	count++;
1512	iter++;
1513	}
1514	buf= iter.getItem();
1515	}
1516	else
1517	{
1518	buf= 1;
1519	for (long j= 1; j <= N.NumRows(); j++, iter++)
1520	{
1521	if (!IsZero (N (j,i)))
1522	buf= mulMod2 (buf, iter.getItem(), yToL);
1523	}
1524	}
1525	buf *= LC (F, x);
1526	buf= mod (buf, yToL);
1527	buf /= content (buf, x);
1528	if (fdivides (buf, F, quot))
1529	{
1530	factorsFoundIndex[i - 1]= 1;
1531	factorsFound++;
1532	F= quot;
1533	F /= Lc (F);
1534	reconstructedFactors.append (buf);
1535	}
1536	if (degree (F) <= 0)
1537	return;
1538	if (factorsFound + 1 == N.NumCols())
1539	{
1540	reconstructedFactors.append (F);
1541	return;
1542	}
1543	}
1544	}
1545
1546	#ifdef HAVE_FLINT
1547	void
1548	reconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const CFList&
1549	factors, const int liftBound, int& factorsFound, int*&
1550	factorsFoundIndex, nmod_mat_t N, bool beenInThres
1551	)
1552	{
1553	Variable y= Variable (2);
1554	Variable x= Variable (1);
1555	CanonicalForm yToL= power (y, liftBound);
1556	if (factors.length() == 2)
1557	{
1558	CanonicalForm tmp1, tmp2, tmp3;
1559	tmp1= factors.getFirst();
1560	tmp2= factors.getLast();
1561	tmp1 *= LC (F, x);
1562	tmp1= mod (tmp1, yToL);
1563	tmp1 /= content (tmp1, x);
1564	tmp2 *= LC (F, x);
1565	tmp2= mod (tmp2, yToL);
1566	tmp2 /= content (tmp2, x);
1567	tmp3 = tmp1*tmp2;
1568	if (tmp3/Lc (tmp3) == F/Lc (F))
1569	{
1570	factorsFound++;
1571	F= 1;
1572	reconstructedFactors.append (tmp1);
1573	reconstructedFactors.append (tmp2);
1574	return;
1575	}
1576	}
1577	CanonicalForm quot, buf;
1578	CFListIterator iter;
1579	for (long i= 0; i < nmod_mat_ncols (N); i++)
1580	{
1581	if (factorsFoundIndex [i] == 1)
1582	continue;
1583	iter= factors;
1584	if (beenInThres)
1585	{
1586	int count= 0;
1587	while (count < i)
1588	{
1589	count++;
1590	iter++;
1591	}
1592	buf= iter.getItem();
1593	}
1594	else
1595	{
1596	buf= 1;
1597	for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
1598	{
1599	if (!(nmod_mat_entry (N, j, i) == 0))
1600	buf= mulMod2 (buf, iter.getItem(), yToL);
1601	}
1602	}
1603	buf *= LC (F, x);
1604	buf= mod (buf, yToL);
1605	buf /= content (buf, x);
1606	if (fdivides (buf, F, quot))
1607	{
1608	factorsFoundIndex[i]= 1;
1609	factorsFound++;
1610	F= quot;
1611	F /= Lc (F);
1612	reconstructedFactors.append (buf);
1613	}
1614	if (degree (F) <= 0)
1615	return;
1616	if (factorsFound + 1 == nmod_mat_ncols (N))
1617	{
1618	reconstructedFactors.append (F);
1619	return;
1620	}
1621	}
1622	}
1623	#endif
1624
1625	CFList
1626	reconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, int
1627	precision, const mat_zz_pE& N
1628	)
1629	{
1630	Variable y= Variable (2);
1631	Variable x= Variable (1);
1632	CanonicalForm F= G;
1633	CanonicalForm yToL= power (y, precision);
1634	CanonicalForm quot, buf;
1635	CFList result, factorsConsidered;
1636	CFList bufFactors= factors;
1637	CFListIterator iter;
1638	for (long i= 1; i <= N.NumCols(); i++)
1639	{
1640	if (zeroOneVecs [i - 1] == 0)
1641	continue;
1642	iter= factors;
1643	buf= 1;
1644	factorsConsidered= CFList();
1645	for (long j= 1; j <= N.NumRows(); j++, iter++)
1646	{
1647	if (!IsZero (N (j,i)))
1648	{
1649	factorsConsidered.append (iter.getItem());
1650	buf= mulMod2 (buf, iter.getItem(), yToL);
1651	}
1652	}
1653	buf *= LC (F, x);
1654	buf= mod (buf, yToL);
1655	buf /= content (buf, x);
1656	if (fdivides (buf, F, quot))
1657	{
1658	F= quot;
1659	F /= Lc (F);
1660	result.append (buf);
1661	bufFactors= Difference (bufFactors, factorsConsidered);
1662	}
1663	if (degree (F) <= 0)
1664	{
1665	G= F;
1666	factors= bufFactors;
1667	return result;
1668	}
1669	}
1670	G= F;
1671	factors= bufFactors;
1672	return result;
1673	}
1674
1675	CFList
1676	monicReconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs,
1677	int precision, const mat_zz_pE& N
1678	)
1679	{
1680	Variable y= Variable (2);
1681	Variable x= Variable (1);
1682	CanonicalForm F= G;
1683	CanonicalForm yToL= power (y, precision);
1684	CanonicalForm quot, buf, buf2;
1685	CFList result;
1686	CFList bufFactors= factors;
1687	CFList factorsConsidered;
1688	CFListIterator iter;
1689	for (long i= 1; i <= N.NumCols(); i++)
1690	{
1691	if (zeroOneVecs [i - 1] == 0)
1692	continue;
1693	iter= factors;
1694	buf= 1;
1695	factorsConsidered= CFList();
1696	for (long j= 1; j <= N.NumRows(); j++, iter++)
1697	{
1698	if (!IsZero (N (j,i)))
1699	{
1700	factorsConsidered.append (iter.getItem());
1701	buf= mulMod2 (buf, iter.getItem(), yToL);
1702	}
1703	}
1704	buf2= buf;
1705	buf *= LC (F, x);
1706	buf= mod (buf, yToL);
1707	buf /= content (buf, x);
1708	if (fdivides (buf, F, quot))
1709	{
1710	F= quot;
1711	F /= Lc (F);
1712	result.append (buf2);
1713	bufFactors= Difference (bufFactors, factorsConsidered);
1714	}
1715	if (degree (F) <= 0)
1716	{
1717	G= F;
1718	factors= bufFactors;
1719	return result;
1720	}
1721	}
1722	G= F;
1723	factors= bufFactors;
1724	return result;
1725	}
1726
1727	CFList
1728	extReconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, int
1729	precision, const mat_zz_p& N, const ExtensionInfo& info,
1730	const CanonicalForm& evaluation
1731	)
1732	{
1733	Variable y= Variable (2);
1734	Variable x= Variable (1);
1735	Variable alpha= info.getAlpha();
1736	Variable beta= info.getBeta();
1737	int k= info.getGFDegree();
1738	CanonicalForm gamma= info.getGamma();
1739	CanonicalForm delta= info.getDelta();
1740	CanonicalForm F= G;
1741	CanonicalForm yToL= power (y, precision);
1742	CFList result;
1743	CFList bufFactors= factors;
1744	CFList factorsConsidered;
1745	CanonicalForm buf2, quot, buf;
1746	CFListIterator iter;
1747	for (long i= 1; i <= N.NumCols(); i++)
1748	{
1749	if (zeroOneVecs [i - 1] == 0)
1750	continue;
1751	iter= factors;
1752	buf= 1;
1753	factorsConsidered= CFList();
1754	for (long j= 1; j <= N.NumRows(); j++, iter++)
1755	{
1756	if (!IsZero (N (j,i)))
1757	{
1758	factorsConsidered.append (iter.getItem());
1759	buf= mulMod2 (buf, iter.getItem(), yToL);
1760	}
1761	}
1762	buf *= LC (F, x);
1763	buf= mod (buf, yToL);
1764	buf /= content (buf, x);
1765	buf2= buf (y-evaluation, y);
1766	if (!k && beta == x)
1767	{
1768	if (degree (buf2, alpha) < 1)
1769	{
1770	if (fdivides (buf, F, quot))
1771	{
1772	F= quot;
1773	F /= Lc (F);
1774	result.append (buf2);
1775	bufFactors= Difference (bufFactors, factorsConsidered);
1776	}
1777	}
1778	}
1779	else
1780	{
1781	CFList source, dest;
1782
1783	if (!isInExtension (buf2, gamma, k, delta, source, dest))
1784	{
1785	if (fdivides (buf, F, quot))
1786	{
1787	F= quot;
1788	F /= Lc (F);
1789	result.append (buf2);
1790	bufFactors= Difference (bufFactors, factorsConsidered);
1791	}
1792	}
1793	}
1794	if (degree (F) <= 0)
1795	{
1796	G= F;
1797	factors= bufFactors;
1798	return result;
1799	}
1800	}
1801	G= F;
1802	factors= bufFactors;
1803	return result;
1804	}
1805
1806	#ifdef HAVE_FLINT
1807	CFList
1808	extReconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, int
1809	precision, const nmod_mat_t N, const ExtensionInfo& info,
1810	const CanonicalForm& evaluation
1811	)
1812	{
1813	Variable y= Variable (2);
1814	Variable x= Variable (1);
1815	Variable alpha= info.getAlpha();
1816	Variable beta= info.getBeta();
1817	int k= info.getGFDegree();
1818	CanonicalForm gamma= info.getGamma();
1819	CanonicalForm delta= info.getDelta();
1820	CanonicalForm F= G;
1821	CanonicalForm yToL= power (y, precision);
1822	CFList result;
1823	CFList bufFactors= factors;
1824	CFList factorsConsidered;
1825	CanonicalForm buf2, quot, buf;
1826	CFListIterator iter;
1827	for (long i= 0; i < nmod_mat_ncols(N); i++)
1828	{
1829	if (zeroOneVecs [i] == 0)
1830	continue;
1831	iter= factors;
1832	buf= 1;
1833	factorsConsidered= CFList();
1834	for (long j= 0; j < nmod_mat_ncols(N); j++, iter++)
1835	{
1836	if (!(nmod_mat_entry (N, j, i) == 0))
1837	{
1838	factorsConsidered.append (iter.getItem());
1839	buf= mulMod2 (buf, iter.getItem(), yToL);
1840	}
1841	}
1842	buf *= LC (F, x);
1843	buf= mod (buf, yToL);
1844	buf /= content (buf, x);
1845	buf2= buf (y-evaluation, y);
1846	if (!k && beta == x)
1847	{
1848	if (degree (buf2, alpha) < 1)
1849	{
1850	if (fdivides (buf, F, quot))
1851	{
1852	F= quot;
1853	F /= Lc (F);
1854	result.append (buf2);
1855	bufFactors= Difference (bufFactors, factorsConsidered);
1856	}
1857	}
1858	}
1859	else
1860	{
1861	CFList source, dest;
1862
1863	if (!isInExtension (buf2, gamma, k, delta, source, dest))
1864	{
1865	if (fdivides (buf, F, quot))
1866	{
1867	F= quot;
1868	F /= Lc (F);
1869	result.append (buf2);
1870	bufFactors= Difference (bufFactors, factorsConsidered);
1871	}
1872	}
1873	}
1874	if (degree (F) <= 0)
1875	{
1876	G= F;
1877	factors= bufFactors;
1878	return result;
1879	}
1880	}
1881	G= F;
1882	factors= bufFactors;
1883	return result;
1884	}
1885	#endif
1886
1887	CFList
1888	reconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs,
1889	int precision, const mat_zz_p& N)
1890	{
1891	Variable y= Variable (2);
1892	Variable x= Variable (1);
1893	CanonicalForm F= G;
1894	CanonicalForm yToL= power (y, precision);
1895	CanonicalForm quot, buf;
1896	CFList result;
1897	CFList bufFactors= factors;
1898	CFList factorsConsidered;
1899	CFListIterator iter;
1900	for (long i= 1; i <= N.NumCols(); i++)
1901	{
1902	if (zeroOneVecs [i - 1] == 0)
1903	continue;
1904	iter= factors;
1905	buf= 1;
1906	factorsConsidered= CFList();
1907	for (long j= 1; j <= N.NumRows(); j++, iter++)
1908	{
1909	if (!IsZero (N (j,i)))
1910	{
1911	factorsConsidered.append (iter.getItem());
1912	buf= mulMod2 (buf, iter.getItem(), yToL);
1913	}
1914	}
1915	buf *= LC (F, x);
1916	buf= mod (buf, yToL);
1917	buf /= content (buf, x);
1918	if (fdivides (buf, F, quot))
1919	{
1920	F= quot;
1921	F /= Lc (F);
1922	result.append (buf);
1923	bufFactors= Difference (bufFactors, factorsConsidered);
1924	}
1925	if (degree (F) <= 0)
1926	{
1927	G= F;
1928	factors= bufFactors;
1929	return result;
1930	}
1931	}
1932	G= F;
1933	factors= bufFactors;
1934	return result;
1935	}
1936
1937	#ifdef HAVE_FLINT
1938	CFList
1939	reconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs,
1940	int precision, const nmod_mat_t N)
1941	{
1942	Variable y= Variable (2);
1943	Variable x= Variable (1);
1944	CanonicalForm F= G;
1945	CanonicalForm yToL= power (y, precision);
1946	CanonicalForm quot, buf;
1947	CFList result;
1948	CFList bufFactors= factors;
1949	CFList factorsConsidered;
1950	CFListIterator iter;
1951	for (long i= 0; i < nmod_mat_ncols (N); i++)
1952	{
1953	if (zeroOneVecs [i] == 0)
1954	continue;
1955	iter= factors;
1956	buf= 1;
1957	factorsConsidered= CFList();
1958	for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
1959	{
1960	if (!(nmod_mat_entry (N, j, i) == 0))
1961	{
1962	factorsConsidered.append (iter.getItem());
1963	buf= mulMod2 (buf, iter.getItem(), yToL);
1964	}
1965	}
1966	buf *= LC (F, x);
1967	buf= mod (buf, yToL);
1968	buf /= content (buf, x);
1969	if (fdivides (buf, F, quot))
1970	{
1971	F= quot;
1972	F /= Lc (F);
1973	result.append (buf);
1974	bufFactors= Difference (bufFactors, factorsConsidered);
1975	}
1976	if (degree (F) <= 0)
1977	{
1978	G= F;
1979	factors= bufFactors;
1980	return result;
1981	}
1982	}
1983	G= F;
1984	factors= bufFactors;
1985	return result;
1986	}
1987	#endif
1988
1989	void
1990	extReconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const
1991	CFList& factors, const int liftBound, int& factorsFound,
1992	int*& factorsFoundIndex, mat_zz_p& N, bool beenInThres,
1993	const ExtensionInfo& info, const CanonicalForm& evaluation
1994	)
1995	{
1996	Variable y= Variable (2);
1997	Variable x= Variable (1);
1998	Variable alpha= info.getAlpha();
1999	Variable beta= info.getBeta();
2000	int k= info.getGFDegree();
2001	CanonicalForm gamma= info.getGamma();
2002	CanonicalForm delta= info.getDelta();
2003	CanonicalForm yToL= power (y, liftBound);
2004	CFList source, dest;
2005	if (factors.length() == 2)
2006	{
2007	CanonicalForm tmp1, tmp2, tmp3;
2008	tmp1= factors.getFirst();
2009	tmp2= factors.getLast();
2010	tmp1 *= LC (F, x);
2011	tmp1= mod (tmp1, yToL);
2012	tmp1 /= content (tmp1, x);
2013	tmp2 *= LC (F, x);
2014	tmp2= mod (tmp2, yToL);
2015	tmp2 /= content (tmp2, x);
2016	tmp3 = tmp1*tmp2;
2017	if (tmp3/Lc (tmp3) == F/Lc (F))
2018	{
2019	tmp1= tmp1 (y - evaluation, y);
2020	tmp2= tmp2 (y - evaluation, y);
2021	if (!k && beta == x && degree (tmp2, alpha) < 1 &&
2022	degree (tmp1, alpha) < 1)
2023	{
2024	factorsFound++;
2025	F= 1;
2026	tmp1= mapDown (tmp1, info, source, dest);
2027	tmp2= mapDown (tmp2, info, source, dest);
2028	reconstructedFactors.append (tmp1);
2029	reconstructedFactors.append (tmp2);
2030	return;
2031	}
2032	else if (!isInExtension (tmp2, gamma, k, delta, source, dest) &&
2033	!isInExtension (tmp1, gamma, k, delta, source, dest))
2034	{
2035	factorsFound++;
2036	F= 1;
2037	tmp1= mapDown (tmp1, info, source, dest);
2038	tmp2= mapDown (tmp2, info, source, dest);
2039	reconstructedFactors.append (tmp1);
2040	reconstructedFactors.append (tmp2);
2041	return;
2042	}
2043	}
2044	}
2045	CanonicalForm quot, buf, buf2;
2046	CFListIterator iter;
2047	for (long i= 1; i <= N.NumCols(); i++)
2048	{
2049	if (factorsFoundIndex [i - 1] == 1)
2050	continue;
2051	iter= factors;
2052	if (beenInThres)
2053	{
2054	int count= 1;
2055	while (count < i)
2056	{
2057	count++;
2058	iter++;
2059	}
2060	buf= iter.getItem();
2061	}
2062	else
2063	{
2064	buf= 1;
2065	for (long j= 1; j <= N.NumRows(); j++, iter++)
2066	{
2067	if (!IsZero (N (j,i)))
2068	buf= mulMod2 (buf, iter.getItem(), yToL);
2069	}
2070	}
2071	buf *= LC (F, x);
2072	buf= mod (buf, yToL);
2073	buf /= content (buf, x);
2074	buf2= buf (y - evaluation, y);
2075	if (!k && beta == x)
2076	{
2077	if (degree (buf2, alpha) < 1)
2078	{
2079	if (fdivides (buf, F, quot))
2080	{
2081	factorsFoundIndex[i - 1]= 1;
2082	factorsFound++;
2083	F= quot;
2084	F /= Lc (F);
2085	buf2= mapDown (buf2, info, source, dest);
2086	reconstructedFactors.append (buf2);
2087	}
2088	}
2089	}
2090	else
2091	{
2092	if (!isInExtension (buf2, gamma, k, delta, source, dest))
2093	{
2094	if (fdivides (buf, F, quot))
2095	{
2096	factorsFoundIndex[i - 1]= 1;
2097	factorsFound++;
2098	F= quot;
2099	F /= Lc (F);
2100	buf2= mapDown (buf2, info, source, dest);
2101	reconstructedFactors.append (buf2);
2102	}
2103	}
2104	}
2105	if (degree (F) <= 0)
2106	return;
2107	if (factorsFound + 1 == N.NumCols())
2108	{
2109	CanonicalForm tmp= F (y - evaluation, y);
2110	tmp= mapDown (tmp, info, source, dest);
2111	reconstructedFactors.append (tmp);
2112	return;
2113	}
2114	}
2115	}
2116
2117	#ifdef HAVE_FLINT
2118	void
2119	extReconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const
2120	CFList& factors, const int liftBound, int& factorsFound,
2121	int*& factorsFoundIndex, nmod_mat_t N, bool beenInThres,
2122	const ExtensionInfo& info, const CanonicalForm& evaluation
2123	)
2124	{
2125	Variable y= Variable (2);
2126	Variable x= Variable (1);
2127	Variable alpha= info.getAlpha();
2128	Variable beta= info.getBeta();
2129	int k= info.getGFDegree();
2130	CanonicalForm gamma= info.getGamma();
2131	CanonicalForm delta= info.getDelta();
2132	CanonicalForm yToL= power (y, liftBound);
2133	CFList source, dest;
2134	if (factors.length() == 2)
2135	{
2136	CanonicalForm tmp1, tmp2, tmp3;
2137	tmp1= factors.getFirst();
2138	tmp2= factors.getLast();
2139	tmp1 *= LC (F, x);
2140	tmp1= mod (tmp1, yToL);
2141	tmp1 /= content (tmp1, x);
2142	tmp2 *= LC (F, x);
2143	tmp2= mod (tmp2, yToL);
2144	tmp2 /= content (tmp2, x);
2145	tmp3 = tmp1*tmp2;
2146	if (tmp3/Lc (tmp3) == F/Lc (F))
2147	{
2148	tmp1= tmp1 (y - evaluation, y);
2149	tmp2= tmp2 (y - evaluation, y);
2150	if (!k && beta == x && degree (tmp2, alpha) < 1 &&
2151	degree (tmp1, alpha) < 1)
2152	{
2153	factorsFound++;
2154	F= 1;
2155	tmp1= mapDown (tmp1, info, source, dest);
2156	tmp2= mapDown (tmp2, info, source, dest);
2157	reconstructedFactors.append (tmp1);
2158	reconstructedFactors.append (tmp2);
2159	return;
2160	}
2161	else if (!isInExtension (tmp2, gamma, k, delta, source, dest) &&
2162	!isInExtension (tmp1, gamma, k, delta, source, dest))
2163	{
2164	factorsFound++;
2165	F= 1;
2166	tmp1= mapDown (tmp1, info, source, dest);
2167	tmp2= mapDown (tmp2, info, source, dest);
2168	reconstructedFactors.append (tmp1);
2169	reconstructedFactors.append (tmp2);
2170	return;
2171	}
2172	}
2173	}
2174	CanonicalForm quot, buf, buf2;
2175	CFListIterator iter;
2176	for (long i= 0; i < nmod_mat_ncols (N); i++)
2177	{
2178	if (factorsFoundIndex [i] == 1)
2179	continue;
2180	iter= factors;
2181	if (beenInThres)
2182	{
2183	int count= 0;
2184	while (count < i)
2185	{
2186	count++;
2187	iter++;
2188	}
2189	buf= iter.getItem();
2190	}
2191	else
2192	{
2193	buf= 1;
2194	for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
2195	{
2196	if (!(nmod_mat_entry (N, j, i) == 0))
2197	buf= mulMod2 (buf, iter.getItem(), yToL);
2198	}
2199	}
2200	buf *= LC (F, x);
2201	buf= mod (buf, yToL);
2202	buf /= content (buf, x);
2203	buf2= buf (y - evaluation, y);
2204	if (!k && beta == x)
2205	{
2206	if (degree (buf2, alpha) < 1)
2207	{
2208	if (fdivides (buf, F, quot))
2209	{
2210	factorsFoundIndex[i]= 1;
2211	factorsFound++;
2212	F= quot;
2213	F /= Lc (F);
2214	buf2= mapDown (buf2, info, source, dest);
2215	reconstructedFactors.append (buf2);
2216	}
2217	}
2218	}
2219	else
2220	{
2221	if (!isInExtension (buf2, gamma, k, delta, source, dest))
2222	{
2223	if (fdivides (buf, F, quot))
2224	{
2225	factorsFoundIndex[i]= 1;
2226	factorsFound++;
2227	F= quot;
2228	F /= Lc (F);
2229	buf2= mapDown (buf2, info, source, dest);
2230	reconstructedFactors.append (buf2);
2231	}
2232	}
2233	}
2234	if (degree (F) <= 0)
2235	return;
2236	if (factorsFound + 1 == nmod_mat_nrows (N))
2237	{
2238	CanonicalForm tmp= F (y - evaluation, y);
2239	tmp= mapDown (tmp, info, source, dest);
2240	reconstructedFactors.append (tmp);
2241	return;
2242	}
2243	}
2244	}
2245	#endif
2246
2247	//over Fp
2248	int
2249	liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds, int
2250	start, int liftBound, int minBound, CFList& factors,
2251	mat_zz_p& NTLN, CFList& diophant, CFMatrix& M, CFArray&
2252	Pi, CFArray& bufQ, bool& irreducible
2253	)
2254	{
2255	CanonicalForm LCF= LC (F, 1);
2256	CFArray *A= new CFArray [factors.length() - 1];
2257	bool wasInBounds= false;
2258	bool hitBound= false;
2259	int l= (minBound+1)*2;
2260	int stepSize= 2;
2261	int oldL= l/2;
2262	bool reduced= false;
2263	mat_zz_p NTLK, *NTLC;
2264	CFMatrix C;
2265	CFArray buf;
2266	CFListIterator j;
2267	CanonicalForm truncF;
2268	Variable y= F.mvar();
2269	while (l <= liftBound)
2270	{
2271	if (start)
2272	{
2273	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2274	start= 0;
2275	}
2276	else
2277	{
2278	if (wasInBounds)
2279	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2280	else
2281	henselLift12 (F, factors, l, Pi, diophant, M);
2282	}
2283
2284	factors.insert (LCF);
2285	j= factors;
2286	j++;
2287
2288	truncF= mod (F, power (y, l));
2289	for (int i= 0; i < factors.length() - 1; i++, j++)
2290	{
2291	if (!wasInBounds)
2292	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2293	else
2294	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2295	bufQ[i]);
2296	}
2297
2298	for (int i= 0; i < sizeBounds; i++)
2299	{
2300	if (bounds [i] + 1 <= l/2)
2301	{
2302	wasInBounds= true;
2303	int k= tmin (bounds [i] + 1, l/2);
2304	C= CFMatrix (l - k, factors.length() - 1);
2305	for (int ii= 0; ii < factors.length() - 1; ii++)
2306	{
2307	if (A[ii].size() - 1 >= i)
2308	{
2309	buf= getCoeffs (A[ii] [i], k);
2310	writeInMatrix (C, buf, ii + 1, 0);
2311	}
2312	}
2313	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
2314	NTLK= (NTLC)NTLN;
2315	transpose (NTLK, NTLK);
2316	kernel (NTLK, NTLK);
2317	transpose (NTLK, NTLK);
2318	NTLN *= NTLK;
2319
2320	if (NTLN.NumCols() == 1)
2321	{
2322	irreducible= true;
2323	break;
2324	}
2325	if (isReduced (NTLN) && l > (minBound+1)*2)
2326	{
2327	reduced= true;
2328	break;
2329	}
2330	}
2331	}
2332
2333	if (irreducible)
2334	break;
2335	if (reduced)
2336	break;
2337	oldL= l;
2338	l += stepSize;
2339	stepSize *= 2;
2340	if (l > liftBound)
2341	{
2342	if (!hitBound)
2343	{
2344	l= liftBound;
2345	hitBound= true;
2346	}
2347	else
2348	break;
2349	}
2350	}
2351	delete [] A;
2352	return l;
2353	}
2354
2355	#ifdef HAVE_FLINT
2356	int
2357	liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds, int
2358	start, int liftBound, int minBound, CFList& factors,
2359	nmod_mat_t FLINTN, CFList& diophant, CFMatrix& M,CFArray&
2360	Pi, CFArray& bufQ, bool& irreducible
2361	)
2362	{
2363	CanonicalForm LCF= LC (F, 1);
2364	CFArray *A= new CFArray [factors.length() - 1];
2365	bool wasInBounds= false;
2366	bool hitBound= false;
2367	int l= (minBound+1)*2;
2368	int stepSize= 2;
2369	int oldL= l/2;
2370	bool reduced= false;
2371	long rank;
2372	nmod_mat_t FLINTK, FLINTC, null;
2373	CFMatrix C;
2374	CFArray buf;
2375	CFListIterator j;
2376	CanonicalForm truncF;
2377	Variable y= F.mvar();
2378	while (l <= liftBound)
2379	{
2380	if (start)
2381	{
2382	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2383	start= 0;
2384	}
2385	else
2386	{
2387	if (wasInBounds)
2388	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2389	else
2390	henselLift12 (F, factors, l, Pi, diophant, M);
2391	}
2392
2393	factors.insert (LCF);
2394	j= factors;
2395	j++;
2396
2397	truncF= mod (F, power (y, l));
2398	for (int i= 0; i < factors.length() - 1; i++, j++)
2399	{
2400	if (!wasInBounds)
2401	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2402	else
2403	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2404	bufQ[i]);
2405	}
2406
2407	for (int i= 0; i < sizeBounds; i++)
2408	{
2409	if (bounds [i] + 1 <= l/2)
2410	{
2411	wasInBounds= true;
2412	int k= tmin (bounds [i] + 1, l/2);
2413	C= CFMatrix (l - k, factors.length() - 1);
2414	for (int ii= 0; ii < factors.length() - 1; ii++)
2415	{
2416	if (A[ii].size() - 1 >= i)
2417	{
2418	buf= getCoeffs (A[ii] [i], k);
2419	writeInMatrix (C, buf, ii + 1, 0);
2420	}
2421	}
2422
2423	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
2424	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
2425	getCharacteristic());
2426	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
2427	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
2428	getCharacteristic());
2429	rank= nmod_mat_nullspace (null, FLINTK);
2430	nmod_mat_clear (FLINTK);
2431	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
2432	nmod_mat_clear (FLINTC);
2433	nmod_mat_init_set (FLINTC, FLINTN);
2434	nmod_mat_clear (FLINTN);
2435	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
2436	getCharacteristic());
2437	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
2438
2439	nmod_mat_clear (FLINTC);
2440	nmod_mat_window_clear (FLINTK);
2441	nmod_mat_clear (null);
2442	if (nmod_mat_ncols (FLINTN) == 1)
2443	{
2444	irreducible= true;
2445	break;
2446	}
2447	if (isReduced (FLINTN) && l > (minBound+1)*2)
2448	{
2449	reduced= true;
2450	break;
2451	}
2452	}
2453	}
2454
2455	if (irreducible)
2456	break;
2457	if (reduced)
2458	break;
2459	oldL= l;
2460	l += stepSize;
2461	stepSize *= 2;
2462	if (l > liftBound)
2463	{
2464	if (!hitBound)
2465	{
2466	l= liftBound;
2467	hitBound= true;
2468	}
2469	else
2470	break;
2471	}
2472	}
2473	delete [] A;
2474	return l;
2475	}
2476	#endif
2477
2478	//over field extension
2479	int
2480	extLiftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds,
2481	int liftBound, int minBound, int start, CFList&
2482	factors, mat_zz_p& NTLN, CFList& diophant,
2483	CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
2484	irreducible, const CanonicalForm& evaluation, const
2485	ExtensionInfo& info, CFList& source, CFList& dest
2486	)
2487	{
2488	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
2489	CanonicalForm LCF= LC (F, 1);
2490	CFArray *A= new CFArray [factors.length() - 1];
2491	bool wasInBounds= false;
2492	bool hitBound= false;
2493	int degMipo;
2494	Variable alpha;
2495	alpha= info.getAlpha();
2496	degMipo= degree (getMipo (alpha));
2497
2498	Variable gamma= info.getBeta();
2499	CanonicalForm primElemAlpha= info.getGamma();
2500	CanonicalForm imPrimElemAlpha= info.getDelta();
2501
2502	int stepSize= 2;
2503	int l= ((minBound+1)/degMipo+1)*2;
2504	l= tmax (l, 2);
2505	if (start > l)
2506	l= start;
2507	int oldL= l/2;
2508	bool reduced= false;
2509	Variable y= F.mvar();
2510	Variable x= Variable (1);
2511	CanonicalForm powX, imBasis, truncF;
2512	CFMatrix Mat, C;
2513	CFArray buf;
2514	CFIterator iter;
2515	mat_zz_p* NTLMat, *NTLC, NTLK;
2516	CFListIterator j;
2517	while (l <= liftBound)
2518	{
2519	if (start)
2520	{
2521	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2522	start= 0;
2523	}
2524	else
2525	{
2526	if (wasInBounds)
2527	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2528	else
2529	henselLift12 (F, factors, l, Pi, diophant, M);
2530	}
2531
2532	factors.insert (LCF);
2533
2534	if (GF)
2535	setCharacteristic (getCharacteristic());
2536
2537	powX= power (y-gamma, l);
2538	Mat= CFMatrix (ldegMipo, ldegMipo);
2539	for (int i= 0; i < l*degMipo; i++)
2540	{
2541	imBasis= mod (power (y, i), powX);
2542	imBasis= imBasis (power (y, degMipo), y);
2543	imBasis= imBasis (y, gamma);
2544	iter= imBasis;
2545	for (; iter.hasTerms(); iter++)
2546	Mat (iter.exp()+ 1, i+1)= iter.coeff();
2547	}
2548
2549	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
2550	NTLMat= inv (NTLMat);
2551
2552	if (GF)
2553	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2554
2555	j= factors;
2556	j++;
2557
2558	truncF= mod (F, power (y, l));
2559	for (int i= 0; i < factors.length() - 1; i++, j++)
2560	{
2561	if (!wasInBounds)
2562	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2563	else
2564	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2565	bufQ[i]);
2566	}
2567
2568	for (int i= 0; i < sizeBounds; i++)
2569	{
2570	if (bounds [i] + 1 <= (l/2)*degMipo)
2571	{
2572	wasInBounds= true;
2573	int k= tmin (bounds [i] + 1, (l/2)*degMipo);
2574	C= CFMatrix (l*degMipo - k, factors.length() - 1);
2575
2576	for (int ii= 0; ii < factors.length() - 1; ii++)
2577	{
2578	if (A[ii].size() - 1 >= i)
2579	{
2580	if (GF)
2581	{
2582	A [ii] [i]= A [ii] [i] (y-evaluation, y);
2583	setCharacteristic (getCharacteristic());
2584	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
2585	if (alpha != gamma)
2586	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2587	gamma, source, dest
2588	);
2589	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
2590	}
2591	else
2592	{
2593	A [ii] [i]= A [ii] [i] (y-evaluation, y);
2594	if (alpha != gamma)
2595	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2596	gamma, source, dest
2597	);
2598	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
2599	}
2600	writeInMatrix (C, buf, ii + 1, 0);
2601	}
2602	if (GF)
2603	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2604	}
2605
2606	if (GF)
2607	setCharacteristic(getCharacteristic());
2608
2609	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
2610	NTLK= (NTLC)NTLN;
2611	transpose (NTLK, NTLK);
2612	kernel (NTLK, NTLK);
2613	transpose (NTLK, NTLK);
2614	NTLN *= NTLK;
2615
2616	if (GF)
2617	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2618
2619	if (NTLN.NumCols() == 1)
2620	{
2621	irreducible= true;
2622	break;
2623	}
2624	if (isReduced (NTLN))
2625	{
2626	reduced= true;
2627	break;
2628	}
2629	}
2630	}
2631
2632	if (NTLN.NumCols() == 1)
2633	{
2634	irreducible= true;
2635	break;
2636	}
2637	if (reduced)
2638	break;
2639	oldL= l;
2640	l += stepSize;
2641	stepSize *= 2;
2642	if (l > liftBound)
2643	{
2644	if (!hitBound)
2645	{
2646	l= liftBound;
2647	hitBound= true;
2648	}
2649	else
2650	break;
2651	}
2652	}
2653	delete [] A;
2654	return l;
2655	}
2656
2657	/*#ifdef HAVE_FLINT
2658	//over field extension
2659	int
2660	extLiftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds,
2661	int liftBound, int minBound, int start, CFList&
2662	factors, nmod_mat_t FLINTN, CFList& diophant,
2663	CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
2664	irreducible, const CanonicalForm& evaluation, const
2665	ExtensionInfo& info, CFList& source, CFList& dest
2666	)
2667	{
2668	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
2669	CanonicalForm LCF= LC (F, 1);
2670	CFArray *A= new CFArray [factors.length() - 1];
2671	bool wasInBounds= false;
2672	bool hitBound= false;
2673	int degMipo;
2674	Variable alpha;
2675	alpha= info.getAlpha();
2676	degMipo= degree (getMipo (alpha));
2677
2678	Variable gamma= info.getBeta();
2679	CanonicalForm primElemAlpha= info.getGamma();
2680	CanonicalForm imPrimElemAlpha= info.getDelta();
2681
2682	int stepSize= 2;
2683	int l= ((minBound+1)/degMipo+1)*2;
2684	l= tmax (l, 2);
2685	if (start > l)
2686	l= start;
2687	int oldL= l/2;
2688	bool reduced= false;
2689	Variable y= F.mvar();
2690	Variable x= Variable (1);
2691	CanonicalForm powX, imBasis, truncF;
2692	CFMatrix Mat, C;
2693	CFArray buf;
2694	CFIterator iter;
2695	long rank;
2696	nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
2697	CFListIterator j;
2698	while (l <= liftBound)
2699	{
2700	if (start)
2701	{
2702	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2703	start= 0;
2704	}
2705	else
2706	{
2707	if (wasInBounds)
2708	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2709	else
2710	henselLift12 (F, factors, l, Pi, diophant, M);
2711	}
2712
2713	factors.insert (LCF);
2714
2715	if (GF)
2716	setCharacteristic (getCharacteristic());
2717
2718	powX= power (y-gamma, l);
2719	Mat= CFMatrix (ldegMipo, ldegMipo);
2720	for (int i= 0; i < l*degMipo; i++)
2721	{
2722	imBasis= mod (power (y, i), powX);
2723	imBasis= imBasis (power (y, degMipo), y);
2724	imBasis= imBasis (y, gamma);
2725	iter= imBasis;
2726	for (; iter.hasTerms(); iter++)
2727	Mat (iter.exp()+ 1, i+1)= iter.coeff();
2728	}
2729
2730	convertFacCFMatrix2nmod_mat_t (FLINTMat, Mat);
2731	nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
2732	nmod_mat_nrows (FLINTMat), getCharacteristic());
2733	nmod_mat_inv (FLINTMatInv, FLINTMat);
2734
2735	if (GF)
2736	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2737
2738	j= factors;
2739	j++;
2740
2741	truncF= mod (F, power (y, l));
2742	for (int i= 0; i < factors.length() - 1; i++, j++)
2743	{
2744	if (!wasInBounds)
2745	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2746	else
2747	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2748	bufQ[i]);
2749	}
2750
2751	for (int i= 0; i < sizeBounds; i++)
2752	{
2753	if (bounds [i] + 1 <= (l/2)*degMipo)
2754	{
2755	wasInBounds= true;
2756	int k= tmin (bounds [i] + 1, (l/2)*degMipo);
2757	C= CFMatrix (l*degMipo - k, factors.length() - 1);
2758
2759	for (int ii= 0; ii < factors.length() - 1; ii++)
2760	{
2761	if (A[ii].size() - 1 >= i)
2762	{
2763	if (GF)
2764	{
2765	A [ii] [i]= A [ii] [i] (y-evaluation, y);
2766	setCharacteristic (getCharacteristic());
2767	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
2768	if (alpha != gamma)
2769	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2770	gamma, source, dest
2771	);
2772	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv); //TODO
2773	}
2774	else
2775	{
2776	A [ii] [i]= A [ii] [i] (y-evaluation, y);
2777	if (alpha != gamma)
2778	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2779	gamma, source, dest
2780	);
2781	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv); //TODO
2782	}
2783	writeInMatrix (C, buf, ii + 1, 0);
2784	}
2785	if (GF)
2786	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2787	}
2788
2789	if (GF)
2790	setCharacteristic(getCharacteristic());
2791
2792	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
2793	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
2794	getCharacteristic());
2795	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
2796	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
2797	getCharacteristic());
2798	rank= nmod_mat_nullspace (null, FLINTK);
2799	nmod_mat_clear (FLINTK);
2800	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
2801	nmod_mat_clear (FLINTC);
2802	nmod_mat_init_set (FLINTC, FLINTN);
2803	nmod_mat_clear (FLINTN);
2804	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
2805	getCharacteristic());
2806	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
2807
2808	nmod_mat_clear (FLINTC);
2809	nmod_mat_window_clear (FLINTK);
2810	nmod_mat_clear (null);
2811
2812	if (GF)
2813	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2814
2815	if (nmod_mat_ncols (FLINTN) == 1)
2816	{
2817	irreducible= true;
2818	break;
2819	}
2820	if (isReduced (FLINTN))
2821	{
2822	reduced= true;
2823	break;
2824	}
2825	}
2826	}
2827
2828	nmod_mat_clear (FLINTMat);
2829	nmod_mat_clear (FLINTMatInv);
2830
2831	if (nmod_mat_ncols (FLINTN) == 1)
2832	{
2833	irreducible= true;
2834	break;
2835	}
2836	if (reduced)
2837	break;
2838	oldL= l;
2839	l += stepSize;
2840	stepSize *= 2;
2841	if (l > liftBound)
2842	{
2843	if (!hitBound)
2844	{
2845	l= liftBound;
2846	hitBound= true;
2847	}
2848	else
2849	break;
2850	}
2851	}
2852	delete [] A;
2853	return l;
2854	}
2855	#endif*/
2856
2857	// over Fq
2858	int
2859	liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds,
2860	int start, int liftBound, int minBound, CFList& factors,
2861	mat_zz_pE& NTLN, CFList& diophant, CFMatrix& M, CFArray&
2862	Pi, CFArray& bufQ, bool& irreducible
2863	)
2864	{
2865	CanonicalForm LCF= LC (F, 1);
2866	CFArray *A= new CFArray [factors.length() - 1];
2867	bool wasInBounds= false;
2868	bool hitBound= false;
2869	int l= (minBound+1)*2;
2870	int stepSize= 2;
2871	int oldL= l/2;
2872	bool reduced= false;
2873	CFListIterator j;
2874	mat_zz_pE* NTLC, NTLK;
2875	CFArray buf;
2876	CFMatrix C;
2877	Variable y= F.mvar();
2878	CanonicalForm truncF;
2879	while (l <= liftBound)
2880	{
2881	if (start)
2882	{
2883	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2884	start= 0;
2885	}
2886	else
2887	{
2888	if (wasInBounds)
2889	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2890	else
2891	henselLift12 (F, factors, l, Pi, diophant, M);
2892	}
2893
2894	factors.insert (LCF);
2895	j= factors;
2896	j++;
2897
2898	truncF= mod (F, power (y,l));
2899	for (int i= 0; i < factors.length() - 1; i++, j++)
2900	{
2901	if (l == (minBound+1)*2)
2902	{
2903	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2904	}
2905	else
2906	{
2907	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2908	bufQ[i]
2909	);
2910	}
2911	}
2912
2913	for (int i= 0; i < sizeBounds; i++)
2914	{
2915	if (bounds [i] + 1 <= l/2)
2916	{
2917	wasInBounds= true;
2918	int k= tmin (bounds [i] + 1, l/2);
2919	C= CFMatrix (l - k, factors.length() - 1);
2920	for (int ii= 0; ii < factors.length() - 1; ii++)
2921	{
2922
2923	if (A[ii].size() - 1 >= i)
2924	{
2925	buf= getCoeffs (A[ii] [i], k);
2926	writeInMatrix (C, buf, ii + 1, 0);
2927	}
2928	}
2929
2930	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
2931	NTLK= (NTLC)NTLN;
2932	transpose (NTLK, NTLK);
2933	kernel (NTLK, NTLK);
2934	transpose (NTLK, NTLK);
2935	NTLN *= NTLK;
2936
2937	if (NTLN.NumCols() == 1)
2938	{
2939	irreducible= true;
2940	break;
2941	}
2942	if (isReduced (NTLN) && l > (minBound+1)*2)
2943	{
2944	reduced= true;
2945	break;
2946	}
2947	}
2948	}
2949
2950	if (NTLN.NumCols() == 1)
2951	{
2952	irreducible= true;
2953	break;
2954	}
2955	if (reduced)
2956	break;
2957	oldL= l;
2958	l += stepSize;
2959	stepSize *= 2;
2960	if (l > liftBound)
2961	{
2962	if (!hitBound)
2963	{
2964	l= liftBound;
2965	hitBound= true;
2966	}
2967	else
2968	break;
2969	}
2970	}
2971	delete [] A;
2972	return l;
2973	}
2974
2975	#ifdef HAVE_FLINT
2976	int
2977	liftAndComputeLatticeFq2Fp (const CanonicalForm& F, int* bounds, int sizeBounds,
2978	int start, int liftBound, int minBound, CFList&
2979	factors, nmod_mat_t FLINTN, CFList& diophant,
2980	CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
2981	irreducible, const Variable& alpha
2982	)
2983	#else
2984	int
2985	liftAndComputeLatticeFq2Fp (const CanonicalForm& F, int* bounds, int sizeBounds,
2986	int start, int liftBound, int minBound, CFList&
2987	factors, mat_zz_p& NTLN, CFList& diophant, CFMatrix&
2988	M, CFArray& Pi, CFArray& bufQ, bool& irreducible,
2989	const Variable& alpha
2990	)
2991	#endif
2992	{
2993	CanonicalForm LCF= LC (F, 1);
2994	CFArray *A= new CFArray [factors.length() - 1];
2995	bool wasInBounds= false;
2996	int l= (minBound+1)*2;
2997	int oldL= l/2;
2998	int stepSize= 2;
2999	bool hitBound= false;
3000	int extensionDeg= degree (getMipo (alpha));
3001	bool reduced= false;
3002	CFListIterator j;
3003	CFMatrix C;
3004	CFArray buf;
3005	#ifdef HAVE_FLINT
3006	long rank;
3007	nmod_mat_t FLINTC, FLINTK, null;
3008	#else
3009	mat_zz_p* NTLC, NTLK;
3010	#endif
3011	Variable y= F.mvar();
3012	CanonicalForm truncF;
3013	while (l <= liftBound)
3014	{
3015	if (start)
3016	{
3017	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
3018	start= 0;
3019	}
3020	else
3021	{
3022	if (wasInBounds)
3023	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
3024	else
3025	henselLift12 (F, factors, l, Pi, diophant, M);
3026	}
3027
3028	factors.insert (LCF);
3029	j= factors;
3030	j++;
3031
3032	truncF= mod (F, power (y,l));
3033	for (int i= 0; i < factors.length() - 1; i++, j++)
3034	{
3035	if (l == (minBound+1)*2)
3036	{
3037	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
3038	}
3039	else
3040	{
3041	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
3042	bufQ[i]
3043	);
3044	}
3045	}
3046
3047	for (int i= 0; i < sizeBounds; i++)
3048	{
3049	if (bounds [i] + 1 <= l/2)
3050	{
3051	wasInBounds= true;
3052	int k= tmin (bounds [i] + 1, l/2);
3053	C= CFMatrix ((l - k)*extensionDeg, factors.length() - 1);
3054	for (int ii= 0; ii < factors.length() - 1; ii++)
3055	{
3056	if (A[ii].size() - 1 >= i)
3057	{
3058	buf= getCoeffs (A[ii] [i], k, alpha);
3059	writeInMatrix (C, buf, ii + 1, 0);
3060	}
3061	}
3062
3063	#ifdef HAVE_FLINT
3064	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
3065	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3066	getCharacteristic());
3067	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3068	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3069	getCharacteristic());
3070	rank= nmod_mat_nullspace (null, FLINTK);
3071	nmod_mat_clear (FLINTK);
3072	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3073	nmod_mat_clear (FLINTC);
3074	nmod_mat_init_set (FLINTC, FLINTN);
3075	nmod_mat_clear (FLINTN);
3076	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3077	getCharacteristic());
3078	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3079
3080	nmod_mat_clear (FLINTC);
3081	nmod_mat_window_clear (FLINTK);
3082	nmod_mat_clear (null);
3083	#else
3084	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
3085	NTLK= (NTLC)NTLN;
3086	transpose (NTLK, NTLK);
3087	kernel (NTLK, NTLK);
3088	transpose (NTLK, NTLK);
3089	NTLN *= NTLK;
3090	#endif
3091
3092	#ifdef HAVE_FLINT
3093	if (nmod_mat_nrows (FLINTN) == 1)
3094	#else
3095	if (NTLN.NumCols() == 1)
3096	#endif
3097	{
3098	irreducible= true;
3099	break;
3100	}
3101	#ifdef HAVE_FLINT
3102	if (isReduced (FLINTN) && l > (minBound+1)*2)
3103	#else
3104	if (isReduced (NTLN) && l > (minBound+1)*2)
3105	#endif
3106	{
3107	reduced= true;
3108	break;
3109	}
3110	}
3111	}
3112
3113	#ifdef HAVE_FLINT
3114	if (nmod_mat_ncols (FLINTN) == 1)
3115	#else
3116	if (NTLN.NumCols() == 1)
3117	#endif
3118	{
3119	irreducible= true;
3120	break;
3121	}
3122	if (reduced)
3123	break;
3124	oldL= l;
3125	l += stepSize;
3126	stepSize *= 2;
3127	if (l > liftBound)
3128	{
3129	if (!hitBound)
3130	{
3131	l= liftBound;
3132	hitBound= true;
3133	}
3134	else
3135	break;
3136	}
3137	}
3138	delete [] A;
3139	return l;
3140	}
3141
3142	CFList
3143	increasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
3144	int oldNumCols, int oldL, int precision
3145	)
3146	{
3147	int d;
3148	bool isIrreducible= false;
3149	int* bounds= computeBounds (F, d, isIrreducible);
3150	if (isIrreducible)
3151	{
3152	delete [] bounds;
3153	CanonicalForm G= F;
3154	F= 1;
3155	return CFList (G);
3156	}
3157	CFArray * A= new CFArray [factors.length()];
3158	CFArray bufQ= CFArray (factors.length());
3159	#ifdef HAVE_FLINT
3160	nmod_mat_t FLINTN;
3161	nmod_mat_init (FLINTN,factors.length(),factors.length(), getCharacteristic());
3162	for (long i=factors.length()-1; i >= 0; i--)
3163	nmod_mat_entry (FLINTN, i, i)= 1;
3164	#else
3165	mat_zz_p NTLN;
3166	ident (NTLN, factors.length());
3167	#endif
3168	int minBound= bounds[0];
3169	for (int i= 1; i < d; i++)
3170	{
3171	if (bounds[i] != 0)
3172	minBound= tmin (minBound, bounds[i]);
3173	}
3174	int l= tmax (2*(minBound + 1), oldL);
3175	int oldL2= l/2;
3176	int stepSize= 2;
3177	bool useOldQs= false;
3178	bool hitBound= false;
3179	CFListIterator j;
3180	CFMatrix C;
3181	CFArray buf;
3182	#ifdef HAVE_FLINT
3183	long rank;
3184	nmod_mat_t FLINTC, FLINTK, null;
3185	#else
3186	mat_zz_p* NTLC, NTLK;
3187	#endif
3188	Variable y= F.mvar();
3189	CanonicalForm truncF;
3190	while (l <= precision)
3191	{
3192	j= factors;
3193	truncF= mod (F, power (y,l));
3194	if (useOldQs)
3195	{
3196	for (int i= 0; i < factors.length(); i++, j++)
3197	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3198	bufQ[i]
3199	);
3200	}
3201	else
3202	{
3203	for (int i= 0; i < factors.length(); i++, j++)
3204	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3205	}
3206	useOldQs= true;
3207	for (int i= 0; i < d; i++)
3208	{
3209	if (bounds [i] + 1 <= l/2)
3210	{
3211	int k= tmin (bounds [i] + 1, l/2);
3212	C= CFMatrix (l - k, factors.length());
3213	for (int ii= 0; ii < factors.length(); ii++)
3214	{
3215	if (A[ii].size() - 1 >= i)
3216	{
3217	buf= getCoeffs (A[ii] [i], k);
3218	writeInMatrix (C, buf, ii + 1, 0);
3219	}
3220	}
3221	#ifdef HAVE_FLINT
3222	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
3223	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3224	getCharacteristic());
3225	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3226	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3227	getCharacteristic());
3228	rank= nmod_mat_nullspace (null, FLINTK);
3229	nmod_mat_clear (FLINTK);
3230	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3231	nmod_mat_clear (FLINTC);
3232	nmod_mat_init_set (FLINTC, FLINTN);
3233	nmod_mat_clear (FLINTN);
3234	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3235	getCharacteristic());
3236	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3237
3238	nmod_mat_clear (FLINTC);
3239	nmod_mat_window_clear (FLINTK);
3240	nmod_mat_clear (null);
3241	#else
3242	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
3243	NTLK= (NTLC)NTLN;
3244	transpose (NTLK, NTLK);
3245	kernel (NTLK, NTLK);
3246	transpose (NTLK, NTLK);
3247	NTLN *= NTLK;
3248	#endif
3249	#ifdef HAVE_FLINT
3250	if (nmod_mat_ncols (FLINTN) == 1)
3251	{
3252	nmod_mat_clear (FLINTN);
3253	#else
3254	if (NTLN.NumCols() == 1)
3255	{
3256	#endif
3257	delete [] A;
3258	delete [] bounds;
3259	CanonicalForm G= F;
3260	F= 1;
3261	return CFList (G);
3262	}
3263	}
3264	}
3265
3266	#ifdef HAVE_FLINT
3267	if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
3268	{
3269	if (isReduced (FLINTN))
3270	{
3271	int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
3272	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
3273	#else
3274	if (NTLN.NumCols() < oldNumCols - factorsFound)
3275	{
3276	if (isReduced (NTLN))
3277	{
3278	int * factorsFoundIndex= new int [NTLN.NumCols()];
3279	for (long i= 0; i < NTLN.NumCols(); i++)
3280	#endif
3281	factorsFoundIndex[i]= 0;
3282	int factorsFound2= 0;
3283	CFList result;
3284	CanonicalForm bufF= F;
3285	#ifdef HAVE_FLINT
3286	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
3287	factorsFoundIndex, FLINTN, false
3288	);
3289	if (result.length() == nmod_mat_ncols (FLINTN))
3290	{
3291	nmod_mat_clear (FLINTN);
3292	#else
3293	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
3294	factorsFoundIndex, NTLN, false
3295	);
3296	if (result.length() == NTLN.NumCols())
3297	{
3298	#endif
3299	delete [] factorsFoundIndex;
3300	delete [] A;
3301	delete [] bounds;
3302	F= 1;
3303	return result;
3304	}
3305	delete [] factorsFoundIndex;
3306	}
3307	else if (l == precision)
3308	{
3309	CanonicalForm bufF= F;
3310	#ifdef HAVE_FLINT
3311	int * zeroOne= extractZeroOneVecs (FLINTN);
3312	CFList result= reconstruction (bufF,factors,zeroOne,precision,FLINTN);
3313	nmod_mat_clear (FLINTN);
3314	#else
3315	int * zeroOne= extractZeroOneVecs (NTLN);
3316	CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
3317	#endif
3318	F= bufF;
3319	delete [] zeroOne;
3320	delete [] A;
3321	delete [] bounds;
3322	return result;
3323	}
3324	}
3325	oldL2= l;
3326	l += stepSize;
3327	stepSize *= 2;
3328	if (l > precision)
3329	{
3330	if (!hitBound)
3331	{
3332	l= precision;
3333	hitBound= true;
3334	}
3335	else
3336	break;
3337	}
3338	}
3339	#ifdef HAVE_FLINT
3340	nmod_mat_clear (FLINTN);
3341	#endif
3342	delete [] bounds;
3343	delete [] A;
3344	return CFList();
3345	}
3346
3347	CFList
3348	increasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
3349	int oldNumCols, int oldL, const Variable&,
3350	int precision
3351	)
3352	{
3353	int d;
3354	bool isIrreducible= false;
3355	int* bounds= computeBounds (F, d, isIrreducible);
3356	if (isIrreducible)
3357	{
3358	delete [] bounds;
3359	CanonicalForm G= F;
3360	F= 1;
3361	return CFList (G);
3362	}
3363	CFArray * A= new CFArray [factors.length()];
3364	CFArray bufQ= CFArray (factors.length());
3365	mat_zz_pE NTLN;
3366	ident (NTLN, factors.length());
3367	int minBound= bounds[0];
3368	for (int i= 1; i < d; i++)
3369	{
3370	if (bounds[i] != 0)
3371	minBound= tmin (minBound, bounds[i]);
3372	}
3373	int l= tmax (2*(minBound + 1), oldL);
3374	int oldL2= l/2;
3375	int stepSize= 2;
3376	bool useOldQs= false;
3377	bool hitBound= false;
3378	CFListIterator j;
3379	CFMatrix C;
3380	mat_zz_pE* NTLC, NTLK;
3381	CFArray buf;
3382	Variable y= F.mvar();
3383	CanonicalForm truncF;
3384	while (l <= precision)
3385	{
3386	j= factors;
3387	truncF= mod (F, power (y,l));
3388	if (useOldQs)
3389	{
3390	for (int i= 0; i < factors.length(); i++, j++)
3391	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3392	bufQ[i]
3393	);
3394	}
3395	else
3396	{
3397	for (int i= 0; i < factors.length(); i++, j++)
3398	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3399	}
3400	useOldQs= true;
3401	for (int i= 0; i < d; i++)
3402	{
3403	if (bounds [i] + 1 <= l/2)
3404	{
3405	int k= tmin (bounds [i] + 1, l/2);
3406	C= CFMatrix (l - k, factors.length());
3407	for (int ii= 0; ii < factors.length(); ii++)
3408	{
3409	if (A[ii].size() - 1 >= i)
3410	{
3411	buf= getCoeffs (A[ii] [i], k);
3412	writeInMatrix (C, buf, ii + 1, 0);
3413	}
3414	}
3415	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
3416	NTLK= (NTLC)NTLN;
3417	transpose (NTLK, NTLK);
3418	kernel (NTLK, NTLK);
3419	transpose (NTLK, NTLK);
3420	NTLN *= NTLK;
3421	if (NTLN.NumCols() == 1)
3422	{
3423	delete [] A;
3424	delete [] bounds;
3425	CanonicalForm G= F;
3426	F= 1;
3427	return CFList (G);
3428	}
3429	}
3430	}
3431
3432	if (NTLN.NumCols() < oldNumCols - factorsFound)
3433	{
3434	if (isReduced (NTLN))
3435	{
3436	int * factorsFoundIndex= new int [NTLN.NumCols()];
3437	for (long i= 0; i < NTLN.NumCols(); i++)
3438	factorsFoundIndex[i]= 0;
3439	int factorsFound2= 0;
3440	CFList result;
3441	CanonicalForm bufF= F;
3442	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
3443	factorsFoundIndex, NTLN, false);
3444	if (result.length() == NTLN.NumCols())
3445	{
3446	delete [] factorsFoundIndex;
3447	delete [] A;
3448	delete [] bounds;
3449	F= 1;
3450	return result;
3451	}
3452	delete [] factorsFoundIndex;
3453	}
3454	else if (l == precision)
3455	{
3456	CanonicalForm bufF= F;
3457	int * zeroOne= extractZeroOneVecs (NTLN);
3458	CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
3459	F= bufF;
3460	delete [] zeroOne;
3461	delete [] A;
3462	delete [] bounds;
3463	return result;
3464	}
3465	}
3466	oldL2= l;
3467	l += stepSize;
3468	stepSize *= 2;
3469	if (l > precision)
3470	{
3471	if (!hitBound)
3472	{
3473	l= precision;
3474	hitBound= true;
3475	}
3476	else
3477	break;
3478	}
3479	}
3480	delete [] bounds;
3481	delete [] A;
3482	return CFList();
3483	}
3484
3485	//over field extension
3486	CFList
3487	extIncreasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
3488	int oldNumCols, int oldL, const CanonicalForm& evaluation,
3489	const ExtensionInfo& info, CFList& source, CFList& dest,
3490	int precision
3491	)
3492	{
3493	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
3494	int degMipo= degree (getMipo (info.getAlpha()));
3495	Variable alpha= info.getAlpha();
3496	int d;
3497	bool isIrreducible= false;
3498	int* bounds= computeBounds (F, d, isIrreducible);
3499	if (isIrreducible)
3500	{
3501	delete [] bounds;
3502	CanonicalForm G= F;
3503	F= 1;
3504	return CFList (G);
3505	}
3506
3507	CFArray * A= new CFArray [factors.length()];
3508	CFArray bufQ= CFArray (factors.length());
3509	zz_p::init (getCharacteristic());
3510	mat_zz_p NTLN;
3511	ident (NTLN, factors.length());
3512	int minBound= bounds[0];
3513	for (int i= 1; i < d; i++)
3514	{
3515	if (bounds[i] != 0)
3516	minBound= tmin (minBound, bounds[i]);
3517	}
3518	int l= tmax (oldL, 2*((minBound+1)/degMipo+1));
3519	int oldL2= l/2;
3520	int stepSize= 2;
3521	bool useOldQs= false;
3522	bool hitBound= false;
3523	Variable gamma= info.getBeta();
3524	CanonicalForm primElemAlpha= info.getGamma();
3525	CanonicalForm imPrimElemAlpha= info.getDelta();
3526	CFListIterator j;
3527	Variable y= F.mvar();
3528	CanonicalForm powX, imBasis, truncF;
3529	CFMatrix Mat, C;
3530	CFIterator iter;
3531	mat_zz_p* NTLMat,*NTLC, NTLK;
3532	CFArray buf;
3533	while (l <= precision)
3534	{
3535	j= factors;
3536	if (GF)
3537	setCharacteristic (getCharacteristic());
3538	powX= power (y-gamma, l);
3539	Mat= CFMatrix (ldegMipo, ldegMipo);
3540	for (int i= 0; i < l*degMipo; i++)
3541	{
3542	imBasis= mod (power (y, i), powX);
3543	imBasis= imBasis (power (y, degMipo), y);
3544	imBasis= imBasis (y, gamma);
3545	iter= imBasis;
3546	for (; iter.hasTerms(); iter++)
3547	Mat (iter.exp()+ 1, i+1)= iter.coeff();
3548	}
3549
3550	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
3551	NTLMat= inv (NTLMat);
3552	if (GF)
3553	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
3554
3555	truncF= mod (F, power (y, l));
3556	if (useOldQs)
3557	{
3558	for (int i= 0; i < factors.length(); i++, j++)
3559	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3560	bufQ[i]
3561	);
3562	}
3563	else
3564	{
3565	for (int i= 0; i < factors.length(); i++, j++)
3566	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3567	}
3568	useOldQs= true;
3569	for (int i= 0; i < d; i++)
3570	{
3571	if (bounds [i] + 1 <= (l/2)*degMipo)
3572	{
3573	int k= tmin (bounds [i] + 1, (l/2)*degMipo);
3574	C= CFMatrix (l*degMipo - k, factors.length());
3575	for (int ii= 0; ii < factors.length(); ii++)
3576	{
3577	if (A[ii].size() - 1 >= i)
3578	{
3579	if (GF)
3580	{
3581	A[ii] [i]= A [ii] [i] (y-evaluation, y);
3582	setCharacteristic (getCharacteristic());
3583	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
3584	if (alpha != gamma)
3585	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
3586	gamma, source, dest
3587	);
3588	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
3589	}
3590	else
3591	{
3592	A [ii] [i]= A [ii] [i] (y-evaluation, y);
3593	if (alpha != gamma)
3594	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
3595	gamma, source, dest
3596	);
3597	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
3598	}
3599	writeInMatrix (C, buf, ii + 1, 0);
3600	}
3601	if (GF)
3602	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
3603	}
3604
3605	if (GF)
3606	setCharacteristic(getCharacteristic());
3607
3608	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
3609	NTLK= (NTLC)NTLN;
3610	transpose (NTLK, NTLK);
3611	kernel (NTLK, NTLK);
3612	transpose (NTLK, NTLK);
3613	NTLN *= NTLK;
3614
3615	if (GF)
3616	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
3617
3618	if (NTLN.NumCols() == 1)
3619	{
3620	Variable y= Variable (2);
3621	CanonicalForm tmp= F (y - evaluation, y);
3622	CFList source, dest;
3623	tmp= mapDown (tmp, info, source, dest);
3624	delete [] A;
3625	delete [] bounds;
3626	F= 1;
3627	return CFList (tmp);
3628	}
3629	}
3630	}
3631
3632	if (NTLN.NumCols() < oldNumCols - factorsFound)
3633	{
3634	if (isReduced (NTLN))
3635	{
3636	int * factorsFoundIndex= new int [NTLN.NumCols()];
3637	for (long i= 0; i < NTLN.NumCols(); i++)
3638	factorsFoundIndex[i]= 0;
3639	int factorsFound2= 0;
3640	CFList result;
3641	CanonicalForm bufF= F;
3642	extReconstructionTry (result, bufF, factors,degree (F)+1, factorsFound2,
3643	factorsFoundIndex, NTLN, false, info, evaluation
3644	);
3645	if (result.length() == NTLN.NumCols())
3646	{
3647	delete [] factorsFoundIndex;
3648	delete [] A;
3649	delete [] bounds;
3650	F= 1;
3651	return result;
3652	}
3653	delete [] factorsFoundIndex;
3654	}
3655	else if (l == precision)
3656	{
3657	CanonicalForm bufF= F;
3658	int * zeroOne= extractZeroOneVecs (NTLN);
3659	CFList result= extReconstruction (bufF, factors, zeroOne, precision,
3660	NTLN, info, evaluation
3661	);
3662	F= bufF;
3663	delete [] zeroOne;
3664	delete [] A;
3665	delete [] bounds;
3666	return result;
3667	}
3668	}
3669	oldL2= l;
3670	l += stepSize;
3671	stepSize *= 2;
3672	if (l > precision)
3673	{
3674	if (!hitBound)
3675	{
3676	hitBound= true;
3677	l= precision;
3678	}
3679	else
3680	break;
3681	}
3682	}
3683	delete [] bounds;
3684	delete [] A;
3685	return CFList();
3686	}
3687
3688	CFList
3689	increasePrecision2 (const CanonicalForm& F, CFList& factors,
3690	const Variable& alpha, int precision)
3691	{
3692	int d;
3693	bool isIrreducible= false;
3694	int* bounds= computeBounds (F, d, isIrreducible);
3695	if (isIrreducible)
3696	{
3697	delete [] bounds;
3698	return CFList (F);
3699	}
3700	CFArray * A= new CFArray [factors.length()];
3701	CFArray bufQ= CFArray (factors.length());
3702	zz_p::init (getCharacteristic());
3703	zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
3704	zz_pE::init (NTLMipo);
3705	mat_zz_pE NTLN;
3706	ident (NTLN, factors.length());
3707	int minBound= bounds[0];
3708	for (int i= 1; i < d; i++)
3709	{
3710	if (bounds[i] != 0)
3711	minBound= tmin (minBound, bounds[i]);
3712	}
3713	int l= tmin (2*(minBound + 1), precision);
3714	int oldL= l/2;
3715	int stepSize= 2;
3716	bool useOldQs= false;
3717	bool hitBound= false;
3718	CFListIterator j;
3719	CFMatrix C;
3720	CFArray buf;
3721	mat_zz_pE* NTLC, NTLK;
3722	Variable y= F.mvar();
3723	CanonicalForm truncF;
3724	while (l <= precision)
3725	{
3726	j= factors;
3727	truncF= mod (F, power (y, l));
3728	if (useOldQs)
3729	{
3730	for (int i= 0; i < factors.length(); i++, j++)
3731	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i], bufQ[i]);
3732	}
3733	else
3734	{
3735	for (int i= 0; i < factors.length(); i++, j++)
3736	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3737	}
3738	useOldQs= true;
3739	for (int i= 0; i < d; i++)
3740	{
3741	if (bounds [i] + 1 <= l/2)
3742	{
3743	int k= tmin (bounds [i] + 1, l/2);
3744	C= CFMatrix (l - k, factors.length());
3745	for (int ii= 0; ii < factors.length(); ii++)
3746	{
3747	if (A[ii].size() - 1 >= i)
3748	{
3749	buf= getCoeffs (A[ii] [i], k);
3750	writeInMatrix (C, buf, ii + 1, 0);
3751	}
3752	}
3753	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
3754	NTLK= (NTLC)NTLN;
3755	transpose (NTLK, NTLK);
3756	kernel (NTLK, NTLK);
3757	transpose (NTLK, NTLK);
3758	NTLN *= NTLK;
3759	if (NTLN.NumCols() == 1)
3760	{
3761	delete [] A;
3762	delete [] bounds;
3763	return CFList (F);
3764	}
3765	}
3766	}
3767
3768	if (isReduced (NTLN) \|\| l == precision)
3769	{
3770	CanonicalForm bufF= F;
3771	int * zeroOne= extractZeroOneVecs (NTLN);
3772	CFList bufFactors= factors;
3773	CFList result= monicReconstruction (bufF, factors, zeroOne, precision,
3774	NTLN
3775	);
3776	if (result.length() != NTLN.NumCols() && l != precision)
3777	factors= bufFactors;
3778	if (result.length() == NTLN.NumCols())
3779	{
3780	delete [] zeroOne;
3781	delete [] A;
3782	delete [] bounds;
3783	return result;
3784	}
3785	if (l == precision)
3786	{
3787	delete [] zeroOne;
3788	delete [] A;
3789	delete [] bounds;
3790	return Union (result, factors);
3791	}
3792	}
3793	oldL= l;
3794	l += stepSize;
3795	stepSize *= 2;
3796	if (l > precision)
3797	{
3798	if (!hitBound)
3799	{
3800	l= precision;
3801	hitBound= true;
3802	}
3803	else
3804	break;
3805	}
3806	}
3807	delete [] bounds;
3808	delete [] A;
3809	return CFList();
3810	}
3811
3812	CFList
3813	increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int factorsFound,
3814	int oldNumCols, int oldL, const Variable& alpha,
3815	int precision
3816	)
3817	{
3818	int d;
3819	bool isIrreducible= false;
3820	int* bounds= computeBounds (F, d, isIrreducible);
3821	if (isIrreducible)
3822	{
3823	delete [] bounds;
3824	CanonicalForm G= F;
3825	F= 1;
3826	return CFList (G);
3827	}
3828	int extensionDeg= degree (getMipo (alpha));
3829	CFArray * A= new CFArray [factors.length()];
3830	CFArray bufQ= CFArray (factors.length());
3831	#ifdef HAVE_FLINT
3832	nmod_mat_t FLINTN;
3833	nmod_mat_init (FLINTN,factors.length(),factors.length(), getCharacteristic());
3834	for (long i=factors.length()-1; i >= 0; i--)
3835	nmod_mat_entry (FLINTN, i, i)= 1;
3836	#else
3837	mat_zz_p NTLN;
3838	ident (NTLN, factors.length());
3839	#endif
3840	int minBound= bounds[0];
3841	for (int i= 1; i < d; i++)
3842	{
3843	if (bounds[i] != 0)
3844	minBound= tmin (minBound, bounds[i]);
3845	}
3846	int l= tmax (2*(minBound + 1), oldL);
3847	int oldL2= l/2;
3848	int stepSize= 2;
3849	bool useOldQs= false;
3850	bool hitBound= false;
3851	CFListIterator j;
3852	CFMatrix C;
3853	#ifdef HAVE_FLINT
3854	long rank;
3855	nmod_mat_t FLINTC, FLINTK, null;
3856	#else
3857	mat_zz_p* NTLC, NTLK;
3858	#endif
3859	CFArray buf;
3860	Variable y= F.mvar();
3861	CanonicalForm truncF;
3862	while (l <= precision)
3863	{
3864	j= factors;
3865	truncF= mod (F, power (y, l));
3866	if (useOldQs)
3867	{
3868	for (int i= 0; i < factors.length(); i++, j++)
3869	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3870	bufQ[i]
3871	);
3872	}
3873	else
3874	{
3875	for (int i= 0; i < factors.length(); i++, j++)
3876	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3877	}
3878	useOldQs= true;
3879	for (int i= 0; i < d; i++)
3880	{
3881	if (bounds [i] + 1 <= l/2)
3882	{
3883	int k= tmin (bounds [i] + 1, l/2);
3884	C= CFMatrix ((l - k)*extensionDeg, factors.length());
3885	for (int ii= 0; ii < factors.length(); ii++)
3886	{
3887	if (A[ii].size() - 1 >= i)
3888	{
3889	buf= getCoeffs (A[ii] [i], k, alpha);
3890	writeInMatrix (C, buf, ii + 1, 0);
3891	}
3892	}
3893	#ifdef HAVE_FLINT
3894	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
3895	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3896	getCharacteristic());
3897	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3898	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3899	getCharacteristic());
3900	rank= nmod_mat_nullspace (null, FLINTK);
3901	nmod_mat_clear (FLINTK);
3902	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3903	nmod_mat_clear (FLINTC);
3904	nmod_mat_init_set (FLINTC, FLINTN);
3905	nmod_mat_clear (FLINTN);
3906	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3907	getCharacteristic());
3908	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3909
3910	nmod_mat_clear (FLINTC);
3911	nmod_mat_window_clear (FLINTK);
3912	nmod_mat_clear (null);
3913	#else
3914	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
3915	NTLK= (NTLC)NTLN;
3916	transpose (NTLK, NTLK);
3917	kernel (NTLK, NTLK);
3918	transpose (NTLK, NTLK);
3919	NTLN *= NTLK;
3920	#endif
3921	#ifdef HAVE_FLINT
3922	if (nmod_mat_ncols (FLINTN) == 1)
3923	{
3924	nmod_mat_clear (FLINTN);
3925	#else
3926	if (NTLN.NumCols() == 1)
3927	{
3928	#endif
3929	delete [] A;
3930	delete [] bounds;
3931	CanonicalForm G= F;
3932	F= 1;
3933	return CFList (G);
3934	}
3935	}
3936	}
3937
3938	#ifdef HAVE_FLINT
3939	if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
3940	{
3941	if (isReduced (FLINTN))
3942	{
3943	int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
3944	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
3945	#else
3946	if (NTLN.NumCols() < oldNumCols - factorsFound)
3947	{
3948	if (isReduced (NTLN))
3949	{
3950	int * factorsFoundIndex= new int [NTLN.NumCols()];
3951	for (long i= 0; i < NTLN.NumCols(); i++)
3952	#endif
3953	factorsFoundIndex[i]= 0;
3954	int factorsFound2= 0;
3955	CFList result;
3956	CanonicalForm bufF= F;
3957	#ifdef HAVE_FLINT
3958	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
3959	factorsFoundIndex, FLINTN, false
3960	);
3961	if (result.length() == nmod_mat_ncols (FLINTN))
3962	{
3963	nmod_mat_clear (FLINTN);
3964	#else
3965	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
3966	factorsFoundIndex, NTLN, false
3967	);
3968	if (result.length() == NTLN.NumCols())
3969	{
3970	#endif
3971	delete [] factorsFoundIndex;
3972	delete [] A;
3973	delete [] bounds;
3974	F= 1;
3975	return result;
3976	}
3977	delete [] factorsFoundIndex;
3978	}
3979	else if (l == precision)
3980	{
3981	CanonicalForm bufF= F;
3982	#ifdef HAVE_FLINT
3983	int * zeroOne= extractZeroOneVecs (FLINTN);
3984	CFList result= reconstruction (bufF,factors,zeroOne,precision,FLINTN);
3985	nmod_mat_clear (FLINTN);
3986	#else
3987	int * zeroOne= extractZeroOneVecs (NTLN);
3988	CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
3989	#endif
3990	F= bufF;
3991	delete [] zeroOne;
3992	delete [] A;
3993	delete [] bounds;
3994	return result;
3995	}
3996	}
3997	oldL2= l;
3998	l += stepSize;
3999	stepSize *= 2;
4000	if (l > precision)
4001	{
4002	if (!hitBound)
4003	{
4004	hitBound= true;
4005	l= precision;
4006	}
4007	else
4008	break;
4009	}
4010	}
4011	#ifdef HAVE_FLINT
4012	nmod_mat_clear (FLINTN);
4013	#endif
4014	delete [] bounds;
4015	delete [] A;
4016	return CFList();
4017	}
4018
4019	#ifdef HAVE_FLINT
4020	CFList
4021	increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int
4022	l, int d, int* bounds, CFArray& bufQ, nmod_mat_t FLINTN
4023	)
4024	#else
4025	CFList
4026	increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int
4027	l, int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN
4028	)
4029	#endif
4030	{
4031	CFList result= CFList();
4032	CFArray * A= new CFArray [factors.length()];
4033	int oldL2= oldL/2;
4034	bool hitBound= false;
4035	#ifdef HAVE_FLINT
4036	if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4037	{
4038	nmod_mat_clear (FLINTN);
4039	nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
4040	for (long i=factors.length()-1; i >= 0; i--)
4041	nmod_mat_entry (FLINTN, i, i)= 1;
4042	bufQ= CFArray (factors.length());
4043	}
4044	#else
4045	if (NTLN.NumRows() != factors.length()) //refined factors
4046	{
4047	ident (NTLN, factors.length());
4048	bufQ= CFArray (factors.length());
4049	}
4050	#endif
4051	bool useOldQs= false;
4052	CFListIterator j;
4053	CFMatrix C;
4054	CFArray buf;
4055	#ifdef HAVE_FLINT
4056	long rank;
4057	nmod_mat_t FLINTC, FLINTK, null;
4058	#else
4059	mat_zz_p* NTLC, NTLK;
4060	#endif
4061	CanonicalForm bufF, truncF;
4062	CFList bufUniFactors;
4063	Variable y= F.mvar();
4064	while (oldL <= l)
4065	{
4066	j= factors;
4067	truncF= mod (F, power (y, oldL));
4068	if (useOldQs)
4069	{
4070	for (int i= 0; i < factors.length(); i++, j++)
4071	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4072	bufQ[i]
4073	);
4074	}
4075	else
4076	{
4077	for (int i= 0; i < factors.length(); i++, j++)
4078	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4079	}
4080	useOldQs= true;
4081
4082	for (int i= 0; i < d; i++)
4083	{
4084	if (bounds [i] + 1 <= oldL/2)
4085	{
4086	int k= tmin (bounds [i] + 1, oldL/2);
4087	C= CFMatrix (oldL - k, factors.length());
4088	for (int ii= 0; ii < factors.length(); ii++)
4089	{
4090	if (A[ii].size() - 1 >= i)
4091	{
4092	buf= getCoeffs (A[ii] [i], k);
4093	writeInMatrix (C, buf, ii + 1, 0);
4094	}
4095	}
4096	#ifdef HAVE_FLINT
4097	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
4098	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4099	getCharacteristic());
4100	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4101	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4102	getCharacteristic());
4103	rank= nmod_mat_nullspace (null, FLINTK);
4104	nmod_mat_clear (FLINTK);
4105	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4106	nmod_mat_clear (FLINTC);
4107	nmod_mat_init_set (FLINTC, FLINTN);
4108	nmod_mat_clear (FLINTN);
4109	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4110	getCharacteristic());
4111	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4112
4113	nmod_mat_clear (FLINTC);
4114	nmod_mat_window_clear (FLINTK);
4115	nmod_mat_clear (null);
4116	#else
4117	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4118	NTLK= (NTLC)NTLN;
4119	transpose (NTLK, NTLK);
4120	kernel (NTLK, NTLK);
4121	transpose (NTLK, NTLK);
4122	NTLN *= NTLK;
4123	#endif
4124	#ifdef HAVE_FLINT
4125	if (nmod_mat_ncols (FLINTN) == 1)
4126	#else
4127	if (NTLN.NumCols() == 1)
4128	#endif
4129	{
4130	delete [] A;
4131	return CFList (F);
4132	}
4133	}
4134	}
4135	#ifdef HAVE_FLINT
4136	if (nmod_mat_ncols (FLINTN) == 1)
4137	#else
4138	if (NTLN.NumCols() == 1)
4139	#endif
4140	{
4141	delete [] A;
4142	return CFList (F);
4143	}
4144	int * zeroOneVecs;
4145	#ifdef HAVE_FLINT
4146	zeroOneVecs= extractZeroOneVecs (FLINTN);
4147	#else
4148	zeroOneVecs= extractZeroOneVecs (NTLN);
4149	#endif
4150	bufF= F;
4151	bufUniFactors= factors;
4152	#ifdef HAVE_FLINT
4153	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, FLINTN);
4154	#else
4155	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
4156	#endif
4157	delete [] zeroOneVecs;
4158	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < oldL && result.length() > 0)
4159	{
4160	F= bufF;
4161	factors= bufUniFactors;
4162	delete [] A;
4163	return result;
4164	}
4165
4166	result= CFList();
4167	oldL2= oldL;
4168	oldL *= 2;
4169	if (oldL > l)
4170	{
4171	if (!hitBound)
4172	{
4173	oldL= l;
4174	hitBound= true;
4175	}
4176	else
4177	break;
4178	}
4179	}
4180	delete [] A;
4181	return result;
4182	}
4183
4184	CFList
4185	increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int
4186	l, int d, int* bounds, CFArray& bufQ, mat_zz_pE& NTLN
4187	)
4188	{
4189	CFList result= CFList();
4190	CFArray * A= new CFArray [factors.length()];
4191	int oldL2= oldL/2;
4192	bool hitBound= false;
4193	bool useOldQs= false;
4194	if (NTLN.NumRows() != factors.length()) //refined factors
4195	ident (NTLN, factors.length());
4196	CFListIterator j;
4197	CFMatrix C;
4198	CFArray buf;
4199	mat_zz_pE* NTLC, NTLK;
4200	CanonicalForm bufF, truncF;
4201	CFList bufUniFactors;
4202	Variable y= F.mvar();
4203	while (oldL <= l)
4204	{
4205	j= factors;
4206	truncF= mod (F, power (y, oldL));
4207	if (useOldQs)
4208	{
4209	for (int i= 0; i < factors.length(); i++, j++)
4210	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4211	bufQ[i]
4212	);
4213	}
4214	else
4215	{
4216	for (int i= 0; i < factors.length(); i++, j++)
4217	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4218	}
4219	useOldQs= true;
4220
4221	for (int i= 0; i < d; i++)
4222	{
4223	if (bounds [i] + 1 <= oldL/2)
4224	{
4225	int k= tmin (bounds [i] + 1, oldL/2);
4226	C= CFMatrix (oldL - k, factors.length());
4227	for (int ii= 0; ii < factors.length(); ii++)
4228	{
4229	if (A[ii].size() - 1 >= i)
4230	{
4231	buf= getCoeffs (A[ii] [i], k);
4232	writeInMatrix (C, buf, ii + 1, 0);
4233	}
4234	}
4235	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
4236	NTLK= (NTLC)NTLN;
4237	transpose (NTLK, NTLK);
4238	kernel (NTLK, NTLK);
4239	transpose (NTLK, NTLK);
4240	NTLN *= NTLK;
4241	if (NTLN.NumCols() == 1)
4242	{
4243	delete [] A;
4244	return CFList (F);
4245	}
4246	}
4247	}
4248	if (NTLN.NumCols() == 1)
4249	{
4250	delete [] A;
4251	return CFList (F);
4252	}
4253
4254	int * zeroOneVecs;
4255	zeroOneVecs= extractZeroOneVecs (NTLN);
4256	bufF= F;
4257	bufUniFactors= factors;
4258	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
4259	delete [] zeroOneVecs;
4260	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4261	{
4262	F= bufF;
4263	factors= bufUniFactors;
4264	delete [] A;
4265	return result;
4266	}
4267
4268	result= CFList();
4269	oldL2= oldL;
4270	oldL *= 2;
4271	if (oldL > l)
4272	{
4273	if (!hitBound)
4274	{
4275	oldL= l;
4276	hitBound= true;
4277	}
4278	else
4279	break;
4280	}
4281	}
4282	delete [] A;
4283	return result;
4284	}
4285
4286	//over field extension
4287	CFList
4288	extIncreasePrecision (CanonicalForm& F, CFList& factors, int oldL, int l, int d,
4289	int* bounds, CFArray& bufQ, mat_zz_p& NTLN, const
4290	CanonicalForm& evaluation, const ExtensionInfo& info,
4291	CFList& source, CFList& dest
4292	)
4293	{
4294	CFList result= CFList();
4295	CFArray * A= new CFArray [factors.length()];
4296	int oldL2= oldL/2; //be careful
4297	bool hitBound= false;
4298	bool useOldQs= false;
4299	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
4300	int degMipo= degree (getMipo (info.getAlpha()));
4301	Variable alpha= info.getAlpha();
4302
4303	Variable gamma= info.getBeta();
4304	CanonicalForm primElemAlpha= info.getGamma();
4305	CanonicalForm imPrimElemAlpha= info.getDelta();
4306	if (NTLN.NumRows() != factors.length()) //refined factors
4307	ident (NTLN, factors.length());
4308	Variable y= F.mvar();
4309	CFListIterator j;
4310	CanonicalForm powX, imBasis, bufF, truncF;
4311	CFMatrix Mat, C;
4312	CFIterator iter;
4313	mat_zz_p* NTLMat;
4314	CFArray buf;
4315	mat_zz_p* NTLC, NTLK;
4316	CFList bufUniFactors;
4317	while (oldL <= l)
4318	{
4319	j= factors;
4320	if (GF)
4321	setCharacteristic (getCharacteristic());
4322
4323	powX= power (y-gamma, oldL);
4324	Mat= CFMatrix (oldLdegMipo, oldLdegMipo);
4325	for (int i= 0; i < oldL*degMipo; i++)
4326	{
4327	imBasis= mod (power (y, i), powX);
4328	imBasis= imBasis (power (y, degMipo), y);
4329	imBasis= imBasis (y, gamma);
4330	iter= imBasis;
4331	for (; iter.hasTerms(); iter++)
4332	Mat (iter.exp()+ 1, i+1)= iter.coeff();
4333	}
4334
4335	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
4336	NTLMat= inv (NTLMat);
4337	if (GF)
4338	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
4339
4340	truncF= mod (F, power (y, oldL));
4341	if (useOldQs)
4342	{
4343	for (int i= 0; i < factors.length(); i++, j++)
4344	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4345	bufQ[i]);
4346	}
4347	else
4348	{
4349	for (int i= 0; i < factors.length(); i++, j++)
4350	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4351	}
4352	useOldQs= true;
4353
4354	for (int i= 0; i < d; i++)
4355	{
4356	if (bounds [i] + 1 <= oldL/2)
4357	{
4358	int k= tmin (bounds [i] + 1, oldL/2);
4359	C= CFMatrix (oldL*degMipo - k, factors.length());
4360	for (int ii= 0; ii < factors.length(); ii++)
4361	{
4362	if (A[ii].size() - 1 >= i)
4363	{
4364	if (GF)
4365	{
4366	A [ii] [i]= A [ii] [i] (y-evaluation, y);
4367	setCharacteristic (getCharacteristic());
4368	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
4369	if (alpha != gamma)
4370	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
4371	gamma, source, dest
4372	);
4373	buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
4374	}
4375	else
4376	{
4377	A [ii] [i]= A [ii] [i] (y-evaluation, y);
4378	if (alpha != gamma)
4379	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
4380	gamma, source, dest
4381	);
4382	buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
4383	}
4384	writeInMatrix (C, buf, ii + 1, 0);
4385	}
4386	if (GF)
4387	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
4388	}
4389
4390	if (GF)
4391	setCharacteristic(getCharacteristic());
4392
4393	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4394	NTLK= (NTLC)NTLN;
4395	transpose (NTLK, NTLK);
4396	kernel (NTLK, NTLK);
4397	transpose (NTLK, NTLK);
4398	NTLN *= NTLK;
4399
4400	if (GF)
4401	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
4402
4403	if (NTLN.NumCols() == 1)
4404	{
4405	Variable y= Variable (2);
4406	CanonicalForm tmp= F (y - evaluation, y);
4407	CFList source, dest;
4408	tmp= mapDown (tmp, info, source, dest);
4409	delete [] A;
4410	return CFList (tmp);
4411	}
4412	}
4413	}
4414	if (NTLN.NumCols() == 1)
4415	{
4416	Variable y= Variable (2);
4417	CanonicalForm tmp= F (y - evaluation, y);
4418	CFList source, dest;
4419	tmp= mapDown (tmp, info, source, dest);
4420	delete [] A;
4421	return CFList (tmp);
4422	}
4423
4424	int * zeroOneVecs;
4425	zeroOneVecs= extractZeroOneVecs (NTLN);
4426	bufF= F;
4427	bufUniFactors= factors;
4428	result= extReconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN,
4429	info, evaluation
4430	);
4431	delete [] zeroOneVecs;
4432	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4433	{
4434	F= bufF;
4435	factors= bufUniFactors;
4436	return result;
4437	}
4438
4439	result= CFList();
4440	oldL2= oldL;
4441	oldL *= 2;
4442	if (oldL > l)
4443	{
4444	if (!hitBound)
4445	{
4446	oldL= l;
4447	hitBound= true;
4448	}
4449	else
4450	break;
4451	}
4452	}
4453	delete [] A;
4454	return result;
4455	}
4456
4457	#ifdef HAVE_FLINT
4458	CFList
4459	increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int oldL, int l,
4460	int d, int* bounds, CFArray& bufQ, nmod_mat_t FLINTN,
4461	const Variable& alpha
4462	)
4463	#else
4464	CFList
4465	increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int oldL, int l,
4466	int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN,
4467	const Variable& alpha
4468	)
4469	#endif
4470	{
4471	CFList result= CFList();
4472	CFArray * A= new CFArray [factors.length()];
4473	int extensionDeg= degree (getMipo (alpha));
4474	int oldL2= oldL/2;
4475	bool hitBound= false;
4476	bool useOldQs= false;
4477	#ifdef HAVE_FLINT
4478	if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4479	{
4480	nmod_mat_clear (FLINTN);
4481	nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
4482	for (long i=factors.length()-1; i >= 0; i--)
4483	nmod_mat_entry (FLINTN, i, i)= 1;
4484	}
4485	#else
4486	if (NTLN.NumRows() != factors.length()) //refined factors
4487	ident (NTLN, factors.length());
4488	#endif
4489	CFListIterator j;
4490	CFMatrix C;
4491	CFArray buf;
4492	#ifdef HAVE_FLINT
4493	long rank;
4494	nmod_mat_t FLINTC, FLINTK, null;
4495	#else
4496	mat_zz_p* NTLC, NTLK;
4497	#endif
4498	CanonicalForm bufF, truncF;
4499	CFList bufUniFactors;
4500	Variable y= F.mvar();
4501	while (oldL <= l)
4502	{
4503	j= factors;
4504	truncF= mod (F, power (y, oldL));
4505	if (useOldQs)
4506	{
4507	for (int i= 0; i < factors.length(); i++, j++)
4508	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4509	bufQ[i]
4510	);
4511	}
4512	else
4513	{
4514	for (int i= 0; i < factors.length(); i++, j++)
4515	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4516	}
4517	useOldQs= true;
4518
4519	for (int i= 0; i < d; i++)
4520	{
4521	if (bounds [i] + 1 <= oldL/2)
4522	{
4523	int k= tmin (bounds [i] + 1, oldL/2);
4524	C= CFMatrix ((oldL - k)*extensionDeg, factors.length());
4525	for (int ii= 0; ii < factors.length(); ii++)
4526	{
4527	if (A[ii].size() - 1 >= i)
4528	{
4529	buf= getCoeffs (A[ii] [i], k, alpha);
4530	writeInMatrix (C, buf, ii + 1, 0);
4531	}
4532	}
4533	#ifdef HAVE_FLINT
4534	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
4535	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4536	getCharacteristic());
4537	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4538	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4539	getCharacteristic());
4540	rank= nmod_mat_nullspace (null, FLINTK);
4541	nmod_mat_clear (FLINTK);
4542	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4543	nmod_mat_clear (FLINTC);
4544	nmod_mat_init_set (FLINTC, FLINTN);
4545	nmod_mat_clear (FLINTN);
4546	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4547	getCharacteristic());
4548	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4549
4550	nmod_mat_clear (FLINTC);
4551	nmod_mat_window_clear (FLINTK);
4552	nmod_mat_clear (null);
4553	#else
4554	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4555	NTLK= (NTLC)NTLN;
4556	transpose (NTLK, NTLK);
4557	kernel (NTLK, NTLK);
4558	transpose (NTLK, NTLK);
4559	NTLN *= NTLK;
4560	#endif
4561	#ifdef HAVE_FLINT
4562	if (nmod_mat_ncols (FLINTN) == 1)
4563	#else
4564	if (NTLN.NumCols() == 1)
4565	#endif
4566	{
4567	delete [] A;
4568	return CFList (F);
4569	}
4570	}
4571	}
4572
4573	int * zeroOneVecs;
4574	#ifdef HAVE_FLINT
4575	zeroOneVecs= extractZeroOneVecs (FLINTN);
4576	#else
4577	zeroOneVecs= extractZeroOneVecs (NTLN);
4578	#endif
4579
4580	bufF= F;
4581	bufUniFactors= factors;
4582	#ifdef HAVE_FLINT
4583	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, FLINTN);
4584	#else
4585	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
4586	#endif
4587	delete [] zeroOneVecs;
4588	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4589	{
4590	F= bufF;
4591	factors= bufUniFactors;
4592	delete [] A;
4593	return result;
4594	}
4595
4596	result= CFList();
4597	oldL2= oldL;
4598	oldL *= 2;
4599	if (oldL > l)
4600	{
4601	if (!hitBound)
4602	{
4603	oldL= l;
4604	hitBound= true;
4605	}
4606	else
4607	break;
4608	}
4609	}
4610	delete [] A;
4611	return result;
4612	}
4613
4614	#ifdef HAVE_FLINT
4615	CFList
4616	furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList&
4617	factors, int l, int liftBound, int d, int*
4618	bounds, nmod_mat_t FLINTN, CFList& diophant,
4619	CFMatrix& M, CFArray& Pi, CFArray& bufQ
4620	)
4621	#else
4622	CFList
4623	furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList&
4624	factors, int l, int liftBound, int d, int*
4625	bounds, mat_zz_p& NTLN, CFList& diophant,
4626	CFMatrix& M, CFArray& Pi, CFArray& bufQ
4627	)
4628	#endif
4629	{
4630	CanonicalForm LCF= LC (F, 1);
4631	CFList result;
4632	bool irreducible= false;
4633	CFList bufFactors= factors;
4634	CFArray *A = new CFArray [bufFactors.length()];
4635	bool useOldQs= false;
4636	bool hitBound= false;
4637	int oldL= l;
4638	int stepSize= 8; //TODO choose better step size?
4639	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
4640	#ifdef HAVE_FLINT
4641	if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4642	{
4643	nmod_mat_clear (FLINTN);
4644	nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
4645	for (long i=factors.length()-1; i >= 0; i--)
4646	nmod_mat_entry (FLINTN, i, i)= 1;
4647	}
4648	#else
4649	if (NTLN.NumRows() != factors.length()) //refined factors
4650	ident (NTLN, factors.length());
4651	#endif
4652	CFListIterator j;
4653	CFMatrix C;
4654	CFArray buf;
4655	#ifdef HAVE_FLINT
4656	long rank;
4657	nmod_mat_t FLINTC, FLINTK, null;
4658	#else
4659	mat_zz_p* NTLC, NTLK;
4660	#endif
4661	CanonicalForm bufF, truncF;
4662	Variable y= F.mvar();
4663	while (l <= liftBound)
4664	{
4665	bufFactors.insert (LCF);
4666	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
4667	bufFactors.insert (LCF);
4668	bufFactors.removeFirst();
4669	j= bufFactors;
4670	truncF= mod (F, power (y, l));
4671	if (useOldQs)
4672	{
4673	for (int i= 0; i < bufFactors.length(); i++, j++)
4674	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
4675	bufQ[i]);
4676	}
4677	else
4678	{
4679	for (int i= 0; i < bufFactors.length(); i++, j++)
4680	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
4681	}
4682	for (int i= 0; i < d; i++)
4683	{
4684	if (bounds [i] + 1 <= l/2)
4685	{
4686	int k= tmin (bounds [i] + 1, l/2);
4687	C= CFMatrix (l - k, bufFactors.length());
4688	for (int ii= 0; ii < bufFactors.length(); ii++)
4689	{
4690	if (A[ii].size() - 1 >= i)
4691	{
4692	buf= getCoeffs (A[ii] [i], k);
4693	writeInMatrix (C, buf, ii + 1, 0);
4694	}
4695	}
4696	#ifdef HAVE_FLINT
4697	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
4698	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4699	getCharacteristic());
4700	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4701	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4702	getCharacteristic());
4703	rank= nmod_mat_nullspace (null, FLINTK);
4704	nmod_mat_clear (FLINTK);
4705	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4706	nmod_mat_clear (FLINTC);
4707	nmod_mat_init_set (FLINTC, FLINTN);
4708	nmod_mat_clear (FLINTN);
4709	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4710	getCharacteristic());
4711	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4712
4713	nmod_mat_clear (FLINTC);
4714	nmod_mat_window_clear (FLINTK);
4715	nmod_mat_clear (null);
4716	#else
4717	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4718	NTLK= (NTLC)NTLN;
4719	transpose (NTLK, NTLK);
4720	kernel (NTLK, NTLK);
4721	transpose (NTLK, NTLK);
4722	NTLN *= NTLK;
4723	#endif
4724	#ifdef HAVE_FLINT
4725	if (nmod_mat_ncols (FLINTN) == 1)
4726	#else
4727	if (NTLN.NumCols() == 1)
4728	#endif
4729	{
4730	irreducible= true;
4731	break;
4732	}
4733	}
4734	}
4735
4736	#ifdef HAVE_FLINT
4737	if (nmod_mat_ncols (FLINTN) == 1)
4738	#else
4739	if (NTLN.NumCols() == 1)
4740	#endif
4741	{
4742	irreducible= true;
4743	break;
4744	}
4745
4746	#ifdef HAVE_FLINT
4747	int * zeroOneVecs= extractZeroOneVecs (FLINTN);
4748	#else
4749	int * zeroOneVecs= extractZeroOneVecs (NTLN);
4750	#endif
4751	bufF= F;
4752	#ifdef HAVE_FLINT
4753	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, FLINTN);
4754	#else
4755	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
4756	#endif
4757	delete [] zeroOneVecs;
4758	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
4759	{
4760	F= bufF;
4761	factors= bufFactors;
4762	delete [] A;
4763	return result;
4764	}
4765
4766	#ifdef HAVE_FLINT
4767	if (isReduced (FLINTN))
4768	#else
4769	if (isReduced (NTLN))
4770	#endif
4771	{
4772	int factorsFound= 0;
4773	bufF= F;
4774	#ifdef HAVE_FLINT
4775	int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
4776	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
4777	#else
4778	int* factorsFoundIndex= new int [NTLN.NumCols()];
4779	for (long i= 0; i < NTLN.NumCols(); i++)
4780	#endif
4781	factorsFoundIndex[i]= 0;
4782	#ifdef HAVE_FLINT
4783	if (l < liftBound)
4784	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
4785	factorsFoundIndex, FLINTN, false
4786	);
4787	else
4788	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
4789	degree (LCF), factorsFound, factorsFoundIndex,
4790	FLINTN, false
4791	);
4792
4793	if (nmod_mat_ncols (FLINTN) == result.length())
4794	#else
4795	if (l < liftBound)
4796	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
4797	factorsFoundIndex, NTLN, false
4798	);
4799	else
4800	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
4801	degree (LCF), factorsFound, factorsFoundIndex,
4802	NTLN, false
4803	);
4804
4805	if (NTLN.NumCols() == result.length())
4806	#endif
4807	{
4808	delete [] A;
4809	delete [] factorsFoundIndex;
4810	return result;
4811	}
4812	delete [] factorsFoundIndex;
4813	}
4814	result= CFList();
4815	oldL= l;
4816	stepSize *= 2;
4817	l += stepSize;
4818	if (l > liftBound)
4819	{
4820	if (!hitBound)
4821	{
4822	l= liftBound;
4823	hitBound= true;
4824	}
4825	else
4826	break;
4827	}
4828	}
4829	if (irreducible)
4830	{
4831	delete [] A;
4832	return CFList (F);
4833	}
4834	delete [] A;
4835	factors= bufFactors;
4836	return CFList();
4837	}
4838
4839	//Fq
4840	CFList
4841	furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList&
4842	factors, int l, int liftBound, int d, int*
4843	bounds, mat_zz_pE& NTLN, CFList& diophant,
4844	CFMatrix& M, CFArray& Pi, CFArray& bufQ
4845	)
4846	{
4847	CanonicalForm LCF= LC (F, 1);
4848	CFList result;
4849	bool irreducible= false;
4850	CFList bufFactors= factors;
4851	CFArray *A = new CFArray [bufFactors.length()];
4852	bool useOldQs= false;
4853	bool hitBound= false;
4854	int oldL= l;
4855	int stepSize= 8; //TODO choose better step size?
4856	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
4857	if (NTLN.NumRows() != factors.length()) //refined factors
4858	ident (NTLN, factors.length());
4859	CFListIterator j;
4860	CFArray buf;
4861	mat_zz_pE* NTLC, NTLK;
4862	CanonicalForm bufF, truncF;
4863	Variable y= F.mvar();
4864	while (l <= liftBound)
4865	{
4866	bufFactors.insert (LCF);
4867	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
4868	j= bufFactors;
4869	truncF= mod (F, power (y, l));
4870	if (useOldQs)
4871	{
4872	for (int i= 0; i < bufFactors.length(); i++, j++)
4873	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
4874	bufQ[i]);
4875	}
4876	else
4877	{
4878	for (int i= 0; i < bufFactors.length(); i++, j++)
4879	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
4880	}
4881	for (int i= 0; i < d; i++)
4882	{
4883	if (bounds [i] + 1 <= l/2)
4884	{
4885	int k= tmin (bounds [i] + 1, l/2);
4886	CFMatrix C= CFMatrix (l - k, bufFactors.length());
4887	for (int ii= 0; ii < bufFactors.length(); ii++)
4888	{
4889	if (A[ii].size() - 1 >= i)
4890	{
4891	buf= getCoeffs (A[ii] [i], k);
4892	writeInMatrix (C, buf, ii + 1, 0);
4893	}
4894	}
4895	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
4896	NTLK= (NTLC)NTLN;
4897	transpose (NTLK, NTLK);
4898	kernel (NTLK, NTLK);
4899	transpose (NTLK, NTLK);
4900	NTLN *= NTLK;
4901	if (NTLN.NumCols() == 1)
4902	{
4903	irreducible= true;
4904	break;
4905	}
4906	}
4907	}
4908	if (NTLN.NumCols() == 1)
4909	{
4910	irreducible= true;
4911	break;
4912	}
4913
4914	int * zeroOneVecs= extractZeroOneVecs (NTLN);
4915	bufF= F;
4916	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
4917	delete [] zeroOneVecs;
4918	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
4919	{
4920	F= bufF;
4921	factors= bufFactors;
4922	delete [] A;
4923	return result;
4924	}
4925
4926	if (isReduced (NTLN))
4927	{
4928	int factorsFound= 0;
4929	bufF= F;
4930	int* factorsFoundIndex= new int [NTLN.NumCols()];
4931	for (long i= 0; i < NTLN.NumCols(); i++)
4932	factorsFoundIndex[i]= 0;
4933	if (l < liftBound)
4934	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
4935	factorsFoundIndex, NTLN, false
4936	);
4937	else
4938	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
4939	degree (LCF), factorsFound, factorsFoundIndex,
4940	NTLN, false
4941	);
4942	if (NTLN.NumCols() == result.length())
4943	{
4944	delete [] A;
4945	delete [] factorsFoundIndex;
4946	return result;
4947	}
4948	delete [] factorsFoundIndex;
4949	}
4950	result= CFList();
4951	oldL= l;
4952	stepSize *= 2;
4953	l += stepSize;
4954	if (l > liftBound)
4955	{
4956	if (!hitBound)
4957	{
4958	l= liftBound;
4959	hitBound= true;
4960	}
4961	else
4962	break;
4963	}
4964	}
4965	if (irreducible)
4966	{
4967	delete [] A;
4968	return CFList (F);
4969	}
4970	delete [] A;
4971	factors= bufFactors;
4972	return CFList();
4973	}
4974
4975	//over field extension
4976	CFList
4977	extFurtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList& factors, int l,
4978	int liftBound, int d, int* bounds,
4979	mat_zz_p& NTLN, CFList& diophant,
4980	CFMatrix& M, CFArray& Pi, CFArray& bufQ,
4981	const CanonicalForm& evaluation, const
4982	ExtensionInfo& info, CFList& source,
4983	CFList& dest
4984	)
4985	{
4986	CanonicalForm LCF= LC (F, 1);
4987	CFList result;
4988	bool irreducible= false;
4989	CFList bufFactors= factors;
4990	CFArray *A = new CFArray [bufFactors.length()];
4991	bool useOldQs= false;
4992	bool hitBound= false;
4993	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
4994	int degMipo= degree (getMipo (info.getAlpha()));
4995	Variable alpha= info.getAlpha();
4996	int oldL= l; //be careful
4997	int stepSize= 8;
4998	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l),2);
4999	Variable gamma= info.getBeta();
5000	CanonicalForm primElemAlpha= info.getGamma();
5001	CanonicalForm imPrimElemAlpha= info.getDelta();
5002	if (NTLN.NumRows() != factors.length()) //refined factors
5003	ident (NTLN, factors.length());
5004	Variable y= F.mvar();
5005	CanonicalForm powX, imBasis, bufF, truncF;
5006	CFMatrix Mat, C;
5007	CFIterator iter;
5008	mat_zz_p* NTLMat,*NTLC, NTLK;
5009	CFListIterator j;
5010	CFArray buf;
5011	while (l <= liftBound)
5012	{
5013	bufFactors.insert (LCF);
5014	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
5015
5016	if (GF)
5017	setCharacteristic (getCharacteristic());
5018
5019	powX= power (y-gamma, l);
5020	Mat= CFMatrix (ldegMipo, ldegMipo);
5021	for (int i= 0; i < l*degMipo; i++)
5022	{
5023
5024	imBasis= mod (power (y, i), powX);
5025	imBasis= imBasis (power (y, degMipo), y);
5026	imBasis= imBasis (y, gamma);
5027	iter= imBasis;
5028	for (; iter.hasTerms(); iter++)
5029	Mat (iter.exp()+ 1, i+1)= iter.coeff();
5030	}
5031
5032	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
5033	NTLMat= inv (NTLMat);
5034
5035	if (GF)
5036	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
5037
5038	j= bufFactors;
5039	truncF= mod (F, power (y, l));
5040	if (useOldQs)
5041	{
5042	for (int i= 0; i < bufFactors.length(); i++, j++)
5043	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5044	bufQ[i]);
5045	}
5046	else
5047	{
5048	for (int i= 0; i < bufFactors.length(); i++, j++)
5049	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5050	}
5051	for (int i= 0; i < d; i++)
5052	{
5053	if (bounds [i] + 1 <= l/2)
5054	{
5055	int k= tmin (bounds [i] + 1, l/2);
5056	C= CFMatrix (l*degMipo - k, bufFactors.length());
5057	for (int ii= 0; ii < bufFactors.length(); ii++)
5058	{
5059	if (A[ii].size() - 1 >= i)
5060	{
5061	if (GF)
5062	{
5063	A [ii] [i]= A [ii] [i] (y-evaluation, y);
5064	setCharacteristic (getCharacteristic());
5065	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
5066	if (alpha != gamma)
5067	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
5068	gamma, source, dest
5069	);
5070	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
5071	}
5072	else
5073	{
5074	A [ii] [i]= A [ii] [i] (y-evaluation, y);
5075	if (alpha != gamma)
5076	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
5077	gamma, source, dest
5078	);
5079	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
5080	}
5081	writeInMatrix (C, buf, ii + 1, 0);
5082	}
5083	if (GF)
5084	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
5085	}
5086
5087	if (GF)
5088	setCharacteristic(getCharacteristic());
5089	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
5090	NTLK= (NTLC)NTLN;
5091	transpose (NTLK, NTLK);
5092	kernel (NTLK, NTLK);
5093	transpose (NTLK, NTLK);
5094	NTLN *= NTLK;
5095	if (GF)
5096	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
5097
5098	if (NTLN.NumCols() == 1)
5099	{
5100	irreducible= true;
5101	break;
5102	}
5103	}
5104	}
5105	if (NTLN.NumCols() == 1)
5106	{
5107	irreducible= true;
5108	break;
5109	}
5110
5111	int * zeroOneVecs= extractZeroOneVecs (NTLN);
5112	bufF= F;
5113	result= extReconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN, info,
5114	evaluation
5115	);
5116	delete [] zeroOneVecs;
5117	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5118	{
5119	F= bufF;
5120	factors= bufFactors;
5121	delete [] A;
5122	return result;
5123	}
5124
5125	if (isReduced (NTLN))
5126	{
5127	int factorsFound= 0;
5128	bufF= F;
5129	int* factorsFoundIndex= new int [NTLN.NumCols()];
5130	for (long i= 0; i < NTLN.NumCols(); i++)
5131	factorsFoundIndex[i]= 0;
5132	if (l < degree (bufF) + 1 + degree (LCF))
5133	extReconstructionTry (result, bufF, bufFactors, l, factorsFound,
5134	factorsFoundIndex, NTLN, false, info, evaluation
5135	);
5136	else
5137	extReconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
5138	degree (LCF), factorsFound, factorsFoundIndex,
5139	NTLN, false, info, evaluation
5140	);
5141	if (NTLN.NumCols() == result.length())
5142	{
5143	delete [] A;
5144	delete [] factorsFoundIndex;
5145	return result;
5146	}
5147	delete [] factorsFoundIndex;
5148	}
5149	result= CFList();
5150	oldL= l;
5151	stepSize *= 2;
5152	l += stepSize;
5153	if (l > liftBound)
5154	{
5155	if (!hitBound)
5156	{
5157	l= liftBound;
5158	hitBound= true;
5159	}
5160	else
5161	break;
5162	}
5163	}
5164	if (irreducible)
5165	{
5166	delete [] A;
5167	Variable y= Variable (2);
5168	CanonicalForm tmp= F (y - evaluation, y);
5169	CFList source, dest;
5170	tmp= mapDown (tmp, info, source, dest);
5171	return CFList (tmp);
5172	}
5173	delete [] A;
5174	factors= bufFactors;
5175	return CFList();
5176	}
5177
5178	#ifdef HAVE_FLINT
5179	CFList
5180	furtherLiftingAndIncreasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int
5181	l, int liftBound, int d, int* bounds,
5182	nmod_mat_t FLINTN, CFList& diophant,
5183	CFMatrix& M, CFArray& Pi, CFArray& bufQ,
5184	const Variable& alpha
5185	)
5186	#else
5187	CFList
5188	furtherLiftingAndIncreasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int
5189	l, int liftBound, int d, int* bounds,
5190	mat_zz_p& NTLN, CFList& diophant,
5191	CFMatrix& M, CFArray& Pi, CFArray& bufQ,
5192	const Variable& alpha
5193	)
5194	#endif
5195	{
5196	CanonicalForm LCF= LC (F, 1);
5197	CFList result;
5198	bool irreducible= false;
5199	CFList bufFactors= factors;
5200	CFArray *A = new CFArray [bufFactors.length()];
5201	bool useOldQs= false;
5202	int extensionDeg= degree (getMipo (alpha));
5203	bool hitBound= false;
5204	int oldL= l;
5205	int stepSize= 8; //TODO choose better step size?
5206	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
5207	#ifdef HAVE_FLINT
5208	if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
5209	{
5210	nmod_mat_clear (FLINTN);
5211	nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
5212	for (long i=factors.length()-1; i >= 0; i--)
5213	nmod_mat_entry (FLINTN, i, i)= 1;
5214	}
5215	#else
5216	if (NTLN.NumRows() != factors.length()) //refined factors
5217	ident (NTLN, factors.length());
5218	#endif
5219	CFListIterator j;
5220	CFMatrix C;
5221	#ifdef HAVE_FLINT
5222	long rank;
5223	nmod_mat_t FLINTC, FLINTK, null;
5224	#else
5225	mat_zz_p* NTLC, NTLK;
5226	#endif
5227	CanonicalForm bufF, truncF;
5228	Variable y= F.mvar();
5229	while (l <= liftBound)
5230	{
5231	bufFactors.insert (LCF);
5232	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
5233	j= bufFactors;
5234	truncF= mod (F, power (y, l));
5235	if (useOldQs)
5236	{
5237	for (int i= 0; i < bufFactors.length(); i++, j++)
5238	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5239	bufQ[i]);
5240	}
5241	else
5242	{
5243	for (int i= 0; i < bufFactors.length(); i++, j++)
5244	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5245	}
5246	for (int i= 0; i < d; i++)
5247	{
5248	if (bounds [i] + 1 <= l/2)
5249	{
5250	int k= tmin (bounds [i] + 1, l/2);
5251	C= CFMatrix ((l - k)*extensionDeg, bufFactors.length());
5252	for (int ii= 0; ii < bufFactors.length(); ii++)
5253	{
5254	CFArray buf;
5255	if (A[ii].size() - 1 >= i)
5256	{
5257	buf= getCoeffs (A[ii] [i], k, alpha);
5258	writeInMatrix (C, buf, ii + 1, 0);
5259	}
5260	}
5261	#ifdef HAVE_FLINT
5262	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
5263	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5264	getCharacteristic());
5265	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5266	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5267	getCharacteristic());
5268	rank= nmod_mat_nullspace (null, FLINTK);
5269	nmod_mat_clear (FLINTK);
5270	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5271	nmod_mat_clear (FLINTC);
5272	nmod_mat_init_set (FLINTC, FLINTN);
5273	nmod_mat_clear (FLINTN);
5274	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5275	getCharacteristic());
5276	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5277
5278	nmod_mat_clear (FLINTC);
5279	nmod_mat_window_clear (FLINTK);
5280	nmod_mat_clear (null);
5281	#else
5282	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
5283	NTLK= (NTLC)NTLN;
5284	transpose (NTLK, NTLK);
5285	kernel (NTLK, NTLK);
5286	transpose (NTLK, NTLK);
5287	NTLN *= NTLK;
5288	#endif
5289	#ifdef HAVE_FLINT
5290	if (nmod_mat_ncols (FLINTN) == 1)
5291	#else
5292	if (NTLN.NumCols() == 1)
5293	#endif
5294	{
5295	irreducible= true;
5296	break;
5297	}
5298	}
5299	}
5300	#ifdef HAVE_FLINT
5301	if (nmod_mat_ncols (FLINTN) == 1)
5302	#else
5303	if (NTLN.NumCols() == 1)
5304	#endif
5305	{
5306	irreducible= true;
5307	break;
5308	}
5309
5310	#ifdef HAVE_FLINT
5311	int * zeroOneVecs= extractZeroOneVecs (FLINTN);
5312	#else
5313	int * zeroOneVecs= extractZeroOneVecs (NTLN);
5314	#endif
5315	CanonicalForm bufF= F;
5316	#ifdef HAVE_FLINT
5317	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, FLINTN);
5318	#else
5319	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
5320	#endif
5321	delete [] zeroOneVecs;
5322	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5323	{
5324	F= bufF;
5325	factors= bufFactors;
5326	delete [] A;
5327	return result;
5328	}
5329
5330	#ifdef HAVE_FLINT
5331	if (isReduced (FLINTN))
5332	#else
5333	if (isReduced (NTLN))
5334	#endif
5335	{
5336	int factorsFound= 0;
5337	bufF= F;
5338	#ifdef HAVE_FLINT
5339	int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
5340	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5341	#else
5342	int* factorsFoundIndex= new int [NTLN.NumCols()];
5343	for (long i= 0; i < NTLN.NumCols(); i++)
5344	#endif
5345	factorsFoundIndex[i]= 0;
5346	#ifdef HAVE_FLINT
5347	if (l < degree (bufF) + 1 + degree (LCF))
5348	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
5349	factorsFoundIndex, FLINTN, false
5350	);
5351	else
5352	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
5353	degree (LCF), factorsFound, factorsFoundIndex,
5354	FLINTN, false
5355	);
5356	if (nmod_mat_ncols (FLINTN) == result.length())
5357	#else
5358	if (l < degree (bufF) + 1 + degree (LCF))
5359	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
5360	factorsFoundIndex, NTLN, false
5361	);
5362	else
5363	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
5364	degree (LCF), factorsFound, factorsFoundIndex,
5365	NTLN, false
5366	);
5367	if (NTLN.NumCols() == result.length())
5368	#endif
5369	{
5370	delete [] A;
5371	delete [] factorsFoundIndex;
5372	return result;
5373	}
5374	delete [] factorsFoundIndex;
5375	}
5376	result= CFList();
5377	oldL= l;
5378	stepSize *= 2;
5379	l += stepSize;
5380	if (l > liftBound)
5381	{
5382	if (!hitBound)
5383	{
5384	l= liftBound;
5385	hitBound= true;
5386	}
5387	else
5388	break;
5389	}
5390	}
5391	if (irreducible)
5392	{
5393	delete [] A;
5394	return CFList (F);
5395	}
5396	delete [] A;
5397	factors= bufFactors;
5398	return CFList();
5399	}
5400
5401	void
5402	refineAndRestartLift (const CanonicalForm& F, const mat_zz_p& NTLN, int
5403	liftBound, int l, CFList& factors, CFMatrix& M, CFArray&
5404	Pi, CFList& diophant
5405	)
5406	{
5407	CFList bufFactors;
5408	Variable y= Variable (2);
5409	CanonicalForm LCF= LC (F, 1);
5410	CFListIterator iter;
5411	CanonicalForm buf;
5412	for (long i= 1; i <= NTLN.NumCols(); i++)
5413	{
5414	iter= factors;
5415	buf= 1;
5416	for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
5417	{
5418	if (!IsZero (NTLN (j,i)))
5419	buf= mulNTL (buf, mod (iter.getItem(), y));
5420	}
5421	bufFactors.append (buf);
5422	}
5423	factors= bufFactors;
5424	M= CFMatrix (liftBound, factors.length());
5425	Pi= CFArray();
5426	diophant= CFList();
5427	factors.insert (LCF);
5428	henselLift12 (F, factors, l, Pi, diophant, M);
5429	}
5430
5431	#ifdef HAVE_FLINT
5432	void
5433	refineAndRestartLift (const CanonicalForm& F, const nmod_mat_t FLINTN, int
5434	liftBound, int l, CFList& factors, CFMatrix& M, CFArray&
5435	Pi, CFList& diophant
5436	)
5437	{
5438	CFList bufFactors;
5439	Variable y= Variable (2);
5440	CanonicalForm LCF= LC (F, 1);
5441	CFListIterator iter;
5442	CanonicalForm buf;
5443	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5444	{
5445	iter= factors;
5446	buf= 1;
5447	for (long j= 0; j < nmod_mat_nrows (FLINTN); j++, iter++)
5448	{
5449	if (!(nmod_mat_entry (FLINTN,j,i) == 0))
5450	buf= mulNTL (buf, mod (iter.getItem(), y));
5451	}
5452	bufFactors.append (buf);
5453	}
5454	factors= bufFactors;
5455	M= CFMatrix (liftBound, factors.length());
5456	Pi= CFArray();
5457	diophant= CFList();
5458	factors.insert (LCF);
5459	henselLift12 (F, factors, l, Pi, diophant, M);
5460	}
5461	#endif
5462
5463	void
5464	refineAndRestartLift (const CanonicalForm& F, const mat_zz_pE& NTLN, int
5465	liftBound, int l, CFList& factors, CFMatrix& M, CFArray&
5466	Pi, CFList& diophant
5467	)
5468	{
5469	CFList bufFactors;
5470	Variable y= Variable (2);
5471	CanonicalForm LCF= LC (F, 1);
5472	CFListIterator iter;
5473	CanonicalForm buf;
5474	for (long i= 1; i <= NTLN.NumCols(); i++)
5475	{
5476	iter= factors;
5477	buf= 1;
5478	for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
5479	{
5480	if (!IsZero (NTLN (j,i)))
5481	buf= mulNTL (buf, mod (iter.getItem(), y));
5482	}
5483	bufFactors.append (buf);
5484	}
5485	factors= bufFactors;
5486	M= CFMatrix (liftBound, factors.length());
5487	Pi= CFArray();
5488	diophant= CFList();
5489	factors.insert (LCF);
5490	henselLift12 (F, factors, l, Pi, diophant, M);
5491	}
5492
5493	#ifdef HAVE_FLINT
5494	CFList
5495	earlyReconstructionAndLifting (const CanonicalForm& F, const nmod_mat_t N,
5496	CanonicalForm& bufF, CFList& factors, int& l,
5497	int& factorsFound, bool beenInThres, CFMatrix& M,
5498	CFArray& Pi, CFList& diophant, bool symmetric,
5499	const CanonicalForm& evaluation
5500	)
5501	#else
5502	CFList
5503	earlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_p& N,
5504	CanonicalForm& bufF, CFList& factors, int& l,
5505	int& factorsFound, bool beenInThres, CFMatrix& M,
5506	CFArray& Pi, CFList& diophant, bool symmetric,
5507	const CanonicalForm& evaluation
5508	)
5509	#endif
5510	{
5511	int sizeOfLiftPre;
5512	int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
5513
5514	Variable y= F.mvar();
5515	factorsFound= 0;
5516	CanonicalForm LCF= LC (F, 1);
5517	CFList result;
5518	int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
5519	#ifdef HAVE_FLINT
5520	nmod_mat_t FLINTN;
5521	nmod_mat_init_set (FLINTN, N);
5522	int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
5523	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5524	#else
5525	mat_zz_p NTLN= N;
5526	int * factorsFoundIndex= new int [NTLN.NumCols()];
5527	for (long i= 0; i < NTLN.NumCols(); i++)
5528	#endif
5529	factorsFoundIndex [i]= 0;
5530
5531	if (degree (F) + 1 > smallFactorDeg)
5532	{
5533	if (l < smallFactorDeg)
5534	{
5535	factors.insert (LCF);
5536	henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
5537	l= smallFactorDeg;
5538	}
5539	#ifdef HAVE_FLINT
5540	reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5541	factorsFoundIndex, FLINTN, beenInThres
5542	);
5543	if (result.length() == nmod_mat_ncols (FLINTN))
5544	{
5545	nmod_mat_clear (FLINTN);
5546	#else
5547	reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5548	factorsFoundIndex, NTLN, beenInThres
5549	);
5550	if (result.length() == NTLN.NumCols())
5551	{
5552	#endif
5553	delete [] liftPre;
5554	delete [] factorsFoundIndex;
5555	return result;
5556	}
5557	}
5558
5559	int i= sizeOfLiftPre - 1;
5560	int dummy= 1;
5561	if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
5562	{
5563	while (i > 0)
5564	{
5565	if (l < liftPre[i-1] + 1)
5566	{
5567	factors.insert (LCF);
5568	henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
5569	l= liftPre[i-1] + 1;
5570	}
5571	else
5572	{
5573	i--;
5574	if (i != 0)
5575	continue;
5576	}
5577	#ifdef HAVE_FLINT
5578	reconstructionTry (result, bufF, factors, l, factorsFound,
5579	factorsFoundIndex, FLINTN, beenInThres
5580	);
5581	if (result.length() == nmod_mat_ncols (FLINTN))
5582	{
5583	nmod_mat_clear (FLINTN);
5584	#else
5585	reconstructionTry (result, bufF, factors, l, factorsFound,
5586	factorsFoundIndex, NTLN, beenInThres
5587	);
5588	if (result.length() == NTLN.NumCols())
5589	{
5590	#endif
5591	delete [] liftPre;
5592	delete [] factorsFoundIndex;
5593	return result;
5594	}
5595	i--;
5596	}
5597	}
5598	else
5599	{
5600	i= 1;
5601	while ((degree (F,y)/4)*i + 4 <= smallFactorDeg)
5602	i++;
5603	while (i < 5)
5604	{
5605	dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4);
5606	if (l < dummy)
5607	{
5608	factors.insert (LCF);
5609	henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
5610	l= dummy;
5611	if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
5612	LC (F,1).inCoeffDomain() &&
5613	(degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
5614	{
5615	Variable x= Variable (1);
5616	CanonicalForm g, h, gg, hh, multiplier1, multiplier2, check1, check2;
5617	int m= degree (F)/4+1;
5618	g= factors.getFirst();
5619	h= factors.getLast();
5620	g= mod (g, power (y,m));
5621	h= mod (h, power (y,m));
5622	g= g (y-evaluation, y);
5623	h= h (y-evaluation, y);
5624	gg= mod (swapvar (g,x,y),power (x,m));
5625	gg= gg (y + evaluation, y);
5626	multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
5627	gg= div (gg, power (y,m));
5628	gg= gg*power (y,m);
5629	hh= mod (swapvar (h,x,y),power (x,m));
5630	hh= hh (y + evaluation, y);
5631	multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
5632	hh= div (hh, power (y,m));
5633	hh= hh*power (y,m);
5634	gg= multiplier1*gg+mod (factors.getLast(), power (y,m));
5635	hh= multiplier2*hh+mod (factors.getFirst(), power (y,m));
5636	check1= gg (y-evaluation,y);
5637	check2= hh (y-evaluation,y);
5638	check1= swapvar (check1, x, y);
5639	if (check1/Lc (check1) == check2/Lc (check2))
5640	{
5641	#ifdef HAVE_FLINT
5642	nmod_mat_clear (FLINTN);
5643	#endif
5644	result.append (gg);
5645	result.append (hh);
5646	delete [] liftPre;
5647	delete [] factorsFoundIndex;
5648	return result;
5649	}
5650	}
5651	}
5652	else
5653	{
5654	i++;
5655	if (i < 5)
5656	continue;
5657	}
5658	#ifdef HAVE_FLINT
5659	reconstructionTry (result, bufF, factors, l, factorsFound,
5660	factorsFoundIndex, FLINTN, beenInThres
5661	);
5662	if (result.length() == nmod_mat_ncols (FLINTN))
5663	{
5664	nmod_mat_clear (FLINTN);
5665	#else
5666	reconstructionTry (result, bufF, factors, l, factorsFound,
5667	factorsFoundIndex, NTLN, beenInThres
5668	);
5669	if (result.length() == NTLN.NumCols())
5670	{
5671	#endif
5672	delete [] liftPre;
5673	delete [] factorsFoundIndex;
5674	return result;
5675	}
5676	i++;
5677	}
5678	}
5679
5680	#ifdef HAVE_FLINT
5681	nmod_mat_clear (FLINTN);
5682	#endif
5683	delete [] liftPre;
5684	delete [] factorsFoundIndex;
5685	return result;
5686	}
5687
5688	CFList
5689	earlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_pE& N,
5690	CanonicalForm& bufF, CFList& factors, int& l,
5691	int& factorsFound, bool beenInThres, CFMatrix& M,
5692	CFArray& Pi, CFList& diophant, bool symmetric,
5693	const CanonicalForm& evaluation
5694	)
5695	{
5696	int sizeOfLiftPre;
5697	int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
5698	Variable y= F.mvar();
5699	factorsFound= 0;
5700	CanonicalForm LCF= LC (F, 1);
5701	CFList result;
5702	int smallFactorDeg= 11;
5703	mat_zz_pE NTLN= N;
5704	int * factorsFoundIndex= new int [NTLN.NumCols()];
5705	for (long i= 0; i < NTLN.NumCols(); i++)
5706	factorsFoundIndex [i]= 0;
5707
5708	if (degree (F) + 1 > smallFactorDeg)
5709	{
5710	if (l < smallFactorDeg)
5711	{
5712	factors.insert (LCF);
5713	henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
5714	l= smallFactorDeg;
5715	}
5716	reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5717	factorsFoundIndex, NTLN, beenInThres
5718	);
5719	if (result.length() == NTLN.NumCols())
5720	{
5721	delete [] liftPre;
5722	delete [] factorsFoundIndex;
5723	return result;
5724	}
5725	}
5726
5727	int i= sizeOfLiftPre - 1;
5728	int dummy= 1;
5729	if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
5730	{
5731	while (i > 0)
5732	{
5733	if (l < liftPre[i-1] + 1)
5734	{
5735	factors.insert (LCF);
5736	henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
5737	l= liftPre[i-1] + 1;
5738	}
5739	else
5740	{
5741	i--;
5742	if (i != 0)
5743	continue;
5744	}
5745	reconstructionTry (result, bufF, factors, l, factorsFound,
5746	factorsFoundIndex, NTLN, beenInThres
5747	);
5748	if (result.length() == NTLN.NumCols())
5749	{
5750	delete [] liftPre;
5751	delete [] factorsFoundIndex;
5752	return result;
5753	}
5754	i--;
5755	}
5756	}
5757	else
5758	{
5759	i= 1;
5760	while ((degree (F,y)/4)*i + 4 <= smallFactorDeg)
5761	i++;
5762	while (i < 5)
5763	{
5764	dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4);
5765	if (l < dummy)
5766	{
5767	factors.insert (LCF);
5768	henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
5769	l= dummy;
5770	if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
5771	LC (F,1).inCoeffDomain() &&
5772	(degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
5773	{
5774	Variable x= Variable (1);
5775	CanonicalForm g, h, gg, hh, multiplier1, multiplier2, check1, check2;
5776	int m= degree (F)/4+1;
5777	g= factors.getFirst();
5778	h= factors.getLast();
5779	g= mod (g, power (y,m));
5780	h= mod (h, power (y,m));
5781	g= g (y-evaluation, y);
5782	h= h (y-evaluation, y);
5783	gg= mod (swapvar (g,x,y),power (x,m));
5784	gg= gg (y + evaluation, y);
5785	multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
5786	gg= div (gg, power (y,m));
5787	gg= gg*power (y,m);
5788	hh= mod (swapvar (h,x,y),power (x,m));
5789	hh= hh (y + evaluation, y);
5790	multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
5791	hh= div (hh, power (y,m));
5792	hh= hh*power (y,m);
5793	gg= multiplier1*gg+mod (factors.getLast(), power (y,m));
5794	hh= multiplier2*hh+mod (factors.getFirst(), power (y,m));
5795	check1= gg (y-evaluation,y);
5796	check2= hh (y-evaluation,y);
5797	check1= swapvar (check1, x, y);
5798	if (check1/Lc (check1) == check2/Lc (check2))
5799	{
5800	result.append (gg);
5801	result.append (hh);
5802	delete [] liftPre;
5803	delete [] factorsFoundIndex;
5804	return result;
5805	}
5806	}
5807	}
5808	else
5809	{
5810	i++;
5811	if (i < 5)
5812	continue;
5813	}
5814	reconstructionTry (result, bufF, factors, l, factorsFound,
5815	factorsFoundIndex, NTLN, beenInThres
5816	);
5817	if (result.length() == NTLN.NumCols())
5818	{
5819	delete [] liftPre;
5820	delete [] factorsFoundIndex;
5821	return result;
5822	}
5823	i++;
5824	}
5825	}
5826
5827	delete [] liftPre;
5828	delete [] factorsFoundIndex;
5829	return result;
5830	}
5831
5832	//over field extension
5833	CFList
5834	extEarlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_p& N,
5835	CanonicalForm& bufF, CFList& factors, int& l,
5836	int& factorsFound, bool beenInThres, CFMatrix&
5837	M, CFArray& Pi, CFList& diophant, const
5838	ExtensionInfo& info, const CanonicalForm&
5839	evaluation
5840	)
5841	{
5842	int sizeOfLiftPre;
5843	int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
5844	Variable y= F.mvar();
5845	factorsFound= 0;
5846	CanonicalForm LCF= LC (F, 1);
5847	CFList result;
5848	int smallFactorDeg= 11;
5849	mat_zz_p NTLN= N;
5850	int * factorsFoundIndex= new int [NTLN.NumCols()];
5851	for (long i= 0; i < NTLN.NumCols(); i++)
5852	factorsFoundIndex [i]= 0;
5853
5854	if (degree (F) + 1 > smallFactorDeg)
5855	{
5856	if (l < smallFactorDeg)
5857	{
5858	factors.insert (LCF);
5859	henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
5860	l= smallFactorDeg;
5861	}
5862	extReconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5863	factorsFoundIndex, NTLN, beenInThres, info,
5864	evaluation
5865	);
5866	if (result.length() == NTLN.NumCols())
5867	{
5868	delete [] liftPre;
5869	delete [] factorsFoundIndex;
5870	return result;
5871	}
5872	}
5873
5874	int i= sizeOfLiftPre - 1;
5875	int dummy= 1;
5876	if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
5877	{
5878	while (i > 0)
5879	{
5880	if (l < liftPre[i-1] + 1)
5881	{
5882	factors.insert (LCF);
5883	henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
5884	l= liftPre[i-1] + 1;
5885	}
5886	else
5887	{
5888	i--;
5889	if (i != 0)
5890	continue;
5891	}
5892	extReconstructionTry (result, bufF, factors, l, factorsFound,
5893	factorsFoundIndex, NTLN, beenInThres, info,
5894	evaluation
5895	);
5896	if (result.length() == NTLN.NumCols())
5897	{
5898	delete [] liftPre;
5899	delete [] factorsFoundIndex;
5900	return result;
5901	}
5902	i--;
5903	}
5904	}
5905	else
5906	{
5907	i= 1;
5908	while ((degree (F,y)/4)*i + 4 <= smallFactorDeg)
5909	i++;
5910	while (i < 5)
5911	{
5912	dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4);
5913	if (l < dummy)
5914	{
5915	factors.insert (LCF);
5916	henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
5917	l= dummy;
5918	}
5919	else
5920	{
5921	i++;
5922	if (i < 5)
5923	continue;
5924	}
5925	extReconstructionTry (result, bufF, factors, l, factorsFound,
5926	factorsFoundIndex, NTLN, beenInThres, info,
5927	evaluation
5928	);
5929	if (result.length() == NTLN.NumCols())
5930	{
5931	delete [] liftPre;
5932	delete [] factorsFoundIndex;
5933	return result;
5934	}
5935	i++;
5936	}
5937	}
5938
5939	delete [] liftPre;
5940	delete [] factorsFoundIndex;
5941	return result;
5942	}
5943
5944	CFList
5945	sieveSmallFactors (const CanonicalForm& G, CFList& uniFactors, DegreePattern&
5946	degPat, CanonicalForm& H, CFList& diophant, CFArray& Pi,
5947	CFMatrix& M, bool& success, int d
5948	)
5949	{
5950	CanonicalForm F= G;
5951	CFList bufUniFactors= uniFactors;
5952	bufUniFactors.insert (LC (F, 1));
5953	int smallFactorDeg= d;
5954	DegreePattern degs= degPat;
5955	henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant, M);
5956	int adaptedLiftBound;
5957	success= false;
5958	int * factorsFoundIndex= new int [uniFactors.length()];
5959	for (int i= 0; i < uniFactors.length(); i++)
5960	factorsFoundIndex [i]= 0;
5961	CFList earlyFactors;
5962	earlyFactorDetection (earlyFactors, F, bufUniFactors, adaptedLiftBound,
5963	factorsFoundIndex, degs, success, smallFactorDeg);
5964	delete [] factorsFoundIndex;
5965	if (degs.getLength() == 1)
5966	{
5967	degPat= degs;
5968	return earlyFactors;
5969	}
5970	if (success)
5971	{
5972	H= F;
5973	return earlyFactors;
5974	}
5975	int sizeOldF= size (G);
5976	if (size (F) < sizeOldF)
5977	{
5978	H= F;
5979	success= true;
5980	return earlyFactors;
5981	}
5982	else
5983	{
5984	uniFactors= bufUniFactors;
5985	return CFList();
5986	}
5987	}
5988
5989	CFList
5990	extSieveSmallFactors (const CanonicalForm& G, CFList& uniFactors, DegreePattern&
5991	degPat, CanonicalForm& H, CFList& diophant, CFArray& Pi,
5992	CFMatrix& M, bool& success, int d, const CanonicalForm&
5993	evaluation, const ExtensionInfo& info
5994	)
5995	{
5996	CanonicalForm F= G;
5997	CFList bufUniFactors= uniFactors;
5998	bufUniFactors.insert (LC (F, 1));
5999	int smallFactorDeg= d;
6000	DegreePattern degs= degPat;
6001	henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant, M);
6002	int adaptedLiftBound;
6003	success= false;
6004	int * factorsFoundIndex= new int [uniFactors.length()];
6005	for (int i= 0; i < uniFactors.length(); i++)
6006	factorsFoundIndex [i]= 0;
6007	CFList earlyFactors;
6008	extEarlyFactorDetection (earlyFactors, F, bufUniFactors, adaptedLiftBound,
6009	factorsFoundIndex, degs, success, info, evaluation,
6010	smallFactorDeg);
6011	delete [] factorsFoundIndex;
6012	if (degs.getLength() == 1)
6013	{
6014	degPat= degs;
6015	return earlyFactors;
6016	}
6017	if (success)
6018	{
6019	H= F;
6020	return earlyFactors;
6021	}
6022	Variable y= F.mvar();
6023	int sizeOldF= size (G);
6024	if (size (F) < sizeOldF)
6025	{
6026	H= F;
6027	success= true;
6028	return earlyFactors;
6029	}
6030	else
6031	{
6032	uniFactors= bufUniFactors;
6033	return CFList();
6034	}
6035	}
6036
6037	CFList
6038	henselLiftAndLatticeRecombi (const CanonicalForm& G, const CFList& uniFactors,
6039	const Variable& alpha, const DegreePattern& degPat,
6040	bool symmetric, const CanonicalForm& evaluation
6041	)
6042	{
6043	DegreePattern degs= degPat;
6044	CanonicalForm F= G;
6045	CanonicalForm LCF= LC (F, 1);
6046	Variable y= F.mvar();
6047	Variable x= Variable (1);
6048	int d;
6049	bool isIrreducible= false;
6050	int* bounds= computeBounds (F, d, isIrreducible);
6051	if (isIrreducible)
6052	{
6053	delete [] bounds;
6054	return CFList (G);
6055	}
6056	int minBound= bounds[0];
6057	for (int i= 1; i < d; i++)
6058	{
6059	if (bounds[i] != 0)
6060	minBound= tmin (minBound, bounds[i]);
6061	}
6062
6063	CFList bufUniFactors= uniFactors;
6064	CFArray Pi;
6065	CFList diophant;
6066	int liftBound= 2*totaldegree (F) - 1;
6067	CFMatrix M= CFMatrix (liftBound, bufUniFactors.length());
6068
6069	CFList smallFactors;
6070	CanonicalForm H;
6071	bool success= false;
6072	smallFactors= sieveSmallFactors (F, bufUniFactors, degs, H, diophant, Pi, M,
6073	success, minBound + 1
6074	);
6075
6076	if (smallFactors.length() > 0)
6077	{
6078	if (smallFactors.length() == 1)
6079	{
6080	if (smallFactors.getFirst() == F)
6081	{
6082	delete [] bounds;
6083	return CFList (G);
6084	}
6085	}
6086	if (degs.getLength() <= 1)
6087	{
6088	delete [] bounds;
6089	return smallFactors;
6090	}
6091	}
6092
6093	int index;
6094	CanonicalForm tmp1, tmp2;
6095	for (CFListIterator i= smallFactors; i.hasItem(); i++)
6096	{
6097	index= 1;
6098	tmp1= mod (i.getItem(),y);
6099	tmp1 /= Lc (tmp1);
6100	for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
6101	{
6102	tmp2= mod (j.getItem(), y);
6103	tmp2 /= Lc (tmp2);
6104	if (tmp1 == tmp2)
6105	{
6106	index++;
6107	j.remove(index);
6108	break;
6109	}
6110	}
6111	}
6112
6113	if (bufUniFactors.isEmpty())
6114	{
6115	delete [] bounds;
6116	return smallFactors;
6117	}
6118
6119	if (success)
6120	{
6121	F= H;
6122	delete [] bounds;
6123	bounds= computeBounds (F, d, isIrreducible);
6124	if (isIrreducible)
6125	{
6126	smallFactors.append (F);
6127	delete [] bounds;
6128	return smallFactors;
6129	}
6130	LCF= LC (F, 1);
6131
6132	minBound= bounds[0];
6133	for (int i= 1; i < d; i++)
6134	{
6135	if (bounds[i] != 0)
6136	minBound= tmin (minBound, bounds[i]);
6137	}
6138	Pi= CFArray();
6139	diophant= CFList();
6140	liftBound= 2*totaldegree (F) - 1;
6141	M= CFMatrix (liftBound, bufUniFactors.length());
6142	DegreePattern bufDegs= DegreePattern (bufUniFactors);
6143	degs.intersect (bufDegs);
6144	degs.refine();
6145	if (degs.getLength() <= 1)
6146	{
6147	smallFactors.append (F);
6148	delete [] bounds;
6149	return smallFactors;
6150	}
6151	}
6152
6153	bool reduceFq2Fp= (degree (F) > getCharacteristic());
6154	bufUniFactors.insert (LCF);
6155	int l= 1;
6156
6157	#ifdef HAVE_FLINT
6158	nmod_mat_t FLINTN;
6159	#else
6160	zz_p::init (getCharacteristic());
6161	mat_zz_p NTLN;
6162	#endif
6163
6164	if (alpha.level() != 1)
6165	{
6166	zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
6167	zz_pE::init (NTLMipo);
6168	}
6169	mat_zz_pE NTLNe;
6170	if (alpha.level() == 1)
6171	{
6172	#ifdef HAVE_FLINT
6173	nmod_mat_init (FLINTN, bufUniFactors.length()-1, bufUniFactors.length()-1, getCharacteristic());
6174	for (long i= bufUniFactors.length()-2; i >= 0; i--)
6175	nmod_mat_entry (FLINTN, i, i)= 1;
6176	#else
6177	ident (NTLN, bufUniFactors.length() - 1);
6178	#endif
6179	}
6180	else
6181	{
6182	if (reduceFq2Fp)
6183	#ifdef HAVE_FLINT
6184	{
6185	nmod_mat_init (FLINTN, bufUniFactors.length()-1, bufUniFactors.length()-1, getCharacteristic());
6186	for (long i= bufUniFactors.length()-2; i >= 0; i--)
6187	nmod_mat_entry (FLINTN, i, i)= 1;
6188	}
6189	#else
6190	ident (NTLN, bufUniFactors.length() - 1);
6191	#endif
6192	else
6193	ident (NTLNe, bufUniFactors.length() - 1);
6194	}
6195	bool irreducible= false;
6196	CFArray bufQ= CFArray (bufUniFactors.length() - 1);
6197
6198	int oldL;
6199	if (success)
6200	{
6201	int start= 0;
6202	if (alpha.level() == 1)
6203	oldL= liftAndComputeLattice (F, bounds, d, start, liftBound, minBound,
6204	#ifdef HAVE_FLINT
6205	bufUniFactors, FLINTN, diophant, M, Pi, bufQ,
6206	#else
6207	bufUniFactors, NTLN, diophant, M, Pi, bufQ,
6208	#endif
6209	irreducible
6210	);
6211	else
6212	{
6213	if (reduceFq2Fp)
6214	oldL= liftAndComputeLatticeFq2Fp (F, bounds, d, start, liftBound,
6215	#ifdef HAVE_FLINT
6216	minBound, bufUniFactors, FLINTN,
6217	#else
6218	minBound, bufUniFactors, NTLN,
6219	#endif
6220	diophant, M, Pi, bufQ, irreducible,
6221	alpha
6222	);
6223	else
6224	oldL= liftAndComputeLattice (F, bounds, d, start, liftBound, minBound,
6225	bufUniFactors, NTLNe, diophant, M, Pi, bufQ,
6226	irreducible
6227	);
6228	}
6229	}
6230	else
6231	{
6232	if (alpha.level() == 1)
6233	{
6234	oldL= liftAndComputeLattice (F, bounds, d, minBound + 1, liftBound,
6235	#ifdef HAVE_FLINT
6236	minBound, bufUniFactors, FLINTN, diophant, M,
6237	#else
6238	minBound, bufUniFactors, NTLN, diophant, M,
6239	#endif
6240	Pi, bufQ, irreducible
6241	);
6242	}
6243	else
6244	{
6245	if (reduceFq2Fp)
6246	oldL= liftAndComputeLatticeFq2Fp (F, bounds, d, minBound + 1,
6247	liftBound, minBound, bufUniFactors,
6248	#ifdef HAVE_FLINT
6249	FLINTN, diophant, M, Pi, bufQ,
6250	#else
6251	NTLN, diophant, M, Pi, bufQ,
6252	#endif
6253	irreducible, alpha
6254	);
6255	else
6256	oldL= liftAndComputeLattice (F, bounds, d, minBound + 1, liftBound,
6257	minBound, bufUniFactors, NTLNe, diophant,
6258	M, Pi, bufQ, irreducible
6259	);
6260	}
6261	}
6262
6263	bufUniFactors.removeFirst();
6264	if (oldL > liftBound)
6265	{
6266	#ifdef HAVE_FLINT
6267	nmod_mat_clear (FLINTN);
6268	#endif
6269	delete [] bounds;
6270	return Union (smallFactors,
6271	factorRecombination (bufUniFactors, F,
6272	power (y, degree (F) + 1 + degree (LCF)),
6273	degs, 1, bufUniFactors.length()/2
6274	)
6275	);
6276	}
6277
6278	l= oldL;
6279	if (irreducible)
6280	{
6281	#ifdef HAVE_FLINT
6282	nmod_mat_clear (FLINTN);
6283	#endif
6284	delete [] bounds;
6285	return Union (CFList (F), smallFactors);
6286	}
6287
6288	CanonicalForm yToL= power (y,l);
6289
6290	CFList result;
6291	if (l >= degree (F) + 1)
6292	{
6293	int * factorsFoundIndex;
6294	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
6295	{
6296	#ifdef HAVE_FLINT
6297	factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
6298	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
6299	#else
6300	factorsFoundIndex= new int [NTLN.NumCols()];
6301	for (long i= 0; i < NTLN.NumCols(); i++)
6302	#endif
6303	factorsFoundIndex[i]= 0;
6304	}
6305	else
6306	{
6307	factorsFoundIndex= new int [NTLNe.NumCols()];
6308	for (long i= 0; i < NTLNe.NumCols(); i++)
6309	factorsFoundIndex[i]= 0;
6310	}
6311	int factorsFound= 0;
6312	CanonicalForm bufF= F;
6313	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
6314	reconstructionTry (result, bufF, bufUniFactors, degree (F) + 1,
6315	#ifdef HAVE_FLINT
6316	factorsFound, factorsFoundIndex, FLINTN, false
6317	#else
6318	factorsFound, factorsFoundIndex, NTLN, false
6319	#endif
6320	);
6321	else
6322	reconstructionTry (result, bufF, bufUniFactors, degree (F) + 1,
6323	factorsFound, factorsFoundIndex, NTLNe, false
6324	);
6325	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
6326	{
6327	#ifdef HAVE_FLINT
6328	if (result.length() == nmod_mat_ncols (FLINTN))
6329	{
6330	nmod_mat_clear (FLINTN);
6331	#else
6332	if (result.length() == NTLN.NumCols())
6333	{
6334	#endif
6335	delete [] factorsFoundIndex;
6336	delete [] bounds;
6337	return Union (result, smallFactors);
6338	}
6339	}
6340	else
6341	{
6342	if (result.length() == NTLNe.NumCols())
6343	{
6344	#ifdef HAVE_FLINT
6345	nmod_mat_clear (FLINTN);
6346	#endif
6347	delete [] factorsFoundIndex;
6348	delete [] bounds;
6349	return Union (result, smallFactors);
6350	}
6351	}
6352	delete [] factorsFoundIndex;
6353	}
6354	if (l >= liftBound)
6355	{
6356	int * factorsFoundIndex;
6357	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
6358	{
6359	#ifdef HAVE_FLINT
6360	factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
6361	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
6362	#else
6363	factorsFoundIndex= new int [NTLN.NumCols()];
6364	for (long i= 0; i < NTLN.NumCols(); i++)
6365	#endif
6366	factorsFoundIndex[i]= 0;
6367	}
6368	else
6369	{
6370	factorsFoundIndex= new int [NTLNe.NumCols()];
6371	for (long i= 0; i < NTLNe.NumCols(); i++)
6372	factorsFoundIndex[i]= 0;
6373	}
6374	CanonicalForm bufF= F;
6375	int factorsFound= 0;
6376	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
6377	reconstructionTry (result, bufF, bufUniFactors, degree (F) + 1 + degree
6378	#ifdef HAVE_FLINT
6379	(LCF), factorsFound, factorsFoundIndex, FLINTN, false
6380	#else
6381	(LCF), factorsFound, factorsFoundIndex, NTLN, false
6382	#endif
6383	);
6384	else
6385	reconstructionTry (result, bufF, bufUniFactors, degree (F) + 1 + degree
6386	(LCF), factorsFound, factorsFoundIndex, NTLNe, false
6387	);
6388	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
6389	{
6390	#ifdef HAVE_FLINT
6391	if (result.length() == nmod_mat_ncols(FLINTN))
6392	{
6393	nmod_mat_clear (FLINTN);
6394	#else
6395	if (result.length() == NTLN.NumCols())
6396	{
6397	#endif
6398	delete [] factorsFoundIndex;
6399	delete [] bounds;
6400	return Union (result, smallFactors);
6401	}
6402	}
6403	else
6404	{
6405	if (result.length() == NTLNe.NumCols())
6406	{
6407	#ifdef HAVE_FLINT
6408	nmod_mat_clear (FLINTN);
6409	#endif
6410	delete [] factorsFoundIndex;
6411	delete [] bounds;
6412	return Union (result, smallFactors);
6413	}
6414	}
6415	delete [] factorsFoundIndex;
6416	}
6417
6418	result= CFList();
6419	bool beenInThres= false;
6420	int thres= 100;
6421	if (l <= thres)
6422	{
6423	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
6424	{
6425	#ifdef HAVE_FLINT
6426	if (nmod_mat_ncols (FLINTN) < bufUniFactors.length())
6427	{
6428	refineAndRestartLift (F, FLINTN, liftBound, l, bufUniFactors, M, Pi,
6429	#else
6430	if (NTLN.NumCols() < bufUniFactors.length())
6431	{
6432	refineAndRestartLift (F, NTLN, liftBound, l, bufUniFactors, M, Pi,
6433	#endif
6434	diophant
6435	);
6436	beenInThres= true;
6437	}
6438	}
6439	else
6440	{
6441	if (NTLNe.NumCols() < bufUniFactors.length())
6442	{
6443	refineAndRestartLift (F, NTLNe, liftBound, l, bufUniFactors, M, Pi,
6444	diophant
6445	);
6446	beenInThres= true;
6447	}
6448	}
6449	}
6450
6451	CanonicalForm bufF= F;
6452	int factorsFound= 0;
6453	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
6454	{
6455	#ifdef HAVE_FLINT
6456	result= earlyReconstructionAndLifting (F, FLINTN, bufF, bufUniFactors, l,
6457	#else
6458	result= earlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l,
6459	#endif
6460	factorsFound, beenInThres, M, Pi,
6461	diophant, symmetric, evaluation
6462	);
6463
6464	#ifdef HAVE_FLINT
6465	if (result.length() == nmod_mat_ncols (FLINTN))
6466	{
6467	nmod_mat_clear (FLINTN);
6468	#else
6469	if (result.length() == NTLN.NumCols())
6470	{
6471	#endif
6472	delete [] bounds;
6473	return Union (result, smallFactors);
6474	}
6475	}
6476	else
6477	{
6478	result= earlyReconstructionAndLifting (F, NTLNe, bufF, bufUniFactors, l,
6479	factorsFound, beenInThres, M, Pi,
6480	diophant, symmetric, evaluation
6481	);
6482
6483	if (result.length() == NTLNe.NumCols())
6484	{
6485	#ifdef HAVE_FLINT
6486	nmod_mat_clear (FLINTN);
6487	#endif
6488	delete [] bounds;
6489	return Union (result, smallFactors);
6490	}
6491	}
6492
6493	if (result.length() > 0)
6494	{
6495	if (beenInThres)
6496	{
6497	int index;
6498	for (CFListIterator i= result; i.hasItem(); i++)
6499	{
6500	index= 1;
6501	tmp1= mod (i.getItem(), y);
6502	tmp1 /= Lc (tmp1);
6503	for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
6504	{
6505	tmp2= mod (j.getItem(), y);
6506	tmp2 /= Lc (tmp2);
6507	if (tmp1 == tmp2)
6508	{
6509	index++;
6510	j.remove(index);
6511	break;
6512	}
6513	}
6514	}
6515	}
6516	else
6517	{
6518	int * zeroOne;
6519	long numCols, numRows;
6520	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
6521	{
6522	#ifdef HAVE_FLINT
6523	numCols= nmod_mat_ncols (FLINTN);
6524	numRows= nmod_mat_nrows (FLINTN);
6525	zeroOne= extractZeroOneVecs (FLINTN);
6526	#else
6527	numCols= NTLN.NumCols();
6528	numRows= NTLN.NumRows();
6529	zeroOne= extractZeroOneVecs (NTLN);
6530	#endif
6531	}
6532	else
6533	{
6534	numCols= NTLNe.NumCols();
6535	numRows= NTLNe.NumRows();
6536	zeroOne= extractZeroOneVecs (NTLNe);
6537	}
6538	CFList bufBufUniFactors= bufUniFactors;
6539	CFListIterator iter, iter2;
6540	CanonicalForm buf;
6541	CFList factorsConsidered;
6542	CanonicalForm tmp;
6543	for (int i= 0; i < numCols; i++)
6544	{
6545	if (zeroOne [i] == 0)
6546	continue;
6547	iter= bufUniFactors;
6548	buf= 1;
6549	factorsConsidered= CFList();
6550	for (int j= 0; j < numRows; j++, iter++)
6551	{
6552	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
6553	{
6554	#ifdef HAVE_FLINT
6555	if (!(nmod_mat_entry (FLINTN, j,i) == 0))
6556	#else
6557	if (!IsZero (NTLN (j + 1,i + 1)))
6558	#endif
6559	{
6560	factorsConsidered.append (iter.getItem());
6561	buf *= mod (iter.getItem(), y);
6562	}
6563	}
6564	else
6565	{
6566	if (!IsZero (NTLNe (j + 1,i + 1)))
6567	{
6568	factorsConsidered.append (iter.getItem());
6569	buf *= mod (iter.getItem(), y);
6570	}
6571	}
6572	}
6573	buf /= Lc (buf);
6574	for (iter2= result; iter2.hasItem(); iter2++)
6575	{
6576	tmp= mod (iter2.getItem(), y);
6577	tmp /= Lc (tmp);
6578	if (tmp == buf)
6579	{
6580	bufBufUniFactors= Difference (bufBufUniFactors, factorsConsidered);
6581	break;
6582	}
6583	}
6584	}
6585	bufUniFactors= bufBufUniFactors;
6586	delete [] zeroOne;
6587	}
6588
6589	int oldNumCols;
6590	CFList resultBufF;
6591	irreducible= false;
6592
6593	if (alpha.level() == 1)
6594	{
6595	#ifdef HAVE_FLINT
6596	oldNumCols= nmod_mat_ncols (FLINTN);
6597	#else
6598	oldNumCols= NTLN.NumCols();
6599	#endif
6600	resultBufF= increasePrecision (bufF, bufUniFactors, factorsFound,
6601	oldNumCols, oldL, l
6602	);
6603	}
6604	else
6605	{
6606	if (reduceFq2Fp)
6607	{
6608	#ifdef HAVE_FLINT
6609	oldNumCols= nmod_mat_ncols (FLINTN);
6610	#else
6611	oldNumCols= NTLN.NumCols();
6612	#endif
6613
6614	resultBufF= increasePrecisionFq2Fp (bufF, bufUniFactors, factorsFound,
6615	oldNumCols, oldL, alpha, l
6616	);
6617	}
6618	else
6619	{
6620	oldNumCols= NTLNe.NumCols();
6621
6622	resultBufF= increasePrecision (bufF, bufUniFactors, factorsFound,
6623	oldNumCols, oldL, alpha, l
6624	);
6625	}
6626	}
6627
6628	if (bufUniFactors.isEmpty() \|\| degree (bufF) <= 0)
6629	{
6630	#ifdef HAVE_FLINT
6631	nmod_mat_clear (FLINTN);
6632	#endif
6633	delete [] bounds;
6634	result= Union (resultBufF, result);
6635	return Union (result, smallFactors);
6636	}
6637
6638	for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
6639	i.getItem()= mod (i.getItem(), y);
6640
6641	result= Union (result, resultBufF);
6642	result= Union (result, smallFactors);
6643	delete [] bounds;
6644	DegreePattern bufDegs= DegreePattern (bufUniFactors);
6645	degs.intersect (bufDegs);
6646	degs.refine();
6647	if (degs.getLength() == 1 \|\| bufUniFactors.length() == 1)
6648	{
6649	#ifdef HAVE_FLINT
6650	nmod_mat_clear (FLINTN);
6651	#endif
6652	result.append (bufF);
6653	return result;
6654	}
6655	#ifdef HAVE_FLINT
6656	nmod_mat_clear (FLINTN);
6657	#endif
6658	return Union (result, henselLiftAndLatticeRecombi (bufF, bufUniFactors,
6659	alpha, degs, symmetric,
6660	evaluation
6661	)
6662	);
6663	}
6664
6665	if (l < liftBound)
6666	{
6667	if (alpha.level() == 1)
6668	{
6669	result=increasePrecision (F, bufUniFactors, oldL, l, d, bounds, bufQ,
6670	#ifdef HAVE_FLINT
6671	FLINTN
6672	#else
6673	NTLN
6674	#endif
6675	);
6676	}
6677	else
6678	{
6679	if (reduceFq2Fp)
6680	{
6681	result=increasePrecisionFq2Fp (F, bufUniFactors, oldL, l, d, bounds,
6682	#ifdef HAVE_FLINT
6683	bufQ, FLINTN, alpha
6684	#else
6685	bufQ, NTLN, alpha
6686	#endif
6687	);
6688	}
6689	else
6690	{
6691	result=increasePrecision (F, bufUniFactors, oldL, l, d, bounds, bufQ,
6692	NTLNe
6693	);
6694	}
6695	}
6696	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
6697	{
6698	#ifdef HAVE_FLINT
6699	if (result.length()== nmod_mat_ncols (FLINTN))
6700	{
6701	nmod_mat_clear (FLINTN);
6702	#else
6703	if (result.length()== NTLN.NumCols())
6704	{
6705	#endif
6706	delete [] bounds;
6707	result= Union (result, smallFactors);
6708	return result;
6709	}
6710	}
6711	else
6712	{
6713	if (result.length()== NTLNe.NumCols())
6714	{
6715	#ifdef HAVE_FLINT
6716	nmod_mat_clear (FLINTN);
6717	#endif
6718	delete [] bounds;
6719	result= Union (result, smallFactors);
6720	return result;
6721	}
6722	}
6723
6724	if (result.isEmpty())
6725	{
6726	if (alpha.level() == 1)
6727	result= furtherLiftingAndIncreasePrecision (F,bufUniFactors, l,
6728	#ifdef HAVE_FLINT
6729	liftBound,d,bounds,FLINTN,
6730	#else
6731	liftBound, d, bounds, NTLN,
6732	#endif
6733	diophant, M, Pi, bufQ
6734	);
6735	else
6736	{
6737	if (reduceFq2Fp)
6738	result= furtherLiftingAndIncreasePrecisionFq2Fp (F,bufUniFactors, l,
6739	liftBound, d, bounds,
6740	#ifdef HAVE_FLINT
6741	FLINTN, diophant, M,
6742	#else
6743	NTLN, diophant, M,
6744	#endif
6745	Pi, bufQ, alpha
6746	);
6747	else
6748	result= furtherLiftingAndIncreasePrecision (F,bufUniFactors, l,
6749	liftBound, d, bounds,
6750	NTLNe, diophant, M,
6751	Pi, bufQ
6752	);
6753	}
6754
6755	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
6756	{
6757	#ifdef HAVE_FLINT
6758	if (result.length() == nmod_mat_ncols (FLINTN))
6759	{
6760	nmod_mat_clear (FLINTN);
6761	#else
6762	if (result.length() == NTLN.NumCols())
6763	{
6764	#endif
6765	delete [] bounds;
6766	result= Union (result, smallFactors);
6767	return result;
6768	}
6769	}
6770	else
6771	{
6772	if (result.length() == NTLNe.NumCols())
6773	{
6774	#ifdef HAVE_FLINT
6775	nmod_mat_clear (FLINTN);
6776	#endif
6777	delete [] bounds;
6778	result= Union (result, smallFactors);
6779	return result;
6780	}
6781	}
6782	}
6783	}
6784
6785	DEBOUTLN (cerr, "lattice recombination failed");
6786
6787	DegreePattern bufDegs= DegreePattern (bufUniFactors);
6788	degs.intersect (bufDegs);
6789	degs.refine();
6790
6791	delete [] bounds;
6792	bounds= computeBounds (F, d, isIrreducible);
6793	#ifdef HAVE_FLINT
6794	nmod_mat_clear (FLINTN);
6795	#endif
6796	if (isIrreducible)
6797	{
6798	delete [] bounds;
6799	result= Union (result, smallFactors);
6800	result.append (F);
6801	return result;
6802	}
6803	minBound= bounds[0];
6804	for (int i= 1; i < d; i++)
6805	{
6806	if (bounds[i] != 0)
6807	minBound= tmin (minBound, bounds[i]);
6808	}
6809
6810	if (minBound > 16 \|\| result.length() == 0)
6811	{
6812	result= Union (result, smallFactors);
6813	CanonicalForm MODl= power (y, degree (F) + 1 + degree (LC (F, 1)));
6814	delete [] bounds;
6815	return Union (result, factorRecombination (bufUniFactors, F, MODl, degs, 1,
6816	bufUniFactors.length()/2
6817	)
6818	);
6819	}
6820	else
6821	{
6822	result= Union (result, smallFactors);
6823	for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
6824	i.getItem()= mod (i.getItem(), y);
6825	delete [] bounds;
6826	return Union (result, henselLiftAndLatticeRecombi (F, bufUniFactors, alpha,
6827	degs,symmetric, evaluation
6828	)
6829	);
6830	}
6831	}
6832
6833	ExtensionInfo
6834	init4ext (const ExtensionInfo& info, const CanonicalForm& evaluation,
6835	int& degMipo
6836	)
6837	{
6838	bool GF= (CFFactory::gettype() == GaloisFieldDomain);
6839	Variable alpha= info.getAlpha();
6840	if (GF)
6841	{
6842	degMipo= getGFDegree();
6843	CanonicalForm GFMipo= gf_mipo;
6844	setCharacteristic (getCharacteristic());
6845	GFMipo.mapinto();
6846	alpha= rootOf (GFMipo);
6847	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
6848	}
6849	else
6850	{
6851	alpha= info.getAlpha();
6852	degMipo= degree (getMipo (alpha));
6853	}
6854
6855	Variable gamma;
6856	CanonicalForm primElemAlpha, imPrimElemAlpha;
6857	if ((!GF && evaluation != alpha) \|\| (GF && evaluation != getGFGenerator()))
6858	{
6859	CanonicalForm bufEvaluation;
6860	if (GF)
6861	{
6862	setCharacteristic (getCharacteristic());
6863	bufEvaluation= GF2FalphaRep (evaluation, alpha);
6864	}
6865	else
6866	bufEvaluation= evaluation;
6867	CanonicalForm mipo= findMinPoly (bufEvaluation, alpha);
6868	gamma= rootOf (mipo);
6869	Variable V_buf;
6870	bool fail= false;
6871	primElemAlpha= primitiveElement (alpha, V_buf, fail);
6872	imPrimElemAlpha= map (primElemAlpha, alpha, bufEvaluation, gamma);
6873
6874	if (GF)
6875	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
6876	}
6877	else
6878	gamma= alpha;
6879	ExtensionInfo info2= ExtensionInfo (alpha, gamma, primElemAlpha,
6880	imPrimElemAlpha, 1, info.getGFName(), true
6881	);
6882
6883	return info2;
6884	}
6885
6886	CFList
6887	extHenselLiftAndLatticeRecombi(const CanonicalForm& G, const CFList& uniFactors,
6888	const ExtensionInfo& extInfo, const
6889	DegreePattern& degPat, const CanonicalForm& eval
6890	)
6891	{
6892	CanonicalForm evaluation= eval;
6893	ExtensionInfo info= extInfo;
6894	Variable alpha;
6895	DegreePattern degs= degPat;
6896	CanonicalForm F= G;
6897	Variable x= Variable (1);
6898	Variable y= F.mvar();
6899	CFList bufUniFactors= uniFactors;
6900
6901
6902	int degMipo;
6903	ExtensionInfo info2= init4ext (info, evaluation, degMipo);
6904
6905	CFList source, dest;
6906	CanonicalForm LCF= LC (F, 1);
6907
6908	int d;
6909	bool isIrreducible= false;
6910	int* bounds= computeBounds (F, d, isIrreducible);
6911	if (isIrreducible)
6912	{
6913	delete [] bounds;
6914	CFList source, dest;
6915	CanonicalForm tmp= G (y - evaluation, y);
6916	tmp= mapDown (tmp, info, source, dest);
6917	return CFList (tmp);
6918	}
6919	int minBound= bounds[0];
6920	for (int i= 1; i < d; i++)
6921	{
6922	if (bounds[i] != 0)
6923	minBound= tmin (minBound, bounds[i]);
6924	}
6925
6926
6927	CFArray Pi;
6928	CFList diophant;
6929	int liftBound= tmax ((2*totaldegree (F) - 1)/degMipo + 1, degree (F) + 1 +
6930	degree (LC (F, 1)));
6931	CFMatrix M= CFMatrix (liftBound, bufUniFactors.length());
6932
6933	CFList smallFactors;
6934	CanonicalForm H;
6935	bool success= false;
6936	smallFactors= extSieveSmallFactors (F, bufUniFactors, degs, H, diophant, Pi,
6937	M, success, minBound + 1, evaluation, info
6938	);
6939
6940	if (smallFactors.length() > 0)
6941	{
6942	if (smallFactors.length() == 1)
6943	{
6944	if (smallFactors.getFirst() == F)
6945	{
6946	delete [] bounds;
6947	CFList source, dest;
6948	CanonicalForm tmp= G (y - evaluation, y);
6949	tmp= mapDown (tmp, info, source, dest);
6950	return CFList (tmp);
6951	}
6952	}
6953	if (degs.getLength() <= 1)
6954	{
6955	delete [] bounds;
6956	return smallFactors;
6957	}
6958	}
6959
6960	int index;
6961	CanonicalForm tmp1, tmp2;
6962	for (CFListIterator i= smallFactors; i.hasItem(); i++)
6963	{
6964	index= 1;
6965	tmp1= mod (i.getItem(), y - evaluation);
6966	tmp1 /= Lc (tmp1);
6967	for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
6968	{
6969	tmp2= mod (j.getItem(), y);
6970	tmp2 /= Lc (tmp2);
6971	if (tmp1 == tmp2)
6972	{
6973	index++;
6974	j.remove(index);
6975	break;
6976	}
6977	}
6978	}
6979
6980	if (bufUniFactors.isEmpty())
6981	{
6982	delete [] bounds;
6983	return smallFactors;
6984	}
6985
6986	if (success)
6987	{
6988	F= H;
6989	delete [] bounds;
6990	bounds= computeBounds (F, d, isIrreducible);
6991	if (isIrreducible)
6992	{
6993	delete [] bounds;
6994	CFList source, dest;
6995	CanonicalForm tmp= F (y - evaluation, y);
6996	tmp= mapDown (tmp, info, source, dest);
6997	smallFactors.append (tmp);
6998	return smallFactors;
6999	}
7000	LCF= LC (F, 1);
7001
7002	minBound= bounds[0];
7003	for (int i= 1; i < d; i++)
7004	{
7005	if (bounds[i] != 0)
7006	minBound= tmin (minBound, bounds[i]);
7007	}
7008	Pi= CFArray();
7009	diophant= CFList();
7010	liftBound=tmax ((2*totaldegree (F) - 1)/degMipo + 1, degree (F) + 1 +
7011	degree (LC (F, 1)));
7012	M= CFMatrix (liftBound, bufUniFactors.length());
7013	DegreePattern bufDegs= DegreePattern (bufUniFactors);
7014	degs.intersect (bufDegs);
7015	degs.refine();
7016	if (degs.getLength() <= 1)
7017	{
7018	delete [] bounds;
7019	CFList source, dest;
7020	CanonicalForm tmp= F (y - evaluation, y);
7021	tmp= mapDown (tmp, info, source, dest);
7022	smallFactors.append (tmp);
7023	return smallFactors;
7024	}
7025	}
7026
7027	bufUniFactors.insert (LCF);
7028	int l= 1;
7029
7030	zz_p::init (getCharacteristic());
7031	zz_pX NTLMipo;
7032	mat_zz_p NTLN;
7033
7034	ident (NTLN, bufUniFactors.length() - 1);
7035	bool irreducible= false;
7036	CFArray bufQ= CFArray (bufUniFactors.length() - 1);
7037
7038	int oldL;
7039	if (success)
7040	{
7041	int start= 0;
7042	oldL= extLiftAndComputeLattice (F, bounds, d, liftBound, minBound, start,
7043	bufUniFactors, NTLN, diophant, M, Pi, bufQ,
7044	irreducible, evaluation, info2, source, dest
7045	);
7046	}
7047	else
7048	{
7049	oldL= extLiftAndComputeLattice (F, bounds, d, liftBound, minBound,
7050	minBound + 1, bufUniFactors, NTLN, diophant,
7051	M, Pi, bufQ, irreducible, evaluation, info2,
7052	source, dest
7053	);
7054	}
7055
7056	bufUniFactors.removeFirst();
7057	if (oldL > liftBound)
7058	{
7059	delete [] bounds;
7060	return Union (smallFactors, extFactorRecombination
7061	(bufUniFactors, F,
7062	power (y, degree (F) + 1 + degree (LCF)),info,
7063	degs, evaluation, 1, bufUniFactors.length()/2
7064	)
7065	);
7066	}
7067
7068	l= oldL;
7069	if (irreducible)
7070	{
7071	delete [] bounds;
7072	CFList source, dest;
7073	CanonicalForm tmp= F (y - evaluation, y);
7074	tmp= mapDown (tmp, info, source, dest);
7075	return Union (CFList (tmp), smallFactors);
7076	}
7077
7078	CanonicalForm yToL= power (y,l);
7079
7080	CFList result;
7081	if (l >= degree (F) + 1)
7082	{
7083	int * factorsFoundIndex;
7084
7085	factorsFoundIndex= new int [NTLN.NumCols()];
7086	for (long i= 0; i < NTLN.NumCols(); i++)
7087	factorsFoundIndex[i]= 0;
7088
7089	int factorsFound= 0;
7090	CanonicalForm bufF= F;
7091
7092	extReconstructionTry (result, bufF, bufUniFactors, degree (F) + 1,
7093	factorsFound, factorsFoundIndex, NTLN, false, info,
7094	evaluation
7095	);
7096
7097	if (result.length() == NTLN.NumCols())
7098	{
7099	delete [] factorsFoundIndex;
7100	delete [] bounds;
7101	return Union (result, smallFactors);
7102	}
7103
7104	delete [] factorsFoundIndex;
7105	}
7106	if (l >= liftBound)
7107	{
7108	int * factorsFoundIndex;
7109	factorsFoundIndex= new int [NTLN.NumCols()];
7110	for (long i= 0; i < NTLN.NumCols(); i++)
7111	factorsFoundIndex[i]= 0;
7112	CanonicalForm bufF= F;
7113	int factorsFound= 0;
7114
7115	extReconstructionTry (result, bufF, bufUniFactors, degree (F) + 1 + degree
7116	(LCF), factorsFound, factorsFoundIndex, NTLN, false,
7117	info, evaluation
7118	);
7119
7120	if (result.length() == NTLN.NumCols())
7121	{
7122	delete [] factorsFoundIndex;
7123	delete [] bounds;
7124	return Union (result, smallFactors);
7125	}
7126	delete [] factorsFoundIndex;
7127	}
7128
7129	result= CFList();
7130	bool beenInThres= false;
7131	int thres= 100;
7132	if (l <= thres && bufUniFactors.length() > NTLN.NumCols())
7133	{
7134	refineAndRestartLift (F, NTLN, 2*totaldegree (F)-1, l, bufUniFactors, M, Pi,
7135	diophant
7136	);
7137	beenInThres= true;
7138	}
7139
7140
7141	CanonicalForm bufF= F;
7142	int factorsFound= 0;
7143
7144	result= extEarlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l,
7145	factorsFound, beenInThres, M, Pi,
7146	diophant, info, evaluation
7147	);
7148
7149	if (result.length() == NTLN.NumCols())
7150	{
7151	delete [] bounds;
7152	return Union (result, smallFactors);
7153	}
7154
7155	if (result.length() > 0)
7156	{
7157	if (beenInThres)
7158	{
7159	int index;
7160	for (CFListIterator i= result; i.hasItem(); i++)
7161	{
7162	index= 1;
7163	tmp1= mod (i.getItem(), y-evaluation);
7164	tmp1 /= Lc (tmp1);
7165	for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
7166	{
7167	tmp2= mod (j.getItem(), y);
7168	tmp2 /= Lc (tmp2);
7169	if (tmp1 == tmp2)
7170	{
7171	index++;
7172	j.remove(index);
7173	break;
7174	}
7175	}
7176	}
7177	}
7178	else
7179	{
7180	int * zeroOne= extractZeroOneVecs (NTLN);
7181	CFList bufBufUniFactors= bufUniFactors;
7182	CFListIterator iter, iter2;
7183	CanonicalForm buf;
7184	CFList factorsConsidered;
7185	for (int i= 0; i < NTLN.NumCols(); i++)
7186	{
7187	if (zeroOne [i] == 0)
7188	continue;
7189	iter= bufUniFactors;
7190	buf= 1;
7191	factorsConsidered= CFList();
7192	for (int j= 0; j < NTLN.NumRows(); j++, iter++)
7193	{
7194	if (!IsZero (NTLN (j + 1,i + 1)))
7195	{
7196	factorsConsidered.append (iter.getItem());
7197	buf *= mod (iter.getItem(), y);
7198	}
7199	}
7200	buf /= Lc (buf);
7201	for (iter2= result; iter2.hasItem(); iter2++)
7202	{
7203	CanonicalForm tmp= mod (iter2.getItem(), y - evaluation);
7204	tmp /= Lc (tmp);
7205	if (tmp == buf)
7206	{
7207	bufBufUniFactors= Difference (bufBufUniFactors, factorsConsidered);
7208	break;
7209	}
7210	}
7211	}
7212	bufUniFactors= bufBufUniFactors;
7213	delete [] zeroOne;
7214	}
7215
7216	int oldNumCols;
7217	CFList resultBufF;
7218	irreducible= false;
7219
7220	oldNumCols= NTLN.NumCols();
7221	resultBufF= extIncreasePrecision (bufF, bufUniFactors, factorsFound,
7222	oldNumCols, oldL, evaluation, info2,
7223	source, dest, l
7224	);
7225
7226	if (bufUniFactors.isEmpty() \|\| degree (bufF) <= 0)
7227	{
7228	delete [] bounds;
7229	result= Union (resultBufF, result);
7230	return Union (result, smallFactors);
7231	}
7232
7233	for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
7234	i.getItem()= mod (i.getItem(), y);
7235
7236	delete [] bounds;
7237	CFList bufResult;
7238	DegreePattern bufDegs= DegreePattern (bufUniFactors);
7239	degs.intersect (bufDegs);
7240	degs.refine();
7241	result= Union (result, smallFactors);
7242	if (degs.getLength() == 1 \|\| bufUniFactors.length() == 1)
7243	{
7244	result.append (bufF);
7245	return result;
7246	}
7247	return Union (result, extHenselLiftAndLatticeRecombi (bufF, bufUniFactors,
7248	info, degs, evaluation
7249	)
7250	);
7251	}
7252
7253	if (l/degMipo < liftBound)
7254	{
7255	result=extIncreasePrecision (F, bufUniFactors, oldL, l, d, bounds, bufQ,
7256	NTLN, evaluation, info2, source, dest
7257	);
7258
7259	if (result.length()== NTLN.NumCols())
7260	{
7261	delete [] bounds;
7262	result= Union (result, smallFactors);
7263	return result;
7264	}
7265
7266	if (result.isEmpty())
7267	{
7268	result= extFurtherLiftingAndIncreasePrecision (F,bufUniFactors, l,
7269	liftBound, d, bounds, NTLN,
7270	diophant, M, Pi, bufQ,
7271	evaluation, info2, source,
7272	dest
7273	);
7274	if (result.length()== NTLN.NumCols())
7275	{
7276	delete [] bounds;
7277	result= Union (result, smallFactors);
7278	return result;
7279	}
7280	}
7281	}
7282
7283	DEBOUTLN (cerr, "lattice recombination failed");
7284
7285	DegreePattern bufDegs= DegreePattern (bufUniFactors);
7286	degs.intersect (bufDegs);
7287	degs.refine();
7288
7289	delete [] bounds;
7290	bounds= computeBounds (F, d, isIrreducible);
7291	if (isIrreducible)
7292	{
7293	delete [] bounds;
7294	CFList source, dest;
7295	CanonicalForm tmp= F (y - evaluation, y);
7296	tmp= mapDown (tmp, info, source, dest);
7297	smallFactors.append (tmp);
7298	result= Union (result, smallFactors);
7299	return result;
7300	}
7301	minBound= bounds[0];
7302	for (int i= 1; i < d; i++)
7303	{
7304	if (bounds[i] != 0)
7305	minBound= tmin (minBound, bounds[i]);
7306	}
7307
7308	if (minBound > 16 \|\| result.length() == 0)
7309	{
7310	result= Union (result, smallFactors);
7311	CanonicalForm MODl= power (y, degree (F) + 1 + degree (LC (F, 1)));
7312	delete [] bounds;
7313	return Union (result, extFactorRecombination (bufUniFactors, F, MODl, info,
7314	degs, evaluation, 1,
7315	bufUniFactors.length()/2
7316	)
7317	);
7318	}
7319	else
7320	{
7321	result= Union (result, smallFactors);
7322	for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
7323	i.getItem()= mod (i.getItem(), y);
7324	delete [] bounds;
7325	return Union (result, extHenselLiftAndLatticeRecombi (F, bufUniFactors,
7326	info, degs, evaluation
7327	)
7328	);
7329	}
7330	}
7331
7332	CFList
7333	extBiFactorize (const CanonicalForm& F, const ExtensionInfo& info);
7334
7335	/// bivariate factorization over finite fields as decribed in "Factoring
7336	/// multivariate polynomials over a finite field" by L Bernardin.
7337	CFList
7338	biFactorize (const CanonicalForm& F, const ExtensionInfo& info)
7339	{
7340	if (F.inCoeffDomain())
7341	return CFList(F);
7342
7343	CanonicalForm A= F;
7344	bool GF= (CFFactory::gettype() == GaloisFieldDomain);
7345
7346	Variable alpha= info.getAlpha();
7347	Variable beta= info.getBeta();
7348	CanonicalForm gamma= info.getGamma();
7349	CanonicalForm delta= info.getDelta();
7350	int k= info.getGFDegree();
7351	bool extension= info.isInExtension();
7352	if (A.isUnivariate())
7353	{
7354	if (extension == false)
7355	return uniFactorizer (F, alpha, GF);
7356	else
7357	{
7358	CFList source, dest;
7359	A= mapDown (A, info, source, dest);
7360	return uniFactorizer (A, beta, GF);
7361	}
7362	}
7363
7364	CFMap N;
7365	A= compress (A, N);
7366	Variable y= A.mvar();
7367
7368	if (y.level() > 2) return CFList (F);
7369	Variable x= Variable (1);
7370
7371	//remove and factorize content
7372	CanonicalForm contentAx= content (A, x);
7373	CanonicalForm contentAy= content (A);
7374
7375	A= A/(contentAx*contentAy);
7376	CFList contentAxFactors, contentAyFactors;
7377
7378	if (!extension)
7379	{
7380	contentAxFactors= uniFactorizer (contentAx, alpha, GF);
7381	contentAyFactors= uniFactorizer (contentAy, alpha, GF);
7382	}
7383
7384	//trivial case
7385	CFList factors;
7386	if (A.inCoeffDomain())
7387	{
7388	append (factors, contentAxFactors);
7389	append (factors, contentAyFactors);
7390	decompress (factors, N);
7391	return factors;
7392	}
7393	else if (A.isUnivariate())
7394	{
7395	factors= uniFactorizer (A, alpha, GF);
7396	append (factors, contentAxFactors);
7397	append (factors, contentAyFactors);
7398	decompress (factors, N);
7399	return factors;
7400	}
7401
7402
7403	//check trivial case
7404	if (degree (A) == 1 \|\| degree (A, 1) == 1 \|\|
7405	(size (A) == 2 && igcd (degree (A), degree (A,1))==1))
7406	{
7407	factors.append (A);
7408
7409	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
7410	false, false, N);
7411
7412	if (!extension)
7413	normalize (factors);
7414	return factors;
7415	}
7416
7417	// check derivatives
7418	bool derivXZero= false;
7419	CanonicalForm derivX= deriv (A, x);
7420	CanonicalForm gcdDerivX;
7421	if (derivX.isZero())
7422	derivXZero= true;
7423	else
7424	{
7425	gcdDerivX= gcd (A, derivX);
7426	if (degree (gcdDerivX) > 0)
7427	{
7428	CanonicalForm g= A/gcdDerivX;
7429	CFList factorsG=
7430	Union (biFactorize (g, info), biFactorize (gcdDerivX, info));
7431	append (factorsG, contentAxFactors);
7432	append (factorsG, contentAyFactors);
7433	decompress (factorsG, N);
7434	if (!extension)
7435	normalize (factorsG);
7436	return factorsG;
7437	}
7438	}
7439	bool derivYZero= false;
7440	CanonicalForm derivY= deriv (A, y);
7441	CanonicalForm gcdDerivY;
7442	if (derivY.isZero())
7443	derivYZero= true;
7444	else
7445	{
7446	gcdDerivY= gcd (A, derivY);
7447	if (degree (gcdDerivY) > 0)
7448	{
7449	CanonicalForm g= A/gcdDerivY;
7450	CFList factorsG=
7451	Union (biFactorize (g, info), biFactorize (gcdDerivY, info));
7452	append (factorsG, contentAxFactors);
7453	append (factorsG, contentAyFactors);
7454	decompress (factorsG, N);
7455	if (!extension)
7456	normalize (factorsG);
7457	return factorsG;
7458	}
7459	}
7460	//main variable is chosen s.t. the degree in x is minimal
7461	bool swap= false;
7462	if ((degree (A) > degree (A, x)) \|\| derivXZero)
7463	{
7464	if (!derivYZero)
7465	{
7466	A= swapvar (A, y, x);
7467	swap= derivXZero;
7468	derivXZero= derivYZero;
7469	derivYZero= swap;
7470	swap= true;
7471	}
7472	}
7473
7474	int boundsLength;
7475	bool isIrreducible= false;
7476	int * bounds= computeBounds (A, boundsLength, isIrreducible);
7477	if (isIrreducible)
7478	{
7479	delete [] bounds;
7480	factors.append (A);
7481
7482	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
7483	swap, false, N);
7484
7485	if (!extension)
7486	normalize (factors);
7487	return factors;
7488	}
7489
7490	bool fail= false;
7491	CanonicalForm Aeval, evaluation, bufAeval, bufEvaluation, buf, tmp;
7492	CFList uniFactors, list, bufUniFactors;
7493	DegreePattern degs;
7494	DegreePattern bufDegs;
7495
7496	bool fail2= false;
7497	CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
7498	CFList bufUniFactors2, list2, uniFactors2;
7499	DegreePattern degs2;
7500	DegreePattern bufDegs2;
7501	bool swap2= false;
7502
7503	// several univariate factorizations to obtain more information about the
7504	// degree pattern therefore usually less combinations have to be tried during
7505	// the recombination process
7506	int factorNums= 3;
7507	int subCheck1= substituteCheck (A, x);
7508	int subCheck2= substituteCheck (A, y);
7509	bool symmetric= false;
7510	for (int i= 0; i < factorNums; i++)
7511	{
7512	bufAeval= A;
7513	TIMING_START (fac_fq_bi_evaluation);
7514	bufEvaluation= evalPoint (A, bufAeval, alpha, list, GF, fail);
7515	TIMING_END_AND_PRINT (fac_fq_bi_evaluation, "time to find eval point: ");
7516	if (!derivXZero && !fail2 && !symmetric)
7517	{
7518	if (i == 0)
7519	{
7520	buf= swapvar (A, x, y);
7521	symmetric= (A/Lc (A) == buf/Lc (buf));
7522	}
7523	bufAeval2= buf;
7524	TIMING_START (fac_fq_bi_evaluation);
7525	bufEvaluation2= evalPoint (buf, bufAeval2, alpha, list2, GF, fail2);
7526	TIMING_END_AND_PRINT (fac_fq_bi_evaluation,
7527	"time to find eval point wrt y: ");
7528	}
7529	// first try to change main variable if there is no valid evaluation point
7530	if (fail && (i == 0))
7531	{
7532	if (!derivXZero && !fail2 && !symmetric)
7533	{
7534	bufEvaluation= bufEvaluation2;
7535	int dummy= subCheck2;
7536	subCheck2= subCheck1;
7537	subCheck1= dummy;
7538	tmp= A;
7539	A= buf;
7540	buf= tmp;
7541	bufAeval= bufAeval2;
7542	swap2= true;
7543	fail= false;
7544	}
7545	else
7546	fail= true;
7547	}
7548
7549	// if there is no valid evaluation point pass to a field extension
7550	if (fail && (i == 0))
7551	{
7552	factors= extBiFactorize (A, info);
7553	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
7554	swap, swap2, N);
7555	normalize (factors);
7556	return factors;
7557	}
7558
7559	// there is at least one valid evaluation point
7560	// but we do not compute more univariate factorization over an extension
7561	if (fail && (i != 0))
7562	break;
7563
7564	// univariate factorization
7565	TIMING_START (fac_fq_uni_factorizer);
7566	bufUniFactors= uniFactorizer (bufAeval, alpha, GF);
7567	TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
7568	"time for univariate factorization over Fq: ");
7569	DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
7570	(prod (bufUniFactors)*Lc (bufAeval) == bufAeval));
7571
7572	if (!derivXZero && !fail2 && !symmetric)
7573	{
7574	TIMING_START (fac_fq_uni_factorizer);
7575	bufUniFactors2= uniFactorizer (bufAeval2, alpha, GF);
7576	TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
7577	"time for univariate factorization in y over Fq: ");
7578	DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
7579	(prod (bufUniFactors2)*Lc (bufAeval2) == bufAeval2));
7580	}
7581
7582	if (bufUniFactors.length() == 1 \|\|
7583	(!fail2 && !derivXZero && !symmetric && (bufUniFactors2.length() == 1)))
7584	{
7585	if (extension)
7586	{
7587	CFList source, dest;
7588	appendMapDown (factors, A, info, source, dest);
7589	}
7590	else
7591	factors.append (A);
7592
7593	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
7594	swap, swap2, N);
7595
7596	if (!extension)
7597	normalize (factors);
7598	return factors;
7599	}
7600
7601	if (i == 0)
7602	{
7603	if (subCheck1 > 0)
7604	{
7605	int subCheck= substituteCheck (bufUniFactors);
7606
7607	if (subCheck > 1 && (subCheck1%subCheck == 0))
7608	{
7609	CanonicalForm bufA= A;
7610	subst (bufA, bufA, subCheck, x);
7611	factors= biFactorize (bufA, info);
7612	reverseSubst (factors, subCheck, x);
7613	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
7614	swap, swap2, N);
7615	if (!extension)
7616	normalize (factors);
7617	return factors;
7618	}
7619	}
7620
7621	if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
7622	{
7623	int subCheck= substituteCheck (bufUniFactors2);
7624
7625	if (subCheck > 1 && (subCheck2%subCheck == 0))
7626	{
7627	CanonicalForm bufA= A;
7628	subst (bufA, bufA, subCheck, y);
7629	factors= biFactorize (bufA, info);
7630	reverseSubst (factors, subCheck, y);
7631	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
7632	swap, swap2, N);
7633	if (!extension)
7634	normalize (factors);
7635	return factors;
7636	}
7637	}
7638	}
7639
7640	// degree analysis
7641	bufDegs = DegreePattern (bufUniFactors);
7642	if (!derivXZero && !fail2 && !symmetric)
7643	bufDegs2= DegreePattern (bufUniFactors2);
7644
7645	if (i == 0)
7646	{
7647	Aeval= bufAeval;
7648	evaluation= bufEvaluation;
7649	uniFactors= bufUniFactors;
7650	degs= bufDegs;
7651	if (!derivXZero && !fail2 && !symmetric)
7652	{
7653	Aeval2= bufAeval2;
7654	evaluation2= bufEvaluation2;
7655	uniFactors2= bufUniFactors2;
7656	degs2= bufDegs2;
7657	}
7658	}
7659	else
7660	{
7661	degs.intersect (bufDegs);
7662	if (!derivXZero && !fail2 && !symmetric)
7663	{
7664	degs2.intersect (bufDegs2);
7665	if (bufUniFactors2.length() < uniFactors2.length())
7666	{
7667	uniFactors2= bufUniFactors2;
7668	Aeval2= bufAeval2;
7669	evaluation2= bufEvaluation2;
7670	}
7671	}
7672	if (bufUniFactors.length() < uniFactors.length())
7673	{
7674	uniFactors= bufUniFactors;
7675	Aeval= bufAeval;
7676	evaluation= bufEvaluation;
7677	}
7678	}
7679	list.append (bufEvaluation);
7680	if (!derivXZero && !fail2 && !symmetric)
7681	list2.append (bufEvaluation2);
7682	}
7683
7684	if (!derivXZero && !fail2 && !symmetric)
7685	{
7686	if (uniFactors.length() > uniFactors2.length() \|\|
7687	(uniFactors.length() == uniFactors2.length()
7688	&& degs.getLength() > degs2.getLength()))
7689	{
7690	degs= degs2;
7691	uniFactors= uniFactors2;
7692	evaluation= evaluation2;
7693	Aeval= Aeval2;
7694	A= buf;
7695	swap2= true;
7696	}
7697	}
7698
7699	if (degs.getLength() == 1) // A is irreducible
7700	{
7701	if (extension)
7702	{
7703	CFList source, dest;
7704	appendMapDown (factors, A, info, source, dest);
7705	}
7706	else
7707	factors.append (A);
7708	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
7709	swap, swap2, N);
7710	if (!extension)
7711	normalize (factors);
7712	return factors;
7713	}
7714
7715	int liftBound= degree (A, y) + 1;
7716
7717	if (swap2)
7718	bounds= computeBounds (A, boundsLength, isIrreducible);
7719
7720	int minBound= bounds[0];
7721	for (int i= 1; i < boundsLength; i++)
7722	{
7723	if (bounds[i] != 0)
7724	minBound= tmin (minBound, bounds[i]);
7725	}
7726
7727	TIMING_START (fac_fq_bi_shift_to_zero);
7728	A= A (y + evaluation, y);
7729	TIMING_END_AND_PRINT (fac_fq_bi_shift_to_zero,
7730	"time to shift eval to zero: ");
7731
7732	int degMipo= 1;
7733	if (extension && alpha.level() != 1 && k==1)
7734	degMipo= degree (getMipo (alpha));
7735
7736	DEBOUTLN (cerr, "uniFactors= " << uniFactors);
7737
7738	if ((GF && !extension) \|\| (GF && extension && k != 1))
7739	{
7740	bool earlySuccess= false;
7741	CFList earlyFactors;
7742	TIMING_START (fac_fq_bi_hensel_lift);
7743	uniFactors= henselLiftAndEarly
7744	(A, earlySuccess, earlyFactors, degs, liftBound,
7745	uniFactors, info, evaluation);
7746	TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
7747	"time for bivariate hensel lifting over Fq: ");
7748	DEBOUTLN (cerr, "lifted factors= " << uniFactors);
7749
7750	CanonicalForm MODl= power (y, liftBound);
7751
7752	TIMING_START (fac_fq_bi_factor_recombination);
7753	if (extension)
7754	factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
7755	evaluation, 1, uniFactors.length()/2);
7756	else
7757	factors= factorRecombination (uniFactors, A, MODl, degs, 1,
7758	uniFactors.length()/2);
7759	TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
7760	"time for naive bivariate factor recombi over Fq: ");
7761
7762	if (earlySuccess)
7763	factors= Union (earlyFactors, factors);
7764	else if (!earlySuccess && degs.getLength() == 1)
7765	factors= earlyFactors;
7766	}
7767	else if (degree (A) > 4 && beta.level() == 1 && (2*minBound)/degMipo < 32)
7768	{
7769	TIMING_START (fac_fq_bi_hensel_lift);
7770	if (extension)
7771	{
7772	CFList lll= extHenselLiftAndLatticeRecombi (A, uniFactors, info, degs,
7773	evaluation
7774	);
7775	factors= Union (lll, factors);
7776	}
7777	else if (alpha.level() == 1 && !GF)
7778	{
7779	CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
7780	symmetric, evaluation);
7781	factors= Union (lll, factors);
7782	}
7783	else if (!extension && (alpha != x \|\| GF))
7784	{
7785	CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
7786	symmetric, evaluation);
7787	factors= Union (lll, factors);
7788	}
7789	TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
7790	"time to bivar lift and LLL recombi over Fq: ");
7791	DEBOUTLN (cerr, "lifted factors= " << uniFactors);
7792	}
7793	else
7794	{
7795	bool earlySuccess= false;
7796	CFList earlyFactors;
7797	TIMING_START (fac_fq_bi_hensel_lift);
7798	uniFactors= henselLiftAndEarly
7799	(A, earlySuccess, earlyFactors, degs, liftBound,
7800	uniFactors, info, evaluation);
7801	TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
7802	"time for bivar hensel lifting over Fq: ");
7803	DEBOUTLN (cerr, "lifted factors= " << uniFactors);
7804
7805	CanonicalForm MODl= power (y, liftBound);
7806	if (!extension)
7807	{
7808	TIMING_START (fac_fq_bi_factor_recombination);
7809	factors= factorRecombination (uniFactors, A, MODl, degs, 1, 3);
7810	TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
7811	"time for small subset naive recombi over Fq: ");
7812
7813	int oldUniFactorsLength= uniFactors.length();
7814	if (degree (A) > 0)
7815	{
7816	CFList tmp;
7817	TIMING_START (fac_fq_bi_hensel_lift);
7818	if (alpha.level() == 1)
7819	tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
7820	liftBound
7821	);
7822	else
7823	{
7824	if (degree (A) > getCharacteristic())
7825	tmp= increasePrecisionFq2Fp (A, uniFactors, 0, uniFactors.length(),
7826	1, alpha, liftBound
7827	);
7828	else
7829	tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
7830	alpha, liftBound
7831	);
7832	}
7833	TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
7834	"time to increase precision: ");
7835	factors= Union (factors, tmp);
7836	if (tmp.length() == 0 \|\| (tmp.length() > 0 && uniFactors.length() != 0
7837	&& uniFactors.length() != oldUniFactorsLength)
7838	)
7839	{
7840	DegreePattern bufDegs= DegreePattern (uniFactors);
7841	degs.intersect (bufDegs);
7842	degs.refine ();
7843	factors= Union (factors, factorRecombination (uniFactors, A, MODl,
7844	degs, 4,
7845	uniFactors.length()/2
7846	)
7847	);
7848	}
7849	}
7850	}
7851	else
7852	{
7853	if (beta.level() != 1 \|\| k > 1)
7854	{
7855	if (k > 1)
7856	{
7857	factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
7858	evaluation, 1, uniFactors.length()/2
7859	);
7860	}
7861	else
7862	{
7863	factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
7864	evaluation, 1, 3
7865	);
7866	if (degree (A) > 0)
7867	{
7868	CFList tmp= increasePrecision2 (A, uniFactors, alpha, liftBound);
7869	DegreePattern bufDegs= DegreePattern (tmp);
7870	degs.intersect (bufDegs);
7871	degs.refine ();
7872	factors= Union (factors, extFactorRecombination (tmp, A, MODl, info,
7873	degs, evaluation,
7874	1, tmp.length()/2
7875	)
7876	);
7877	}
7878	}
7879	}
7880	else
7881	{
7882	factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
7883	evaluation, 1, 3
7884	);
7885	int oldUniFactorsLength= uniFactors.length();
7886	if (degree (A) > 0)
7887	{
7888	int degMipo;
7889	ExtensionInfo info2= init4ext (info, evaluation, degMipo);
7890
7891	CFList source, dest;
7892	CFList tmp= extIncreasePrecision (A, uniFactors, 0,
7893	uniFactors.length(), 1, evaluation,
7894	info2, source, dest, liftBound
7895	);
7896	factors= Union (factors, tmp);
7897	if (tmp.length() == 0 \|\| (tmp.length() > 0 && uniFactors.length() != 0
7898	&& uniFactors.length() != oldUniFactorsLength)
7899	)
7900	{
7901	DegreePattern bufDegs= DegreePattern (uniFactors);
7902	degs.intersect (bufDegs);
7903	degs.refine ();
7904	factors= Union (factors,extFactorRecombination (uniFactors, A, MODl,
7905	info, degs, evaluation,
7906	4, uniFactors.length()/2
7907	)
7908	);
7909	}
7910	}
7911	}
7912	}
7913
7914	if (earlySuccess)
7915	factors= Union (earlyFactors, factors);
7916	else if (!earlySuccess && degs.getLength() == 1)
7917	factors= earlyFactors;
7918	}
7919	delete [] bounds;
7920	if (!extension)
7921	{
7922	for (CFListIterator i= factors; i.hasItem(); i++)
7923	i.getItem()= i.getItem() (y - evaluation, y);
7924	}
7925
7926	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
7927	swap, swap2, N);
7928	if (!extension)
7929	normalize (factors);
7930
7931	return factors;
7932	}
7933
7934	CFList
7935	extBiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
7936	{
7937
7938	CanonicalForm A= F;
7939	Variable alpha= info.getAlpha();
7940	Variable beta= info.getBeta();
7941	int k= info.getGFDegree();
7942	char cGFName= info.getGFName();
7943	CanonicalForm delta= info.getDelta();
7944
7945	bool GF= (CFFactory::gettype() == GaloisFieldDomain);
7946	Variable x= Variable (1);
7947	CFList factors;
7948	if (!GF && alpha == x) // we are in F_p
7949	{
7950	bool extension= true;
7951	int p= getCharacteristic();
7952	if (p*p < (1<<16)) // pass to GF if possible
7953	{
7954	setCharacteristic (getCharacteristic(), 2, 'Z');
7955	A= A.mapinto();
7956	ExtensionInfo info2= ExtensionInfo (extension);
7957	factors= biFactorize (A, info2);
7958
7959	CanonicalForm mipo= gf_mipo;
7960	setCharacteristic (getCharacteristic());
7961	Variable vBuf= rootOf (mipo.mapinto());
7962	for (CFListIterator j= factors; j.hasItem(); j++)
7963	j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
7964	}
7965	else // not able to pass to GF, pass to F_p(\alpha)
7966	{
7967	CanonicalForm mipo= randomIrredpoly (2, x);
7968	Variable v= rootOf (mipo);
7969	ExtensionInfo info2= ExtensionInfo (v);
7970	factors= biFactorize (A, info2);
7971	}
7972	return factors;
7973	}
7974	else if (!GF && (alpha != x)) // we are in F_p(\alpha)
7975	{
7976	if (k == 1) // need factorization over F_p
7977	{
7978	int extDeg= degree (getMipo (alpha));
7979	extDeg++;
7980	CanonicalForm mipo= randomIrredpoly (extDeg + 1, x);
7981	Variable v= rootOf (mipo);
7982	ExtensionInfo info2= ExtensionInfo (v);
7983	factors= biFactorize (A, info2);
7984	}
7985	else
7986	{
7987	if (beta == x)
7988	{
7989	Variable v= chooseExtension (alpha, beta, k);
7990	CanonicalForm primElem, imPrimElem;
7991	bool primFail= false;
7992	Variable vBuf;
7993	primElem= primitiveElement (alpha, vBuf, primFail);
7994	ASSERT (!primFail, "failure in integer factorizer");
7995	if (primFail)
7996	; //ERROR
7997	else
7998	imPrimElem= mapPrimElem (primElem, alpha, v);
7999
8000	CFList source, dest;
8001	CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
8002	source, dest);
8003	ExtensionInfo info2= ExtensionInfo (v, alpha, imPrimElem, primElem);
8004	factors= biFactorize (bufA, info2);
8005	}
8006	else
8007	{
8008	Variable v= chooseExtension (alpha, beta, k);
8009	CanonicalForm primElem, imPrimElem;
8010	bool primFail= false;
8011	Variable vBuf;
8012	ASSERT (!primFail, "failure in integer factorizer");
8013	if (primFail)
8014	; //ERROR
8015	else
8016	imPrimElem= mapPrimElem (delta, beta, v);
8017
8018	CFList source, dest;
8019	CanonicalForm bufA= mapDown (A, info, source, dest);
8020	source= CFList();
8021	dest= CFList();
8022	bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
8023	ExtensionInfo info2= ExtensionInfo (v, beta, imPrimElem, delta);
8024	factors= biFactorize (bufA, info2);
8025	}
8026	}
8027	return factors;
8028	}
8029	else // we are in GF (p^k)
8030	{
8031	int p= getCharacteristic();
8032	int extensionDeg= getGFDegree();
8033	bool extension= true;
8034	if (k == 1) // need factorization over F_p
8035	{
8036	extensionDeg++;
8037	if (ipower (p, extensionDeg) < (1<<16))
8038	// pass to GF(p^k+1)
8039	{
8040	CanonicalForm mipo= gf_mipo;
8041	setCharacteristic (p);
8042	Variable vBuf= rootOf (mipo.mapinto());
8043	A= GF2FalphaRep (A, vBuf);
8044	setCharacteristic (p, extensionDeg, 'Z');
8045	ExtensionInfo info2= ExtensionInfo (extension);
8046	factors= biFactorize (A.mapinto(), info2);
8047	}
8048	else // not able to pass to another GF, pass to F_p(\alpha)
8049	{
8050	CanonicalForm mipo= gf_mipo;
8051	setCharacteristic (p);
8052	Variable vBuf= rootOf (mipo.mapinto());
8053	A= GF2FalphaRep (A, vBuf);
8054	Variable v= chooseExtension (vBuf, beta, k);
8055	ExtensionInfo info2= ExtensionInfo (v, extension);
8056	factors= biFactorize (A, info2);
8057	}
8058	}
8059	else // need factorization over GF (p^k)
8060	{
8061	if (ipower (p, 2*extensionDeg) < (1<<16))
8062	// pass to GF (p^2k)
8063	{
8064	setCharacteristic (p, 2*extensionDeg, 'Z');
8065	ExtensionInfo info2= ExtensionInfo (k, cGFName, extension);
8066	factors= biFactorize (GFMapUp (A, extensionDeg), info2);
8067	setCharacteristic (p, extensionDeg, cGFName);
8068	}
8069	else // not able to pass to GF (p^2k), pass to F_p (\alpha)
8070	{
8071	CanonicalForm mipo= gf_mipo;
8072	setCharacteristic (p);
8073	Variable v1= rootOf (mipo.mapinto());
8074	A= GF2FalphaRep (A, v1);
8075	Variable v2= chooseExtension (v1, v1, k);
8076	CanonicalForm primElem, imPrimElem;
8077	bool primFail= false;
8078	Variable vBuf;
8079	primElem= primitiveElement (v1, vBuf, primFail);
8080	ASSERT (!primFail, "failure in integer factorizer");
8081	if (primFail)
8082	; //ERROR
8083	else
8084	imPrimElem= mapPrimElem (primElem, v1, v2);
8085
8086	CFList source, dest;
8087	CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
8088	source, dest);
8089	ExtensionInfo info2= ExtensionInfo (v2, v1, imPrimElem, primElem);
8090	factors= biFactorize (bufA, info2);
8091	setCharacteristic (p, k, cGFName);
8092	for (CFListIterator i= factors; i.hasItem(); i++)
8093	i.getItem()= Falpha2GFRep (i.getItem());
8094	}
8095	}
8096	return factors;
8097	}
8098	}
8099
8100	#endif
8101	/* HAVE_NTL */
8102
8103

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

Download in other formats: