Context Navigation

facFqBivar.cc @ a209e1d

jengelh-datetimespielwiese

Last change on this file since a209e1d was a209e1d, checked in by Martin Lee <martinlee84@…>, 11 years ago
fix: make sure factors are lifted high enough to apply naive recombination
Property mode set to `100644`
File size: 220.9 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	if (!wasInBounds)
2353	{
2354	if (start)
2355	henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2356	else
2357	henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2358	factors.insert (LCF);
2359	}
2360	return l;
2361	}
2362
2363	#ifdef HAVE_FLINT
2364	int
2365	liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds, int
2366	start, int liftBound, int minBound, CFList& factors,
2367	nmod_mat_t FLINTN, CFList& diophant, CFMatrix& M,CFArray&
2368	Pi, CFArray& bufQ, bool& irreducible
2369	)
2370	{
2371	CanonicalForm LCF= LC (F, 1);
2372	CFArray *A= new CFArray [factors.length() - 1];
2373	bool wasInBounds= false;
2374	bool hitBound= false;
2375	int l= (minBound+1)*2;
2376	int stepSize= 2;
2377	int oldL= l/2;
2378	bool reduced= false;
2379	long rank;
2380	nmod_mat_t FLINTK, FLINTC, null;
2381	CFMatrix C;
2382	CFArray buf;
2383	CFListIterator j;
2384	CanonicalForm truncF;
2385	Variable y= F.mvar();
2386	while (l <= liftBound)
2387	{
2388	if (start)
2389	{
2390	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2391	start= 0;
2392	}
2393	else
2394	{
2395	if (wasInBounds)
2396	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2397	else
2398	henselLift12 (F, factors, l, Pi, diophant, M);
2399	}
2400
2401	factors.insert (LCF);
2402	j= factors;
2403	j++;
2404
2405	truncF= mod (F, power (y, l));
2406	for (int i= 0; i < factors.length() - 1; i++, j++)
2407	{
2408	if (!wasInBounds)
2409	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2410	else
2411	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2412	bufQ[i]);
2413	}
2414
2415	for (int i= 0; i < sizeBounds; i++)
2416	{
2417	if (bounds [i] + 1 <= l/2)
2418	{
2419	wasInBounds= true;
2420	int k= tmin (bounds [i] + 1, l/2);
2421	C= CFMatrix (l - k, factors.length() - 1);
2422	for (int ii= 0; ii < factors.length() - 1; ii++)
2423	{
2424	if (A[ii].size() - 1 >= i)
2425	{
2426	buf= getCoeffs (A[ii] [i], k);
2427	writeInMatrix (C, buf, ii + 1, 0);
2428	}
2429	}
2430
2431	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
2432	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
2433	getCharacteristic());
2434	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
2435	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
2436	getCharacteristic());
2437	rank= nmod_mat_nullspace (null, FLINTK);
2438	nmod_mat_clear (FLINTK);
2439	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
2440	nmod_mat_clear (FLINTC);
2441	nmod_mat_init_set (FLINTC, FLINTN);
2442	nmod_mat_clear (FLINTN);
2443	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
2444	getCharacteristic());
2445	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
2446
2447	nmod_mat_clear (FLINTC);
2448	nmod_mat_window_clear (FLINTK);
2449	nmod_mat_clear (null);
2450	if (nmod_mat_ncols (FLINTN) == 1)
2451	{
2452	irreducible= true;
2453	break;
2454	}
2455	if (isReduced (FLINTN) && l > (minBound+1)*2)
2456	{
2457	reduced= true;
2458	break;
2459	}
2460	}
2461	}
2462
2463	if (irreducible)
2464	break;
2465	if (reduced)
2466	break;
2467	oldL= l;
2468	l += stepSize;
2469	stepSize *= 2;
2470	if (l > liftBound)
2471	{
2472	if (!hitBound)
2473	{
2474	l= liftBound;
2475	hitBound= true;
2476	}
2477	else
2478	break;
2479	}
2480	}
2481	delete [] A;
2482	if (!wasInBounds)
2483	{
2484	if (start)
2485	henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2486	else
2487	henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2488	factors.insert (LCF);
2489	}
2490	return l;
2491	}
2492	#endif
2493
2494	//over field extension
2495	int
2496	extLiftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds,
2497	int liftBound, int minBound, int start, CFList&
2498	factors, mat_zz_p& NTLN, CFList& diophant,
2499	CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
2500	irreducible, const CanonicalForm& evaluation, const
2501	ExtensionInfo& info, CFList& source, CFList& dest
2502	)
2503	{
2504	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
2505	CanonicalForm LCF= LC (F, 1);
2506	CFArray *A= new CFArray [factors.length() - 1];
2507	bool wasInBounds= false;
2508	bool hitBound= false;
2509	int degMipo;
2510	Variable alpha;
2511	alpha= info.getAlpha();
2512	degMipo= degree (getMipo (alpha));
2513
2514	Variable gamma= info.getBeta();
2515	CanonicalForm primElemAlpha= info.getGamma();
2516	CanonicalForm imPrimElemAlpha= info.getDelta();
2517
2518	int stepSize= 2;
2519	int l= ((minBound+1)/degMipo+1)*2;
2520	l= tmax (l, 2);
2521	if (start > l)
2522	l= start;
2523	int oldL= l/2;
2524	bool reduced= false;
2525	Variable y= F.mvar();
2526	Variable x= Variable (1);
2527	CanonicalForm powX, imBasis, truncF;
2528	CFMatrix Mat, C;
2529	CFArray buf;
2530	CFIterator iter;
2531	mat_zz_p* NTLMat, *NTLC, NTLK;
2532	CFListIterator j;
2533	while (l <= liftBound)
2534	{
2535	if (start)
2536	{
2537	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2538	start= 0;
2539	}
2540	else
2541	{
2542	if (wasInBounds)
2543	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2544	else
2545	henselLift12 (F, factors, l, Pi, diophant, M);
2546	}
2547
2548	factors.insert (LCF);
2549
2550	if (GF)
2551	setCharacteristic (getCharacteristic());
2552
2553	powX= power (y-gamma, l);
2554	Mat= CFMatrix (ldegMipo, ldegMipo);
2555	for (int i= 0; i < l*degMipo; i++)
2556	{
2557	imBasis= mod (power (y, i), powX);
2558	imBasis= imBasis (power (y, degMipo), y);
2559	imBasis= imBasis (y, gamma);
2560	iter= imBasis;
2561	for (; iter.hasTerms(); iter++)
2562	Mat (iter.exp()+ 1, i+1)= iter.coeff();
2563	}
2564
2565	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
2566	NTLMat= inv (NTLMat);
2567
2568	if (GF)
2569	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2570
2571	j= factors;
2572	j++;
2573
2574	truncF= mod (F, power (y, l));
2575	for (int i= 0; i < factors.length() - 1; i++, j++)
2576	{
2577	if (!wasInBounds)
2578	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2579	else
2580	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2581	bufQ[i]);
2582	}
2583
2584	for (int i= 0; i < sizeBounds; i++)
2585	{
2586	if (bounds [i] + 1 <= (l/2)*degMipo)
2587	{
2588	wasInBounds= true;
2589	int k= tmin (bounds [i] + 1, (l/2)*degMipo);
2590	C= CFMatrix (l*degMipo - k, factors.length() - 1);
2591
2592	for (int ii= 0; ii < factors.length() - 1; ii++)
2593	{
2594	if (A[ii].size() - 1 >= i)
2595	{
2596	if (GF)
2597	{
2598	A [ii] [i]= A [ii] [i] (y-evaluation, y);
2599	setCharacteristic (getCharacteristic());
2600	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
2601	if (alpha != gamma)
2602	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2603	gamma, source, dest
2604	);
2605	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
2606	}
2607	else
2608	{
2609	A [ii] [i]= A [ii] [i] (y-evaluation, y);
2610	if (alpha != gamma)
2611	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2612	gamma, source, dest
2613	);
2614	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
2615	}
2616	writeInMatrix (C, buf, ii + 1, 0);
2617	}
2618	if (GF)
2619	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2620	}
2621
2622	if (GF)
2623	setCharacteristic(getCharacteristic());
2624
2625	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
2626	NTLK= (NTLC)NTLN;
2627	transpose (NTLK, NTLK);
2628	kernel (NTLK, NTLK);
2629	transpose (NTLK, NTLK);
2630	NTLN *= NTLK;
2631
2632	if (GF)
2633	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2634
2635	if (NTLN.NumCols() == 1)
2636	{
2637	irreducible= true;
2638	break;
2639	}
2640	if (isReduced (NTLN))
2641	{
2642	reduced= true;
2643	break;
2644	}
2645	}
2646	}
2647
2648	if (NTLN.NumCols() == 1)
2649	{
2650	irreducible= true;
2651	break;
2652	}
2653	if (reduced)
2654	break;
2655	oldL= l;
2656	l += stepSize;
2657	stepSize *= 2;
2658	if (l > liftBound)
2659	{
2660	if (!hitBound)
2661	{
2662	l= liftBound;
2663	hitBound= true;
2664	}
2665	else
2666	break;
2667	}
2668	}
2669	delete [] A;
2670	if (!wasInBounds)
2671	{
2672	if (start)
2673	henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2674	else
2675	henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2676	factors.insert (LCF);
2677	}
2678	return l;
2679	}
2680
2681	/*#ifdef HAVE_FLINT
2682	//over field extension
2683	int
2684	extLiftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds,
2685	int liftBound, int minBound, int start, CFList&
2686	factors, nmod_mat_t FLINTN, CFList& diophant,
2687	CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
2688	irreducible, const CanonicalForm& evaluation, const
2689	ExtensionInfo& info, CFList& source, CFList& dest
2690	)
2691	{
2692	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
2693	CanonicalForm LCF= LC (F, 1);
2694	CFArray *A= new CFArray [factors.length() - 1];
2695	bool wasInBounds= false;
2696	bool hitBound= false;
2697	int degMipo;
2698	Variable alpha;
2699	alpha= info.getAlpha();
2700	degMipo= degree (getMipo (alpha));
2701
2702	Variable gamma= info.getBeta();
2703	CanonicalForm primElemAlpha= info.getGamma();
2704	CanonicalForm imPrimElemAlpha= info.getDelta();
2705
2706	int stepSize= 2;
2707	int l= ((minBound+1)/degMipo+1)*2;
2708	l= tmax (l, 2);
2709	if (start > l)
2710	l= start;
2711	int oldL= l/2;
2712	bool reduced= false;
2713	Variable y= F.mvar();
2714	Variable x= Variable (1);
2715	CanonicalForm powX, imBasis, truncF;
2716	CFMatrix Mat, C;
2717	CFArray buf;
2718	CFIterator iter;
2719	long rank;
2720	nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
2721	CFListIterator j;
2722	while (l <= liftBound)
2723	{
2724	if (start)
2725	{
2726	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2727	start= 0;
2728	}
2729	else
2730	{
2731	if (wasInBounds)
2732	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2733	else
2734	henselLift12 (F, factors, l, Pi, diophant, M);
2735	}
2736
2737	factors.insert (LCF);
2738
2739	if (GF)
2740	setCharacteristic (getCharacteristic());
2741
2742	powX= power (y-gamma, l);
2743	Mat= CFMatrix (ldegMipo, ldegMipo);
2744	for (int i= 0; i < l*degMipo; i++)
2745	{
2746	imBasis= mod (power (y, i), powX);
2747	imBasis= imBasis (power (y, degMipo), y);
2748	imBasis= imBasis (y, gamma);
2749	iter= imBasis;
2750	for (; iter.hasTerms(); iter++)
2751	Mat (iter.exp()+ 1, i+1)= iter.coeff();
2752	}
2753
2754	convertFacCFMatrix2nmod_mat_t (FLINTMat, Mat);
2755	nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
2756	nmod_mat_nrows (FLINTMat), getCharacteristic());
2757	nmod_mat_inv (FLINTMatInv, FLINTMat);
2758
2759	if (GF)
2760	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2761
2762	j= factors;
2763	j++;
2764
2765	truncF= mod (F, power (y, l));
2766	for (int i= 0; i < factors.length() - 1; i++, j++)
2767	{
2768	if (!wasInBounds)
2769	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2770	else
2771	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2772	bufQ[i]);
2773	}
2774
2775	for (int i= 0; i < sizeBounds; i++)
2776	{
2777	if (bounds [i] + 1 <= (l/2)*degMipo)
2778	{
2779	wasInBounds= true;
2780	int k= tmin (bounds [i] + 1, (l/2)*degMipo);
2781	C= CFMatrix (l*degMipo - k, factors.length() - 1);
2782
2783	for (int ii= 0; ii < factors.length() - 1; ii++)
2784	{
2785	if (A[ii].size() - 1 >= i)
2786	{
2787	if (GF)
2788	{
2789	A [ii] [i]= A [ii] [i] (y-evaluation, y);
2790	setCharacteristic (getCharacteristic());
2791	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
2792	if (alpha != gamma)
2793	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2794	gamma, source, dest
2795	);
2796	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv); //TODO
2797	}
2798	else
2799	{
2800	A [ii] [i]= A [ii] [i] (y-evaluation, y);
2801	if (alpha != gamma)
2802	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2803	gamma, source, dest
2804	);
2805	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv); //TODO
2806	}
2807	writeInMatrix (C, buf, ii + 1, 0);
2808	}
2809	if (GF)
2810	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2811	}
2812
2813	if (GF)
2814	setCharacteristic(getCharacteristic());
2815
2816	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
2817	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
2818	getCharacteristic());
2819	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
2820	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
2821	getCharacteristic());
2822	rank= nmod_mat_nullspace (null, FLINTK);
2823	nmod_mat_clear (FLINTK);
2824	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
2825	nmod_mat_clear (FLINTC);
2826	nmod_mat_init_set (FLINTC, FLINTN);
2827	nmod_mat_clear (FLINTN);
2828	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
2829	getCharacteristic());
2830	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
2831
2832	nmod_mat_clear (FLINTC);
2833	nmod_mat_window_clear (FLINTK);
2834	nmod_mat_clear (null);
2835
2836	if (GF)
2837	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2838
2839	if (nmod_mat_ncols (FLINTN) == 1)
2840	{
2841	irreducible= true;
2842	break;
2843	}
2844	if (isReduced (FLINTN))
2845	{
2846	reduced= true;
2847	break;
2848	}
2849	}
2850	}
2851
2852	nmod_mat_clear (FLINTMat);
2853	nmod_mat_clear (FLINTMatInv);
2854
2855	if (nmod_mat_ncols (FLINTN) == 1)
2856	{
2857	irreducible= true;
2858	break;
2859	}
2860	if (reduced)
2861	break;
2862	oldL= l;
2863	l += stepSize;
2864	stepSize *= 2;
2865	if (l > liftBound)
2866	{
2867	if (!hitBound)
2868	{
2869	l= liftBound;
2870	hitBound= true;
2871	}
2872	else
2873	break;
2874	}
2875	}
2876	delete [] A;
2877	if (!wasInBounds)
2878	{
2879	if (start)
2880	henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2881	else
2882	henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2883	factors.insert (LCF);
2884	}
2885	return l;
2886	}
2887	#endif*/
2888
2889	// over Fq
2890	int
2891	liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds,
2892	int start, int liftBound, int minBound, CFList& factors,
2893	mat_zz_pE& NTLN, CFList& diophant, CFMatrix& M, CFArray&
2894	Pi, CFArray& bufQ, bool& irreducible
2895	)
2896	{
2897	CanonicalForm LCF= LC (F, 1);
2898	CFArray *A= new CFArray [factors.length() - 1];
2899	bool wasInBounds= false;
2900	bool hitBound= false;
2901	int l= (minBound+1)*2;
2902	int stepSize= 2;
2903	int oldL= l/2;
2904	bool reduced= false;
2905	CFListIterator j;
2906	mat_zz_pE* NTLC, NTLK;
2907	CFArray buf;
2908	CFMatrix C;
2909	Variable y= F.mvar();
2910	CanonicalForm truncF;
2911	while (l <= liftBound)
2912	{
2913	if (start)
2914	{
2915	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2916	start= 0;
2917	}
2918	else
2919	{
2920	if (wasInBounds)
2921	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2922	else
2923	henselLift12 (F, factors, l, Pi, diophant, M);
2924	}
2925
2926	factors.insert (LCF);
2927	j= factors;
2928	j++;
2929
2930	truncF= mod (F, power (y,l));
2931	for (int i= 0; i < factors.length() - 1; i++, j++)
2932	{
2933	if (l == (minBound+1)*2)
2934	{
2935	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2936	}
2937	else
2938	{
2939	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2940	bufQ[i]
2941	);
2942	}
2943	}
2944
2945	for (int i= 0; i < sizeBounds; i++)
2946	{
2947	if (bounds [i] + 1 <= l/2)
2948	{
2949	wasInBounds= true;
2950	int k= tmin (bounds [i] + 1, l/2);
2951	C= CFMatrix (l - k, factors.length() - 1);
2952	for (int ii= 0; ii < factors.length() - 1; ii++)
2953	{
2954
2955	if (A[ii].size() - 1 >= i)
2956	{
2957	buf= getCoeffs (A[ii] [i], k);
2958	writeInMatrix (C, buf, ii + 1, 0);
2959	}
2960	}
2961
2962	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
2963	NTLK= (NTLC)NTLN;
2964	transpose (NTLK, NTLK);
2965	kernel (NTLK, NTLK);
2966	transpose (NTLK, NTLK);
2967	NTLN *= NTLK;
2968
2969	if (NTLN.NumCols() == 1)
2970	{
2971	irreducible= true;
2972	break;
2973	}
2974	if (isReduced (NTLN) && l > (minBound+1)*2)
2975	{
2976	reduced= true;
2977	break;
2978	}
2979	}
2980	}
2981
2982	if (NTLN.NumCols() == 1)
2983	{
2984	irreducible= true;
2985	break;
2986	}
2987	if (reduced)
2988	break;
2989	oldL= l;
2990	l += stepSize;
2991	stepSize *= 2;
2992	if (l > liftBound)
2993	{
2994	if (!hitBound)
2995	{
2996	l= liftBound;
2997	hitBound= true;
2998	}
2999	else
3000	break;
3001	}
3002	}
3003	delete [] A;
3004	if (!wasInBounds)
3005	{
3006	if (start)
3007	henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3008	else
3009	henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3010	factors.insert (LCF);
3011	}
3012	return l;
3013	}
3014
3015	#ifdef HAVE_FLINT
3016	int
3017	liftAndComputeLatticeFq2Fp (const CanonicalForm& F, int* bounds, int sizeBounds,
3018	int start, int liftBound, int minBound, CFList&
3019	factors, nmod_mat_t FLINTN, CFList& diophant,
3020	CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
3021	irreducible, const Variable& alpha
3022	)
3023	#else
3024	int
3025	liftAndComputeLatticeFq2Fp (const CanonicalForm& F, int* bounds, int sizeBounds,
3026	int start, int liftBound, int minBound, CFList&
3027	factors, mat_zz_p& NTLN, CFList& diophant, CFMatrix&
3028	M, CFArray& Pi, CFArray& bufQ, bool& irreducible,
3029	const Variable& alpha
3030	)
3031	#endif
3032	{
3033	CanonicalForm LCF= LC (F, 1);
3034	CFArray *A= new CFArray [factors.length() - 1];
3035	bool wasInBounds= false;
3036	int l= (minBound+1)*2;
3037	int oldL= l/2;
3038	int stepSize= 2;
3039	bool hitBound= false;
3040	int extensionDeg= degree (getMipo (alpha));
3041	bool reduced= false;
3042	CFListIterator j;
3043	CFMatrix C;
3044	CFArray buf;
3045	#ifdef HAVE_FLINT
3046	long rank;
3047	nmod_mat_t FLINTC, FLINTK, null;
3048	#else
3049	mat_zz_p* NTLC, NTLK;
3050	#endif
3051	Variable y= F.mvar();
3052	CanonicalForm truncF;
3053	while (l <= liftBound)
3054	{
3055	if (start)
3056	{
3057	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
3058	start= 0;
3059	}
3060	else
3061	{
3062	if (wasInBounds)
3063	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
3064	else
3065	henselLift12 (F, factors, l, Pi, diophant, M);
3066	}
3067
3068	factors.insert (LCF);
3069	j= factors;
3070	j++;
3071
3072	truncF= mod (F, power (y,l));
3073	for (int i= 0; i < factors.length() - 1; i++, j++)
3074	{
3075	if (l == (minBound+1)*2)
3076	{
3077	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
3078	}
3079	else
3080	{
3081	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
3082	bufQ[i]
3083	);
3084	}
3085	}
3086
3087	for (int i= 0; i < sizeBounds; i++)
3088	{
3089	if (bounds [i] + 1 <= l/2)
3090	{
3091	wasInBounds= true;
3092	int k= tmin (bounds [i] + 1, l/2);
3093	C= CFMatrix ((l - k)*extensionDeg, factors.length() - 1);
3094	for (int ii= 0; ii < factors.length() - 1; ii++)
3095	{
3096	if (A[ii].size() - 1 >= i)
3097	{
3098	buf= getCoeffs (A[ii] [i], k, alpha);
3099	writeInMatrix (C, buf, ii + 1, 0);
3100	}
3101	}
3102
3103	#ifdef HAVE_FLINT
3104	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
3105	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3106	getCharacteristic());
3107	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3108	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3109	getCharacteristic());
3110	rank= nmod_mat_nullspace (null, FLINTK);
3111	nmod_mat_clear (FLINTK);
3112	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3113	nmod_mat_clear (FLINTC);
3114	nmod_mat_init_set (FLINTC, FLINTN);
3115	nmod_mat_clear (FLINTN);
3116	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3117	getCharacteristic());
3118	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3119
3120	nmod_mat_clear (FLINTC);
3121	nmod_mat_window_clear (FLINTK);
3122	nmod_mat_clear (null);
3123	#else
3124	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
3125	NTLK= (NTLC)NTLN;
3126	transpose (NTLK, NTLK);
3127	kernel (NTLK, NTLK);
3128	transpose (NTLK, NTLK);
3129	NTLN *= NTLK;
3130	#endif
3131
3132	#ifdef HAVE_FLINT
3133	if (nmod_mat_nrows (FLINTN) == 1)
3134	#else
3135	if (NTLN.NumCols() == 1)
3136	#endif
3137	{
3138	irreducible= true;
3139	break;
3140	}
3141	#ifdef HAVE_FLINT
3142	if (isReduced (FLINTN) && l > (minBound+1)*2)
3143	#else
3144	if (isReduced (NTLN) && l > (minBound+1)*2)
3145	#endif
3146	{
3147	reduced= true;
3148	break;
3149	}
3150	}
3151	}
3152
3153	#ifdef HAVE_FLINT
3154	if (nmod_mat_ncols (FLINTN) == 1)
3155	#else
3156	if (NTLN.NumCols() == 1)
3157	#endif
3158	{
3159	irreducible= true;
3160	break;
3161	}
3162	if (reduced)
3163	break;
3164	oldL= l;
3165	l += stepSize;
3166	stepSize *= 2;
3167	if (l > liftBound)
3168	{
3169	if (!hitBound)
3170	{
3171	l= liftBound;
3172	hitBound= true;
3173	}
3174	else
3175	break;
3176	}
3177	}
3178	delete [] A;
3179	if (!wasInBounds)
3180	{
3181	if (start)
3182	henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3183	else
3184	henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3185	factors.insert (LCF);
3186	}
3187	return l;
3188	}
3189
3190	CFList
3191	increasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
3192	int oldNumCols, int oldL, int precision
3193	)
3194	{
3195	int d;
3196	bool isIrreducible= false;
3197	int* bounds= computeBounds (F, d, isIrreducible);
3198	if (isIrreducible)
3199	{
3200	delete [] bounds;
3201	CanonicalForm G= F;
3202	F= 1;
3203	return CFList (G);
3204	}
3205	CFArray * A= new CFArray [factors.length()];
3206	CFArray bufQ= CFArray (factors.length());
3207	#ifdef HAVE_FLINT
3208	nmod_mat_t FLINTN;
3209	nmod_mat_init (FLINTN,factors.length(),factors.length(), getCharacteristic());
3210	for (long i=factors.length()-1; i >= 0; i--)
3211	nmod_mat_entry (FLINTN, i, i)= 1;
3212	#else
3213	mat_zz_p NTLN;
3214	ident (NTLN, factors.length());
3215	#endif
3216	int minBound= bounds[0];
3217	for (int i= 1; i < d; i++)
3218	{
3219	if (bounds[i] != 0)
3220	minBound= tmin (minBound, bounds[i]);
3221	}
3222	int l= tmax (2*(minBound + 1), oldL);
3223	int oldL2= l/2;
3224	int stepSize= 2;
3225	bool useOldQs= false;
3226	bool hitBound= false;
3227	CFListIterator j;
3228	CFMatrix C;
3229	CFArray buf;
3230	#ifdef HAVE_FLINT
3231	long rank;
3232	nmod_mat_t FLINTC, FLINTK, null;
3233	#else
3234	mat_zz_p* NTLC, NTLK;
3235	#endif
3236	Variable y= F.mvar();
3237	CanonicalForm truncF;
3238	while (l <= precision)
3239	{
3240	j= factors;
3241	truncF= mod (F, power (y,l));
3242	if (useOldQs)
3243	{
3244	for (int i= 0; i < factors.length(); i++, j++)
3245	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3246	bufQ[i]
3247	);
3248	}
3249	else
3250	{
3251	for (int i= 0; i < factors.length(); i++, j++)
3252	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3253	}
3254	useOldQs= true;
3255	for (int i= 0; i < d; i++)
3256	{
3257	if (bounds [i] + 1 <= l/2)
3258	{
3259	int k= tmin (bounds [i] + 1, l/2);
3260	C= CFMatrix (l - k, factors.length());
3261	for (int ii= 0; ii < factors.length(); ii++)
3262	{
3263	if (A[ii].size() - 1 >= i)
3264	{
3265	buf= getCoeffs (A[ii] [i], k);
3266	writeInMatrix (C, buf, ii + 1, 0);
3267	}
3268	}
3269	#ifdef HAVE_FLINT
3270	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
3271	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3272	getCharacteristic());
3273	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3274	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3275	getCharacteristic());
3276	rank= nmod_mat_nullspace (null, FLINTK);
3277	nmod_mat_clear (FLINTK);
3278	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3279	nmod_mat_clear (FLINTC);
3280	nmod_mat_init_set (FLINTC, FLINTN);
3281	nmod_mat_clear (FLINTN);
3282	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3283	getCharacteristic());
3284	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3285
3286	nmod_mat_clear (FLINTC);
3287	nmod_mat_window_clear (FLINTK);
3288	nmod_mat_clear (null);
3289	#else
3290	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
3291	NTLK= (NTLC)NTLN;
3292	transpose (NTLK, NTLK);
3293	kernel (NTLK, NTLK);
3294	transpose (NTLK, NTLK);
3295	NTLN *= NTLK;
3296	#endif
3297	#ifdef HAVE_FLINT
3298	if (nmod_mat_ncols (FLINTN) == 1)
3299	{
3300	nmod_mat_clear (FLINTN);
3301	#else
3302	if (NTLN.NumCols() == 1)
3303	{
3304	#endif
3305	delete [] A;
3306	delete [] bounds;
3307	CanonicalForm G= F;
3308	F= 1;
3309	return CFList (G);
3310	}
3311	}
3312	}
3313
3314	#ifdef HAVE_FLINT
3315	if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
3316	{
3317	if (isReduced (FLINTN))
3318	{
3319	int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
3320	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
3321	#else
3322	if (NTLN.NumCols() < oldNumCols - factorsFound)
3323	{
3324	if (isReduced (NTLN))
3325	{
3326	int * factorsFoundIndex= new int [NTLN.NumCols()];
3327	for (long i= 0; i < NTLN.NumCols(); i++)
3328	#endif
3329	factorsFoundIndex[i]= 0;
3330	int factorsFound2= 0;
3331	CFList result;
3332	CanonicalForm bufF= F;
3333	#ifdef HAVE_FLINT
3334	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
3335	factorsFoundIndex, FLINTN, false
3336	);
3337	if (result.length() == nmod_mat_ncols (FLINTN))
3338	{
3339	nmod_mat_clear (FLINTN);
3340	#else
3341	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
3342	factorsFoundIndex, NTLN, false
3343	);
3344	if (result.length() == NTLN.NumCols())
3345	{
3346	#endif
3347	delete [] factorsFoundIndex;
3348	delete [] A;
3349	delete [] bounds;
3350	F= 1;
3351	return result;
3352	}
3353	delete [] factorsFoundIndex;
3354	}
3355	else if (l == precision)
3356	{
3357	CanonicalForm bufF= F;
3358	#ifdef HAVE_FLINT
3359	int * zeroOne= extractZeroOneVecs (FLINTN);
3360	CFList result= reconstruction (bufF,factors,zeroOne,precision,FLINTN);
3361	nmod_mat_clear (FLINTN);
3362	#else
3363	int * zeroOne= extractZeroOneVecs (NTLN);
3364	CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
3365	#endif
3366	F= bufF;
3367	delete [] zeroOne;
3368	delete [] A;
3369	delete [] bounds;
3370	return result;
3371	}
3372	}
3373	oldL2= l;
3374	l += stepSize;
3375	stepSize *= 2;
3376	if (l > precision)
3377	{
3378	if (!hitBound)
3379	{
3380	l= precision;
3381	hitBound= true;
3382	}
3383	else
3384	break;
3385	}
3386	}
3387	#ifdef HAVE_FLINT
3388	nmod_mat_clear (FLINTN);
3389	#endif
3390	delete [] bounds;
3391	delete [] A;
3392	return CFList();
3393	}
3394
3395	CFList
3396	increasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
3397	int oldNumCols, int oldL, const Variable&,
3398	int precision
3399	)
3400	{
3401	int d;
3402	bool isIrreducible= false;
3403	int* bounds= computeBounds (F, d, isIrreducible);
3404	if (isIrreducible)
3405	{
3406	delete [] bounds;
3407	CanonicalForm G= F;
3408	F= 1;
3409	return CFList (G);
3410	}
3411	CFArray * A= new CFArray [factors.length()];
3412	CFArray bufQ= CFArray (factors.length());
3413	mat_zz_pE NTLN;
3414	ident (NTLN, factors.length());
3415	int minBound= bounds[0];
3416	for (int i= 1; i < d; i++)
3417	{
3418	if (bounds[i] != 0)
3419	minBound= tmin (minBound, bounds[i]);
3420	}
3421	int l= tmax (2*(minBound + 1), oldL);
3422	int oldL2= l/2;
3423	int stepSize= 2;
3424	bool useOldQs= false;
3425	bool hitBound= false;
3426	CFListIterator j;
3427	CFMatrix C;
3428	mat_zz_pE* NTLC, NTLK;
3429	CFArray buf;
3430	Variable y= F.mvar();
3431	CanonicalForm truncF;
3432	while (l <= precision)
3433	{
3434	j= factors;
3435	truncF= mod (F, power (y,l));
3436	if (useOldQs)
3437	{
3438	for (int i= 0; i < factors.length(); i++, j++)
3439	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3440	bufQ[i]
3441	);
3442	}
3443	else
3444	{
3445	for (int i= 0; i < factors.length(); i++, j++)
3446	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3447	}
3448	useOldQs= true;
3449	for (int i= 0; i < d; i++)
3450	{
3451	if (bounds [i] + 1 <= l/2)
3452	{
3453	int k= tmin (bounds [i] + 1, l/2);
3454	C= CFMatrix (l - k, factors.length());
3455	for (int ii= 0; ii < factors.length(); ii++)
3456	{
3457	if (A[ii].size() - 1 >= i)
3458	{
3459	buf= getCoeffs (A[ii] [i], k);
3460	writeInMatrix (C, buf, ii + 1, 0);
3461	}
3462	}
3463	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
3464	NTLK= (NTLC)NTLN;
3465	transpose (NTLK, NTLK);
3466	kernel (NTLK, NTLK);
3467	transpose (NTLK, NTLK);
3468	NTLN *= NTLK;
3469	if (NTLN.NumCols() == 1)
3470	{
3471	delete [] A;
3472	delete [] bounds;
3473	CanonicalForm G= F;
3474	F= 1;
3475	return CFList (G);
3476	}
3477	}
3478	}
3479
3480	if (NTLN.NumCols() < oldNumCols - factorsFound)
3481	{
3482	if (isReduced (NTLN))
3483	{
3484	int * factorsFoundIndex= new int [NTLN.NumCols()];
3485	for (long i= 0; i < NTLN.NumCols(); i++)
3486	factorsFoundIndex[i]= 0;
3487	int factorsFound2= 0;
3488	CFList result;
3489	CanonicalForm bufF= F;
3490	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
3491	factorsFoundIndex, NTLN, false);
3492	if (result.length() == NTLN.NumCols())
3493	{
3494	delete [] factorsFoundIndex;
3495	delete [] A;
3496	delete [] bounds;
3497	F= 1;
3498	return result;
3499	}
3500	delete [] factorsFoundIndex;
3501	}
3502	else if (l == precision)
3503	{
3504	CanonicalForm bufF= F;
3505	int * zeroOne= extractZeroOneVecs (NTLN);
3506	CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
3507	F= bufF;
3508	delete [] zeroOne;
3509	delete [] A;
3510	delete [] bounds;
3511	return result;
3512	}
3513	}
3514	oldL2= l;
3515	l += stepSize;
3516	stepSize *= 2;
3517	if (l > precision)
3518	{
3519	if (!hitBound)
3520	{
3521	l= precision;
3522	hitBound= true;
3523	}
3524	else
3525	break;
3526	}
3527	}
3528	delete [] bounds;
3529	delete [] A;
3530	return CFList();
3531	}
3532
3533	//over field extension
3534	CFList
3535	extIncreasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
3536	int oldNumCols, int oldL, const CanonicalForm& evaluation,
3537	const ExtensionInfo& info, CFList& source, CFList& dest,
3538	int precision
3539	)
3540	{
3541	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
3542	int degMipo= degree (getMipo (info.getAlpha()));
3543	Variable alpha= info.getAlpha();
3544	int d;
3545	bool isIrreducible= false;
3546	int* bounds= computeBounds (F, d, isIrreducible);
3547	if (isIrreducible)
3548	{
3549	delete [] bounds;
3550	CanonicalForm G= F;
3551	F= 1;
3552	return CFList (G);
3553	}
3554
3555	CFArray * A= new CFArray [factors.length()];
3556	CFArray bufQ= CFArray (factors.length());
3557	zz_p::init (getCharacteristic());
3558	mat_zz_p NTLN;
3559	ident (NTLN, factors.length());
3560	int minBound= bounds[0];
3561	for (int i= 1; i < d; i++)
3562	{
3563	if (bounds[i] != 0)
3564	minBound= tmin (minBound, bounds[i]);
3565	}
3566	int l= tmax (oldL, 2*((minBound+1)/degMipo+1));
3567	int oldL2= l/2;
3568	int stepSize= 2;
3569	bool useOldQs= false;
3570	bool hitBound= false;
3571	Variable gamma= info.getBeta();
3572	CanonicalForm primElemAlpha= info.getGamma();
3573	CanonicalForm imPrimElemAlpha= info.getDelta();
3574	CFListIterator j;
3575	Variable y= F.mvar();
3576	CanonicalForm powX, imBasis, truncF;
3577	CFMatrix Mat, C;
3578	CFIterator iter;
3579	mat_zz_p* NTLMat,*NTLC, NTLK;
3580	CFArray buf;
3581	while (l <= precision)
3582	{
3583	j= factors;
3584	if (GF)
3585	setCharacteristic (getCharacteristic());
3586	powX= power (y-gamma, l);
3587	Mat= CFMatrix (ldegMipo, ldegMipo);
3588	for (int i= 0; i < l*degMipo; i++)
3589	{
3590	imBasis= mod (power (y, i), powX);
3591	imBasis= imBasis (power (y, degMipo), y);
3592	imBasis= imBasis (y, gamma);
3593	iter= imBasis;
3594	for (; iter.hasTerms(); iter++)
3595	Mat (iter.exp()+ 1, i+1)= iter.coeff();
3596	}
3597
3598	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
3599	NTLMat= inv (NTLMat);
3600	if (GF)
3601	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
3602
3603	truncF= mod (F, power (y, l));
3604	if (useOldQs)
3605	{
3606	for (int i= 0; i < factors.length(); i++, j++)
3607	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3608	bufQ[i]
3609	);
3610	}
3611	else
3612	{
3613	for (int i= 0; i < factors.length(); i++, j++)
3614	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3615	}
3616	useOldQs= true;
3617	for (int i= 0; i < d; i++)
3618	{
3619	if (bounds [i] + 1 <= (l/2)*degMipo)
3620	{
3621	int k= tmin (bounds [i] + 1, (l/2)*degMipo);
3622	C= CFMatrix (l*degMipo - k, factors.length());
3623	for (int ii= 0; ii < factors.length(); ii++)
3624	{
3625	if (A[ii].size() - 1 >= i)
3626	{
3627	if (GF)
3628	{
3629	A[ii] [i]= A [ii] [i] (y-evaluation, y);
3630	setCharacteristic (getCharacteristic());
3631	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
3632	if (alpha != gamma)
3633	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
3634	gamma, source, dest
3635	);
3636	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
3637	}
3638	else
3639	{
3640	A [ii] [i]= A [ii] [i] (y-evaluation, y);
3641	if (alpha != gamma)
3642	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
3643	gamma, source, dest
3644	);
3645	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
3646	}
3647	writeInMatrix (C, buf, ii + 1, 0);
3648	}
3649	if (GF)
3650	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
3651	}
3652
3653	if (GF)
3654	setCharacteristic(getCharacteristic());
3655
3656	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
3657	NTLK= (NTLC)NTLN;
3658	transpose (NTLK, NTLK);
3659	kernel (NTLK, NTLK);
3660	transpose (NTLK, NTLK);
3661	NTLN *= NTLK;
3662
3663	if (GF)
3664	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
3665
3666	if (NTLN.NumCols() == 1)
3667	{
3668	Variable y= Variable (2);
3669	CanonicalForm tmp= F (y - evaluation, y);
3670	CFList source, dest;
3671	tmp= mapDown (tmp, info, source, dest);
3672	delete [] A;
3673	delete [] bounds;
3674	F= 1;
3675	return CFList (tmp);
3676	}
3677	}
3678	}
3679
3680	if (NTLN.NumCols() < oldNumCols - factorsFound)
3681	{
3682	if (isReduced (NTLN))
3683	{
3684	int * factorsFoundIndex= new int [NTLN.NumCols()];
3685	for (long i= 0; i < NTLN.NumCols(); i++)
3686	factorsFoundIndex[i]= 0;
3687	int factorsFound2= 0;
3688	CFList result;
3689	CanonicalForm bufF= F;
3690	extReconstructionTry (result, bufF, factors,degree (F)+1, factorsFound2,
3691	factorsFoundIndex, NTLN, false, info, evaluation
3692	);
3693	if (result.length() == NTLN.NumCols())
3694	{
3695	delete [] factorsFoundIndex;
3696	delete [] A;
3697	delete [] bounds;
3698	F= 1;
3699	return result;
3700	}
3701	delete [] factorsFoundIndex;
3702	}
3703	else if (l == precision)
3704	{
3705	CanonicalForm bufF= F;
3706	int * zeroOne= extractZeroOneVecs (NTLN);
3707	CFList result= extReconstruction (bufF, factors, zeroOne, precision,
3708	NTLN, info, evaluation
3709	);
3710	F= bufF;
3711	delete [] zeroOne;
3712	delete [] A;
3713	delete [] bounds;
3714	return result;
3715	}
3716	}
3717	oldL2= l;
3718	l += stepSize;
3719	stepSize *= 2;
3720	if (l > precision)
3721	{
3722	if (!hitBound)
3723	{
3724	hitBound= true;
3725	l= precision;
3726	}
3727	else
3728	break;
3729	}
3730	}
3731	delete [] bounds;
3732	delete [] A;
3733	return CFList();
3734	}
3735
3736	CFList
3737	increasePrecision2 (const CanonicalForm& F, CFList& factors,
3738	const Variable& alpha, int precision)
3739	{
3740	int d;
3741	bool isIrreducible= false;
3742	int* bounds= computeBounds (F, d, isIrreducible);
3743	if (isIrreducible)
3744	{
3745	delete [] bounds;
3746	return CFList (F);
3747	}
3748	CFArray * A= new CFArray [factors.length()];
3749	CFArray bufQ= CFArray (factors.length());
3750	zz_p::init (getCharacteristic());
3751	zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
3752	zz_pE::init (NTLMipo);
3753	mat_zz_pE NTLN;
3754	ident (NTLN, factors.length());
3755	int minBound= bounds[0];
3756	for (int i= 1; i < d; i++)
3757	{
3758	if (bounds[i] != 0)
3759	minBound= tmin (minBound, bounds[i]);
3760	}
3761	int l= tmin (2*(minBound + 1), precision);
3762	int oldL= l/2;
3763	int stepSize= 2;
3764	bool useOldQs= false;
3765	bool hitBound= false;
3766	CFListIterator j;
3767	CFMatrix C;
3768	CFArray buf;
3769	mat_zz_pE* NTLC, NTLK;
3770	Variable y= F.mvar();
3771	CanonicalForm truncF;
3772	while (l <= precision)
3773	{
3774	j= factors;
3775	truncF= mod (F, power (y, l));
3776	if (useOldQs)
3777	{
3778	for (int i= 0; i < factors.length(); i++, j++)
3779	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i], bufQ[i]);
3780	}
3781	else
3782	{
3783	for (int i= 0; i < factors.length(); i++, j++)
3784	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3785	}
3786	useOldQs= true;
3787	for (int i= 0; i < d; i++)
3788	{
3789	if (bounds [i] + 1 <= l/2)
3790	{
3791	int k= tmin (bounds [i] + 1, l/2);
3792	C= CFMatrix (l - k, factors.length());
3793	for (int ii= 0; ii < factors.length(); ii++)
3794	{
3795	if (A[ii].size() - 1 >= i)
3796	{
3797	buf= getCoeffs (A[ii] [i], k);
3798	writeInMatrix (C, buf, ii + 1, 0);
3799	}
3800	}
3801	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
3802	NTLK= (NTLC)NTLN;
3803	transpose (NTLK, NTLK);
3804	kernel (NTLK, NTLK);
3805	transpose (NTLK, NTLK);
3806	NTLN *= NTLK;
3807	if (NTLN.NumCols() == 1)
3808	{
3809	delete [] A;
3810	delete [] bounds;
3811	return CFList (F);
3812	}
3813	}
3814	}
3815
3816	if (isReduced (NTLN) \|\| l == precision)
3817	{
3818	CanonicalForm bufF= F;
3819	int * zeroOne= extractZeroOneVecs (NTLN);
3820	CFList bufFactors= factors;
3821	CFList result= monicReconstruction (bufF, factors, zeroOne, precision,
3822	NTLN
3823	);
3824	if (result.length() != NTLN.NumCols() && l != precision)
3825	factors= bufFactors;
3826	if (result.length() == NTLN.NumCols())
3827	{
3828	delete [] zeroOne;
3829	delete [] A;
3830	delete [] bounds;
3831	return result;
3832	}
3833	if (l == precision)
3834	{
3835	delete [] zeroOne;
3836	delete [] A;
3837	delete [] bounds;
3838	return Union (result, factors);
3839	}
3840	}
3841	oldL= l;
3842	l += stepSize;
3843	stepSize *= 2;
3844	if (l > precision)
3845	{
3846	if (!hitBound)
3847	{
3848	l= precision;
3849	hitBound= true;
3850	}
3851	else
3852	break;
3853	}
3854	}
3855	delete [] bounds;
3856	delete [] A;
3857	return CFList();
3858	}
3859
3860	CFList
3861	increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int factorsFound,
3862	int oldNumCols, int oldL, const Variable& alpha,
3863	int precision
3864	)
3865	{
3866	int d;
3867	bool isIrreducible= false;
3868	int* bounds= computeBounds (F, d, isIrreducible);
3869	if (isIrreducible)
3870	{
3871	delete [] bounds;
3872	CanonicalForm G= F;
3873	F= 1;
3874	return CFList (G);
3875	}
3876	int extensionDeg= degree (getMipo (alpha));
3877	CFArray * A= new CFArray [factors.length()];
3878	CFArray bufQ= CFArray (factors.length());
3879	#ifdef HAVE_FLINT
3880	nmod_mat_t FLINTN;
3881	nmod_mat_init (FLINTN,factors.length(),factors.length(), getCharacteristic());
3882	for (long i=factors.length()-1; i >= 0; i--)
3883	nmod_mat_entry (FLINTN, i, i)= 1;
3884	#else
3885	mat_zz_p NTLN;
3886	ident (NTLN, factors.length());
3887	#endif
3888	int minBound= bounds[0];
3889	for (int i= 1; i < d; i++)
3890	{
3891	if (bounds[i] != 0)
3892	minBound= tmin (minBound, bounds[i]);
3893	}
3894	int l= tmax (2*(minBound + 1), oldL);
3895	int oldL2= l/2;
3896	int stepSize= 2;
3897	bool useOldQs= false;
3898	bool hitBound= false;
3899	CFListIterator j;
3900	CFMatrix C;
3901	#ifdef HAVE_FLINT
3902	long rank;
3903	nmod_mat_t FLINTC, FLINTK, null;
3904	#else
3905	mat_zz_p* NTLC, NTLK;
3906	#endif
3907	CFArray buf;
3908	Variable y= F.mvar();
3909	CanonicalForm truncF;
3910	while (l <= precision)
3911	{
3912	j= factors;
3913	truncF= mod (F, power (y, l));
3914	if (useOldQs)
3915	{
3916	for (int i= 0; i < factors.length(); i++, j++)
3917	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3918	bufQ[i]
3919	);
3920	}
3921	else
3922	{
3923	for (int i= 0; i < factors.length(); i++, j++)
3924	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3925	}
3926	useOldQs= true;
3927	for (int i= 0; i < d; i++)
3928	{
3929	if (bounds [i] + 1 <= l/2)
3930	{
3931	int k= tmin (bounds [i] + 1, l/2);
3932	C= CFMatrix ((l - k)*extensionDeg, factors.length());
3933	for (int ii= 0; ii < factors.length(); ii++)
3934	{
3935	if (A[ii].size() - 1 >= i)
3936	{
3937	buf= getCoeffs (A[ii] [i], k, alpha);
3938	writeInMatrix (C, buf, ii + 1, 0);
3939	}
3940	}
3941	#ifdef HAVE_FLINT
3942	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
3943	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3944	getCharacteristic());
3945	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3946	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3947	getCharacteristic());
3948	rank= nmod_mat_nullspace (null, FLINTK);
3949	nmod_mat_clear (FLINTK);
3950	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3951	nmod_mat_clear (FLINTC);
3952	nmod_mat_init_set (FLINTC, FLINTN);
3953	nmod_mat_clear (FLINTN);
3954	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3955	getCharacteristic());
3956	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3957
3958	nmod_mat_clear (FLINTC);
3959	nmod_mat_window_clear (FLINTK);
3960	nmod_mat_clear (null);
3961	#else
3962	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
3963	NTLK= (NTLC)NTLN;
3964	transpose (NTLK, NTLK);
3965	kernel (NTLK, NTLK);
3966	transpose (NTLK, NTLK);
3967	NTLN *= NTLK;
3968	#endif
3969	#ifdef HAVE_FLINT
3970	if (nmod_mat_ncols (FLINTN) == 1)
3971	{
3972	nmod_mat_clear (FLINTN);
3973	#else
3974	if (NTLN.NumCols() == 1)
3975	{
3976	#endif
3977	delete [] A;
3978	delete [] bounds;
3979	CanonicalForm G= F;
3980	F= 1;
3981	return CFList (G);
3982	}
3983	}
3984	}
3985
3986	#ifdef HAVE_FLINT
3987	if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
3988	{
3989	if (isReduced (FLINTN))
3990	{
3991	int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
3992	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
3993	#else
3994	if (NTLN.NumCols() < oldNumCols - factorsFound)
3995	{
3996	if (isReduced (NTLN))
3997	{
3998	int * factorsFoundIndex= new int [NTLN.NumCols()];
3999	for (long i= 0; i < NTLN.NumCols(); i++)
4000	#endif
4001	factorsFoundIndex[i]= 0;
4002	int factorsFound2= 0;
4003	CFList result;
4004	CanonicalForm bufF= F;
4005	#ifdef HAVE_FLINT
4006	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
4007	factorsFoundIndex, FLINTN, false
4008	);
4009	if (result.length() == nmod_mat_ncols (FLINTN))
4010	{
4011	nmod_mat_clear (FLINTN);
4012	#else
4013	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
4014	factorsFoundIndex, NTLN, false
4015	);
4016	if (result.length() == NTLN.NumCols())
4017	{
4018	#endif
4019	delete [] factorsFoundIndex;
4020	delete [] A;
4021	delete [] bounds;
4022	F= 1;
4023	return result;
4024	}
4025	delete [] factorsFoundIndex;
4026	}
4027	else if (l == precision)
4028	{
4029	CanonicalForm bufF= F;
4030	#ifdef HAVE_FLINT
4031	int * zeroOne= extractZeroOneVecs (FLINTN);
4032	CFList result= reconstruction (bufF,factors,zeroOne,precision,FLINTN);
4033	nmod_mat_clear (FLINTN);
4034	#else
4035	int * zeroOne= extractZeroOneVecs (NTLN);
4036	CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
4037	#endif
4038	F= bufF;
4039	delete [] zeroOne;
4040	delete [] A;
4041	delete [] bounds;
4042	return result;
4043	}
4044	}
4045	oldL2= l;
4046	l += stepSize;
4047	stepSize *= 2;
4048	if (l > precision)
4049	{
4050	if (!hitBound)
4051	{
4052	hitBound= true;
4053	l= precision;
4054	}
4055	else
4056	break;
4057	}
4058	}
4059	#ifdef HAVE_FLINT
4060	nmod_mat_clear (FLINTN);
4061	#endif
4062	delete [] bounds;
4063	delete [] A;
4064	return CFList();
4065	}
4066
4067	#ifdef HAVE_FLINT
4068	CFList
4069	increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int
4070	l, int d, int* bounds, CFArray& bufQ, nmod_mat_t FLINTN
4071	)
4072	#else
4073	CFList
4074	increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int
4075	l, int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN
4076	)
4077	#endif
4078	{
4079	CFList result= CFList();
4080	CFArray * A= new CFArray [factors.length()];
4081	int oldL2= oldL/2;
4082	bool hitBound= false;
4083	#ifdef HAVE_FLINT
4084	if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4085	{
4086	nmod_mat_clear (FLINTN);
4087	nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
4088	for (long i=factors.length()-1; i >= 0; i--)
4089	nmod_mat_entry (FLINTN, i, i)= 1;
4090	bufQ= CFArray (factors.length());
4091	}
4092	#else
4093	if (NTLN.NumRows() != factors.length()) //refined factors
4094	{
4095	ident (NTLN, factors.length());
4096	bufQ= CFArray (factors.length());
4097	}
4098	#endif
4099	bool useOldQs= false;
4100	CFListIterator j;
4101	CFMatrix C;
4102	CFArray buf;
4103	#ifdef HAVE_FLINT
4104	long rank;
4105	nmod_mat_t FLINTC, FLINTK, null;
4106	#else
4107	mat_zz_p* NTLC, NTLK;
4108	#endif
4109	CanonicalForm bufF, truncF;
4110	CFList bufUniFactors;
4111	Variable y= F.mvar();
4112	while (oldL <= l)
4113	{
4114	j= factors;
4115	truncF= mod (F, power (y, oldL));
4116	if (useOldQs)
4117	{
4118	for (int i= 0; i < factors.length(); i++, j++)
4119	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4120	bufQ[i]
4121	);
4122	}
4123	else
4124	{
4125	for (int i= 0; i < factors.length(); i++, j++)
4126	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4127	}
4128	useOldQs= true;
4129
4130	for (int i= 0; i < d; i++)
4131	{
4132	if (bounds [i] + 1 <= oldL/2)
4133	{
4134	int k= tmin (bounds [i] + 1, oldL/2);
4135	C= CFMatrix (oldL - k, factors.length());
4136	for (int ii= 0; ii < factors.length(); ii++)
4137	{
4138	if (A[ii].size() - 1 >= i)
4139	{
4140	buf= getCoeffs (A[ii] [i], k);
4141	writeInMatrix (C, buf, ii + 1, 0);
4142	}
4143	}
4144	#ifdef HAVE_FLINT
4145	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
4146	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4147	getCharacteristic());
4148	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4149	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4150	getCharacteristic());
4151	rank= nmod_mat_nullspace (null, FLINTK);
4152	nmod_mat_clear (FLINTK);
4153	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4154	nmod_mat_clear (FLINTC);
4155	nmod_mat_init_set (FLINTC, FLINTN);
4156	nmod_mat_clear (FLINTN);
4157	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4158	getCharacteristic());
4159	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4160
4161	nmod_mat_clear (FLINTC);
4162	nmod_mat_window_clear (FLINTK);
4163	nmod_mat_clear (null);
4164	#else
4165	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4166	NTLK= (NTLC)NTLN;
4167	transpose (NTLK, NTLK);
4168	kernel (NTLK, NTLK);
4169	transpose (NTLK, NTLK);
4170	NTLN *= NTLK;
4171	#endif
4172	#ifdef HAVE_FLINT
4173	if (nmod_mat_ncols (FLINTN) == 1)
4174	#else
4175	if (NTLN.NumCols() == 1)
4176	#endif
4177	{
4178	delete [] A;
4179	return CFList (F);
4180	}
4181	}
4182	}
4183	#ifdef HAVE_FLINT
4184	if (nmod_mat_ncols (FLINTN) == 1)
4185	#else
4186	if (NTLN.NumCols() == 1)
4187	#endif
4188	{
4189	delete [] A;
4190	return CFList (F);
4191	}
4192	int * zeroOneVecs;
4193	#ifdef HAVE_FLINT
4194	zeroOneVecs= extractZeroOneVecs (FLINTN);
4195	#else
4196	zeroOneVecs= extractZeroOneVecs (NTLN);
4197	#endif
4198	bufF= F;
4199	bufUniFactors= factors;
4200	#ifdef HAVE_FLINT
4201	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, FLINTN);
4202	#else
4203	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
4204	#endif
4205	delete [] zeroOneVecs;
4206	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < oldL && result.length() > 0)
4207	{
4208	F= bufF;
4209	factors= bufUniFactors;
4210	delete [] A;
4211	return result;
4212	}
4213
4214	result= CFList();
4215	oldL2= oldL;
4216	oldL *= 2;
4217	if (oldL > l)
4218	{
4219	if (!hitBound)
4220	{
4221	oldL= l;
4222	hitBound= true;
4223	}
4224	else
4225	break;
4226	}
4227	}
4228	delete [] A;
4229	return result;
4230	}
4231
4232	CFList
4233	increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int
4234	l, int d, int* bounds, CFArray& bufQ, mat_zz_pE& NTLN
4235	)
4236	{
4237	CFList result= CFList();
4238	CFArray * A= new CFArray [factors.length()];
4239	int oldL2= oldL/2;
4240	bool hitBound= false;
4241	bool useOldQs= false;
4242	if (NTLN.NumRows() != factors.length()) //refined factors
4243	ident (NTLN, factors.length());
4244	CFListIterator j;
4245	CFMatrix C;
4246	CFArray buf;
4247	mat_zz_pE* NTLC, NTLK;
4248	CanonicalForm bufF, truncF;
4249	CFList bufUniFactors;
4250	Variable y= F.mvar();
4251	while (oldL <= l)
4252	{
4253	j= factors;
4254	truncF= mod (F, power (y, oldL));
4255	if (useOldQs)
4256	{
4257	for (int i= 0; i < factors.length(); i++, j++)
4258	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4259	bufQ[i]
4260	);
4261	}
4262	else
4263	{
4264	for (int i= 0; i < factors.length(); i++, j++)
4265	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4266	}
4267	useOldQs= true;
4268
4269	for (int i= 0; i < d; i++)
4270	{
4271	if (bounds [i] + 1 <= oldL/2)
4272	{
4273	int k= tmin (bounds [i] + 1, oldL/2);
4274	C= CFMatrix (oldL - k, factors.length());
4275	for (int ii= 0; ii < factors.length(); ii++)
4276	{
4277	if (A[ii].size() - 1 >= i)
4278	{
4279	buf= getCoeffs (A[ii] [i], k);
4280	writeInMatrix (C, buf, ii + 1, 0);
4281	}
4282	}
4283	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
4284	NTLK= (NTLC)NTLN;
4285	transpose (NTLK, NTLK);
4286	kernel (NTLK, NTLK);
4287	transpose (NTLK, NTLK);
4288	NTLN *= NTLK;
4289	if (NTLN.NumCols() == 1)
4290	{
4291	delete [] A;
4292	return CFList (F);
4293	}
4294	}
4295	}
4296	if (NTLN.NumCols() == 1)
4297	{
4298	delete [] A;
4299	return CFList (F);
4300	}
4301
4302	int * zeroOneVecs;
4303	zeroOneVecs= extractZeroOneVecs (NTLN);
4304	bufF= F;
4305	bufUniFactors= factors;
4306	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
4307	delete [] zeroOneVecs;
4308	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4309	{
4310	F= bufF;
4311	factors= bufUniFactors;
4312	delete [] A;
4313	return result;
4314	}
4315
4316	result= CFList();
4317	oldL2= oldL;
4318	oldL *= 2;
4319	if (oldL > l)
4320	{
4321	if (!hitBound)
4322	{
4323	oldL= l;
4324	hitBound= true;
4325	}
4326	else
4327	break;
4328	}
4329	}
4330	delete [] A;
4331	return result;
4332	}
4333
4334	//over field extension
4335	CFList
4336	extIncreasePrecision (CanonicalForm& F, CFList& factors, int oldL, int l, int d,
4337	int* bounds, CFArray& bufQ, mat_zz_p& NTLN, const
4338	CanonicalForm& evaluation, const ExtensionInfo& info,
4339	CFList& source, CFList& dest
4340	)
4341	{
4342	CFList result= CFList();
4343	CFArray * A= new CFArray [factors.length()];
4344	int oldL2= oldL/2; //be careful
4345	bool hitBound= false;
4346	bool useOldQs= false;
4347	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
4348	int degMipo= degree (getMipo (info.getAlpha()));
4349	Variable alpha= info.getAlpha();
4350
4351	Variable gamma= info.getBeta();
4352	CanonicalForm primElemAlpha= info.getGamma();
4353	CanonicalForm imPrimElemAlpha= info.getDelta();
4354	if (NTLN.NumRows() != factors.length()) //refined factors
4355	ident (NTLN, factors.length());
4356	Variable y= F.mvar();
4357	CFListIterator j;
4358	CanonicalForm powX, imBasis, bufF, truncF;
4359	CFMatrix Mat, C;
4360	CFIterator iter;
4361	mat_zz_p* NTLMat;
4362	CFArray buf;
4363	mat_zz_p* NTLC, NTLK;
4364	CFList bufUniFactors;
4365	while (oldL <= l)
4366	{
4367	j= factors;
4368	if (GF)
4369	setCharacteristic (getCharacteristic());
4370
4371	powX= power (y-gamma, oldL);
4372	Mat= CFMatrix (oldLdegMipo, oldLdegMipo);
4373	for (int i= 0; i < oldL*degMipo; i++)
4374	{
4375	imBasis= mod (power (y, i), powX);
4376	imBasis= imBasis (power (y, degMipo), y);
4377	imBasis= imBasis (y, gamma);
4378	iter= imBasis;
4379	for (; iter.hasTerms(); iter++)
4380	Mat (iter.exp()+ 1, i+1)= iter.coeff();
4381	}
4382
4383	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
4384	NTLMat= inv (NTLMat);
4385	if (GF)
4386	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
4387
4388	truncF= mod (F, power (y, oldL));
4389	if (useOldQs)
4390	{
4391	for (int i= 0; i < factors.length(); i++, j++)
4392	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4393	bufQ[i]);
4394	}
4395	else
4396	{
4397	for (int i= 0; i < factors.length(); i++, j++)
4398	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4399	}
4400	useOldQs= true;
4401
4402	for (int i= 0; i < d; i++)
4403	{
4404	if (bounds [i] + 1 <= oldL/2)
4405	{
4406	int k= tmin (bounds [i] + 1, oldL/2);
4407	C= CFMatrix (oldL*degMipo - k, factors.length());
4408	for (int ii= 0; ii < factors.length(); ii++)
4409	{
4410	if (A[ii].size() - 1 >= i)
4411	{
4412	if (GF)
4413	{
4414	A [ii] [i]= A [ii] [i] (y-evaluation, y);
4415	setCharacteristic (getCharacteristic());
4416	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
4417	if (alpha != gamma)
4418	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
4419	gamma, source, dest
4420	);
4421	buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
4422	}
4423	else
4424	{
4425	A [ii] [i]= A [ii] [i] (y-evaluation, y);
4426	if (alpha != gamma)
4427	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
4428	gamma, source, dest
4429	);
4430	buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
4431	}
4432	writeInMatrix (C, buf, ii + 1, 0);
4433	}
4434	if (GF)
4435	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
4436	}
4437
4438	if (GF)
4439	setCharacteristic(getCharacteristic());
4440
4441	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4442	NTLK= (NTLC)NTLN;
4443	transpose (NTLK, NTLK);
4444	kernel (NTLK, NTLK);
4445	transpose (NTLK, NTLK);
4446	NTLN *= NTLK;
4447
4448	if (GF)
4449	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
4450
4451	if (NTLN.NumCols() == 1)
4452	{
4453	Variable y= Variable (2);
4454	CanonicalForm tmp= F (y - evaluation, y);
4455	CFList source, dest;
4456	tmp= mapDown (tmp, info, source, dest);
4457	delete [] A;
4458	return CFList (tmp);
4459	}
4460	}
4461	}
4462	if (NTLN.NumCols() == 1)
4463	{
4464	Variable y= Variable (2);
4465	CanonicalForm tmp= F (y - evaluation, y);
4466	CFList source, dest;
4467	tmp= mapDown (tmp, info, source, dest);
4468	delete [] A;
4469	return CFList (tmp);
4470	}
4471
4472	int * zeroOneVecs;
4473	zeroOneVecs= extractZeroOneVecs (NTLN);
4474	bufF= F;
4475	bufUniFactors= factors;
4476	result= extReconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN,
4477	info, evaluation
4478	);
4479	delete [] zeroOneVecs;
4480	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4481	{
4482	F= bufF;
4483	factors= bufUniFactors;
4484	return result;
4485	}
4486
4487	result= CFList();
4488	oldL2= oldL;
4489	oldL *= 2;
4490	if (oldL > l)
4491	{
4492	if (!hitBound)
4493	{
4494	oldL= l;
4495	hitBound= true;
4496	}
4497	else
4498	break;
4499	}
4500	}
4501	delete [] A;
4502	return result;
4503	}
4504
4505	#ifdef HAVE_FLINT
4506	CFList
4507	increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int oldL, int l,
4508	int d, int* bounds, CFArray& bufQ, nmod_mat_t FLINTN,
4509	const Variable& alpha
4510	)
4511	#else
4512	CFList
4513	increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int oldL, int l,
4514	int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN,
4515	const Variable& alpha
4516	)
4517	#endif
4518	{
4519	CFList result= CFList();
4520	CFArray * A= new CFArray [factors.length()];
4521	int extensionDeg= degree (getMipo (alpha));
4522	int oldL2= oldL/2;
4523	bool hitBound= false;
4524	bool useOldQs= false;
4525	#ifdef HAVE_FLINT
4526	if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4527	{
4528	nmod_mat_clear (FLINTN);
4529	nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
4530	for (long i=factors.length()-1; i >= 0; i--)
4531	nmod_mat_entry (FLINTN, i, i)= 1;
4532	}
4533	#else
4534	if (NTLN.NumRows() != factors.length()) //refined factors
4535	ident (NTLN, factors.length());
4536	#endif
4537	CFListIterator j;
4538	CFMatrix C;
4539	CFArray buf;
4540	#ifdef HAVE_FLINT
4541	long rank;
4542	nmod_mat_t FLINTC, FLINTK, null;
4543	#else
4544	mat_zz_p* NTLC, NTLK;
4545	#endif
4546	CanonicalForm bufF, truncF;
4547	CFList bufUniFactors;
4548	Variable y= F.mvar();
4549	while (oldL <= l)
4550	{
4551	j= factors;
4552	truncF= mod (F, power (y, oldL));
4553	if (useOldQs)
4554	{
4555	for (int i= 0; i < factors.length(); i++, j++)
4556	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4557	bufQ[i]
4558	);
4559	}
4560	else
4561	{
4562	for (int i= 0; i < factors.length(); i++, j++)
4563	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4564	}
4565	useOldQs= true;
4566
4567	for (int i= 0; i < d; i++)
4568	{
4569	if (bounds [i] + 1 <= oldL/2)
4570	{
4571	int k= tmin (bounds [i] + 1, oldL/2);
4572	C= CFMatrix ((oldL - k)*extensionDeg, factors.length());
4573	for (int ii= 0; ii < factors.length(); ii++)
4574	{
4575	if (A[ii].size() - 1 >= i)
4576	{
4577	buf= getCoeffs (A[ii] [i], k, alpha);
4578	writeInMatrix (C, buf, ii + 1, 0);
4579	}
4580	}
4581	#ifdef HAVE_FLINT
4582	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
4583	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4584	getCharacteristic());
4585	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4586	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4587	getCharacteristic());
4588	rank= nmod_mat_nullspace (null, FLINTK);
4589	nmod_mat_clear (FLINTK);
4590	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4591	nmod_mat_clear (FLINTC);
4592	nmod_mat_init_set (FLINTC, FLINTN);
4593	nmod_mat_clear (FLINTN);
4594	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4595	getCharacteristic());
4596	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4597
4598	nmod_mat_clear (FLINTC);
4599	nmod_mat_window_clear (FLINTK);
4600	nmod_mat_clear (null);
4601	#else
4602	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4603	NTLK= (NTLC)NTLN;
4604	transpose (NTLK, NTLK);
4605	kernel (NTLK, NTLK);
4606	transpose (NTLK, NTLK);
4607	NTLN *= NTLK;
4608	#endif
4609	#ifdef HAVE_FLINT
4610	if (nmod_mat_ncols (FLINTN) == 1)
4611	#else
4612	if (NTLN.NumCols() == 1)
4613	#endif
4614	{
4615	delete [] A;
4616	return CFList (F);
4617	}
4618	}
4619	}
4620
4621	int * zeroOneVecs;
4622	#ifdef HAVE_FLINT
4623	zeroOneVecs= extractZeroOneVecs (FLINTN);
4624	#else
4625	zeroOneVecs= extractZeroOneVecs (NTLN);
4626	#endif
4627
4628	bufF= F;
4629	bufUniFactors= factors;
4630	#ifdef HAVE_FLINT
4631	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, FLINTN);
4632	#else
4633	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
4634	#endif
4635	delete [] zeroOneVecs;
4636	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4637	{
4638	F= bufF;
4639	factors= bufUniFactors;
4640	delete [] A;
4641	return result;
4642	}
4643
4644	result= CFList();
4645	oldL2= oldL;
4646	oldL *= 2;
4647	if (oldL > l)
4648	{
4649	if (!hitBound)
4650	{
4651	oldL= l;
4652	hitBound= true;
4653	}
4654	else
4655	break;
4656	}
4657	}
4658	delete [] A;
4659	return result;
4660	}
4661
4662	#ifdef HAVE_FLINT
4663	CFList
4664	furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList&
4665	factors, int l, int liftBound, int d, int*
4666	bounds, nmod_mat_t FLINTN, CFList& diophant,
4667	CFMatrix& M, CFArray& Pi, CFArray& bufQ
4668	)
4669	#else
4670	CFList
4671	furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList&
4672	factors, int l, int liftBound, int d, int*
4673	bounds, mat_zz_p& NTLN, CFList& diophant,
4674	CFMatrix& M, CFArray& Pi, CFArray& bufQ
4675	)
4676	#endif
4677	{
4678	CanonicalForm LCF= LC (F, 1);
4679	CFList result;
4680	bool irreducible= false;
4681	CFList bufFactors= factors;
4682	CFArray *A = new CFArray [bufFactors.length()];
4683	bool useOldQs= false;
4684	bool hitBound= false;
4685	int oldL= l;
4686	int stepSize= 8; //TODO choose better step size?
4687	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
4688	#ifdef HAVE_FLINT
4689	if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4690	{
4691	nmod_mat_clear (FLINTN);
4692	nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
4693	for (long i=factors.length()-1; i >= 0; i--)
4694	nmod_mat_entry (FLINTN, i, i)= 1;
4695	}
4696	#else
4697	if (NTLN.NumRows() != factors.length()) //refined factors
4698	ident (NTLN, factors.length());
4699	#endif
4700	CFListIterator j;
4701	CFMatrix C;
4702	CFArray buf;
4703	#ifdef HAVE_FLINT
4704	long rank;
4705	nmod_mat_t FLINTC, FLINTK, null;
4706	#else
4707	mat_zz_p* NTLC, NTLK;
4708	#endif
4709	CanonicalForm bufF, truncF;
4710	Variable y= F.mvar();
4711	while (l <= liftBound)
4712	{
4713	bufFactors.insert (LCF);
4714	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
4715	bufFactors.insert (LCF);
4716	bufFactors.removeFirst();
4717	j= bufFactors;
4718	truncF= mod (F, power (y, l));
4719	if (useOldQs)
4720	{
4721	for (int i= 0; i < bufFactors.length(); i++, j++)
4722	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
4723	bufQ[i]);
4724	}
4725	else
4726	{
4727	for (int i= 0; i < bufFactors.length(); i++, j++)
4728	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
4729	}
4730	for (int i= 0; i < d; i++)
4731	{
4732	if (bounds [i] + 1 <= l/2)
4733	{
4734	int k= tmin (bounds [i] + 1, l/2);
4735	C= CFMatrix (l - k, bufFactors.length());
4736	for (int ii= 0; ii < bufFactors.length(); ii++)
4737	{
4738	if (A[ii].size() - 1 >= i)
4739	{
4740	buf= getCoeffs (A[ii] [i], k);
4741	writeInMatrix (C, buf, ii + 1, 0);
4742	}
4743	}
4744	#ifdef HAVE_FLINT
4745	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
4746	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4747	getCharacteristic());
4748	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4749	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4750	getCharacteristic());
4751	rank= nmod_mat_nullspace (null, FLINTK);
4752	nmod_mat_clear (FLINTK);
4753	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4754	nmod_mat_clear (FLINTC);
4755	nmod_mat_init_set (FLINTC, FLINTN);
4756	nmod_mat_clear (FLINTN);
4757	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4758	getCharacteristic());
4759	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4760
4761	nmod_mat_clear (FLINTC);
4762	nmod_mat_window_clear (FLINTK);
4763	nmod_mat_clear (null);
4764	#else
4765	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4766	NTLK= (NTLC)NTLN;
4767	transpose (NTLK, NTLK);
4768	kernel (NTLK, NTLK);
4769	transpose (NTLK, NTLK);
4770	NTLN *= NTLK;
4771	#endif
4772	#ifdef HAVE_FLINT
4773	if (nmod_mat_ncols (FLINTN) == 1)
4774	#else
4775	if (NTLN.NumCols() == 1)
4776	#endif
4777	{
4778	irreducible= true;
4779	break;
4780	}
4781	}
4782	}
4783
4784	#ifdef HAVE_FLINT
4785	if (nmod_mat_ncols (FLINTN) == 1)
4786	#else
4787	if (NTLN.NumCols() == 1)
4788	#endif
4789	{
4790	irreducible= true;
4791	break;
4792	}
4793
4794	#ifdef HAVE_FLINT
4795	int * zeroOneVecs= extractZeroOneVecs (FLINTN);
4796	#else
4797	int * zeroOneVecs= extractZeroOneVecs (NTLN);
4798	#endif
4799	bufF= F;
4800	#ifdef HAVE_FLINT
4801	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, FLINTN);
4802	#else
4803	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
4804	#endif
4805	delete [] zeroOneVecs;
4806	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
4807	{
4808	F= bufF;
4809	factors= bufFactors;
4810	delete [] A;
4811	return result;
4812	}
4813
4814	#ifdef HAVE_FLINT
4815	if (isReduced (FLINTN))
4816	#else
4817	if (isReduced (NTLN))
4818	#endif
4819	{
4820	int factorsFound= 0;
4821	bufF= F;
4822	#ifdef HAVE_FLINT
4823	int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
4824	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
4825	#else
4826	int* factorsFoundIndex= new int [NTLN.NumCols()];
4827	for (long i= 0; i < NTLN.NumCols(); i++)
4828	#endif
4829	factorsFoundIndex[i]= 0;
4830	#ifdef HAVE_FLINT
4831	if (l < liftBound)
4832	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
4833	factorsFoundIndex, FLINTN, false
4834	);
4835	else
4836	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
4837	degree (LCF), factorsFound, factorsFoundIndex,
4838	FLINTN, false
4839	);
4840
4841	if (nmod_mat_ncols (FLINTN) == result.length())
4842	#else
4843	if (l < liftBound)
4844	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
4845	factorsFoundIndex, NTLN, false
4846	);
4847	else
4848	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
4849	degree (LCF), factorsFound, factorsFoundIndex,
4850	NTLN, false
4851	);
4852
4853	if (NTLN.NumCols() == result.length())
4854	#endif
4855	{
4856	delete [] A;
4857	delete [] factorsFoundIndex;
4858	return result;
4859	}
4860	delete [] factorsFoundIndex;
4861	}
4862	result= CFList();
4863	oldL= l;
4864	stepSize *= 2;
4865	l += stepSize;
4866	if (l > liftBound)
4867	{
4868	if (!hitBound)
4869	{
4870	l= liftBound;
4871	hitBound= true;
4872	}
4873	else
4874	break;
4875	}
4876	}
4877	if (irreducible)
4878	{
4879	delete [] A;
4880	return CFList (F);
4881	}
4882	delete [] A;
4883	factors= bufFactors;
4884	return CFList();
4885	}
4886
4887	//Fq
4888	CFList
4889	furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList&
4890	factors, int l, int liftBound, int d, int*
4891	bounds, mat_zz_pE& NTLN, CFList& diophant,
4892	CFMatrix& M, CFArray& Pi, CFArray& bufQ
4893	)
4894	{
4895	CanonicalForm LCF= LC (F, 1);
4896	CFList result;
4897	bool irreducible= false;
4898	CFList bufFactors= factors;
4899	CFArray *A = new CFArray [bufFactors.length()];
4900	bool useOldQs= false;
4901	bool hitBound= false;
4902	int oldL= l;
4903	int stepSize= 8; //TODO choose better step size?
4904	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
4905	if (NTLN.NumRows() != factors.length()) //refined factors
4906	ident (NTLN, factors.length());
4907	CFListIterator j;
4908	CFArray buf;
4909	mat_zz_pE* NTLC, NTLK;
4910	CanonicalForm bufF, truncF;
4911	Variable y= F.mvar();
4912	while (l <= liftBound)
4913	{
4914	bufFactors.insert (LCF);
4915	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
4916	j= bufFactors;
4917	truncF= mod (F, power (y, l));
4918	if (useOldQs)
4919	{
4920	for (int i= 0; i < bufFactors.length(); i++, j++)
4921	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
4922	bufQ[i]);
4923	}
4924	else
4925	{
4926	for (int i= 0; i < bufFactors.length(); i++, j++)
4927	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
4928	}
4929	for (int i= 0; i < d; i++)
4930	{
4931	if (bounds [i] + 1 <= l/2)
4932	{
4933	int k= tmin (bounds [i] + 1, l/2);
4934	CFMatrix C= CFMatrix (l - k, bufFactors.length());
4935	for (int ii= 0; ii < bufFactors.length(); ii++)
4936	{
4937	if (A[ii].size() - 1 >= i)
4938	{
4939	buf= getCoeffs (A[ii] [i], k);
4940	writeInMatrix (C, buf, ii + 1, 0);
4941	}
4942	}
4943	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
4944	NTLK= (NTLC)NTLN;
4945	transpose (NTLK, NTLK);
4946	kernel (NTLK, NTLK);
4947	transpose (NTLK, NTLK);
4948	NTLN *= NTLK;
4949	if (NTLN.NumCols() == 1)
4950	{
4951	irreducible= true;
4952	break;
4953	}
4954	}
4955	}
4956	if (NTLN.NumCols() == 1)
4957	{
4958	irreducible= true;
4959	break;
4960	}
4961
4962	int * zeroOneVecs= extractZeroOneVecs (NTLN);
4963	bufF= F;
4964	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
4965	delete [] zeroOneVecs;
4966	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
4967	{
4968	F= bufF;
4969	factors= bufFactors;
4970	delete [] A;
4971	return result;
4972	}
4973
4974	if (isReduced (NTLN))
4975	{
4976	int factorsFound= 0;
4977	bufF= F;
4978	int* factorsFoundIndex= new int [NTLN.NumCols()];
4979	for (long i= 0; i < NTLN.NumCols(); i++)
4980	factorsFoundIndex[i]= 0;
4981	if (l < liftBound)
4982	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
4983	factorsFoundIndex, NTLN, false
4984	);
4985	else
4986	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
4987	degree (LCF), factorsFound, factorsFoundIndex,
4988	NTLN, false
4989	);
4990	if (NTLN.NumCols() == result.length())
4991	{
4992	delete [] A;
4993	delete [] factorsFoundIndex;
4994	return result;
4995	}
4996	delete [] factorsFoundIndex;
4997	}
4998	result= CFList();
4999	oldL= l;
5000	stepSize *= 2;
5001	l += stepSize;
5002	if (l > liftBound)
5003	{
5004	if (!hitBound)
5005	{
5006	l= liftBound;
5007	hitBound= true;
5008	}
5009	else
5010	break;
5011	}
5012	}
5013	if (irreducible)
5014	{
5015	delete [] A;
5016	return CFList (F);
5017	}
5018	delete [] A;
5019	factors= bufFactors;
5020	return CFList();
5021	}
5022
5023	//over field extension
5024	CFList
5025	extFurtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList& factors, int l,
5026	int liftBound, int d, int* bounds,
5027	mat_zz_p& NTLN, CFList& diophant,
5028	CFMatrix& M, CFArray& Pi, CFArray& bufQ,
5029	const CanonicalForm& evaluation, const
5030	ExtensionInfo& info, CFList& source,
5031	CFList& dest
5032	)
5033	{
5034	CanonicalForm LCF= LC (F, 1);
5035	CFList result;
5036	bool irreducible= false;
5037	CFList bufFactors= factors;
5038	CFArray *A = new CFArray [bufFactors.length()];
5039	bool useOldQs= false;
5040	bool hitBound= false;
5041	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
5042	int degMipo= degree (getMipo (info.getAlpha()));
5043	Variable alpha= info.getAlpha();
5044	int oldL= l; //be careful
5045	int stepSize= 8;
5046	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l),2);
5047	Variable gamma= info.getBeta();
5048	CanonicalForm primElemAlpha= info.getGamma();
5049	CanonicalForm imPrimElemAlpha= info.getDelta();
5050	if (NTLN.NumRows() != factors.length()) //refined factors
5051	ident (NTLN, factors.length());
5052	Variable y= F.mvar();
5053	CanonicalForm powX, imBasis, bufF, truncF;
5054	CFMatrix Mat, C;
5055	CFIterator iter;
5056	mat_zz_p* NTLMat,*NTLC, NTLK;
5057	CFListIterator j;
5058	CFArray buf;
5059	while (l <= liftBound)
5060	{
5061	bufFactors.insert (LCF);
5062	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
5063
5064	if (GF)
5065	setCharacteristic (getCharacteristic());
5066
5067	powX= power (y-gamma, l);
5068	Mat= CFMatrix (ldegMipo, ldegMipo);
5069	for (int i= 0; i < l*degMipo; i++)
5070	{
5071
5072	imBasis= mod (power (y, i), powX);
5073	imBasis= imBasis (power (y, degMipo), y);
5074	imBasis= imBasis (y, gamma);
5075	iter= imBasis;
5076	for (; iter.hasTerms(); iter++)
5077	Mat (iter.exp()+ 1, i+1)= iter.coeff();
5078	}
5079
5080	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
5081	NTLMat= inv (NTLMat);
5082
5083	if (GF)
5084	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
5085
5086	j= bufFactors;
5087	truncF= mod (F, power (y, l));
5088	if (useOldQs)
5089	{
5090	for (int i= 0; i < bufFactors.length(); i++, j++)
5091	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5092	bufQ[i]);
5093	}
5094	else
5095	{
5096	for (int i= 0; i < bufFactors.length(); i++, j++)
5097	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5098	}
5099	for (int i= 0; i < d; i++)
5100	{
5101	if (bounds [i] + 1 <= l/2)
5102	{
5103	int k= tmin (bounds [i] + 1, l/2);
5104	C= CFMatrix (l*degMipo - k, bufFactors.length());
5105	for (int ii= 0; ii < bufFactors.length(); ii++)
5106	{
5107	if (A[ii].size() - 1 >= i)
5108	{
5109	if (GF)
5110	{
5111	A [ii] [i]= A [ii] [i] (y-evaluation, y);
5112	setCharacteristic (getCharacteristic());
5113	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
5114	if (alpha != gamma)
5115	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
5116	gamma, source, dest
5117	);
5118	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
5119	}
5120	else
5121	{
5122	A [ii] [i]= A [ii] [i] (y-evaluation, y);
5123	if (alpha != gamma)
5124	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
5125	gamma, source, dest
5126	);
5127	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
5128	}
5129	writeInMatrix (C, buf, ii + 1, 0);
5130	}
5131	if (GF)
5132	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
5133	}
5134
5135	if (GF)
5136	setCharacteristic(getCharacteristic());
5137	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
5138	NTLK= (NTLC)NTLN;
5139	transpose (NTLK, NTLK);
5140	kernel (NTLK, NTLK);
5141	transpose (NTLK, NTLK);
5142	NTLN *= NTLK;
5143	if (GF)
5144	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
5145
5146	if (NTLN.NumCols() == 1)
5147	{
5148	irreducible= true;
5149	break;
5150	}
5151	}
5152	}
5153	if (NTLN.NumCols() == 1)
5154	{
5155	irreducible= true;
5156	break;
5157	}
5158
5159	int * zeroOneVecs= extractZeroOneVecs (NTLN);
5160	bufF= F;
5161	result= extReconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN, info,
5162	evaluation
5163	);
5164	delete [] zeroOneVecs;
5165	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5166	{
5167	F= bufF;
5168	factors= bufFactors;
5169	delete [] A;
5170	return result;
5171	}
5172
5173	if (isReduced (NTLN))
5174	{
5175	int factorsFound= 0;
5176	bufF= F;
5177	int* factorsFoundIndex= new int [NTLN.NumCols()];
5178	for (long i= 0; i < NTLN.NumCols(); i++)
5179	factorsFoundIndex[i]= 0;
5180	if (l < degree (bufF) + 1 + degree (LCF))
5181	extReconstructionTry (result, bufF, bufFactors, l, factorsFound,
5182	factorsFoundIndex, NTLN, false, info, evaluation
5183	);
5184	else
5185	extReconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
5186	degree (LCF), factorsFound, factorsFoundIndex,
5187	NTLN, false, info, evaluation
5188	);
5189	if (NTLN.NumCols() == result.length())
5190	{
5191	delete [] A;
5192	delete [] factorsFoundIndex;
5193	return result;
5194	}
5195	delete [] factorsFoundIndex;
5196	}
5197	result= CFList();
5198	oldL= l;
5199	stepSize *= 2;
5200	l += stepSize;
5201	if (l > liftBound)
5202	{
5203	if (!hitBound)
5204	{
5205	l= liftBound;
5206	hitBound= true;
5207	}
5208	else
5209	break;
5210	}
5211	}
5212	if (irreducible)
5213	{
5214	delete [] A;
5215	Variable y= Variable (2);
5216	CanonicalForm tmp= F (y - evaluation, y);
5217	CFList source, dest;
5218	tmp= mapDown (tmp, info, source, dest);
5219	return CFList (tmp);
5220	}
5221	delete [] A;
5222	factors= bufFactors;
5223	return CFList();
5224	}
5225
5226	#ifdef HAVE_FLINT
5227	CFList
5228	furtherLiftingAndIncreasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int
5229	l, int liftBound, int d, int* bounds,
5230	nmod_mat_t FLINTN, CFList& diophant,
5231	CFMatrix& M, CFArray& Pi, CFArray& bufQ,
5232	const Variable& alpha
5233	)
5234	#else
5235	CFList
5236	furtherLiftingAndIncreasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int
5237	l, int liftBound, int d, int* bounds,
5238	mat_zz_p& NTLN, CFList& diophant,
5239	CFMatrix& M, CFArray& Pi, CFArray& bufQ,
5240	const Variable& alpha
5241	)
5242	#endif
5243	{
5244	CanonicalForm LCF= LC (F, 1);
5245	CFList result;
5246	bool irreducible= false;
5247	CFList bufFactors= factors;
5248	CFArray *A = new CFArray [bufFactors.length()];
5249	bool useOldQs= false;
5250	int extensionDeg= degree (getMipo (alpha));
5251	bool hitBound= false;
5252	int oldL= l;
5253	int stepSize= 8; //TODO choose better step size?
5254	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
5255	#ifdef HAVE_FLINT
5256	if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
5257	{
5258	nmod_mat_clear (FLINTN);
5259	nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
5260	for (long i=factors.length()-1; i >= 0; i--)
5261	nmod_mat_entry (FLINTN, i, i)= 1;
5262	}
5263	#else
5264	if (NTLN.NumRows() != factors.length()) //refined factors
5265	ident (NTLN, factors.length());
5266	#endif
5267	CFListIterator j;
5268	CFMatrix C;
5269	#ifdef HAVE_FLINT
5270	long rank;
5271	nmod_mat_t FLINTC, FLINTK, null;
5272	#else
5273	mat_zz_p* NTLC, NTLK;
5274	#endif
5275	CanonicalForm bufF, truncF;
5276	Variable y= F.mvar();
5277	while (l <= liftBound)
5278	{
5279	bufFactors.insert (LCF);
5280	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
5281	j= bufFactors;
5282	truncF= mod (F, power (y, l));
5283	if (useOldQs)
5284	{
5285	for (int i= 0; i < bufFactors.length(); i++, j++)
5286	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5287	bufQ[i]);
5288	}
5289	else
5290	{
5291	for (int i= 0; i < bufFactors.length(); i++, j++)
5292	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5293	}
5294	for (int i= 0; i < d; i++)
5295	{
5296	if (bounds [i] + 1 <= l/2)
5297	{
5298	int k= tmin (bounds [i] + 1, l/2);
5299	C= CFMatrix ((l - k)*extensionDeg, bufFactors.length());
5300	for (int ii= 0; ii < bufFactors.length(); ii++)
5301	{
5302	CFArray buf;
5303	if (A[ii].size() - 1 >= i)
5304	{
5305	buf= getCoeffs (A[ii] [i], k, alpha);
5306	writeInMatrix (C, buf, ii + 1, 0);
5307	}
5308	}
5309	#ifdef HAVE_FLINT
5310	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
5311	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5312	getCharacteristic());
5313	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5314	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5315	getCharacteristic());
5316	rank= nmod_mat_nullspace (null, FLINTK);
5317	nmod_mat_clear (FLINTK);
5318	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5319	nmod_mat_clear (FLINTC);
5320	nmod_mat_init_set (FLINTC, FLINTN);
5321	nmod_mat_clear (FLINTN);
5322	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5323	getCharacteristic());
5324	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5325
5326	nmod_mat_clear (FLINTC);
5327	nmod_mat_window_clear (FLINTK);
5328	nmod_mat_clear (null);
5329	#else
5330	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
5331	NTLK= (NTLC)NTLN;
5332	transpose (NTLK, NTLK);
5333	kernel (NTLK, NTLK);
5334	transpose (NTLK, NTLK);
5335	NTLN *= NTLK;
5336	#endif
5337	#ifdef HAVE_FLINT
5338	if (nmod_mat_ncols (FLINTN) == 1)
5339	#else
5340	if (NTLN.NumCols() == 1)
5341	#endif
5342	{
5343	irreducible= true;
5344	break;
5345	}
5346	}
5347	}
5348	#ifdef HAVE_FLINT
5349	if (nmod_mat_ncols (FLINTN) == 1)
5350	#else
5351	if (NTLN.NumCols() == 1)
5352	#endif
5353	{
5354	irreducible= true;
5355	break;
5356	}
5357
5358	#ifdef HAVE_FLINT
5359	int * zeroOneVecs= extractZeroOneVecs (FLINTN);
5360	#else
5361	int * zeroOneVecs= extractZeroOneVecs (NTLN);
5362	#endif
5363	CanonicalForm bufF= F;
5364	#ifdef HAVE_FLINT
5365	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, FLINTN);
5366	#else
5367	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
5368	#endif
5369	delete [] zeroOneVecs;
5370	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5371	{
5372	F= bufF;
5373	factors= bufFactors;
5374	delete [] A;
5375	return result;
5376	}
5377
5378	#ifdef HAVE_FLINT
5379	if (isReduced (FLINTN))
5380	#else
5381	if (isReduced (NTLN))
5382	#endif
5383	{
5384	int factorsFound= 0;
5385	bufF= F;
5386	#ifdef HAVE_FLINT
5387	int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
5388	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5389	#else
5390	int* factorsFoundIndex= new int [NTLN.NumCols()];
5391	for (long i= 0; i < NTLN.NumCols(); i++)
5392	#endif
5393	factorsFoundIndex[i]= 0;
5394	#ifdef HAVE_FLINT
5395	if (l < degree (bufF) + 1 + degree (LCF))
5396	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
5397	factorsFoundIndex, FLINTN, false
5398	);
5399	else
5400	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
5401	degree (LCF), factorsFound, factorsFoundIndex,
5402	FLINTN, false
5403	);
5404	if (nmod_mat_ncols (FLINTN) == result.length())
5405	#else
5406	if (l < degree (bufF) + 1 + degree (LCF))
5407	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
5408	factorsFoundIndex, NTLN, false
5409	);
5410	else
5411	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
5412	degree (LCF), factorsFound, factorsFoundIndex,
5413	NTLN, false
5414	);
5415	if (NTLN.NumCols() == result.length())
5416	#endif
5417	{
5418	delete [] A;
5419	delete [] factorsFoundIndex;
5420	return result;
5421	}
5422	delete [] factorsFoundIndex;
5423	}
5424	result= CFList();
5425	oldL= l;
5426	stepSize *= 2;
5427	l += stepSize;
5428	if (l > liftBound)
5429	{
5430	if (!hitBound)
5431	{
5432	l= liftBound;
5433	hitBound= true;
5434	}
5435	else
5436	break;
5437	}
5438	}
5439	if (irreducible)
5440	{
5441	delete [] A;
5442	return CFList (F);
5443	}
5444	delete [] A;
5445	factors= bufFactors;
5446	return CFList();
5447	}
5448
5449	void
5450	refineAndRestartLift (const CanonicalForm& F, const mat_zz_p& NTLN, int
5451	liftBound, int l, CFList& factors, CFMatrix& M, CFArray&
5452	Pi, CFList& diophant
5453	)
5454	{
5455	CFList bufFactors;
5456	Variable y= Variable (2);
5457	CanonicalForm LCF= LC (F, 1);
5458	CFListIterator iter;
5459	CanonicalForm buf;
5460	for (long i= 1; i <= NTLN.NumCols(); i++)
5461	{
5462	iter= factors;
5463	buf= 1;
5464	for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
5465	{
5466	if (!IsZero (NTLN (j,i)))
5467	buf= mulNTL (buf, mod (iter.getItem(), y));
5468	}
5469	bufFactors.append (buf);
5470	}
5471	factors= bufFactors;
5472	M= CFMatrix (liftBound, factors.length());
5473	Pi= CFArray();
5474	diophant= CFList();
5475	factors.insert (LCF);
5476	henselLift12 (F, factors, l, Pi, diophant, M);
5477	}
5478
5479	#ifdef HAVE_FLINT
5480	void
5481	refineAndRestartLift (const CanonicalForm& F, const nmod_mat_t FLINTN, int
5482	liftBound, int l, CFList& factors, CFMatrix& M, CFArray&
5483	Pi, CFList& diophant
5484	)
5485	{
5486	CFList bufFactors;
5487	Variable y= Variable (2);
5488	CanonicalForm LCF= LC (F, 1);
5489	CFListIterator iter;
5490	CanonicalForm buf;
5491	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5492	{
5493	iter= factors;
5494	buf= 1;
5495	for (long j= 0; j < nmod_mat_nrows (FLINTN); j++, iter++)
5496	{
5497	if (!(nmod_mat_entry (FLINTN,j,i) == 0))
5498	buf= mulNTL (buf, mod (iter.getItem(), y));
5499	}
5500	bufFactors.append (buf);
5501	}
5502	factors= bufFactors;
5503	M= CFMatrix (liftBound, factors.length());
5504	Pi= CFArray();
5505	diophant= CFList();
5506	factors.insert (LCF);
5507	henselLift12 (F, factors, l, Pi, diophant, M);
5508	}
5509	#endif
5510
5511	void
5512	refineAndRestartLift (const CanonicalForm& F, const mat_zz_pE& NTLN, int
5513	liftBound, int l, CFList& factors, CFMatrix& M, CFArray&
5514	Pi, CFList& diophant
5515	)
5516	{
5517	CFList bufFactors;
5518	Variable y= Variable (2);
5519	CanonicalForm LCF= LC (F, 1);
5520	CFListIterator iter;
5521	CanonicalForm buf;
5522	for (long i= 1; i <= NTLN.NumCols(); i++)
5523	{
5524	iter= factors;
5525	buf= 1;
5526	for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
5527	{
5528	if (!IsZero (NTLN (j,i)))
5529	buf= mulNTL (buf, mod (iter.getItem(), y));
5530	}
5531	bufFactors.append (buf);
5532	}
5533	factors= bufFactors;
5534	M= CFMatrix (liftBound, factors.length());
5535	Pi= CFArray();
5536	diophant= CFList();
5537	factors.insert (LCF);
5538	henselLift12 (F, factors, l, Pi, diophant, M);
5539	}
5540
5541	#ifdef HAVE_FLINT
5542	CFList
5543	earlyReconstructionAndLifting (const CanonicalForm& F, const nmod_mat_t N,
5544	CanonicalForm& bufF, CFList& factors, int& l,
5545	int& factorsFound, bool beenInThres, CFMatrix& M,
5546	CFArray& Pi, CFList& diophant, bool symmetric,
5547	const CanonicalForm& evaluation
5548	)
5549	#else
5550	CFList
5551	earlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_p& N,
5552	CanonicalForm& bufF, CFList& factors, int& l,
5553	int& factorsFound, bool beenInThres, CFMatrix& M,
5554	CFArray& Pi, CFList& diophant, bool symmetric,
5555	const CanonicalForm& evaluation
5556	)
5557	#endif
5558	{
5559	int sizeOfLiftPre;
5560	int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
5561
5562	Variable y= F.mvar();
5563	factorsFound= 0;
5564	CanonicalForm LCF= LC (F, 1);
5565	CFList result;
5566	int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
5567	#ifdef HAVE_FLINT
5568	nmod_mat_t FLINTN;
5569	nmod_mat_init_set (FLINTN, N);
5570	int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
5571	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5572	#else
5573	mat_zz_p NTLN= N;
5574	int * factorsFoundIndex= new int [NTLN.NumCols()];
5575	for (long i= 0; i < NTLN.NumCols(); i++)
5576	#endif
5577	factorsFoundIndex [i]= 0;
5578
5579	if (degree (F) + 1 > smallFactorDeg)
5580	{
5581	if (l < smallFactorDeg)
5582	{
5583	factors.insert (LCF);
5584	henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
5585	l= smallFactorDeg;
5586	}
5587	#ifdef HAVE_FLINT
5588	reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5589	factorsFoundIndex, FLINTN, beenInThres
5590	);
5591	if (result.length() == nmod_mat_ncols (FLINTN))
5592	{
5593	nmod_mat_clear (FLINTN);
5594	#else
5595	reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5596	factorsFoundIndex, NTLN, beenInThres
5597	);
5598	if (result.length() == NTLN.NumCols())
5599	{
5600	#endif
5601	delete [] liftPre;
5602	delete [] factorsFoundIndex;
5603	return result;
5604	}
5605	}
5606
5607	int i= sizeOfLiftPre - 1;
5608	int dummy= 1;
5609	if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
5610	{
5611	while (i > 0)
5612	{
5613	if (l < liftPre[i-1] + 1)
5614	{
5615	factors.insert (LCF);
5616	henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
5617	l= liftPre[i-1] + 1;
5618	}
5619	else
5620	{
5621	i--;
5622	if (i != 0)
5623	continue;
5624	}
5625	#ifdef HAVE_FLINT
5626	reconstructionTry (result, bufF, factors, l, factorsFound,
5627	factorsFoundIndex, FLINTN, beenInThres
5628	);
5629	if (result.length() == nmod_mat_ncols (FLINTN))
5630	{
5631	nmod_mat_clear (FLINTN);
5632	#else
5633	reconstructionTry (result, bufF, factors, l, factorsFound,
5634	factorsFoundIndex, NTLN, beenInThres
5635	);
5636	if (result.length() == NTLN.NumCols())
5637	{
5638	#endif
5639	delete [] liftPre;
5640	delete [] factorsFoundIndex;
5641	return result;
5642	}
5643	i--;
5644	}
5645	}
5646	else
5647	{
5648	i= 1;
5649	while ((degree (F,y)/4)*i + 4 <= smallFactorDeg)
5650	i++;
5651	while (i < 5)
5652	{
5653	dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4);
5654	if (l < dummy)
5655	{
5656	factors.insert (LCF);
5657	henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
5658	l= dummy;
5659	if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
5660	LC (F,1).inCoeffDomain() &&
5661	(degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
5662	{
5663	Variable x= Variable (1);
5664	CanonicalForm g, h, gg, hh, multiplier1, multiplier2, check1, check2;
5665	int m= degree (F)/4+1;
5666	g= factors.getFirst();
5667	h= factors.getLast();
5668	g= mod (g, power (y,m));
5669	h= mod (h, power (y,m));
5670	g= g (y-evaluation, y);
5671	h= h (y-evaluation, y);
5672	gg= mod (swapvar (g,x,y),power (x,m));
5673	gg= gg (y + evaluation, y);
5674	multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
5675	gg= div (gg, power (y,m));
5676	gg= gg*power (y,m);
5677	hh= mod (swapvar (h,x,y),power (x,m));
5678	hh= hh (y + evaluation, y);
5679	multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
5680	hh= div (hh, power (y,m));
5681	hh= hh*power (y,m);
5682	gg= multiplier1*gg+mod (factors.getLast(), power (y,m));
5683	hh= multiplier2*hh+mod (factors.getFirst(), power (y,m));
5684	check1= gg (y-evaluation,y);
5685	check2= hh (y-evaluation,y);
5686	check1= swapvar (check1, x, y);
5687	if (check1/Lc (check1) == check2/Lc (check2))
5688	{
5689	#ifdef HAVE_FLINT
5690	nmod_mat_clear (FLINTN);
5691	#endif
5692	result.append (gg);
5693	result.append (hh);
5694	delete [] liftPre;
5695	delete [] factorsFoundIndex;
5696	return result;
5697	}
5698	}
5699	}
5700	else
5701	{
5702	i++;
5703	if (i < 5)
5704	continue;
5705	}
5706	#ifdef HAVE_FLINT
5707	reconstructionTry (result, bufF, factors, l, factorsFound,
5708	factorsFoundIndex, FLINTN, beenInThres
5709	);
5710	if (result.length() == nmod_mat_ncols (FLINTN))
5711	{
5712	nmod_mat_clear (FLINTN);
5713	#else
5714	reconstructionTry (result, bufF, factors, l, factorsFound,
5715	factorsFoundIndex, NTLN, beenInThres
5716	);
5717	if (result.length() == NTLN.NumCols())
5718	{
5719	#endif
5720	delete [] liftPre;
5721	delete [] factorsFoundIndex;
5722	return result;
5723	}
5724	i++;
5725	}
5726	}
5727
5728	#ifdef HAVE_FLINT
5729	nmod_mat_clear (FLINTN);
5730	#endif
5731	delete [] liftPre;
5732	delete [] factorsFoundIndex;
5733	return result;
5734	}
5735
5736	CFList
5737	earlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_pE& N,
5738	CanonicalForm& bufF, CFList& factors, int& l,
5739	int& factorsFound, bool beenInThres, CFMatrix& M,
5740	CFArray& Pi, CFList& diophant, bool symmetric,
5741	const CanonicalForm& evaluation
5742	)
5743	{
5744	int sizeOfLiftPre;
5745	int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
5746	Variable y= F.mvar();
5747	factorsFound= 0;
5748	CanonicalForm LCF= LC (F, 1);
5749	CFList result;
5750	int smallFactorDeg= 11;
5751	mat_zz_pE NTLN= N;
5752	int * factorsFoundIndex= new int [NTLN.NumCols()];
5753	for (long i= 0; i < NTLN.NumCols(); i++)
5754	factorsFoundIndex [i]= 0;
5755
5756	if (degree (F) + 1 > smallFactorDeg)
5757	{
5758	if (l < smallFactorDeg)
5759	{
5760	factors.insert (LCF);
5761	henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
5762	l= smallFactorDeg;
5763	}
5764	reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5765	factorsFoundIndex, NTLN, beenInThres
5766	);
5767	if (result.length() == NTLN.NumCols())
5768	{
5769	delete [] liftPre;
5770	delete [] factorsFoundIndex;
5771	return result;
5772	}
5773	}
5774
5775	int i= sizeOfLiftPre - 1;
5776	int dummy= 1;
5777	if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
5778	{
5779	while (i > 0)
5780	{
5781	if (l < liftPre[i-1] + 1)
5782	{
5783	factors.insert (LCF);
5784	henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
5785	l= liftPre[i-1] + 1;
5786	}
5787	else
5788	{
5789	i--;
5790	if (i != 0)
5791	continue;
5792	}
5793	reconstructionTry (result, bufF, factors, l, factorsFound,
5794	factorsFoundIndex, NTLN, beenInThres
5795	);
5796	if (result.length() == NTLN.NumCols())
5797	{
5798	delete [] liftPre;
5799	delete [] factorsFoundIndex;
5800	return result;
5801	}
5802	i--;
5803	}
5804	}
5805	else
5806	{
5807	i= 1;
5808	while ((degree (F,y)/4)*i + 4 <= smallFactorDeg)
5809	i++;
5810	while (i < 5)
5811	{
5812	dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4);
5813	if (l < dummy)
5814	{
5815	factors.insert (LCF);
5816	henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
5817	l= dummy;
5818	if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
5819	LC (F,1).inCoeffDomain() &&
5820	(degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
5821	{
5822	Variable x= Variable (1);
5823	CanonicalForm g, h, gg, hh, multiplier1, multiplier2, check1, check2;
5824	int m= degree (F)/4+1;
5825	g= factors.getFirst();
5826	h= factors.getLast();
5827	g= mod (g, power (y,m));
5828	h= mod (h, power (y,m));
5829	g= g (y-evaluation, y);
5830	h= h (y-evaluation, y);
5831	gg= mod (swapvar (g,x,y),power (x,m));
5832	gg= gg (y + evaluation, y);
5833	multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
5834	gg= div (gg, power (y,m));
5835	gg= gg*power (y,m);
5836	hh= mod (swapvar (h,x,y),power (x,m));
5837	hh= hh (y + evaluation, y);
5838	multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
5839	hh= div (hh, power (y,m));
5840	hh= hh*power (y,m);
5841	gg= multiplier1*gg+mod (factors.getLast(), power (y,m));
5842	hh= multiplier2*hh+mod (factors.getFirst(), power (y,m));
5843	check1= gg (y-evaluation,y);
5844	check2= hh (y-evaluation,y);
5845	check1= swapvar (check1, x, y);
5846	if (check1/Lc (check1) == check2/Lc (check2))
5847	{
5848	result.append (gg);
5849	result.append (hh);
5850	delete [] liftPre;
5851	delete [] factorsFoundIndex;
5852	return result;
5853	}
5854	}
5855	}
5856	else
5857	{
5858	i++;
5859	if (i < 5)
5860	continue;
5861	}
5862	reconstructionTry (result, bufF, factors, l, factorsFound,
5863	factorsFoundIndex, NTLN, beenInThres
5864	);
5865	if (result.length() == NTLN.NumCols())
5866	{
5867	delete [] liftPre;
5868	delete [] factorsFoundIndex;
5869	return result;
5870	}
5871	i++;
5872	}
5873	}
5874
5875	delete [] liftPre;
5876	delete [] factorsFoundIndex;
5877	return result;
5878	}
5879
5880	//over field extension
5881	CFList
5882	extEarlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_p& N,
5883	CanonicalForm& bufF, CFList& factors, int& l,
5884	int& factorsFound, bool beenInThres, CFMatrix&
5885	M, CFArray& Pi, CFList& diophant, const
5886	ExtensionInfo& info, const CanonicalForm&
5887	evaluation
5888	)
5889	{
5890	int sizeOfLiftPre;
5891	int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
5892	Variable y= F.mvar();
5893	factorsFound= 0;
5894	CanonicalForm LCF= LC (F, 1);
5895	CFList result;
5896	int smallFactorDeg= 11;
5897	mat_zz_p NTLN= N;
5898	int * factorsFoundIndex= new int [NTLN.NumCols()];
5899	for (long i= 0; i < NTLN.NumCols(); i++)
5900	factorsFoundIndex [i]= 0;
5901
5902	if (degree (F) + 1 > smallFactorDeg)
5903	{
5904	if (l < smallFactorDeg)
5905	{
5906	factors.insert (LCF);
5907	henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
5908	l= smallFactorDeg;
5909	}
5910	extReconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5911	factorsFoundIndex, NTLN, beenInThres, info,
5912	evaluation
5913	);
5914	if (result.length() == NTLN.NumCols())
5915	{
5916	delete [] liftPre;
5917	delete [] factorsFoundIndex;
5918	return result;
5919	}
5920	}
5921
5922	int i= sizeOfLiftPre - 1;
5923	int dummy= 1;
5924	if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
5925	{
5926	while (i > 0)
5927	{
5928	if (l < liftPre[i-1] + 1)
5929	{
5930	factors.insert (LCF);
5931	henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
5932	l= liftPre[i-1] + 1;
5933	}
5934	else
5935	{
5936	i--;
5937	if (i != 0)
5938	continue;
5939	}
5940	extReconstructionTry (result, bufF, factors, l, factorsFound,
5941	factorsFoundIndex, NTLN, beenInThres, info,
5942	evaluation
5943	);
5944	if (result.length() == NTLN.NumCols())
5945	{
5946	delete [] liftPre;
5947	delete [] factorsFoundIndex;
5948	return result;
5949	}
5950	i--;
5951	}
5952	}
5953	else
5954	{
5955	i= 1;
5956	while ((degree (F,y)/4)*i + 4 <= smallFactorDeg)
5957	i++;
5958	while (i < 5)
5959	{
5960	dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4);
5961	if (l < dummy)
5962	{
5963	factors.insert (LCF);
5964	henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
5965	l= dummy;
5966	}
5967	else
5968	{
5969	i++;
5970	if (i < 5)
5971	continue;
5972	}
5973	extReconstructionTry (result, bufF, factors, l, factorsFound,
5974	factorsFoundIndex, NTLN, beenInThres, info,
5975	evaluation
5976	);
5977	if (result.length() == NTLN.NumCols())
5978	{
5979	delete [] liftPre;
5980	delete [] factorsFoundIndex;
5981	return result;
5982	}
5983	i++;
5984	}
5985	}
5986
5987	delete [] liftPre;
5988	delete [] factorsFoundIndex;
5989	return result;
5990	}
5991
5992	CFList
5993	sieveSmallFactors (const CanonicalForm& G, CFList& uniFactors, DegreePattern&
5994	degPat, CanonicalForm& H, CFList& diophant, CFArray& Pi,
5995	CFMatrix& M, bool& success, int d
5996	)
5997	{
5998	CanonicalForm F= G;
5999	CFList bufUniFactors= uniFactors;
6000	�