Context Navigation

facFqBivar.cc @ 49660c

spielwiese

Last change on this file since 49660c was 49660c, checked in by Martin Lee <martinlee84@…>, 11 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