Context Navigation

facFqBivar.cc @ f659855

spielwiese

Last change on this file since f659855 was f659855, checked in by Martin Lee <martinlee84@…>, 11 years ago
fix: wrong deletion of FLINT matrices
Property mode set to `100644`
File size: 222.4 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	if (fac_NTL_char != getCharacteristic())
158	{
159	fac_NTL_char= getCharacteristic();
160	zz_p::init (getCharacteristic());
161	}
162	if (GF)
163	{
164	int k= getGFDegree();
165	char cGFName= gf_name;
166	CanonicalForm mipo= gf_mipo;
167	setCharacteristic (getCharacteristic());
168	Variable beta= rootOf (mipo.mapinto());
169	CanonicalForm buf= GF2FalphaRep (A, beta);
170	if (getCharacteristic() > 2)
171	{
172	zz_pX NTLMipo= convertFacCF2NTLzzpX (mipo.mapinto());
173	zz_pE::init (NTLMipo);
174	zz_pEX NTLA= convertFacCF2NTLzz_pEX (buf, NTLMipo);
175	MakeMonic (NTLA);
176	vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
177	zz_pE multi= to_zz_pE (1);
178	factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
179	x, beta);
180	}
181	else
182	{
183	GF2X NTLMipo= convertFacCF2NTLGF2X (mipo.mapinto());
184	GF2E::init (NTLMipo);
185	GF2EX NTLA= convertFacCF2NTLGF2EX (buf, NTLMipo);
186	MakeMonic (NTLA);
187	vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
188	GF2E multi= to_GF2E (1);
189	factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
190	x, beta);
191	}
192	setCharacteristic (getCharacteristic(), k, cGFName);
193	for (CFFListIterator i= factorsA; i.hasItem(); i++)
194	{
195	buf= i.getItem().factor();
196	buf= Falpha2GFRep (buf);
197	i.getItem()= CFFactor (buf, i.getItem().exp());
198	}
199	}
200	else if (alpha.level() != 1)
201	{
202	if (getCharacteristic() > 2)
203	{
204	zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
205	zz_pE::init (NTLMipo);
206	zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
207	MakeMonic (NTLA);
208	vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
209	zz_pE multi= to_zz_pE (1);
210	factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
211	x, alpha);
212	}
213	else
214	{
215	GF2X NTLMipo= convertFacCF2NTLGF2X (getMipo (alpha));
216	GF2E::init (NTLMipo);
217	GF2EX NTLA= convertFacCF2NTLGF2EX (A, NTLMipo);
218	MakeMonic (NTLA);
219	vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
220	GF2E multi= to_GF2E (1);
221	factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
222	x, alpha);
223	}
224	}
225	else
226	{
227	#ifdef HAVE_FLINT
228	nmod_poly_t FLINTA;
229	convertFacCF2nmod_poly_t (FLINTA, A);
230	nmod_poly_factor_t result;
231	nmod_poly_factor_init (result);
232	mp_limb_t leadingCoeff= nmod_poly_factor (result, FLINTA);
233	factorsA= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, x);
234	if (factorsA.getFirst().factor().inCoeffDomain())
235	factorsA.removeFirst();
236	nmod_poly_factor_clear (result);
237	nmod_poly_clear (FLINTA);
238	#else
239	if (getCharacteristic() > 2)
240	{
241	zz_pX NTLA= convertFacCF2NTLzzpX (A);
242	MakeMonic (NTLA);
243	vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
244	zz_p multi= to_zz_p (1);
245	factorsA= convertNTLvec_pair_zzpX_long2FacCFFList (NTLFactorsA, multi,
246	x);
247	}
248	else
249	{
250	GF2X NTLA= convertFacCF2NTLGF2X (A);
251	vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
252	GF2 multi= to_GF2 (1);
253	factorsA= convertNTLvec_pair_GF2X_long2FacCFFList (NTLFactorsA, multi,
254	x);
255	}
256	#endif
257	}
258	CFList uniFactors;
259	for (CFFListIterator i= factorsA; i.hasItem(); i++)
260	uniFactors.append (i.getItem().factor());
261	return uniFactors;
262	}
263
264	/// naive factor recombination as decribed in "Factoring
265	/// multivariate polynomials over a finite field" by L Bernardin.
266	CFList
267	extFactorRecombination (CFList& factors, CanonicalForm& F,
268	const CanonicalForm& N, const ExtensionInfo& info,
269	DegreePattern& degs, const CanonicalForm& eval, int s,
270	int thres)
271	{
272	if (factors.length() == 0)
273	{
274	F= 1;
275	return CFList();
276	}
277	if (F.inCoeffDomain())
278	return CFList();
279
280	Variable alpha= info.getAlpha();
281	Variable beta= info.getBeta();
282	CanonicalForm gamma= info.getGamma();
283	CanonicalForm delta= info.getDelta();
284	int k= info.getGFDegree();
285
286	CanonicalForm M= N;
287	int l= degree (N);
288	Variable y= F.mvar();
289	Variable x= Variable (1);
290	CFList source, dest;
291	if (degs.getLength() <= 1 \|\| factors.length() == 1)
292	{
293	CFList result= CFList(mapDown (F(y-eval, y), info, source, dest));
294	F= 1;
295	return result;
296	}
297
298	DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, M) == F " <<
299	(mod (LC (F, 1)prodMod (factors, M), M)/Lc (mod (LC (F, 1)prodMod (factors, M), M)) == F/Lc (F)));
300	int degMipoBeta= 1;
301	if (!k && beta.level() != 1)
302	degMipoBeta= degree (getMipo (beta));
303
304	CFList T, S, Diff;
305	T= factors;
306
307	CFList result;
308	CanonicalForm buf, buf2, quot;
309
310	buf= F;
311
312	CanonicalForm g, LCBuf= LC (buf, x);
313	int * v= new int [T.length()];
314	for (int i= 0; i < T.length(); i++)
315	v[i]= 0;
316
317	CFArray TT;
318	DegreePattern bufDegs1, bufDegs2;
319	bufDegs1= degs;
320	int subsetDeg;
321	TT= copy (factors);
322	bool nosubset= false;
323	bool recombination= false;
324	bool trueFactor= false;
325	CanonicalForm test;
326	CanonicalForm buf0= buf (0, x)*LCBuf;
327	while (T.length() >= 2*s && s <= thres)
328	{
329	while (nosubset == false)
330	{
331	if (T.length() == s)
332	{
333	delete [] v;
334	if (recombination)
335	{
336	T.insert (LCBuf);
337	g= prodMod (T, M);
338	T.removeFirst();
339	g /= content(g);
340	g= g (y - eval, y);
341	g /= Lc (g);
342	appendTestMapDown (result, g, info, source, dest);
343	F= 1;
344	return result;
345	}
346	else
347	{
348	appendMapDown (result, F (y - eval, y), info, source, dest);
349	F= 1;
350	return result;
351	}
352	}
353	S= subset (v, s, TT, nosubset);
354	if (nosubset) break;
355	subsetDeg= subsetDegree (S);
356	// skip those combinations that are not possible
357	if (!degs.find (subsetDeg))
358	continue;
359	else
360	{
361	test= prodMod0 (S, M);
362	test *= LCBuf;
363	test = mod (test, M);
364	if (fdivides (test, buf0))
365	{
366	S.insert (LCBuf);
367	g= prodMod (S, M);
368	S.removeFirst();
369	g /= content (g, x);
370	if (fdivides (g, buf, quot))
371	{
372	buf2= g (y - eval, y);
373	buf2 /= Lc (buf2);
374
375	if (!k && beta.level() == 1)
376	{
377	if (degree (buf2, alpha) < degMipoBeta)
378	{
379	buf= quot;
380	LCBuf= LC (buf, x);
381	recombination= true;
382	appendTestMapDown (result, buf2, info, source, dest);
383	trueFactor= true;
384	}
385	}
386	else
387	{
388	if (!isInExtension (buf2, gamma, k, delta, source, dest))
389	{
390	buf= quot;
391	LCBuf= LC (buf, x);
392	recombination= true;
393	appendTestMapDown (result, buf2, info, source, dest);
394	trueFactor= true;
395	}
396	}
397	if (trueFactor)
398	{
399	T= Difference (T, S);
400	l -= degree (g);
401	M= power (y, l);
402	buf0= buf (0, x)*LCBuf;
403
404	// compute new possible degree pattern
405	bufDegs2= DegreePattern (T);
406	bufDegs1.intersect (bufDegs2);
407	bufDegs1.refine ();
408	if (T.length() < 2*s \|\| T.length() == s \|\|
409	bufDegs1.getLength() == 1)
410	{
411	delete [] v;
412	if (recombination)
413	{
414	buf= buf (y-eval,y);
415	buf /= Lc (buf);
416	appendTestMapDown (result, buf, info, source,
417	dest);
418	F= 1;
419	return result;
420	}
421	else
422	{
423	appendMapDown (result, F (y - eval, y), info, source, dest);
424	F= 1;
425	return result;
426	}
427	}
428	trueFactor= false;
429	TT= copy (T);
430	indexUpdate (v, s, T.length(), nosubset);
431	if (nosubset) break;
432	}
433	}
434	}
435	}
436	}
437	s++;
438	if (T.length() < 2*s \|\| T.length() == s)
439	{
440	delete [] v;
441	if (recombination)
442	{
443	buf= buf (y-eval,y);
444	buf /= Lc (buf);
445	appendTestMapDown (result, buf, info, source, dest);
446	F= 1;
447	return result;
448	}
449	else
450	{
451	appendMapDown (result, F (y - eval, y), info, source, dest);
452	F= 1;
453	return result;
454	}
455	}
456	for (int i= 0; i < T.length(); i++)
457	v[i]= 0;
458	nosubset= false;
459	}
460	if (T.length() < 2*s)
461	{
462	appendMapDown (result, F (y - eval, y), info, source, dest);
463	F= 1;
464	delete [] v;
465	return result;
466	}
467
468	if (s > thres)
469	{
470	factors= T;
471	F= buf;
472	degs= bufDegs1;
473	}
474
475	delete [] v;
476	return result;
477	}
478
479	/// naive factor recombination as decribed in "Factoring
480	/// multivariate polynomials over a finite field" by L Bernardin.
481	CFList
482	factorRecombination (CFList& factors, CanonicalForm& F,
483	const CanonicalForm& N, DegreePattern& degs, int s,
484	int thres, const modpk& b
485	)
486	{
487	if (factors.length() == 0)
488	{
489	F= 1;
490	return CFList ();
491	}
492	if (F.inCoeffDomain())
493	return CFList();
494	if (degs.getLength() <= 1 \|\| factors.length() == 1)
495	{
496	CFList result= CFList (F);
497	F= 1;
498	return result;
499	}
500	#ifdef DEBUGOUTPUT
501	if (b.getp() == 0)
502	DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
503	(mod (LC (F, 1)prodMod (factors, N),N)/Lc (mod (LC (F, 1)prodMod (factors, N),N)) == F/Lc(F)));
504	else
505	DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
506	(mod (b(LC (F, 1)prodMod (factors, N)),N)/Lc (mod (b(LC (F, 1)prodMod (factors, N)),N)) == F/Lc(F)));
507	#endif
508
509	CFList T, S;
510
511	CanonicalForm M= N;
512	int l= degree (N);
513	T= factors;
514	CFList result;
515	Variable y= Variable (2);
516	Variable x= Variable (1);
517	CanonicalForm LCBuf= LC (F, x);
518	CanonicalForm g, quot, buf= F;
519	int * v= new int [T.length()];
520	for (int i= 0; i < T.length(); i++)
521	v[i]= 0;
522	bool nosubset= false;
523	CFArray TT;
524	DegreePattern bufDegs1, bufDegs2;
525	bufDegs1= degs;
526	int subsetDeg;
527	TT= copy (factors);
528	bool recombination= false;
529	CanonicalForm test;
530	bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) \|\|
531	getCharacteristic() > 0;
532	if (!isRat)
533	On (SW_RATIONAL);
534	CanonicalForm buf0= mulNTL (buf (0, x), LCBuf);
535	if (!isRat)
536	Off (SW_RATIONAL);
537	while (T.length() >= 2*s && s <= thres)
538	{
539	while (nosubset == false)
540	{
541	if (T.length() == s)
542	{
543	delete [] v;
544	if (recombination)
545	{
546	T.insert (LCBuf);
547	g= prodMod (T, M);
548	if (b.getp() != 0)
549	g= b(g);
550	T.removeFirst();
551	result.append (g/content (g, x));
552	F= 1;
553	return result;
554	}
555	else
556	{
557	result= CFList (F);
558	F= 1;
559	return result;
560	}
561	}
562	S= subset (v, s, TT, nosubset);
563	if (nosubset) break;
564	subsetDeg= subsetDegree (S);
565	// skip those combinations that are not possible
566	if (!degs.find (subsetDeg))
567	continue;
568	else
569	{
570	if (!isRat)
571	On (SW_RATIONAL);
572	test= prodMod0 (S, M);
573	if (!isRat)
574	{
575	test *= bCommonDen (test);
576	Off (SW_RATIONAL);
577	}
578	test= mulNTL (test, LCBuf, b);
579	test= mod (test, M);
580	if (uniFdivides (test, buf0))
581	{
582	if (!isRat)
583	On (SW_RATIONAL);
584	S.insert (LCBuf);
585	g= prodMod (S, M);
586	S.removeFirst();
587	if (!isRat)
588	{
589	g *= bCommonDen(g);
590	Off (SW_RATIONAL);
591	}
592	if (b.getp() != 0)
593	g= b(g);
594	if (!isRat)
595	On (SW_RATIONAL);
596	g /= content (g, x);
597	if (!isRat)
598	{
599	On (SW_RATIONAL);
600	g *= bCommonDen (g);
601	Off (SW_RATIONAL);
602	g /= icontent (g);
603	On (SW_RATIONAL);
604	}
605	if (fdivides (g, buf, quot))
606	{
607	recombination= true;
608	result.append (g);
609	if (b.getp() != 0)
610	buf= quot*bCommonDen (quot);
611	else
612	buf= quot;
613	LCBuf= LC (buf, x);
614	T= Difference (T, S);
615	l -= degree (g);
616	M= power (y, l);
617	buf0= mulNTL (buf (0, x), LCBuf);
618	if (!isRat)
619	Off (SW_RATIONAL);
620	// compute new possible degree pattern
621	bufDegs2= DegreePattern (T);
622	bufDegs1.intersect (bufDegs2);
623	bufDegs1.refine ();
624	if (T.length() < 2*s \|\| T.length() == s \|\|
625	bufDegs1.getLength() == 1)
626	{
627	delete [] v;
628	if (recombination)
629	{
630	result.append (buf);
631	F= 1;
632	return result;
633	}
634	else
635	{
636	result= CFList (F);
637	F= 1;
638	return result;
639	}
640	}
641	TT= copy (T);
642	indexUpdate (v, s, T.length(), nosubset);
643	if (nosubset) break;
644	}
645	if (!isRat)
646	Off (SW_RATIONAL);
647	}
648	}
649	}
650	s++;
651	if (T.length() < 2*s \|\| T.length() == s)
652	{
653	delete [] v;
654	if (recombination)
655	{
656	result.append (buf);
657	F= 1;
658	return result;
659	}
660	else
661	{
662	result= CFList (F);
663	F= 1;
664	return result;
665	}
666	}
667	for (int i= 0; i < T.length(); i++)
668	v[i]= 0;
669	nosubset= false;
670	}
671	delete [] v;
672	if (T.length() < 2*s)
673	{
674	result.append (F);
675	F= 1;
676	return result;
677	}
678
679	if (s > thres)
680	{
681	factors= T;
682	F= buf;
683	degs= bufDegs1;
684	}
685
686	return result;
687	}
688
689	Variable chooseExtension (const Variable & alpha, const Variable& beta, int k)
690	{
691	if (fac_NTL_char != getCharacteristic())
692	{
693	fac_NTL_char= getCharacteristic();
694	zz_p::init (getCharacteristic());
695	}
696	zz_pX NTLIrredpoly;
697	int i=1, m= 2;
698	// extension of F_p needed
699	if (alpha.level() == 1 && beta.level() == 1 && k == 1)
700	{
701	i= 1;
702	m= 2;
703	} //extension of F_p(alpha) needed but want to factorize over F_p
704	else if (alpha.level() != 1 && beta.level() == 1 && k == 1)
705	{
706	i= 1;
707	m= degree (getMipo (alpha)) + 1;
708	} //extension of F_p(alpha) needed for first time
709	else if (alpha.level() != 1 && beta.level() == 1 && k != 1)
710	{
711	i= 2;
712	m= degree (getMipo (alpha));
713	}
714	else if (alpha.level() != 1 && beta.level() != 1 && k != 1)
715	{
716	m= degree (getMipo (beta));
717	i= degree (getMipo (alpha))/m + 1;
718	}
719	BuildIrred (NTLIrredpoly, i*m);
720	CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
721	return rootOf (newMipo);
722	}
723
724	void
725	earlyFactorDetection (CFList& reconstructedFactors, CanonicalForm& F, CFList&
726	factors, int& adaptedLiftBound, int*& factorsFoundIndex,
727	DegreePattern& degs, bool& success, int deg,
728	const modpk& b)
729	{
730	DegreePattern bufDegs1= degs;
731	DegreePattern bufDegs2;
732	CFList T= factors;
733	CanonicalForm buf= F;
734	Variable x= Variable (1);
735	CanonicalForm g, quot;
736	CanonicalForm M= power (F.mvar(), deg);
737	adaptedLiftBound= 0;
738	int d= degree (F), l= 0;
739	bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) \|\| getCharacteristic() > 0;
740	if (!isRat)
741	On (SW_RATIONAL);
742	if (b.getp() != 0)
743	buf *= bCommonDen (buf);
744	CanonicalForm LCBuf= LC (buf, x);
745	CanonicalForm buf0= mulNTL (buf (0,x), LCBuf);
746	CanonicalForm buf1= mulNTL (buf (1,x), LCBuf);
747	if (!isRat)
748	Off (SW_RATIONAL);
749	CanonicalForm test0, test1;
750
751	for (CFListIterator i= factors; i.hasItem(); i++, l++)
752	{
753	if (!bufDegs1.find (degree (i.getItem(), 1)) \|\| factorsFoundIndex[l] == 1)
754	continue;
755	else
756	{
757	test1= mod (mulNTL (i.getItem() (1,x), LCBuf, b), M);
758	if (uniFdivides (test1, buf1))
759	{
760	test0= mod (mulNTL (i.getItem() (0,x), LCBuf, b), M);
761	if (uniFdivides (test0, buf0))
762	{
763	if (!isRat)
764	On (SW_RATIONAL);
765	g= mulMod2 (i.getItem(), LCBuf, M);
766	if (!isRat)
767	{
768	g *= bCommonDen(g);
769	Off (SW_RATIONAL);
770	}
771	if (b.getp() != 0)
772	g= b(g);
773	if (!isRat)
774	On (SW_RATIONAL);
775	g /= content (g, x);
776	if (!isRat)
777	{
778	On (SW_RATIONAL);
779	g *= bCommonDen (g);
780	Off (SW_RATIONAL);
781	g /= icontent (g);
782	On (SW_RATIONAL);
783	}
784	if (fdivides (g, buf, quot))
785	{
786	reconstructedFactors.append (g);
787	factorsFoundIndex[l]= 1;
788	if (b.getp() != 0)
789	buf= quot*bCommonDen(quot);
790	else
791	buf= quot;
792	d -= degree (g);
793	LCBuf= LC (buf, x);
794	buf0= mulNTL (buf (0,x), LCBuf);
795	buf1= mulNTL (buf (1,x), LCBuf);
796	if (!isRat)
797	Off (SW_RATIONAL);
798	T= Difference (T, CFList (i.getItem()));
799	F= buf;
800
801	// compute new possible degree pattern
802	bufDegs2= DegreePattern (T);
803	bufDegs1.intersect (bufDegs2);
804	bufDegs1.refine ();
805	if (bufDegs1.getLength() <= 1)
806	{
807	if (!buf.inCoeffDomain())
808	{
809	reconstructedFactors.append (buf);
810	F= 1;
811	}
812	break;
813	}
814	}
815	if (!isRat)
816	Off (SW_RATIONAL);
817	}
818	}
819	}
820	}
821	adaptedLiftBound= d + 1;
822	if (adaptedLiftBound < deg)
823	{
824	degs= bufDegs1;
825	success= true;
826	}
827	if (bufDegs1.getLength() <= 1)
828	degs= bufDegs1;
829	}
830
831	void
832	extEarlyFactorDetection (CFList& reconstructedFactors, CanonicalForm& F, CFList&
833	factors,int& adaptedLiftBound, int*& factorsFoundIndex,
834	DegreePattern& degs, bool& success, const
835	ExtensionInfo& info, const CanonicalForm& eval, int deg
836	)
837	{
838	Variable alpha= info.getAlpha();
839	Variable beta= info.getBeta();
840	CanonicalForm gamma= info.getGamma();
841	CanonicalForm delta= info.getDelta();
842	int k= info.getGFDegree();
843	DegreePattern bufDegs1= degs, bufDegs2;
844	CFList result;
845	CFList T= factors;
846	Variable y= F.mvar();
847	Variable x= Variable (1);
848	CanonicalForm buf= F, LCBuf= LC (buf, x), g, buf2;
849	CanonicalForm M= power (y, deg);
850	adaptedLiftBound= 0;
851	bool trueFactor= false;
852	int d= degree (F), l= 0;
853	CFList source, dest;
854	int degMipoBeta= 1;
855	if (!k && beta.level() != 1)
856	degMipoBeta= degree (getMipo (beta));
857	CanonicalForm quot;
858	for (CFListIterator i= factors; i.hasItem(); i++, l++)
859	{
860	if (!bufDegs1.find (degree (i.getItem(), 1)) \|\| factorsFoundIndex[l] == 1)
861	continue;
862	else
863	{
864	g= mulMod2 (i.getItem(), LCBuf, M);
865	g /= content (g, x);
866	if (fdivides (g, buf, quot))
867	{
868	buf2= g (y - eval, y);
869	buf2 /= Lc (buf2);
870
871	if (!k && beta == x)
872	{
873	if (degree (buf2, alpha) < degMipoBeta)
874	{
875	appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
876	factorsFoundIndex[l]= 1;
877	buf= quot;
878	d -= degree (g);
879	LCBuf= LC (buf, x);
880	trueFactor= true;
881	}
882	}
883	else
884	{
885	if (!isInExtension (buf2, gamma, k, delta, source, dest))
886	{
887	appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
888	factorsFoundIndex[l]= 1;
889	buf= quot;
890	d -= degree (g);
891	LCBuf= LC (buf, x);
892	trueFactor= true;
893	}
894	}
895	if (trueFactor)
896	{
897	T= Difference (T, CFList (i.getItem()));
898	F= buf;
899
900	// compute new possible degree pattern
901	bufDegs2= DegreePattern (T);
902	bufDegs1.intersect (bufDegs2);
903	bufDegs1.refine ();
904	trueFactor= false;
905	if (bufDegs1.getLength() <= 1)
906	{
907	if (!buf.inCoeffDomain())
908	{
909	buf= buf (y - eval, y);
910	buf /= Lc (buf);
911	appendMapDown (reconstructedFactors, buf, info, source, dest);
912	F= 1;
913	}
914	break;
915	}
916	}
917	}
918	}
919	}
920	adaptedLiftBound= d + 1;
921	if (adaptedLiftBound < deg)
922	{
923	degs= bufDegs1;
924	success= true;
925	}
926	if (bufDegs1.getLength() <= 1)
927	degs= bufDegs1;
928	}
929
930	int*
931	getCombinations (int * rightSide, int sizeOfRightSide, int& sizeOfOutput,
932	int degreeLC)
933	{
934	Variable x= Variable (1);
935	int p= getCharacteristic();
936	int d= getGFDegree();
937	char cGFName= gf_name;
938	setCharacteristic(0);
939	CanonicalForm buf= 1;
940	for (int i= 0; i < sizeOfRightSide; i++)
941	buf *= (power (x, rightSide [i]) + 1);
942
943	int j= 0;
944	for (CFIterator i= buf; i.hasTerms(); i++, j++)
945	{
946	if (i.exp() < degreeLC)
947	{
948	j++;
949	break;
950	}
951	}
952
953	ASSERT ( j > 1, "j > 1 expected" );
954
955	int* result = new int [j - 1];
956	sizeOfOutput= j - 1;
957
958	int i= 0;
959	for (CFIterator m = buf; i < j - 1; i++, m++)
960	result [i]= m.exp();
961
962	if (d > 1)
963	setCharacteristic (p, d, cGFName);
964	else
965	setCharacteristic (p);
966	return result;
967	}
968
969	int *
970	getLiftPrecisions (const CanonicalForm& F, int& sizeOfOutput, int degreeLC)
971	{
972	int sizeOfNewtonPoly;
973	int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPoly);
974	int sizeOfRightSide;
975	int * rightSide= getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
976	int * result= getCombinations(rightSide, sizeOfRightSide, sizeOfOutput,
977	degreeLC);
978	delete [] rightSide;
979	for (int i= 0; i < sizeOfNewtonPoly; i++)
980	delete [] newtonPolyg[i];
981	delete [] newtonPolyg;
982	return result;
983	}
984
985	void
986	deleteFactors (CFList& factors, int* factorsFoundIndex)
987	{
988	CFList result;
989	int i= 0;
990	for (CFListIterator iter= factors; iter.hasItem(); iter++, i++)
991	{
992	if (factorsFoundIndex[i] == 1)
993	continue;
994	else
995	result.append (iter.getItem());
996	}
997	factors= result;
998	}
999
1000	CFList
1001	henselLiftAndEarly (CanonicalForm& A, bool& earlySuccess, CFList&
1002	earlyFactors, DegreePattern& degs, int& liftBound,
1003	const CFList& uniFactors, const ExtensionInfo& info,
1004	const CanonicalForm& eval, modpk& b)
1005	{
1006	Variable alpha= info.getAlpha();
1007	Variable beta= info.getBeta();
1008	CanonicalForm gamma= info.getGamma();
1009	CanonicalForm delta= info.getDelta();
1010	bool extension= info.isInExtension();
1011
1012	int sizeOfLiftPre;
1013	int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
1014
1015	Variable x= Variable (1);
1016	Variable y= Variable (2);
1017	CFArray Pi;
1018	CFList diophant;
1019	CFList bufUniFactors= uniFactors;
1020	CanonicalForm bufA= A;
1021	CanonicalForm lcA0= 0;
1022	bool mipoHasDen= false;
1023	if (getCharacteristic() == 0 && b.getp() != 0)
1024	{
1025	if (alpha.level() == 1)
1026	{
1027	lcA0= lc (A (0, 2));
1028	A *= b.inverse (lcA0);
1029	A= b (A);
1030	for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
1031	i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1032	}
1033	else
1034	{
1035	lcA0= Lc (A (0,2));
1036	On (SW_RATIONAL);
1037	mipoHasDen= !bCommonDen(getMipo(alpha)).isOne();
1038	Off (SW_RATIONAL);
1039	CanonicalForm lcA0inverse= b.inverse (lcA0);
1040	A *= lcA0inverse;
1041	A= b (A);
1042	// Lc of bufUniFactors is in Z
1043	for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
1044	i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1045	}
1046	}
1047	bufUniFactors.insert (LC (A, x));
1048	CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1);
1049	earlySuccess= false;
1050	int newLiftBound= 0;
1051
1052	int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
1053	int dummy;
1054	int * factorsFoundIndex= new int [uniFactors.length()];
1055	for (int i= 0; i < uniFactors.length(); i++)
1056	factorsFoundIndex [i]= 0;
1057
1058	CFList bufBufUniFactors;
1059	Variable v= alpha;
1060	if (smallFactorDeg >= liftBound \|\| degree (A,y) <= 4)
1061	henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M, b, true);
1062	else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1063	{
1064	henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
1065	if (mipoHasDen)
1066	{
1067	for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1068	if (hasFirstAlgVar (iter.getItem(), v))
1069	break;
1070	if (v != alpha)
1071	{
1072	bufBufUniFactors= bufUniFactors;
1073	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1074	iter.getItem()= replacevar (iter.getItem(), v, alpha);
1075	A= replacevar (A, alpha, v);
1076	}
1077	}
1078
1079	if (!extension)
1080	{
1081	if (v==alpha)
1082	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1083	factorsFoundIndex, degs, earlySuccess,
1084	smallFactorDeg, b);
1085	else
1086	earlyFactorDetection(earlyFactors, bufA, bufBufUniFactors, newLiftBound,
1087	factorsFoundIndex, degs, earlySuccess,
1088	smallFactorDeg, b);
1089	}
1090	else
1091	extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1092	factorsFoundIndex, degs, earlySuccess, info,
1093	eval, smallFactorDeg);
1094	if (degs.getLength() > 1 && !earlySuccess &&
1095	smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
1096	{
1097	if (newLiftBound >= liftPre[sizeOfLiftPre-1]+1)
1098	{
1099	bufUniFactors.insert (LC (A, x));
1100	henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
1101	liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M, b);
1102	if (v!=alpha)
1103	{
1104	bufBufUniFactors= bufUniFactors;
1105	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1106	iter.getItem()= replacevar (iter.getItem(), v, alpha);
1107	}
1108	if (!extension)
1109	{
1110	if (v==alpha)
1111	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1112	factorsFoundIndex, degs, earlySuccess,
1113	liftPre[sizeOfLiftPre-1] + 1, b);
1114	else
1115	earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1116	factorsFoundIndex, degs, earlySuccess,
1117	liftPre[sizeOfLiftPre-1] + 1, b);
1118	}
1119	else
1120	extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1121	factorsFoundIndex, degs, earlySuccess, info,
1122	eval, liftPre[sizeOfLiftPre-1] + 1);
1123	}
1124	}
1125	else if (earlySuccess)
1126	liftBound= newLiftBound;
1127
1128	int i= sizeOfLiftPre - 1;
1129	while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
1130	{
1131	if (newLiftBound >= liftPre[i] + 1)
1132	{
1133	bufUniFactors.insert (LC (A, x));
1134	henselLiftResume12 (A, bufUniFactors, liftPre[i] + 1,
1135	liftPre[i-1] + 1, Pi, diophant, M, b);
1136	if (v!=alpha)
1137	{
1138	bufBufUniFactors= bufUniFactors;
1139	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1140	iter.getItem()= replacevar (iter.getItem(), v, alpha);
1141	}
1142	if (!extension)
1143	{
1144	if (v==alpha)
1145	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1146	factorsFoundIndex, degs, earlySuccess,
1147	liftPre[i-1] + 1, b);
1148	else
1149	earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1150	factorsFoundIndex, degs, earlySuccess,
1151	liftPre[i-1] + 1, b);
1152	}
1153	else
1154	extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1155	factorsFoundIndex, degs, earlySuccess, info,
1156	eval, liftPre[i-1] + 1);
1157	}
1158	else
1159	{
1160	liftBound= newLiftBound;
1161	break;
1162	}
1163	i--;
1164	}
1165	if (earlySuccess)
1166	liftBound= newLiftBound;
1167	//after here all factors are lifted to liftPre[sizeOfLiftPre-1]
1168	}
1169	else
1170	{
1171	henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
1172	if (mipoHasDen)
1173	{
1174	for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1175	if (hasFirstAlgVar (iter.getItem(), v))
1176	break;
1177	if (v != alpha)
1178	{
1179	bufBufUniFactors= bufUniFactors;
1180	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1181	iter.getItem()= replacevar (iter.getItem(), v, alpha);
1182	A= replacevar (A, alpha, v);
1183	}
1184	}
1185	if (!extension)
1186	{
1187	if (v==alpha)
1188	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1189	factorsFoundIndex, degs, earlySuccess,
1190	smallFactorDeg, b);
1191	else
1192	earlyFactorDetection (earlyFactors, bufA, bufBufUniFactors, newLiftBound,
1193	factorsFoundIndex, degs, earlySuccess,
1194	smallFactorDeg, b);
1195	}
1196	else
1197	extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1198	factorsFoundIndex, degs, earlySuccess, info,
1199	eval, smallFactorDeg);
1200	int i= 1;
1201	while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
1202	i++;
1203	dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
1204	if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1205	{
1206	bufUniFactors.insert (LC (A, x));
1207	henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
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	while (degs.getLength() > 1 && !earlySuccess && i < 4)
1230	{
1231	if (newLiftBound >= dummy)
1232	{
1233	bufUniFactors.insert (LC (A, x));
1234	dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
1235	henselLiftResume12 (A, bufUniFactors, (degree (A,y)/4)*i + 4,
1236	dummy, Pi, diophant, M, b);
1237	if (v!=alpha)
1238	{
1239	bufBufUniFactors= bufUniFactors;
1240	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1241	iter.getItem()= replacevar (iter.getItem(), v, alpha);
1242	}
1243	if (!extension)
1244	{
1245	if (v==alpha)
1246	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1247	factorsFoundIndex, degs, earlySuccess, dummy,b);
1248	else
1249	earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1250	factorsFoundIndex, degs, earlySuccess, dummy,b);
1251	}
1252	else
1253	extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1254	factorsFoundIndex, degs, earlySuccess, info,
1255	eval, dummy);
1256	}
1257	else
1258	{
1259	liftBound= newLiftBound;
1260	break;
1261	}
1262	i++;
1263	}
1264	if (earlySuccess)
1265	liftBound= newLiftBound;
1266	}
1267
1268	A= bufA;
1269	if (earlyFactors.length() > 0 && degs.getLength() > 1)
1270	{
1271	liftBound= degree (A,y) + 1;
1272	earlySuccess= true;
1273	deleteFactors (bufUniFactors, factorsFoundIndex);
1274	}
1275
1276	delete [] factorsFoundIndex;
1277	delete [] liftPre;
1278
1279	return bufUniFactors;
1280	}
1281
1282	CFList
1283	henselLiftAndEarly (CanonicalForm& A, bool& earlySuccess, CFList&
1284	earlyFactors, DegreePattern& degs, int& liftBound,
1285	const CFList& uniFactors, const ExtensionInfo& info,
1286	const CanonicalForm& eval)
1287	{
1288	modpk dummy= modpk();
1289	return henselLiftAndEarly (A, earlySuccess, earlyFactors, degs, liftBound,
1290	uniFactors, info, eval, dummy);
1291	}
1292
1293	long isReduced (const mat_zz_p& M)
1294	{
1295	long i, j, nonZero;
1296	for (i = 1; i <= M.NumRows(); i++)
1297	{
1298	nonZero= 0;
1299	for (j = 1; j <= M.NumCols(); j++)
1300	{
1301	if (!IsZero (M (i,j)))
1302	nonZero++;
1303	}
1304	if (nonZero != 1)
1305	return 0;
1306	}
1307	return 1;
1308	}
1309
1310	#ifdef HAVE_FLINT
1311	long isReduced (const nmod_mat_t M)
1312	{
1313	long i, j, nonZero;
1314	for (i = 1; i <= nmod_mat_nrows(M); i++)
1315	{
1316	nonZero= 0;
1317	for (j = 1; j <= nmod_mat_ncols (M); j++)
1318	{
1319	if (!(nmod_mat_entry (M, i-1, j-1)==0))
1320	nonZero++;
1321	}
1322	if (nonZero != 1)
1323	return 0;
1324	}
1325	return 1;
1326	}
1327	#endif
1328
1329	long isReduced (const mat_zz_pE& M)
1330	{
1331	long i, j, nonZero;
1332	for (i = 1; i <= M.NumRows(); i++)
1333	{
1334	nonZero= 0;
1335	for (j = 1; j <= M.NumCols(); j++)
1336	{
1337	if (!IsZero (M (i,j)))
1338	nonZero++;
1339	}
1340	if (nonZero != 1)
1341	return 0;
1342	}
1343	return 1;
1344	}
1345
1346	int * extractZeroOneVecs (const mat_zz_p& M)
1347	{
1348	long i, j;
1349	bool nonZeroOne= false;
1350	int * result= new int [M.NumCols()];
1351	for (i = 1; i <= M.NumCols(); i++)
1352	{
1353	for (j = 1; j <= M.NumRows(); j++)
1354	{
1355	if (!(IsOne (M (j,i)) \|\| IsZero (M (j,i))))
1356	{
1357	nonZeroOne= true;
1358	break;
1359	}
1360	}
1361	if (!nonZeroOne)
1362	result [i - 1]= 1;
1363	else
1364	result [i - 1]= 0;
1365	nonZeroOne= false;
1366	}
1367	return result;
1368	}
1369
1370	#ifdef HAVE_FLINT
1371	int * extractZeroOneVecs (const nmod_mat_t M)
1372	{
1373	long i, j;
1374	bool nonZeroOne= false;
1375	int * result= new int [nmod_mat_ncols (M)];
1376	for (i = 0; i < nmod_mat_ncols (M); i++)
1377	{
1378	for (j = 0; j < nmod_mat_nrows (M); j++)
1379	{
1380	if (!((nmod_mat_entry (M, j, i) == 1) \|\| (nmod_mat_entry (M, j,i) == 0)))
1381	{
1382	nonZeroOne= true;
1383	break;
1384	}
1385	}
1386	if (!nonZeroOne)
1387	result [i]= 1;
1388	else
1389	result [i]= 0;
1390	nonZeroOne= false;
1391	}
1392	return result;
1393	}
1394	#endif
1395
1396	int * extractZeroOneVecs (const mat_zz_pE& M)
1397	{
1398	long i, j;
1399	bool nonZeroOne= false;
1400	int * result= new int [M.NumCols()];
1401	for (i = 1; i <= M.NumCols(); i++)
1402	{
1403	for (j = 1; j <= M.NumRows(); j++)
1404	{
1405	if (!(IsOne (M (j,i)) \|\| IsZero (M (j,i))))
1406	{
1407	nonZeroOne= true;
1408	break;
1409	}
1410	}
1411	if (!nonZeroOne)
1412	result [i - 1]= 1;
1413	else
1414	result [i - 1]= 0;
1415	nonZeroOne= false;
1416	}
1417	return result;
1418	}
1419
1420	void
1421	reconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const CFList&
1422	factors, const int liftBound, int& factorsFound, int*&
1423	factorsFoundIndex, mat_zz_pE& N, bool beenInThres
1424	)
1425	{
1426	Variable y= Variable (2);
1427	Variable x= Variable (1);
1428	CanonicalForm yToL= power (y, liftBound);
1429	if (factors.length() == 2)
1430	{
1431	CanonicalForm tmp1, tmp2, tmp3;
1432	tmp1= factors.getFirst();
1433	tmp2= factors.getLast();
1434	tmp1 *= LC (F, x);
1435	tmp1= mod (tmp1, yToL);
1436	tmp1 /= content (tmp1, x);
1437	tmp2 *= LC (F, x);
1438	tmp2= mod (tmp2, yToL);
1439	tmp2 /= content (tmp2, x);
1440	tmp3 = tmp1*tmp2;
1441	if (tmp3/Lc (tmp3) == F/Lc (F))
1442	{
1443	factorsFound++;
1444	F= 1;
1445	reconstructedFactors.append (tmp1);
1446	reconstructedFactors.append (tmp2);
1447	return;
1448	}
1449	}
1450	CanonicalForm quot, buf;
1451	CFListIterator iter;
1452	for (long i= 1; i <= N.NumCols(); i++)
1453	{
1454	if (factorsFoundIndex [i - 1] == 1)
1455	continue;
1456	iter= factors;
1457	if (beenInThres)
1458	{
1459	int count= 1;
1460	while (count < i)
1461	{
1462	count++;
1463	iter++;
1464	}
1465	buf= iter.getItem();
1466	}
1467	else
1468	{
1469	buf= 1;
1470	for (long j= 1; j <= N.NumRows(); j++, iter++)
1471	{
1472	if (!IsZero (N (j,i)))
1473	buf= mulMod2 (buf, iter.getItem(), yToL);
1474	}
1475	}
1476	buf *= LC (F, x);
1477	buf= mod (buf, yToL);
1478	buf /= content (buf, x);
1479	if (fdivides (buf, F, quot))
1480	{
1481	factorsFoundIndex[i - 1]= 1;
1482	factorsFound++;
1483	F= quot;
1484	F /= Lc (F);
1485	reconstructedFactors.append (buf);
1486	}
1487	if (degree (F) <= 0)
1488	return;
1489	if (factorsFound + 1 == N.NumCols())
1490	{
1491	reconstructedFactors.append (F);
1492	return;
1493	}
1494	}
1495	}
1496
1497	void
1498	reconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const CFList&
1499	factors, const int liftBound, int& factorsFound, int*&
1500	factorsFoundIndex, mat_zz_p& N, bool beenInThres
1501	)
1502	{
1503	Variable y= Variable (2);
1504	Variable x= Variable (1);
1505	CanonicalForm yToL= power (y, liftBound);
1506	if (factors.length() == 2)
1507	{
1508	CanonicalForm tmp1, tmp2, tmp3;
1509	tmp1= factors.getFirst();
1510	tmp2= factors.getLast();
1511	tmp1 *= LC (F, x);
1512	tmp1= mod (tmp1, yToL);
1513	tmp1 /= content (tmp1, x);
1514	tmp2 *= LC (F, x);
1515	tmp2= mod (tmp2, yToL);
1516	tmp2 /= content (tmp2, x);
1517	tmp3 = tmp1*tmp2;
1518	if (tmp3/Lc (tmp3) == F/Lc (F))
1519	{
1520	factorsFound++;
1521	F= 1;
1522	reconstructedFactors.append (tmp1);
1523	reconstructedFactors.append (tmp2);
1524	return;
1525	}
1526	}
1527	CanonicalForm quot, buf;
1528	CFListIterator iter;
1529	for (long i= 1; i <= N.NumCols(); i++)
1530	{
1531	if (factorsFoundIndex [i - 1] == 1)
1532	continue;
1533	iter= factors;
1534	if (beenInThres)
1535	{
1536	int count= 1;
1537	while (count < i)
1538	{
1539	count++;
1540	iter++;
1541	}
1542	buf= iter.getItem();
1543	}
1544	else
1545	{
1546	buf= 1;
1547	for (long j= 1; j <= N.NumRows(); j++, iter++)
1548	{
1549	if (!IsZero (N (j,i)))
1550	buf= mulMod2 (buf, iter.getItem(), yToL);
1551	}
1552	}
1553	buf *= LC (F, x);
1554	buf= mod (buf, yToL);
1555	buf /= content (buf, x);
1556	if (fdivides (buf, F, quot))
1557	{
1558	factorsFoundIndex[i - 1]= 1;
1559	factorsFound++;
1560	F= quot;
1561	F /= Lc (F);
1562	reconstructedFactors.append (buf);
1563	}
1564	if (degree (F) <= 0)
1565	return;
1566	if (factorsFound + 1 == N.NumCols())
1567	{
1568	reconstructedFactors.append (F);
1569	return;
1570	}
1571	}
1572	}
1573
1574	#ifdef HAVE_FLINT
1575	void
1576	reconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const CFList&
1577	factors, const int liftBound, int& factorsFound, int*&
1578	factorsFoundIndex, nmod_mat_t N, bool beenInThres
1579	)
1580	{
1581	Variable y= Variable (2);
1582	Variable x= Variable (1);
1583	CanonicalForm yToL= power (y, liftBound);
1584	if (factors.length() == 2)
1585	{
1586	CanonicalForm tmp1, tmp2, tmp3;
1587	tmp1= factors.getFirst();
1588	tmp2= factors.getLast();
1589	tmp1 *= LC (F, x);
1590	tmp1= mod (tmp1, yToL);
1591	tmp1 /= content (tmp1, x);
1592	tmp2 *= LC (F, x);
1593	tmp2= mod (tmp2, yToL);
1594	tmp2 /= content (tmp2, x);
1595	tmp3 = tmp1*tmp2;
1596	if (tmp3/Lc (tmp3) == F/Lc (F))
1597	{
1598	factorsFound++;
1599	F= 1;
1600	reconstructedFactors.append (tmp1);
1601	reconstructedFactors.append (tmp2);
1602	return;
1603	}
1604	}
1605	CanonicalForm quot, buf;
1606	CFListIterator iter;
1607	for (long i= 0; i < nmod_mat_ncols (N); i++)
1608	{
1609	if (factorsFoundIndex [i] == 1)
1610	continue;
1611	iter= factors;
1612	if (beenInThres)
1613	{
1614	int count= 0;
1615	while (count < i)
1616	{
1617	count++;
1618	iter++;
1619	}
1620	buf= iter.getItem();
1621	}
1622	else
1623	{
1624	buf= 1;
1625	for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
1626	{
1627	if (!(nmod_mat_entry (N, j, i) == 0))
1628	buf= mulMod2 (buf, iter.getItem(), yToL);
1629	}
1630	}
1631	buf *= LC (F, x);
1632	buf= mod (buf, yToL);
1633	buf /= content (buf, x);
1634	if (fdivides (buf, F, quot))
1635	{
1636	factorsFoundIndex[i]= 1;
1637	factorsFound++;
1638	F= quot;
1639	F /= Lc (F);
1640	reconstructedFactors.append (buf);
1641	}
1642	if (degree (F) <= 0)
1643	return;
1644	if (factorsFound + 1 == nmod_mat_ncols (N))
1645	{
1646	reconstructedFactors.append (F);
1647	return;
1648	}
1649	}
1650	}
1651	#endif
1652
1653	CFList
1654	reconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, int
1655	precision, const mat_zz_pE& N
1656	)
1657	{
1658	Variable y= Variable (2);
1659	Variable x= Variable (1);
1660	CanonicalForm F= G;
1661	CanonicalForm yToL= power (y, precision);
1662	CanonicalForm quot, buf;
1663	CFList result, factorsConsidered;
1664	CFList bufFactors= factors;
1665	CFListIterator iter;
1666	for (long i= 1; i <= N.NumCols(); i++)
1667	{
1668	if (zeroOneVecs [i - 1] == 0)
1669	continue;
1670	iter= factors;
1671	buf= 1;
1672	factorsConsidered= CFList();
1673	for (long j= 1; j <= N.NumRows(); j++, iter++)
1674	{
1675	if (!IsZero (N (j,i)))
1676	{
1677	factorsConsidered.append (iter.getItem());
1678	buf= mulMod2 (buf, iter.getItem(), yToL);
1679	}
1680	}
1681	buf *= LC (F, x);
1682	buf= mod (buf, yToL);
1683	buf /= content (buf, x);
1684	if (fdivides (buf, F, quot))
1685	{
1686	F= quot;
1687	F /= Lc (F);
1688	result.append (buf);
1689	bufFactors= Difference (bufFactors, factorsConsidered);
1690	}
1691	if (degree (F) <= 0)
1692	{
1693	G= F;
1694	factors= bufFactors;
1695	return result;
1696	}
1697	}
1698	G= F;
1699	factors= bufFactors;
1700	return result;
1701	}
1702
1703	CFList
1704	monicReconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs,
1705	int precision, const mat_zz_pE& N
1706	)
1707	{
1708	Variable y= Variable (2);
1709	Variable x= Variable (1);
1710	CanonicalForm F= G;
1711	CanonicalForm yToL= power (y, precision);
1712	CanonicalForm quot, buf, buf2;
1713	CFList result;
1714	CFList bufFactors= factors;
1715	CFList factorsConsidered;
1716	CFListIterator iter;
1717	for (long i= 1; i <= N.NumCols(); i++)
1718	{
1719	if (zeroOneVecs [i - 1] == 0)
1720	continue;
1721	iter= factors;
1722	buf= 1;
1723	factorsConsidered= CFList();
1724	for (long j= 1; j <= N.NumRows(); j++, iter++)
1725	{
1726	if (!IsZero (N (j,i)))
1727	{
1728	factorsConsidered.append (iter.getItem());
1729	buf= mulMod2 (buf, iter.getItem(), yToL);
1730	}
1731	}
1732	buf2= buf;
1733	buf *= LC (F, x);
1734	buf= mod (buf, yToL);
1735	buf /= content (buf, x);
1736	if (fdivides (buf, F, quot))
1737	{
1738	F= quot;
1739	F /= Lc (F);
1740	result.append (buf2);
1741	bufFactors= Difference (bufFactors, factorsConsidered);
1742	}
1743	if (degree (F) <= 0)
1744	{
1745	G= F;
1746	factors= bufFactors;
1747	return result;
1748	}
1749	}
1750	G= F;
1751	factors= bufFactors;
1752	return result;
1753	}
1754
1755	CFList
1756	extReconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, int
1757	precision, const mat_zz_p& N, const ExtensionInfo& info,
1758	const CanonicalForm& evaluation
1759	)
1760	{
1761	Variable y= Variable (2);
1762	Variable x= Variable (1);
1763	Variable alpha= info.getAlpha();
1764	Variable beta= info.getBeta();
1765	int k= info.getGFDegree();
1766	CanonicalForm gamma= info.getGamma();
1767	CanonicalForm delta= info.getDelta();
1768	CanonicalForm F= G;
1769	CanonicalForm yToL= power (y, precision);
1770	CFList result;
1771	CFList bufFactors= factors;
1772	CFList factorsConsidered;
1773	CanonicalForm buf2, quot, buf;
1774	CFListIterator iter;
1775	for (long i= 1; i <= N.NumCols(); i++)
1776	{
1777	if (zeroOneVecs [i - 1] == 0)
1778	continue;
1779	iter= factors;
1780	buf= 1;
1781	factorsConsidered= CFList();
1782	for (long j= 1; j <= N.NumRows(); j++, iter++)
1783	{
1784	if (!IsZero (N (j,i)))
1785	{
1786	factorsConsidered.append (iter.getItem());
1787	buf= mulMod2 (buf, iter.getItem(), yToL);
1788	}
1789	}
1790	buf *= LC (F, x);
1791	buf= mod (buf, yToL);
1792	buf /= content (buf, x);
1793	buf2= buf (y-evaluation, y);
1794	buf2 /= Lc (buf2);
1795	if (!k && beta == x)
1796	{
1797	if (degree (buf2, alpha) < 1)
1798	{
1799	if (fdivides (buf, F, quot))
1800	{
1801	F= quot;
1802	F /= Lc (F);
1803	result.append (buf2);
1804	bufFactors= Difference (bufFactors, factorsConsidered);
1805	}
1806	}
1807	}
1808	else
1809	{
1810	CFList source, dest;
1811
1812	if (!isInExtension (buf2, gamma, k, delta, source, dest))
1813	{
1814	if (fdivides (buf, F, quot))
1815	{
1816	F= quot;
1817	F /= Lc (F);
1818	result.append (buf2);
1819	bufFactors= Difference (bufFactors, factorsConsidered);
1820	}
1821	}
1822	}
1823	if (degree (F) <= 0)
1824	{
1825	G= F;
1826	factors= bufFactors;
1827	return result;
1828	}
1829	}
1830	G= F;
1831	factors= bufFactors;
1832	return result;
1833	}
1834
1835	#ifdef HAVE_FLINT
1836	CFList
1837	extReconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, int
1838	precision, const nmod_mat_t N, const ExtensionInfo& info,
1839	const CanonicalForm& evaluation
1840	)
1841	{
1842	Variable y= Variable (2);
1843	Variable x= Variable (1);
1844	Variable alpha= info.getAlpha();
1845	Variable beta= info.getBeta();
1846	int k= info.getGFDegree();
1847	CanonicalForm gamma= info.getGamma();
1848	CanonicalForm delta= info.getDelta();
1849	CanonicalForm F= G;
1850	CanonicalForm yToL= power (y, precision);
1851	CFList result;
1852	CFList bufFactors= factors;
1853	CFList factorsConsidered;
1854	CanonicalForm buf2, quot, buf;
1855	CFListIterator iter;
1856	for (long i= 0; i < nmod_mat_ncols(N); i++)
1857	{
1858	if (zeroOneVecs [i] == 0)
1859	continue;
1860	iter= factors;
1861	buf= 1;
1862	factorsConsidered= CFList();
1863	for (long j= 0; j < nmod_mat_ncols(N); j++, iter++)
1864	{
1865	if (!(nmod_mat_entry (N, j, i) == 0))
1866	{
1867	factorsConsidered.append (iter.getItem());
1868	buf= mulMod2 (buf, iter.getItem(), yToL);
1869	}
1870	}
1871	buf *= LC (F, x);
1872	buf= mod (buf, yToL);
1873	buf /= content (buf, x);
1874	buf2= buf (y-evaluation, y);
1875	buf2 /= Lc (buf2);
1876	if (!k && beta == x)
1877	{
1878	if (degree (buf2, alpha) < 1)
1879	{
1880	if (fdivides (buf, F, quot))
1881	{
1882	F= quot;
1883	F /= Lc (F);
1884	result.append (buf2);
1885	bufFactors= Difference (bufFactors, factorsConsidered);
1886	}
1887	}
1888	}
1889	else
1890	{
1891	CFList source, dest;
1892
1893	if (!isInExtension (buf2, gamma, k, delta, source, dest))
1894	{
1895	if (fdivides (buf, F, quot))
1896	{
1897	F= quot;
1898	F /= Lc (F);
1899	result.append (buf2);
1900	bufFactors= Difference (bufFactors, factorsConsidered);
1901	}
1902	}
1903	}
1904	if (degree (F) <= 0)
1905	{
1906	G= F;
1907	factors= bufFactors;
1908	return result;
1909	}
1910	}
1911	G= F;
1912	factors= bufFactors;
1913	return result;
1914	}
1915	#endif
1916
1917	CFList
1918	reconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs,
1919	int precision, const mat_zz_p& N)
1920	{
1921	Variable y= Variable (2);
1922	Variable x= Variable (1);
1923	CanonicalForm F= G;
1924	CanonicalForm yToL= power (y, precision);
1925	CanonicalForm quot, buf;
1926	CFList result;
1927	CFList bufFactors= factors;
1928	CFList factorsConsidered;
1929	CFListIterator iter;
1930	for (long i= 1; i <= N.NumCols(); i++)
1931	{
1932	if (zeroOneVecs [i - 1] == 0)
1933	continue;
1934	iter= factors;
1935	buf= 1;
1936	factorsConsidered= CFList();
1937	for (long j= 1; j <= N.NumRows(); j++, iter++)
1938	{
1939	if (!IsZero (N (j,i)))
1940	{
1941	factorsConsidered.append (iter.getItem());
1942	buf= mulMod2 (buf, iter.getItem(), yToL);
1943	}
1944	}
1945	buf *= LC (F, x);
1946	buf= mod (buf, yToL);
1947	buf /= content (buf, x);
1948	if (fdivides (buf, F, quot))
1949	{
1950	F= quot;
1951	F /= Lc (F);
1952	result.append (buf);
1953	bufFactors= Difference (bufFactors, factorsConsidered);
1954	}
1955	if (degree (F) <= 0)
1956	{
1957	G= F;
1958	factors= bufFactors;
1959	return result;
1960	}
1961	}
1962	G= F;
1963	factors= bufFactors;
1964	return result;
1965	}
1966
1967	#ifdef HAVE_FLINT
1968	CFList
1969	reconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs,
1970	int precision, const nmod_mat_t N)
1971	{
1972	Variable y= Variable (2);
1973	Variable x= Variable (1);
1974	CanonicalForm F= G;
1975	CanonicalForm yToL= power (y, precision);
1976	CanonicalForm quot, buf;
1977	CFList result;
1978	CFList bufFactors= factors;
1979	CFList factorsConsidered;
1980	CFListIterator iter;
1981	for (long i= 0; i < nmod_mat_ncols (N); i++)
1982	{
1983	if (zeroOneVecs [i] == 0)
1984	continue;
1985	iter= factors;
1986	buf= 1;
1987	factorsConsidered= CFList();
1988	for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
1989	{
1990	if (!(nmod_mat_entry (N, j, i) == 0))
1991	{
1992	factorsConsidered.append (iter.getItem());
1993	buf= mulMod2 (buf, iter.getItem(), yToL);
1994	}
1995	}
1996	buf *= LC (F, x);
1997	buf= mod (buf, yToL);
1998	buf /= content (buf, x);
1999	if (fdivides (buf, F, quot))
2000	{
2001	F= quot;
2002	F /= Lc (F);
2003	result.append (buf);
2004	bufFactors= Difference (bufFactors, factorsConsidered);
2005	}
2006	if (degree (F) <= 0)
2007	{
2008	G= F;
2009	factors= bufFactors;
2010	return result;
2011	}
2012	}
2013	G= F;
2014	factors= bufFactors;
2015	return result;
2016	}
2017	#endif
2018
2019	void
2020	extReconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const
2021	CFList& factors, const int liftBound, int& factorsFound,
2022	int*& factorsFoundIndex, mat_zz_p& N, bool beenInThres,
2023	const ExtensionInfo& info, const CanonicalForm& evaluation
2024	)
2025	{
2026	Variable y= Variable (2);
2027	Variable x= Variable (1);
2028	Variable alpha= info.getAlpha();
2029	Variable beta= info.getBeta();
2030	int k= info.getGFDegree();
2031	CanonicalForm gamma= info.getGamma();
2032	CanonicalForm delta= info.getDelta();
2033	CanonicalForm yToL= power (y, liftBound);
2034	CFList source, dest;
2035	if (factors.length() == 2)
2036	{
2037	CanonicalForm tmp1, tmp2, tmp3;
2038	tmp1= factors.getFirst();
2039	tmp2= factors.getLast();
2040	tmp1 *= LC (F, x);
2041	tmp1= mod (tmp1, yToL);
2042	tmp1 /= content (tmp1, x);
2043	tmp2 *= LC (F, x);
2044	tmp2= mod (tmp2, yToL);
2045	tmp2 /= content (tmp2, x);
2046	tmp3 = tmp1*tmp2;
2047	if (tmp3/Lc (tmp3) == F/Lc (F))
2048	{
2049	tmp1= tmp1 (y - evaluation, y);
2050	tmp2= tmp2 (y - evaluation, y);
2051	tmp1 /= Lc (tmp1);
2052	tmp2 /= Lc (tmp2);
2053	if (!k && beta == x && degree (tmp2, alpha) < 1 &&
2054	degree (tmp1, alpha) < 1)
2055	{
2056	factorsFound++;
2057	F= 1;
2058	tmp1= mapDown (tmp1, info, source, dest);
2059	tmp2= mapDown (tmp2, info, source, dest);
2060	reconstructedFactors.append (tmp1);
2061	reconstructedFactors.append (tmp2);
2062	return;
2063	}
2064	else if (!isInExtension (tmp2, gamma, k, delta, source, dest) &&
2065	!isInExtension (tmp1, gamma, k, delta, source, dest))
2066	{
2067	factorsFound++;
2068	F= 1;
2069	tmp1= mapDown (tmp1, info, source, dest);
2070	tmp2= mapDown (tmp2, info, source, dest);
2071	reconstructedFactors.append (tmp1);
2072	reconstructedFactors.append (tmp2);
2073	return;
2074	}
2075	}
2076	}
2077	CanonicalForm quot, buf, buf2;
2078	CFListIterator iter;
2079	for (long i= 1; i <= N.NumCols(); i++)
2080	{
2081	if (factorsFoundIndex [i - 1] == 1)
2082	continue;
2083	iter= factors;
2084	if (beenInThres)
2085	{
2086	int count= 1;
2087	while (count < i)
2088	{
2089	count++;
2090	iter++;
2091	}
2092	buf= iter.getItem();
2093	}
2094	else
2095	{
2096	buf= 1;
2097	for (long j= 1; j <= N.NumRows(); j++, iter++)
2098	{
2099	if (!IsZero (N (j,i)))
2100	buf= mulMod2 (buf, iter.getItem(), yToL);
2101	}
2102	}
2103	buf *= LC (F, x);
2104	buf= mod (buf, yToL);
2105	buf /= content (buf, x);
2106	buf2= buf (y - evaluation, y);
2107	buf2 /= Lc (buf2);
2108	if (!k && beta == x)
2109	{
2110	if (degree (buf2, alpha) < 1)
2111	{
2112	if (fdivides (buf, F, quot))
2113	{
2114	factorsFoundIndex[i - 1]= 1;
2115	factorsFound++;
2116	F= quot;
2117	F /= Lc (F);
2118	buf2= mapDown (buf2, info, source, dest);
2119	reconstructedFactors.append (buf2);
2120	}
2121	}
2122	}
2123	else
2124	{
2125	if (!isInExtension (buf2, gamma, k, delta, source, dest))
2126	{
2127	if (fdivides (buf, F, quot))
2128	{
2129	factorsFoundIndex[i - 1]= 1;
2130	factorsFound++;
2131	F= quot;
2132	F /= Lc (F);
2133	buf2= mapDown (buf2, info, source, dest);
2134	reconstructedFactors.append (buf2);
2135	}
2136	}
2137	}
2138	if (degree (F) <= 0)
2139	return;
2140	if (factorsFound + 1 == N.NumCols())
2141	{
2142	CanonicalForm tmp= F (y - evaluation, y);
2143	tmp= mapDown (tmp, info, source, dest);
2144	reconstructedFactors.append (tmp);
2145	return;
2146	}
2147	}
2148	}
2149
2150	#ifdef HAVE_FLINT
2151	void
2152	extReconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const
2153	CFList& factors, const int liftBound, int& factorsFound,
2154	int*& factorsFoundIndex, nmod_mat_t N, bool beenInThres,
2155	const ExtensionInfo& info, const CanonicalForm& evaluation
2156	)
2157	{
2158	Variable y= Variable (2);
2159	Variable x= Variable (1);
2160	Variable alpha= info.getAlpha();
2161	Variable beta= info.getBeta();
2162	int k= info.getGFDegree();
2163	CanonicalForm gamma= info.getGamma();
2164	CanonicalForm delta= info.getDelta();
2165	CanonicalForm yToL= power (y, liftBound);
2166	CFList source, dest;
2167	if (factors.length() == 2)
2168	{
2169	CanonicalForm tmp1, tmp2, tmp3;
2170	tmp1= factors.getFirst();
2171	tmp2= factors.getLast();
2172	tmp1 *= LC (F, x);
2173	tmp1= mod (tmp1, yToL);
2174	tmp1 /= content (tmp1, x);
2175	tmp2 *= LC (F, x);
2176	tmp2= mod (tmp2, yToL);
2177	tmp2 /= content (tmp2, x);
2178	tmp3 = tmp1*tmp2;
2179	if (tmp3/Lc (tmp3) == F/Lc (F))
2180	{
2181	tmp1= tmp1 (y - evaluation, y);
2182	tmp2= tmp2 (y - evaluation, y);
2183	tmp1 /= Lc (tmp1);
2184	tmp2 /= Lc (tmp2);
2185	if (!k && beta == x && degree (tmp2, alpha) < 1 &&
2186	degree (tmp1, alpha) < 1)
2187	{
2188	factorsFound++;
2189	F= 1;
2190	tmp1= mapDown (tmp1, info, source, dest);
2191	tmp2= mapDown (tmp2, info, source, dest);
2192	reconstructedFactors.append (tmp1);
2193	reconstructedFactors.append (tmp2);
2194	return;
2195	}
2196	else if (!isInExtension (tmp2, gamma, k, delta, source, dest) &&
2197	!isInExtension (tmp1, gamma, k, delta, source, dest))
2198	{
2199	factorsFound++;
2200	F= 1;
2201	tmp1= mapDown (tmp1, info, source, dest);
2202	tmp2= mapDown (tmp2, info, source, dest);
2203	reconstructedFactors.append (tmp1);
2204	reconstructedFactors.append (tmp2);
2205	return;
2206	}
2207	}
2208	}
2209	CanonicalForm quot, buf, buf2;
2210	CFListIterator iter;
2211	for (long i= 0; i < nmod_mat_ncols (N); i++)
2212	{
2213	if (factorsFoundIndex [i] == 1)
2214	continue;
2215	iter= factors;
2216	if (beenInThres)
2217	{
2218	int count= 0;
2219	while (count < i)
2220	{
2221	count++;
2222	iter++;
2223	}
2224	buf= iter.getItem();
2225	}
2226	else
2227	{
2228	buf= 1;
2229	for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
2230	{
2231	if (!(nmod_mat_entry (N, j, i) == 0))
2232	buf= mulMod2 (buf, iter.getItem(), yToL);
2233	}
2234	}
2235	buf *= LC (F, x);
2236	buf= mod (buf, yToL);
2237	buf /= content (buf, x);
2238	buf2= buf (y - evaluation, y);
2239	buf2 /= Lc (buf2);
2240	if (!k && beta == x)
2241	{
2242	if (degree (buf2, alpha) < 1)
2243	{
2244	if (fdivides (buf, F, quot))
2245	{
2246	factorsFoundIndex[i]= 1;
2247	factorsFound++;
2248	F= quot;
2249	F /= Lc (F);
2250	buf2= mapDown (buf2, info, source, dest);
2251	reconstructedFactors.append (buf2);
2252	}
2253	}
2254	}
2255	else
2256	{
2257	if (!isInExtension (buf2, gamma, k, delta, source, dest))
2258	{
2259	if (fdivides (buf, F, quot))
2260	{
2261	factorsFoundIndex[i]= 1;
2262	factorsFound++;
2263	F= quot;
2264	F /= Lc (F);
2265	buf2= mapDown (buf2, info, source, dest);
2266	reconstructedFactors.append (buf2);
2267	}
2268	}
2269	}
2270	if (degree (F) <= 0)
2271	return;
2272	if (factorsFound + 1 == nmod_mat_nrows (N))
2273	{
2274	CanonicalForm tmp= F (y - evaluation, y);
2275	tmp= mapDown (tmp, info, source, dest);
2276	reconstructedFactors.append (tmp);
2277	return;
2278	}
2279	}
2280	}
2281	#endif
2282
2283	//over Fp
2284	int
2285	liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds, int
2286	start, int liftBound, int minBound, CFList& factors,
2287	mat_zz_p& NTLN, CFList& diophant, CFMatrix& M, CFArray&
2288	Pi, CFArray& bufQ, bool& irreducible
2289	)
2290	{
2291	CanonicalForm LCF= LC (F, 1);
2292	CFArray *A= new CFArray [factors.length() - 1];
2293	bool wasInBounds= false;
2294	bool hitBound= false;
2295	int l= (minBound+1)*2;
2296	int stepSize= 2;
2297	int oldL= l/2;
2298	bool reduced= false;
2299	mat_zz_p NTLK, *NTLC;
2300	CFMatrix C;
2301	CFArray buf;
2302	CFListIterator j;
2303	CanonicalForm truncF;
2304	Variable y= F.mvar();
2305	while (l <= liftBound)
2306	{
2307	if (start)
2308	{
2309	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2310	start= 0;
2311	}
2312	else
2313	{
2314	if (wasInBounds)
2315	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2316	else
2317	henselLift12 (F, factors, l, Pi, diophant, M);
2318	}
2319
2320	factors.insert (LCF);
2321	j= factors;
2322	j++;
2323
2324	truncF= mod (F, power (y, l));
2325	for (int i= 0; i < factors.length() - 1; i++, j++)
2326	{
2327	if (!wasInBounds)
2328	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2329	else
2330	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2331	bufQ[i]);
2332	}
2333
2334	for (int i= 0; i < sizeBounds; i++)
2335	{
2336	if (bounds [i] + 1 <= l/2)
2337	{
2338	wasInBounds= true;
2339	int k= tmin (bounds [i] + 1, l/2);
2340	C= CFMatrix (l - k, factors.length() - 1);
2341	for (int ii= 0; ii < factors.length() - 1; ii++)
2342	{
2343	if (A[ii].size() - 1 >= i)
2344	{
2345	buf= getCoeffs (A[ii] [i], k);
2346	writeInMatrix (C, buf, ii + 1, 0);
2347	}
2348	}
2349	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
2350	NTLK= (NTLC)NTLN;
2351	transpose (NTLK, NTLK);
2352	kernel (NTLK, NTLK);
2353	transpose (NTLK, NTLK);
2354	NTLN *= NTLK;
2355
2356	if (NTLN.NumCols() == 1)
2357	{
2358	irreducible= true;
2359	break;
2360	}
2361	if (isReduced (NTLN) && l > (minBound+1)*2)
2362	{
2363	reduced= true;
2364	break;
2365	}
2366	}
2367	}
2368
2369	if (irreducible)
2370	break;
2371	if (reduced)
2372	break;
2373	oldL= l;
2374	l += stepSize;
2375	stepSize *= 2;
2376	if (l > liftBound)
2377	{
2378	if (!hitBound)
2379	{
2380	l= liftBound;
2381	hitBound= true;
2382	}
2383	else
2384	break;
2385	}
2386	}
2387	delete [] A;
2388	if (!wasInBounds)
2389	{
2390	if (start)
2391	henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2392	else
2393	henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2394	factors.insert (LCF);
2395	}
2396	return l;
2397	}
2398
2399	#ifdef HAVE_FLINT
2400	int
2401	liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds, int
2402	start, int liftBound, int minBound, CFList& factors,
2403	nmod_mat_t FLINTN, CFList& diophant, CFMatrix& M,CFArray&
2404	Pi, CFArray& bufQ, bool& irreducible
2405	)
2406	{
2407	CanonicalForm LCF= LC (F, 1);
2408	CFArray *A= new CFArray [factors.length() - 1];
2409	bool wasInBounds= false;
2410	bool hitBound= false;
2411	int l= (minBound+1)*2;
2412	int stepSize= 2;
2413	int oldL= l/2;
2414	bool reduced= false;
2415	long rank;
2416	nmod_mat_t FLINTK, FLINTC, null;
2417	CFMatrix C;
2418	CFArray buf;
2419	CFListIterator j;
2420	CanonicalForm truncF;
2421	Variable y= F.mvar();
2422	while (l <= liftBound)
2423	{
2424	if (start)
2425	{
2426	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2427	start= 0;
2428	}
2429	else
2430	{
2431	if (wasInBounds)
2432	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2433	else
2434	henselLift12 (F, factors, l, Pi, diophant, M);
2435	}
2436
2437	factors.insert (LCF);
2438	j= factors;
2439	j++;
2440
2441	truncF= mod (F, power (y, l));
2442	for (int i= 0; i < factors.length() - 1; i++, j++)
2443	{
2444	if (!wasInBounds)
2445	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2446	else
2447	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2448	bufQ[i]);
2449	}
2450
2451	for (int i= 0; i < sizeBounds; i++)
2452	{
2453	if (bounds [i] + 1 <= l/2)
2454	{
2455	wasInBounds= true;
2456	int k= tmin (bounds [i] + 1, l/2);
2457	C= CFMatrix (l - k, factors.length() - 1);
2458	for (int ii= 0; ii < factors.length() - 1; ii++)
2459	{
2460	if (A[ii].size() - 1 >= i)
2461	{
2462	buf= getCoeffs (A[ii] [i], k);
2463	writeInMatrix (C, buf, ii + 1, 0);
2464	}
2465	}
2466
2467	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
2468	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
2469	getCharacteristic());
2470	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
2471	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
2472	getCharacteristic());
2473	rank= nmod_mat_nullspace (null, FLINTK);
2474	nmod_mat_clear (FLINTK);
2475	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
2476	nmod_mat_clear (FLINTC);
2477	nmod_mat_init_set (FLINTC, FLINTN);
2478	nmod_mat_clear (FLINTN);
2479	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
2480	getCharacteristic());
2481	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
2482
2483	nmod_mat_clear (FLINTC);
2484	nmod_mat_window_clear (FLINTK);
2485	nmod_mat_clear (null);
2486	if (nmod_mat_ncols (FLINTN) == 1)
2487	{
2488	irreducible= true;
2489	break;
2490	}
2491	if (isReduced (FLINTN) && l > (minBound+1)*2)
2492	{
2493	reduced= true;
2494	break;
2495	}
2496	}
2497	}
2498
2499	if (irreducible)
2500	break;
2501	if (reduced)
2502	break;
2503	oldL= l;
2504	l += stepSize;
2505	stepSize *= 2;
2506	if (l > liftBound)
2507	{
2508	if (!hitBound)
2509	{
2510	l= liftBound;
2511	hitBound= true;
2512	}
2513	else
2514	break;
2515	}
2516	}
2517	delete [] A;
2518	if (!wasInBounds)
2519	{
2520	if (start)
2521	henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2522	else
2523	henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2524	factors.insert (LCF);
2525	}
2526	return l;
2527	}
2528	#endif
2529
2530	//over field extension
2531	int
2532	extLiftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds,
2533	int liftBound, int minBound, int start, CFList&
2534	factors, mat_zz_p& NTLN, CFList& diophant,
2535	CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
2536	irreducible, const CanonicalForm& evaluation, const
2537	ExtensionInfo& info, CFList& source, CFList& dest
2538	)
2539	{
2540	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
2541	CanonicalForm LCF= LC (F, 1);
2542	CFArray *A= new CFArray [factors.length() - 1];
2543	bool wasInBounds= false;
2544	bool hitBound= false;
2545	int degMipo;
2546	Variable alpha;
2547	alpha= info.getAlpha();
2548	degMipo= degree (getMipo (alpha));
2549
2550	Variable gamma= info.getBeta();
2551	CanonicalForm primElemAlpha= info.getGamma();
2552	CanonicalForm imPrimElemAlpha= info.getDelta();
2553
2554	int stepSize= 2;
2555	int l= ((minBound+1)/degMipo+1)*2;
2556	l= tmax (l, 2);
2557	if (start > l)
2558	l= start;
2559	int oldL= l/2;
2560	bool reduced= false;
2561	Variable y= F.mvar();
2562	Variable x= Variable (1);
2563	CanonicalForm powX, imBasis, truncF;
2564	CFMatrix Mat, C;
2565	CFArray buf;
2566	CFIterator iter;
2567	mat_zz_p* NTLMat, *NTLC, NTLK;
2568	CFListIterator j;
2569	while (l <= liftBound)
2570	{
2571	if (start)
2572	{
2573	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2574	start= 0;
2575	}
2576	else
2577	{
2578	if (wasInBounds)
2579	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2580	else
2581	henselLift12 (F, factors, l, Pi, diophant, M);
2582	}
2583
2584	factors.insert (LCF);
2585
2586	if (GF)
2587	setCharacteristic (getCharacteristic());
2588
2589	powX= power (y-gamma, l);
2590	Mat= CFMatrix (ldegMipo, ldegMipo);
2591	for (int i= 0; i < l*degMipo; i++)
2592	{
2593	imBasis= mod (power (y, i), powX);
2594	imBasis= imBasis (power (y, degMipo), y);
2595	imBasis= imBasis (y, gamma);
2596	iter= imBasis;
2597	for (; iter.hasTerms(); iter++)
2598	Mat (iter.exp()+ 1, i+1)= iter.coeff();
2599	}
2600
2601	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
2602	NTLMat= inv (NTLMat);
2603
2604	if (GF)
2605	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2606
2607	j= factors;
2608	j++;
2609
2610	truncF= mod (F, power (y, l));
2611	for (int i= 0; i < factors.length() - 1; i++, j++)
2612	{
2613	if (!wasInBounds)
2614	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2615	else
2616	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2617	bufQ[i]);
2618	}
2619
2620	for (int i= 0; i < sizeBounds; i++)
2621	{
2622	if (bounds [i] + 1 <= (l/2)*degMipo)
2623	{
2624	wasInBounds= true;
2625	int k= tmin (bounds [i] + 1, (l/2)*degMipo);
2626	C= CFMatrix (l*degMipo - k, factors.length() - 1);
2627
2628	for (int ii= 0; ii < factors.length() - 1; ii++)
2629	{
2630	if (A[ii].size() - 1 >= i)
2631	{
2632	if (GF)
2633	{
2634	A [ii] [i]= A [ii] [i] (y-evaluation, y);
2635	setCharacteristic (getCharacteristic());
2636	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
2637	if (alpha != gamma)
2638	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2639	gamma, source, dest
2640	);
2641	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
2642	}
2643	else
2644	{
2645	A [ii] [i]= A [ii] [i] (y-evaluation, y);
2646	if (alpha != gamma)
2647	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2648	gamma, source, dest
2649	);
2650	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
2651	}
2652	writeInMatrix (C, buf, ii + 1, 0);
2653	}
2654	if (GF)
2655	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2656	}
2657
2658	if (GF)
2659	setCharacteristic(getCharacteristic());
2660
2661	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
2662	NTLK= (NTLC)NTLN;
2663	transpose (NTLK, NTLK);
2664	kernel (NTLK, NTLK);
2665	transpose (NTLK, NTLK);
2666	NTLN *= NTLK;
2667
2668	if (GF)
2669	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2670
2671	if (NTLN.NumCols() == 1)
2672	{
2673	irreducible= true;
2674	break;
2675	}
2676	if (isReduced (NTLN))
2677	{
2678	reduced= true;
2679	break;
2680	}
2681	}
2682	}
2683
2684	if (NTLN.NumCols() == 1)
2685	{
2686	irreducible= true;
2687	break;
2688	}
2689	if (reduced)
2690	break;
2691	oldL= l;
2692	l += stepSize;
2693	stepSize *= 2;
2694	if (l > liftBound)
2695	{
2696	if (!hitBound)
2697	{
2698	l= liftBound;
2699	hitBound= true;
2700	}
2701	else
2702	break;
2703	}
2704	}
2705	delete [] A;
2706	if (!wasInBounds)
2707	{
2708	if (start)
2709	henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2710	else
2711	henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2712	factors.insert (LCF);
2713	}
2714	return l;
2715	}
2716
2717	/*#ifdef HAVE_FLINT
2718	//over field extension
2719	int
2720	extLiftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds,
2721	int liftBound, int minBound, int start, CFList&
2722	factors, nmod_mat_t FLINTN, CFList& diophant,
2723	CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
2724	irreducible, const CanonicalForm& evaluation, const
2725	ExtensionInfo& info, CFList& source, CFList& dest
2726	)
2727	{
2728	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
2729	CanonicalForm LCF= LC (F, 1);
2730	CFArray *A= new CFArray [factors.length() - 1];
2731	bool wasInBounds= false;
2732	bool hitBound= false;
2733	int degMipo;
2734	Variable alpha;
2735	alpha= info.getAlpha();
2736	degMipo= degree (getMipo (alpha));
2737
2738	Variable gamma= info.getBeta();
2739	CanonicalForm primElemAlpha= info.getGamma();
2740	CanonicalForm imPrimElemAlpha= info.getDelta();
2741
2742	int stepSize= 2;
2743	int l= ((minBound+1)/degMipo+1)*2;
2744	l= tmax (l, 2);
2745	if (start > l)
2746	l= start;
2747	int oldL= l/2;
2748	bool reduced= false;
2749	Variable y= F.mvar();
2750	Variable x= Variable (1);
2751	CanonicalForm powX, imBasis, truncF;
2752	CFMatrix Mat, C;
2753	CFArray buf;
2754	CFIterator iter;
2755	long rank;
2756	nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK, null;
2757	CFListIterator j;
2758	while (l <= liftBound)
2759	{
2760	if (start)
2761	{
2762	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2763	start= 0;
2764	}
2765	else
2766	{
2767	if (wasInBounds)
2768	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2769	else
2770	henselLift12 (F, factors, l, Pi, diophant, M);
2771	}
2772
2773	factors.insert (LCF);
2774
2775	if (GF)
2776	setCharacteristic (getCharacteristic());
2777
2778	powX= power (y-gamma, l);
2779	Mat= CFMatrix (ldegMipo, ldegMipo);
2780	for (int i= 0; i < l*degMipo; i++)
2781	{
2782	imBasis= mod (power (y, i), powX);
2783	imBasis= imBasis (power (y, degMipo), y);
2784	imBasis= imBasis (y, gamma);
2785	iter= imBasis;
2786	for (; iter.hasTerms(); iter++)
2787	Mat (iter.exp()+ 1, i+1)= iter.coeff();
2788	}
2789
2790	convertFacCFMatrix2nmod_mat_t (FLINTMat, Mat);
2791	nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
2792	nmod_mat_nrows (FLINTMat), getCharacteristic());
2793	nmod_mat_inv (FLINTMatInv, FLINTMat);
2794
2795	if (GF)
2796	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2797
2798	j= factors;
2799	j++;
2800
2801	truncF= mod (F, power (y, l));
2802	for (int i= 0; i < factors.length() - 1; i++, j++)
2803	{
2804	if (!wasInBounds)
2805	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2806	else
2807	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2808	bufQ[i]);
2809	}
2810
2811	for (int i= 0; i < sizeBounds; i++)
2812	{
2813	if (bounds [i] + 1 <= (l/2)*degMipo)
2814	{
2815	wasInBounds= true;
2816	int k= tmin (bounds [i] + 1, (l/2)*degMipo);
2817	C= CFMatrix (l*degMipo - k, factors.length() - 1);
2818
2819	for (int ii= 0; ii < factors.length() - 1; ii++)
2820	{
2821	if (A[ii].size() - 1 >= i)
2822	{
2823	if (GF)
2824	{
2825	A [ii] [i]= A [ii] [i] (y-evaluation, y);
2826	setCharacteristic (getCharacteristic());
2827	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
2828	if (alpha != gamma)
2829	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2830	gamma, source, dest
2831	);
2832	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv); //TODO
2833	}
2834	else
2835	{
2836	A [ii] [i]= A [ii] [i] (y-evaluation, y);
2837	if (alpha != gamma)
2838	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
2839	gamma, source, dest
2840	);
2841	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv); //TODO
2842	}
2843	writeInMatrix (C, buf, ii + 1, 0);
2844	}
2845	if (GF)
2846	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2847	}
2848
2849	if (GF)
2850	setCharacteristic(getCharacteristic());
2851
2852	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
2853	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
2854	getCharacteristic());
2855	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
2856	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
2857	getCharacteristic());
2858	rank= nmod_mat_nullspace (null, FLINTK);
2859	nmod_mat_clear (FLINTK);
2860	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
2861	nmod_mat_clear (FLINTC);
2862	nmod_mat_init_set (FLINTC, FLINTN);
2863	nmod_mat_clear (FLINTN);
2864	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
2865	getCharacteristic());
2866	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
2867
2868	nmod_mat_clear (FLINTC);
2869	nmod_mat_window_clear (FLINTK);
2870	nmod_mat_clear (null);
2871
2872	if (GF)
2873	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
2874
2875	if (nmod_mat_ncols (FLINTN) == 1)
2876	{
2877	irreducible= true;
2878	break;
2879	}
2880	if (isReduced (FLINTN))
2881	{
2882	reduced= true;
2883	break;
2884	}
2885	}
2886	}
2887
2888	nmod_mat_clear (FLINTMat);
2889	nmod_mat_clear (FLINTMatInv);
2890
2891	if (nmod_mat_ncols (FLINTN) == 1)
2892	{
2893	irreducible= true;
2894	break;
2895	}
2896	if (reduced)
2897	break;
2898	oldL= l;
2899	l += stepSize;
2900	stepSize *= 2;
2901	if (l > liftBound)
2902	{
2903	if (!hitBound)
2904	{
2905	l= liftBound;
2906	hitBound= true;
2907	}
2908	else
2909	break;
2910	}
2911	}
2912	delete [] A;
2913	if (!wasInBounds)
2914	{
2915	if (start)
2916	henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2917	else
2918	henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2919	factors.insert (LCF);
2920	}
2921	return l;
2922	}
2923	#endif*/
2924
2925	// over Fq
2926	int
2927	liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds,
2928	int start, int liftBound, int minBound, CFList& factors,
2929	mat_zz_pE& NTLN, CFList& diophant, CFMatrix& M, CFArray&
2930	Pi, CFArray& bufQ, bool& irreducible
2931	)
2932	{
2933	CanonicalForm LCF= LC (F, 1);
2934	CFArray *A= new CFArray [factors.length() - 1];
2935	bool wasInBounds= false;
2936	bool hitBound= false;
2937	int l= (minBound+1)*2;
2938	int stepSize= 2;
2939	int oldL= l/2;
2940	bool reduced= false;
2941	CFListIterator j;
2942	mat_zz_pE* NTLC, NTLK;
2943	CFArray buf;
2944	CFMatrix C;
2945	Variable y= F.mvar();
2946	CanonicalForm truncF;
2947	while (l <= liftBound)
2948	{
2949	if (start)
2950	{
2951	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2952	start= 0;
2953	}
2954	else
2955	{
2956	if (wasInBounds)
2957	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
2958	else
2959	henselLift12 (F, factors, l, Pi, diophant, M);
2960	}
2961
2962	factors.insert (LCF);
2963	j= factors;
2964	j++;
2965
2966	truncF= mod (F, power (y,l));
2967	for (int i= 0; i < factors.length() - 1; i++, j++)
2968	{
2969	if (l == (minBound+1)*2)
2970	{
2971	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2972	}
2973	else
2974	{
2975	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2976	bufQ[i]
2977	);
2978	}
2979	}
2980
2981	for (int i= 0; i < sizeBounds; i++)
2982	{
2983	if (bounds [i] + 1 <= l/2)
2984	{
2985	wasInBounds= true;
2986	int k= tmin (bounds [i] + 1, l/2);
2987	C= CFMatrix (l - k, factors.length() - 1);
2988	for (int ii= 0; ii < factors.length() - 1; ii++)
2989	{
2990
2991	if (A[ii].size() - 1 >= i)
2992	{
2993	buf= getCoeffs (A[ii] [i], k);
2994	writeInMatrix (C, buf, ii + 1, 0);
2995	}
2996	}
2997
2998	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
2999	NTLK= (NTLC)NTLN;
3000	transpose (NTLK, NTLK);
3001	kernel (NTLK, NTLK);
3002	transpose (NTLK, NTLK);
3003	NTLN *= NTLK;
3004
3005	if (NTLN.NumCols() == 1)
3006	{
3007	irreducible= true;
3008	break;
3009	}
3010	if (isReduced (NTLN) && l > (minBound+1)*2)
3011	{
3012	reduced= true;
3013	break;
3014	}
3015	}
3016	}
3017
3018	if (NTLN.NumCols() == 1)
3019	{
3020	irreducible= true;
3021	break;
3022	}
3023	if (reduced)
3024	break;
3025	oldL= l;
3026	l += stepSize;
3027	stepSize *= 2;
3028	if (l > liftBound)
3029	{
3030	if (!hitBound)
3031	{
3032	l= liftBound;
3033	hitBound= true;
3034	}
3035	else
3036	break;
3037	}
3038	}
3039	delete [] A;
3040	if (!wasInBounds)
3041	{
3042	if (start)
3043	henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3044	else
3045	henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3046	factors.insert (LCF);
3047	}
3048	return l;
3049	}
3050
3051	#ifdef HAVE_FLINT
3052	int
3053	liftAndComputeLatticeFq2Fp (const CanonicalForm& F, int* bounds, int sizeBounds,
3054	int start, int liftBound, int minBound, CFList&
3055	factors, nmod_mat_t FLINTN, CFList& diophant,
3056	CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
3057	irreducible, const Variable& alpha
3058	)
3059	#else
3060	int
3061	liftAndComputeLatticeFq2Fp (const CanonicalForm& F, int* bounds, int sizeBounds,
3062	int start, int liftBound, int minBound, CFList&
3063	factors, mat_zz_p& NTLN, CFList& diophant, CFMatrix&
3064	M, CFArray& Pi, CFArray& bufQ, bool& irreducible,
3065	const Variable& alpha
3066	)
3067	#endif
3068	{
3069	CanonicalForm LCF= LC (F, 1);
3070	CFArray *A= new CFArray [factors.length() - 1];
3071	bool wasInBounds= false;
3072	int l= (minBound+1)*2;
3073	int oldL= l/2;
3074	int stepSize= 2;
3075	bool hitBound= false;
3076	int extensionDeg= degree (getMipo (alpha));
3077	bool reduced= false;
3078	CFListIterator j;
3079	CFMatrix C;
3080	CFArray buf;
3081	#ifdef HAVE_FLINT
3082	long rank;
3083	nmod_mat_t FLINTC, FLINTK, null;
3084	#else
3085	mat_zz_p* NTLC, NTLK;
3086	#endif
3087	Variable y= F.mvar();
3088	CanonicalForm truncF;
3089	while (l <= liftBound)
3090	{
3091	if (start)
3092	{
3093	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
3094	start= 0;
3095	}
3096	else
3097	{
3098	if (wasInBounds)
3099	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
3100	else
3101	henselLift12 (F, factors, l, Pi, diophant, M);
3102	}
3103
3104	factors.insert (LCF);
3105	j= factors;
3106	j++;
3107
3108	truncF= mod (F, power (y,l));
3109	for (int i= 0; i < factors.length() - 1; i++, j++)
3110	{
3111	if (l == (minBound+1)*2)
3112	{
3113	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
3114	}
3115	else
3116	{
3117	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
3118	bufQ[i]
3119	);
3120	}
3121	}
3122
3123	for (int i= 0; i < sizeBounds; i++)
3124	{
3125	if (bounds [i] + 1 <= l/2)
3126	{
3127	wasInBounds= true;
3128	int k= tmin (bounds [i] + 1, l/2);
3129	C= CFMatrix ((l - k)*extensionDeg, factors.length() - 1);
3130	for (int ii= 0; ii < factors.length() - 1; ii++)
3131	{
3132	if (A[ii].size() - 1 >= i)
3133	{
3134	buf= getCoeffs (A[ii] [i], k, alpha);
3135	writeInMatrix (C, buf, ii + 1, 0);
3136	}
3137	}
3138
3139	#ifdef HAVE_FLINT
3140	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
3141	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3142	getCharacteristic());
3143	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3144	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3145	getCharacteristic());
3146	rank= nmod_mat_nullspace (null, FLINTK);
3147	nmod_mat_clear (FLINTK);
3148	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3149	nmod_mat_clear (FLINTC);
3150	nmod_mat_init_set (FLINTC, FLINTN);
3151	nmod_mat_clear (FLINTN);
3152	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3153	getCharacteristic());
3154	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3155
3156	nmod_mat_clear (FLINTC);
3157	nmod_mat_window_clear (FLINTK);
3158	nmod_mat_clear (null);
3159	#else
3160	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
3161	NTLK= (NTLC)NTLN;
3162	transpose (NTLK, NTLK);
3163	kernel (NTLK, NTLK);
3164	transpose (NTLK, NTLK);
3165	NTLN *= NTLK;
3166	#endif
3167
3168	#ifdef HAVE_FLINT
3169	if (nmod_mat_nrows (FLINTN) == 1)
3170	#else
3171	if (NTLN.NumCols() == 1)
3172	#endif
3173	{
3174	irreducible= true;
3175	break;
3176	}
3177	#ifdef HAVE_FLINT
3178	if (isReduced (FLINTN) && l > (minBound+1)*2)
3179	#else
3180	if (isReduced (NTLN) && l > (minBound+1)*2)
3181	#endif
3182	{
3183	reduced= true;
3184	break;
3185	}
3186	}
3187	}
3188
3189	#ifdef HAVE_FLINT
3190	if (nmod_mat_ncols (FLINTN) == 1)
3191	#else
3192	if (NTLN.NumCols() == 1)
3193	#endif
3194	{
3195	irreducible= true;
3196	break;
3197	}
3198	if (reduced)
3199	break;
3200	oldL= l;
3201	l += stepSize;
3202	stepSize *= 2;
3203	if (l > liftBound)
3204	{
3205	if (!hitBound)
3206	{
3207	l= liftBound;
3208	hitBound= true;
3209	}
3210	else
3211	break;
3212	}
3213	}
3214	delete [] A;
3215	if (!wasInBounds)
3216	{
3217	if (start)
3218	henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3219	else
3220	henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3221	factors.insert (LCF);
3222	}
3223	return l;
3224	}
3225
3226	CFList
3227	increasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
3228	int oldNumCols, int oldL, int precision
3229	)
3230	{
3231	int d;
3232	bool isIrreducible= false;
3233	int* bounds= computeBounds (F, d, isIrreducible);
3234	if (isIrreducible)
3235	{
3236	delete [] bounds;
3237	CanonicalForm G= F;
3238	F= 1;
3239	return CFList (G);
3240	}
3241	CFArray * A= new CFArray [factors.length()];
3242	CFArray bufQ= CFArray (factors.length());
3243	#ifdef HAVE_FLINT
3244	nmod_mat_t FLINTN;
3245	nmod_mat_init (FLINTN,factors.length(),factors.length(), getCharacteristic());
3246	for (long i=factors.length()-1; i >= 0; i--)
3247	nmod_mat_entry (FLINTN, i, i)= 1;
3248	#else
3249	mat_zz_p NTLN;
3250	ident (NTLN, factors.length());
3251	#endif
3252	int minBound= bounds[0];
3253	for (int i= 1; i < d; i++)
3254	{
3255	if (bounds[i] != 0)
3256	minBound= tmin (minBound, bounds[i]);
3257	}
3258	int l= tmax (2*(minBound + 1), oldL);
3259	int oldL2= l/2;
3260	int stepSize= 2;
3261	bool useOldQs= false;
3262	bool hitBound= false;
3263	CFListIterator j;
3264	CFMatrix C;
3265	CFArray buf;
3266	#ifdef HAVE_FLINT
3267	long rank;
3268	nmod_mat_t FLINTC, FLINTK, null;
3269	#else
3270	mat_zz_p* NTLC, NTLK;
3271	#endif
3272	Variable y= F.mvar();
3273	CanonicalForm truncF;
3274	while (l <= precision)
3275	{
3276	j= factors;
3277	truncF= mod (F, power (y,l));
3278	if (useOldQs)
3279	{
3280	for (int i= 0; i < factors.length(); i++, j++)
3281	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3282	bufQ[i]
3283	);
3284	}
3285	else
3286	{
3287	for (int i= 0; i < factors.length(); i++, j++)
3288	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3289	}
3290	useOldQs= true;
3291	for (int i= 0; i < d; i++)
3292	{
3293	if (bounds [i] + 1 <= l/2)
3294	{
3295	int k= tmin (bounds [i] + 1, l/2);
3296	C= CFMatrix (l - k, factors.length());
3297	for (int ii= 0; ii < factors.length(); ii++)
3298	{
3299	if (A[ii].size() - 1 >= i)
3300	{
3301	buf= getCoeffs (A[ii] [i], k);
3302	writeInMatrix (C, buf, ii + 1, 0);
3303	}
3304	}
3305	#ifdef HAVE_FLINT
3306	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
3307	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3308	getCharacteristic());
3309	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3310	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3311	getCharacteristic());
3312	rank= nmod_mat_nullspace (null, FLINTK);
3313	nmod_mat_clear (FLINTK);
3314	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3315	nmod_mat_clear (FLINTC);
3316	nmod_mat_init_set (FLINTC, FLINTN);
3317	nmod_mat_clear (FLINTN);
3318	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3319	getCharacteristic());
3320	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3321
3322	nmod_mat_clear (FLINTC);
3323	nmod_mat_window_clear (FLINTK);
3324	nmod_mat_clear (null);
3325	#else
3326	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
3327	NTLK= (NTLC)NTLN;
3328	transpose (NTLK, NTLK);
3329	kernel (NTLK, NTLK);
3330	transpose (NTLK, NTLK);
3331	NTLN *= NTLK;
3332	#endif
3333	#ifdef HAVE_FLINT
3334	if (nmod_mat_ncols (FLINTN) == 1)
3335	{
3336	nmod_mat_clear (FLINTN);
3337	#else
3338	if (NTLN.NumCols() == 1)
3339	{
3340	#endif
3341	delete [] A;
3342	delete [] bounds;
3343	CanonicalForm G= F;
3344	F= 1;
3345	return CFList (G);
3346	}
3347	}
3348	}
3349
3350	#ifdef HAVE_FLINT
3351	if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
3352	{
3353	if (isReduced (FLINTN))
3354	{
3355	int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
3356	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
3357	#else
3358	if (NTLN.NumCols() < oldNumCols - factorsFound)
3359	{
3360	if (isReduced (NTLN))
3361	{
3362	int * factorsFoundIndex= new int [NTLN.NumCols()];
3363	for (long i= 0; i < NTLN.NumCols(); i++)
3364	#endif
3365	factorsFoundIndex[i]= 0;
3366	int factorsFound2= 0;
3367	CFList result;
3368	CanonicalForm bufF= F;
3369	#ifdef HAVE_FLINT
3370	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
3371	factorsFoundIndex, FLINTN, false
3372	);
3373	if (result.length() == nmod_mat_ncols (FLINTN))
3374	{
3375	nmod_mat_clear (FLINTN);
3376	#else
3377	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
3378	factorsFoundIndex, NTLN, false
3379	);
3380	if (result.length() == NTLN.NumCols())
3381	{
3382	#endif
3383	delete [] factorsFoundIndex;
3384	delete [] A;
3385	delete [] bounds;
3386	F= 1;
3387	return result;
3388	}
3389	delete [] factorsFoundIndex;
3390	}
3391	else if (l == precision)
3392	{
3393	CanonicalForm bufF= F;
3394	#ifdef HAVE_FLINT
3395	int * zeroOne= extractZeroOneVecs (FLINTN);
3396	CFList result= reconstruction (bufF,factors,zeroOne,precision,FLINTN);
3397	nmod_mat_clear (FLINTN);
3398	#else
3399	int * zeroOne= extractZeroOneVecs (NTLN);
3400	CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
3401	#endif
3402	F= bufF;
3403	delete [] zeroOne;
3404	delete [] A;
3405	delete [] bounds;
3406	return result;
3407	}
3408	}
3409	oldL2= l;
3410	l += stepSize;
3411	stepSize *= 2;
3412	if (l > precision)
3413	{
3414	if (!hitBound)
3415	{
3416	l= precision;
3417	hitBound= true;
3418	}
3419	else
3420	break;
3421	}
3422	}
3423	#ifdef HAVE_FLINT
3424	nmod_mat_clear (FLINTN);
3425	#endif
3426	delete [] bounds;
3427	delete [] A;
3428	return CFList();
3429	}
3430
3431	CFList
3432	increasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
3433	int oldNumCols, int oldL, const Variable&,
3434	int precision
3435	)
3436	{
3437	int d;
3438	bool isIrreducible= false;
3439	int* bounds= computeBounds (F, d, isIrreducible);
3440	if (isIrreducible)
3441	{
3442	delete [] bounds;
3443	CanonicalForm G= F;
3444	F= 1;
3445	return CFList (G);
3446	}
3447	CFArray * A= new CFArray [factors.length()];
3448	CFArray bufQ= CFArray (factors.length());
3449	mat_zz_pE NTLN;
3450	ident (NTLN, factors.length());
3451	int minBound= bounds[0];
3452	for (int i= 1; i < d; i++)
3453	{
3454	if (bounds[i] != 0)
3455	minBound= tmin (minBound, bounds[i]);
3456	}
3457	int l= tmax (2*(minBound + 1), oldL);
3458	int oldL2= l/2;
3459	int stepSize= 2;
3460	bool useOldQs= false;
3461	bool hitBound= false;
3462	CFListIterator j;
3463	CFMatrix C;
3464	mat_zz_pE* NTLC, NTLK;
3465	CFArray buf;
3466	Variable y= F.mvar();
3467	CanonicalForm truncF;
3468	while (l <= precision)
3469	{
3470	j= factors;
3471	truncF= mod (F, power (y,l));
3472	if (useOldQs)
3473	{
3474	for (int i= 0; i < factors.length(); i++, j++)
3475	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3476	bufQ[i]
3477	);
3478	}
3479	else
3480	{
3481	for (int i= 0; i < factors.length(); i++, j++)
3482	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3483	}
3484	useOldQs= true;
3485	for (int i= 0; i < d; i++)
3486	{
3487	if (bounds [i] + 1 <= l/2)
3488	{
3489	int k= tmin (bounds [i] + 1, l/2);
3490	C= CFMatrix (l - k, factors.length());
3491	for (int ii= 0; ii < factors.length(); ii++)
3492	{
3493	if (A[ii].size() - 1 >= i)
3494	{
3495	buf= getCoeffs (A[ii] [i], k);
3496	writeInMatrix (C, buf, ii + 1, 0);
3497	}
3498	}
3499	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
3500	NTLK= (NTLC)NTLN;
3501	transpose (NTLK, NTLK);
3502	kernel (NTLK, NTLK);
3503	transpose (NTLK, NTLK);
3504	NTLN *= NTLK;
3505	if (NTLN.NumCols() == 1)
3506	{
3507	delete [] A;
3508	delete [] bounds;
3509	CanonicalForm G= F;
3510	F= 1;
3511	return CFList (G);
3512	}
3513	}
3514	}
3515
3516	if (NTLN.NumCols() < oldNumCols - factorsFound)
3517	{
3518	if (isReduced (NTLN))
3519	{
3520	int * factorsFoundIndex= new int [NTLN.NumCols()];
3521	for (long i= 0; i < NTLN.NumCols(); i++)
3522	factorsFoundIndex[i]= 0;
3523	int factorsFound2= 0;
3524	CFList result;
3525	CanonicalForm bufF= F;
3526	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
3527	factorsFoundIndex, NTLN, false);
3528	if (result.length() == NTLN.NumCols())
3529	{
3530	delete [] factorsFoundIndex;
3531	delete [] A;
3532	delete [] bounds;
3533	F= 1;
3534	return result;
3535	}
3536	delete [] factorsFoundIndex;
3537	}
3538	else if (l == precision)
3539	{
3540	CanonicalForm bufF= F;
3541	int * zeroOne= extractZeroOneVecs (NTLN);
3542	CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
3543	F= bufF;
3544	delete [] zeroOne;
3545	delete [] A;
3546	delete [] bounds;
3547	return result;
3548	}
3549	}
3550	oldL2= l;
3551	l += stepSize;
3552	stepSize *= 2;
3553	if (l > precision)
3554	{
3555	if (!hitBound)
3556	{
3557	l= precision;
3558	hitBound= true;
3559	}
3560	else
3561	break;
3562	}
3563	}
3564	delete [] bounds;
3565	delete [] A;
3566	return CFList();
3567	}
3568
3569	//over field extension
3570	CFList
3571	extIncreasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
3572	int oldNumCols, int oldL, const CanonicalForm& evaluation,
3573	const ExtensionInfo& info, CFList& source, CFList& dest,
3574	int precision
3575	)
3576	{
3577	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
3578	int degMipo= degree (getMipo (info.getAlpha()));
3579	Variable alpha= info.getAlpha();
3580	int d;
3581	bool isIrreducible= false;
3582	int* bounds= computeBounds (F, d, isIrreducible);
3583	if (isIrreducible)
3584	{
3585	delete [] bounds;
3586	Variable y= Variable (2);
3587	CanonicalForm tmp= F (y - evaluation, y);
3588	CFList source, dest;
3589	tmp= mapDown (tmp, info, source, dest);
3590	F= 1;
3591	return CFList (tmp);
3592	}
3593
3594	CFArray * A= new CFArray [factors.length()];
3595	CFArray bufQ= CFArray (factors.length());
3596	if (fac_NTL_char != getCharacteristic())
3597	{
3598	fac_NTL_char= getCharacteristic();
3599	zz_p::init (getCharacteristic());
3600	}
3601	mat_zz_p NTLN;
3602	ident (NTLN, factors.length());
3603	int minBound= bounds[0];
3604	for (int i= 1; i < d; i++)
3605	{
3606	if (bounds[i] != 0)
3607	minBound= tmin (minBound, bounds[i]);
3608	}
3609	int l= tmax (oldL, 2*((minBound+1)/degMipo+1));
3610	int oldL2= l/2;
3611	int stepSize= 2;
3612	bool useOldQs= false;
3613	bool hitBound= false;
3614	Variable gamma= info.getBeta();
3615	CanonicalForm primElemAlpha= info.getGamma();
3616	CanonicalForm imPrimElemAlpha= info.getDelta();
3617	CFListIterator j;
3618	Variable y= F.mvar();
3619	CanonicalForm powX, imBasis, truncF;
3620	CFMatrix Mat, C;
3621	CFIterator iter;
3622	mat_zz_p* NTLMat,*NTLC, NTLK;
3623	CFArray buf;
3624	while (l <= precision)
3625	{
3626	j= factors;
3627	if (GF)
3628	setCharacteristic (getCharacteristic());
3629	powX= power (y-gamma, l);
3630	Mat= CFMatrix (ldegMipo, ldegMipo);
3631	for (int i= 0; i < l*degMipo; i++)
3632	{
3633	imBasis= mod (power (y, i), powX);
3634	imBasis= imBasis (power (y, degMipo), y);
3635	imBasis= imBasis (y, gamma);
3636	iter= imBasis;
3637	for (; iter.hasTerms(); iter++)
3638	Mat (iter.exp()+ 1, i+1)= iter.coeff();
3639	}
3640
3641	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
3642	NTLMat= inv (NTLMat);
3643	if (GF)
3644	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
3645
3646	truncF= mod (F, power (y, l));
3647	if (useOldQs)
3648	{
3649	for (int i= 0; i < factors.length(); i++, j++)
3650	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3651	bufQ[i]
3652	);
3653	}
3654	else
3655	{
3656	for (int i= 0; i < factors.length(); i++, j++)
3657	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3658	}
3659	useOldQs= true;
3660	for (int i= 0; i < d; i++)
3661	{
3662	if (bounds [i] + 1 <= (l/2)*degMipo)
3663	{
3664	int k= tmin (bounds [i] + 1, (l/2)*degMipo);
3665	C= CFMatrix (l*degMipo - k, factors.length());
3666	for (int ii= 0; ii < factors.length(); ii++)
3667	{
3668	if (A[ii].size() - 1 >= i)
3669	{
3670	if (GF)
3671	{
3672	A[ii] [i]= A [ii] [i] (y-evaluation, y);
3673	setCharacteristic (getCharacteristic());
3674	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
3675	if (alpha != gamma)
3676	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
3677	gamma, source, dest
3678	);
3679	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
3680	}
3681	else
3682	{
3683	A [ii] [i]= A [ii] [i] (y-evaluation, y);
3684	if (alpha != gamma)
3685	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
3686	gamma, source, dest
3687	);
3688	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
3689	}
3690	writeInMatrix (C, buf, ii + 1, 0);
3691	}
3692	if (GF)
3693	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
3694	}
3695
3696	if (GF)
3697	setCharacteristic(getCharacteristic());
3698
3699	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
3700	NTLK= (NTLC)NTLN;
3701	transpose (NTLK, NTLK);
3702	kernel (NTLK, NTLK);
3703	transpose (NTLK, NTLK);
3704	NTLN *= NTLK;
3705
3706	if (GF)
3707	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
3708
3709	if (NTLN.NumCols() == 1)
3710	{
3711	Variable y= Variable (2);
3712	CanonicalForm tmp= F (y - evaluation, y);
3713	CFList source, dest;
3714	tmp= mapDown (tmp, info, source, dest);
3715	delete [] A;
3716	delete [] bounds;
3717	F= 1;
3718	return CFList (tmp);
3719	}
3720	}
3721	}
3722
3723	if (NTLN.NumCols() < oldNumCols - factorsFound)
3724	{
3725	if (isReduced (NTLN))
3726	{
3727	int * factorsFoundIndex= new int [NTLN.NumCols()];
3728	for (long i= 0; i < NTLN.NumCols(); i++)
3729	factorsFoundIndex[i]= 0;
3730	int factorsFound2= 0;
3731	CFList result;
3732	CanonicalForm bufF= F;
3733	extReconstructionTry (result, bufF, factors,degree (F)+1, factorsFound2,
3734	factorsFoundIndex, NTLN, false, info, evaluation
3735	);
3736	if (result.length() == NTLN.NumCols())
3737	{
3738	delete [] factorsFoundIndex;
3739	delete [] A;
3740	delete [] bounds;
3741	F= 1;
3742	return result;
3743	}
3744	delete [] factorsFoundIndex;
3745	}
3746	else if (l == precision)
3747	{
3748	CanonicalForm bufF= F;
3749	int * zeroOne= extractZeroOneVecs (NTLN);
3750	CFList result= extReconstruction (bufF, factors, zeroOne, precision,
3751	NTLN, info, evaluation
3752	);
3753	F= bufF;
3754	delete [] zeroOne;
3755	delete [] A;
3756	delete [] bounds;
3757	return result;
3758	}
3759	}
3760	oldL2= l;
3761	l += stepSize;
3762	stepSize *= 2;
3763	if (l > precision)
3764	{
3765	if (!hitBound)
3766	{
3767	hitBound= true;
3768	l= precision;
3769	}
3770	else
3771	break;
3772	}
3773	}
3774	delete [] bounds;
3775	delete [] A;
3776	return CFList();
3777	}
3778
3779	CFList
3780	increasePrecision2 (const CanonicalForm& F, CFList& factors,
3781	const Variable& alpha, int precision)
3782	{
3783	int d;
3784	bool isIrreducible= false;
3785	int* bounds= computeBounds (F, d, isIrreducible);
3786	if (isIrreducible)
3787	{
3788	delete [] bounds;
3789	return CFList (F);
3790	}
3791	CFArray * A= new CFArray [factors.length()];
3792	CFArray bufQ= CFArray (factors.length());
3793	if (fac_NTL_char != getCharacteristic())
3794	{
3795	fac_NTL_char= getCharacteristic();
3796	zz_p::init (getCharacteristic());
3797	}
3798	zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
3799	zz_pE::init (NTLMipo);
3800	mat_zz_pE NTLN;
3801	ident (NTLN, factors.length());
3802	int minBound= bounds[0];
3803	for (int i= 1; i < d; i++)
3804	{
3805	if (bounds[i] != 0)
3806	minBound= tmin (minBound, bounds[i]);
3807	}
3808	int l= tmin (2*(minBound + 1), precision);
3809	int oldL= l/2;
3810	int stepSize= 2;
3811	bool useOldQs= false;
3812	bool hitBound= false;
3813	CFListIterator j;
3814	CFMatrix C;
3815	CFArray buf;
3816	mat_zz_pE* NTLC, NTLK;
3817	Variable y= F.mvar();
3818	CanonicalForm truncF;
3819	while (l <= precision)
3820	{
3821	j= factors;
3822	truncF= mod (F, power (y, l));
3823	if (useOldQs)
3824	{
3825	for (int i= 0; i < factors.length(); i++, j++)
3826	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i], bufQ[i]);
3827	}
3828	else
3829	{
3830	for (int i= 0; i < factors.length(); i++, j++)
3831	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3832	}
3833	useOldQs= true;
3834	for (int i= 0; i < d; i++)
3835	{
3836	if (bounds [i] + 1 <= l/2)
3837	{
3838	int k= tmin (bounds [i] + 1, l/2);
3839	C= CFMatrix (l - k, factors.length());
3840	for (int ii= 0; ii < factors.length(); ii++)
3841	{
3842	if (A[ii].size() - 1 >= i)
3843	{
3844	buf= getCoeffs (A[ii] [i], k);
3845	writeInMatrix (C, buf, ii + 1, 0);
3846	}
3847	}
3848	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
3849	NTLK= (NTLC)NTLN;
3850	transpose (NTLK, NTLK);
3851	kernel (NTLK, NTLK);
3852	transpose (NTLK, NTLK);
3853	NTLN *= NTLK;
3854	if (NTLN.NumCols() == 1)
3855	{
3856	delete [] A;
3857	delete [] bounds;
3858	return CFList (F);
3859	}
3860	}
3861	}
3862
3863	if (isReduced (NTLN) \|\| l == precision)
3864	{
3865	CanonicalForm bufF= F;
3866	int * zeroOne= extractZeroOneVecs (NTLN);
3867	CFList bufFactors= factors;
3868	CFList result= monicReconstruction (bufF, factors, zeroOne, precision,
3869	NTLN
3870	);
3871	if (result.length() != NTLN.NumCols() && l != precision)
3872	factors= bufFactors;
3873	if (result.length() == NTLN.NumCols())
3874	{
3875	delete [] zeroOne;
3876	delete [] A;
3877	delete [] bounds;
3878	return result;
3879	}
3880	if (l == precision)
3881	{
3882	delete [] zeroOne;
3883	delete [] A;
3884	delete [] bounds;
3885	return Union (result, factors);
3886	}
3887	}
3888	oldL= l;
3889	l += stepSize;
3890	stepSize *= 2;
3891	if (l > precision)
3892	{
3893	if (!hitBound)
3894	{
3895	l= precision;
3896	hitBound= true;
3897	}
3898	else
3899	break;
3900	}
3901	}
3902	delete [] bounds;
3903	delete [] A;
3904	return CFList();
3905	}
3906
3907	CFList
3908	increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int factorsFound,
3909	int oldNumCols, int oldL, const Variable& alpha,
3910	int precision
3911	)
3912	{
3913	int d;
3914	bool isIrreducible= false;
3915	int* bounds= computeBounds (F, d, isIrreducible);
3916	if (isIrreducible)
3917	{
3918	delete [] bounds;
3919	CanonicalForm G= F;
3920	F= 1;
3921	return CFList (G);
3922	}
3923	int extensionDeg= degree (getMipo (alpha));
3924	CFArray * A= new CFArray [factors.length()];
3925	CFArray bufQ= CFArray (factors.length());
3926	#ifdef HAVE_FLINT
3927	nmod_mat_t FLINTN;
3928	nmod_mat_init (FLINTN,factors.length(),factors.length(), getCharacteristic());
3929	for (long i=factors.length()-1; i >= 0; i--)
3930	nmod_mat_entry (FLINTN, i, i)= 1;
3931	#else
3932	mat_zz_p NTLN;
3933	ident (NTLN, factors.length());
3934	#endif
3935	int minBound= bounds[0];
3936	for (int i= 1; i < d; i++)
3937	{
3938	if (bounds[i] != 0)
3939	minBound= tmin (minBound, bounds[i]);
3940	}
3941	int l= tmax (2*(minBound + 1), oldL);
3942	int oldL2= l/2;
3943	int stepSize= 2;
3944	bool useOldQs= false;
3945	bool hitBound= false;
3946	CFListIterator j;
3947	CFMatrix C;
3948	#ifdef HAVE_FLINT
3949	long rank;
3950	nmod_mat_t FLINTC, FLINTK, null;
3951	#else
3952	mat_zz_p* NTLC, NTLK;
3953	#endif
3954	CFArray buf;
3955	Variable y= F.mvar();
3956	CanonicalForm truncF;
3957	while (l <= precision)
3958	{
3959	j= factors;
3960	truncF= mod (F, power (y, l));
3961	if (useOldQs)
3962	{
3963	for (int i= 0; i < factors.length(); i++, j++)
3964	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3965	bufQ[i]
3966	);
3967	}
3968	else
3969	{
3970	for (int i= 0; i < factors.length(); i++, j++)
3971	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3972	}
3973	useOldQs= true;
3974	for (int i= 0; i < d; i++)
3975	{
3976	if (bounds [i] + 1 <= l/2)
3977	{
3978	int k= tmin (bounds [i] + 1, l/2);
3979	C= CFMatrix ((l - k)*extensionDeg, factors.length());
3980	for (int ii= 0; ii < factors.length(); ii++)
3981	{
3982	if (A[ii].size() - 1 >= i)
3983	{
3984	buf= getCoeffs (A[ii] [i], k, alpha);
3985	writeInMatrix (C, buf, ii + 1, 0);
3986	}
3987	}
3988	#ifdef HAVE_FLINT
3989	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
3990	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3991	getCharacteristic());
3992	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3993	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3994	getCharacteristic());
3995	rank= nmod_mat_nullspace (null, FLINTK);
3996	nmod_mat_clear (FLINTK);
3997	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
3998	nmod_mat_clear (FLINTC);
3999	nmod_mat_init_set (FLINTC, FLINTN);
4000	nmod_mat_clear (FLINTN);
4001	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4002	getCharacteristic());
4003	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4004
4005	nmod_mat_clear (FLINTC);
4006	nmod_mat_window_clear (FLINTK);
4007	nmod_mat_clear (null);
4008	#else
4009	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4010	NTLK= (NTLC)NTLN;
4011	transpose (NTLK, NTLK);
4012	kernel (NTLK, NTLK);
4013	transpose (NTLK, NTLK);
4014	NTLN *= NTLK;
4015	#endif
4016	#ifdef HAVE_FLINT
4017	if (nmod_mat_ncols (FLINTN) == 1)
4018	{
4019	nmod_mat_clear (FLINTN);
4020	#else
4021	if (NTLN.NumCols() == 1)
4022	{
4023	#endif
4024	delete [] A;
4025	delete [] bounds;
4026	CanonicalForm G= F;
4027	F= 1;
4028	return CFList (G);
4029	}
4030	}
4031	}
4032
4033	#ifdef HAVE_FLINT
4034	if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
4035	{
4036	if (isReduced (FLINTN))
4037	{
4038	int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
4039	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
4040	#else
4041	if (NTLN.NumCols() < oldNumCols - factorsFound)
4042	{
4043	if (isReduced (NTLN))
4044	{
4045	int * factorsFoundIndex= new int [NTLN.NumCols()];
4046	for (long i= 0; i < NTLN.NumCols(); i++)
4047	#endif
4048	factorsFoundIndex[i]= 0;
4049	int factorsFound2= 0;
4050	CFList result;
4051	CanonicalForm bufF= F;
4052	#ifdef HAVE_FLINT
4053	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
4054	factorsFoundIndex, FLINTN, false
4055	);
4056	if (result.length() == nmod_mat_ncols (FLINTN))
4057	{
4058	nmod_mat_clear (FLINTN);
4059	#else
4060	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
4061	factorsFoundIndex, NTLN, false
4062	);
4063	if (result.length() == NTLN.NumCols())
4064	{
4065	#endif
4066	delete [] factorsFoundIndex;
4067	delete [] A;
4068	delete [] bounds;
4069	F= 1;
4070	return result;
4071	}
4072	delete [] factorsFoundIndex;
4073	}
4074	else if (l == precision)
4075	{
4076	CanonicalForm bufF= F;
4077	#ifdef HAVE_FLINT
4078	int * zeroOne= extractZeroOneVecs (FLINTN);
4079	CFList result= reconstruction (bufF,factors,zeroOne,precision,FLINTN);
4080	nmod_mat_clear (FLINTN);
4081	#else
4082	int * zeroOne= extractZeroOneVecs (NTLN);
4083	CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
4084	#endif
4085	F= bufF;
4086	delete [] zeroOne;
4087	delete [] A;
4088	delete [] bounds;
4089	return result;
4090	}
4091	}
4092	oldL2= l;
4093	l += stepSize;
4094	stepSize *= 2;
4095	if (l > precision)
4096	{
4097	if (!hitBound)
4098	{
4099	hitBound= true;
4100	l= precision;
4101	}
4102	else
4103	break;
4104	}
4105	}
4106	#ifdef HAVE_FLINT
4107	nmod_mat_clear (FLINTN);
4108	#endif
4109	delete [] bounds;
4110	delete [] A;
4111	return CFList();
4112	}
4113
4114	#ifdef HAVE_FLINT
4115	CFList
4116	increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int
4117	l, int d, int* bounds, CFArray& bufQ, nmod_mat_t FLINTN
4118	)
4119	#else
4120	CFList
4121	increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int
4122	l, int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN
4123	)
4124	#endif
4125	{
4126	CFList result= CFList();
4127	CFArray * A= new CFArray [factors.length()];
4128	int oldL2= oldL/2;
4129	bool hitBound= false;
4130	#ifdef HAVE_FLINT
4131	if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4132	{
4133	nmod_mat_clear (FLINTN);
4134	nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
4135	for (long i=factors.length()-1; i >= 0; i--)
4136	nmod_mat_entry (FLINTN, i, i)= 1;
4137	bufQ= CFArray (factors.length());
4138	}
4139	#else
4140	if (NTLN.NumRows() != factors.length()) //refined factors
4141	{
4142	ident (NTLN, factors.length());
4143	bufQ= CFArray (factors.length());
4144	}
4145	#endif
4146	bool useOldQs= false;
4147	CFListIterator j;
4148	CFMatrix C;
4149	CFArray buf;
4150	#ifdef HAVE_FLINT
4151	long rank;
4152	nmod_mat_t FLINTC, FLINTK, null;
4153	#else
4154	mat_zz_p* NTLC, NTLK;
4155	#endif
4156	CanonicalForm bufF, truncF;
4157	CFList bufUniFactors;
4158	Variable y= F.mvar();
4159	while (oldL <= l)
4160	{
4161	j= factors;
4162	truncF= mod (F, power (y, oldL));
4163	if (useOldQs)
4164	{
4165	for (int i= 0; i < factors.length(); i++, j++)
4166	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4167	bufQ[i]
4168	);
4169	}
4170	else
4171	{
4172	for (int i= 0; i < factors.length(); i++, j++)
4173	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4174	}
4175	useOldQs= true;
4176
4177	for (int i= 0; i < d; i++)
4178	{
4179	if (bounds [i] + 1 <= oldL/2)
4180	{
4181	int k= tmin (bounds [i] + 1, oldL/2);
4182	C= CFMatrix (oldL - k, factors.length());
4183	for (int ii= 0; ii < factors.length(); ii++)
4184	{
4185	if (A[ii].size() - 1 >= i)
4186	{
4187	buf= getCoeffs (A[ii] [i], k);
4188	writeInMatrix (C, buf, ii + 1, 0);
4189	}
4190	}
4191	#ifdef HAVE_FLINT
4192	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
4193	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4194	getCharacteristic());
4195	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4196	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4197	getCharacteristic());
4198	rank= nmod_mat_nullspace (null, FLINTK);
4199	nmod_mat_clear (FLINTK);
4200	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4201	nmod_mat_clear (FLINTC);
4202	nmod_mat_init_set (FLINTC, FLINTN);
4203	nmod_mat_clear (FLINTN);
4204	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4205	getCharacteristic());
4206	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4207
4208	nmod_mat_clear (FLINTC);
4209	nmod_mat_window_clear (FLINTK);
4210	nmod_mat_clear (null);
4211	#else
4212	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4213	NTLK= (NTLC)NTLN;
4214	transpose (NTLK, NTLK);
4215	kernel (NTLK, NTLK);
4216	transpose (NTLK, NTLK);
4217	NTLN *= NTLK;
4218	#endif
4219	#ifdef HAVE_FLINT
4220	if (nmod_mat_ncols (FLINTN) == 1)
4221	#else
4222	if (NTLN.NumCols() == 1)
4223	#endif
4224	{
4225	delete [] A;
4226	return CFList (F);
4227	}
4228	}
4229	}
4230	#ifdef HAVE_FLINT
4231	if (nmod_mat_ncols (FLINTN) == 1)
4232	#else
4233	if (NTLN.NumCols() == 1)
4234	#endif
4235	{
4236	delete [] A;
4237	return CFList (F);
4238	}
4239	int * zeroOneVecs;
4240	#ifdef HAVE_FLINT
4241	zeroOneVecs= extractZeroOneVecs (FLINTN);
4242	#else
4243	zeroOneVecs= extractZeroOneVecs (NTLN);
4244	#endif
4245	bufF= F;
4246	bufUniFactors= factors;
4247	#ifdef HAVE_FLINT
4248	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, FLINTN);
4249	#else
4250	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
4251	#endif
4252	delete [] zeroOneVecs;
4253	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < oldL && result.length() > 0)
4254	{
4255	F= bufF;
4256	factors= bufUniFactors;
4257	delete [] A;
4258	return result;
4259	}
4260
4261	result= CFList();
4262	oldL2= oldL;
4263	oldL *= 2;
4264	if (oldL > l)
4265	{
4266	if (!hitBound)
4267	{
4268	oldL= l;
4269	hitBound= true;
4270	}
4271	else
4272	break;
4273	}
4274	}
4275	delete [] A;
4276	return result;
4277	}
4278
4279	CFList
4280	increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int
4281	l, int d, int* bounds, CFArray& bufQ, mat_zz_pE& NTLN
4282	)
4283	{
4284	CFList result= CFList();
4285	CFArray * A= new CFArray [factors.length()];
4286	int oldL2= oldL/2;
4287	bool hitBound= false;
4288	bool useOldQs= false;
4289	if (NTLN.NumRows() != factors.length()) //refined factors
4290	ident (NTLN, factors.length());
4291	CFListIterator j;
4292	CFMatrix C;
4293	CFArray buf;
4294	mat_zz_pE* NTLC, NTLK;
4295	CanonicalForm bufF, truncF;
4296	CFList bufUniFactors;
4297	Variable y= F.mvar();
4298	while (oldL <= l)
4299	{
4300	j= factors;
4301	truncF= mod (F, power (y, oldL));
4302	if (useOldQs)
4303	{
4304	for (int i= 0; i < factors.length(); i++, j++)
4305	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4306	bufQ[i]
4307	);
4308	}
4309	else
4310	{
4311	for (int i= 0; i < factors.length(); i++, j++)
4312	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4313	}
4314	useOldQs= true;
4315
4316	for (int i= 0; i < d; i++)
4317	{
4318	if (bounds [i] + 1 <= oldL/2)
4319	{
4320	int k= tmin (bounds [i] + 1, oldL/2);
4321	C= CFMatrix (oldL - k, factors.length());
4322	for (int ii= 0; ii < factors.length(); ii++)
4323	{
4324	if (A[ii].size() - 1 >= i)
4325	{
4326	buf= getCoeffs (A[ii] [i], k);
4327	writeInMatrix (C, buf, ii + 1, 0);
4328	}
4329	}
4330	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
4331	NTLK= (NTLC)NTLN;
4332	transpose (NTLK, NTLK);
4333	kernel (NTLK, NTLK);
4334	transpose (NTLK, NTLK);
4335	NTLN *= NTLK;
4336	if (NTLN.NumCols() == 1)
4337	{
4338	delete [] A;
4339	return CFList (F);
4340	}
4341	}
4342	}
4343	if (NTLN.NumCols() == 1)
4344	{
4345	delete [] A;
4346	return CFList (F);
4347	}
4348
4349	int * zeroOneVecs;
4350	zeroOneVecs= extractZeroOneVecs (NTLN);
4351	bufF= F;
4352	bufUniFactors= factors;
4353	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
4354	delete [] zeroOneVecs;
4355	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4356	{
4357	F= bufF;
4358	factors= bufUniFactors;
4359	delete [] A;
4360	return result;
4361	}
4362
4363	result= CFList();
4364	oldL2= oldL;
4365	oldL *= 2;
4366	if (oldL > l)
4367	{
4368	if (!hitBound)
4369	{
4370	oldL= l;
4371	hitBound= true;
4372	}
4373	else
4374	break;
4375	}
4376	}
4377	delete [] A;
4378	return result;
4379	}
4380
4381	//over field extension
4382	CFList
4383	extIncreasePrecision (CanonicalForm& F, CFList& factors, int oldL, int l, int d,
4384	int* bounds, CFArray& bufQ, mat_zz_p& NTLN, const
4385	CanonicalForm& evaluation, const ExtensionInfo& info,
4386	CFList& source, CFList& dest
4387	)
4388	{
4389	CFList result= CFList();
4390	CFArray * A= new CFArray [factors.length()];
4391	int oldL2= oldL/2; //be careful
4392	bool hitBound= false;
4393	bool useOldQs= false;
4394	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
4395	int degMipo= degree (getMipo (info.getAlpha()));
4396	Variable alpha= info.getAlpha();
4397
4398	Variable gamma= info.getBeta();
4399	CanonicalForm primElemAlpha= info.getGamma();
4400	CanonicalForm imPrimElemAlpha= info.getDelta();
4401	if (NTLN.NumRows() != factors.length()) //refined factors
4402	ident (NTLN, factors.length());
4403	Variable y= F.mvar();
4404	CFListIterator j;
4405	CanonicalForm powX, imBasis, bufF, truncF;
4406	CFMatrix Mat, C;
4407	CFIterator iter;
4408	mat_zz_p* NTLMat;
4409	CFArray buf;
4410	mat_zz_p* NTLC, NTLK;
4411	CFList bufUniFactors;
4412	while (oldL <= l)
4413	{
4414	j= factors;
4415	if (GF)
4416	setCharacteristic (getCharacteristic());
4417
4418	powX= power (y-gamma, oldL);
4419	Mat= CFMatrix (oldLdegMipo, oldLdegMipo);
4420	for (int i= 0; i < oldL*degMipo; i++)
4421	{
4422	imBasis= mod (power (y, i), powX);
4423	imBasis= imBasis (power (y, degMipo), y);
4424	imBasis= imBasis (y, gamma);
4425	iter= imBasis;
4426	for (; iter.hasTerms(); iter++)
4427	Mat (iter.exp()+ 1, i+1)= iter.coeff();
4428	}
4429
4430	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
4431	NTLMat= inv (NTLMat);
4432	if (GF)
4433	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
4434
4435	truncF= mod (F, power (y, oldL));
4436	if (useOldQs)
4437	{
4438	for (int i= 0; i < factors.length(); i++, j++)
4439	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4440	bufQ[i]);
4441	}
4442	else
4443	{
4444	for (int i= 0; i < factors.length(); i++, j++)
4445	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4446	}
4447	useOldQs= true;
4448
4449	for (int i= 0; i < d; i++)
4450	{
4451	if (bounds [i] + 1 <= oldL/2)
4452	{
4453	int k= tmin (bounds [i] + 1, oldL/2);
4454	C= CFMatrix (oldL*degMipo - k, factors.length());
4455	for (int ii= 0; ii < factors.length(); ii++)
4456	{
4457	if (A[ii].size() - 1 >= i)
4458	{
4459	if (GF)
4460	{
4461	A [ii] [i]= A [ii] [i] (y-evaluation, y);
4462	setCharacteristic (getCharacteristic());
4463	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
4464	if (alpha != gamma)
4465	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
4466	gamma, source, dest
4467	);
4468	buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
4469	}
4470	else
4471	{
4472	A [ii] [i]= A [ii] [i] (y-evaluation, y);
4473	if (alpha != gamma)
4474	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
4475	gamma, source, dest
4476	);
4477	buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
4478	}
4479	writeInMatrix (C, buf, ii + 1, 0);
4480	}
4481	if (GF)
4482	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
4483	}
4484
4485	if (GF)
4486	setCharacteristic(getCharacteristic());
4487
4488	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4489	NTLK= (NTLC)NTLN;
4490	transpose (NTLK, NTLK);
4491	kernel (NTLK, NTLK);
4492	transpose (NTLK, NTLK);
4493	NTLN *= NTLK;
4494
4495	if (GF)
4496	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
4497
4498	if (NTLN.NumCols() == 1)
4499	{
4500	Variable y= Variable (2);
4501	CanonicalForm tmp= F (y - evaluation, y);
4502	CFList source, dest;
4503	tmp= mapDown (tmp, info, source, dest);
4504	delete [] A;
4505	return CFList (tmp);
4506	}
4507	}
4508	}
4509	if (NTLN.NumCols() == 1)
4510	{
4511	Variable y= Variable (2);
4512	CanonicalForm tmp= F (y - evaluation, y);
4513	CFList source, dest;
4514	tmp= mapDown (tmp, info, source, dest);
4515	delete [] A;
4516	return CFList (tmp);
4517	}
4518
4519	int * zeroOneVecs;
4520	zeroOneVecs= extractZeroOneVecs (NTLN);
4521	bufF= F;
4522	bufUniFactors= factors;
4523	result= extReconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN,
4524	info, evaluation
4525	);
4526	delete [] zeroOneVecs;
4527	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4528	{
4529	F= bufF;
4530	factors= bufUniFactors;
4531	return result;
4532	}
4533
4534	result= CFList();
4535	oldL2= oldL;
4536	oldL *= 2;
4537	if (oldL > l)
4538	{
4539	if (!hitBound)
4540	{
4541	oldL= l;
4542	hitBound= true;
4543	}
4544	else
4545	break;
4546	}
4547	}
4548	delete [] A;
4549	return result;
4550	}
4551
4552	#ifdef HAVE_FLINT
4553	CFList
4554	increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int oldL, int l,
4555	int d, int* bounds, CFArray& bufQ, nmod_mat_t FLINTN,
4556	const Variable& alpha
4557	)
4558	#else
4559	CFList
4560	increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int oldL, int l,
4561	int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN,
4562	const Variable& alpha
4563	)
4564	#endif
4565	{
4566	CFList result= CFList();
4567	CFArray * A= new CFArray [factors.length()];
4568	int extensionDeg= degree (getMipo (alpha));
4569	int oldL2= oldL/2;
4570	bool hitBound= false;
4571	bool useOldQs= false;
4572	#ifdef HAVE_FLINT
4573	if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4574	{
4575	nmod_mat_clear (FLINTN);
4576	nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
4577	for (long i=factors.length()-1; i >= 0; i--)
4578	nmod_mat_entry (FLINTN, i, i)= 1;
4579	}
4580	#else
4581	if (NTLN.NumRows() != factors.length()) //refined factors
4582	ident (NTLN, factors.length());
4583	#endif
4584	CFListIterator j;
4585	CFMatrix C;
4586	CFArray buf;
4587	#ifdef HAVE_FLINT
4588	long rank;
4589	nmod_mat_t FLINTC, FLINTK, null;
4590	#else
4591	mat_zz_p* NTLC, NTLK;
4592	#endif
4593	CanonicalForm bufF, truncF;
4594	CFList bufUniFactors;
4595	Variable y= F.mvar();
4596	while (oldL <= l)
4597	{
4598	j= factors;
4599	truncF= mod (F, power (y, oldL));
4600	if (useOldQs)
4601	{
4602	for (int i= 0; i < factors.length(); i++, j++)
4603	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4604	bufQ[i]
4605	);
4606	}
4607	else
4608	{
4609	for (int i= 0; i < factors.length(); i++, j++)
4610	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4611	}
4612	useOldQs= true;
4613
4614	for (int i= 0; i < d; i++)
4615	{
4616	if (bounds [i] + 1 <= oldL/2)
4617	{
4618	int k= tmin (bounds [i] + 1, oldL/2);
4619	C= CFMatrix ((oldL - k)*extensionDeg, factors.length());
4620	for (int ii= 0; ii < factors.length(); ii++)
4621	{
4622	if (A[ii].size() - 1 >= i)
4623	{
4624	buf= getCoeffs (A[ii] [i], k, alpha);
4625	writeInMatrix (C, buf, ii + 1, 0);
4626	}
4627	}
4628	#ifdef HAVE_FLINT
4629	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
4630	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4631	getCharacteristic());
4632	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4633	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4634	getCharacteristic());
4635	rank= nmod_mat_nullspace (null, FLINTK);
4636	nmod_mat_clear (FLINTK);
4637	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4638	nmod_mat_clear (FLINTC);
4639	nmod_mat_init_set (FLINTC, FLINTN);
4640	nmod_mat_clear (FLINTN);
4641	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4642	getCharacteristic());
4643	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4644
4645	nmod_mat_clear (FLINTC);
4646	nmod_mat_window_clear (FLINTK);
4647	nmod_mat_clear (null);
4648	#else
4649	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4650	NTLK= (NTLC)NTLN;
4651	transpose (NTLK, NTLK);
4652	kernel (NTLK, NTLK);
4653	transpose (NTLK, NTLK);
4654	NTLN *= NTLK;
4655	#endif
4656	#ifdef HAVE_FLINT
4657	if (nmod_mat_ncols (FLINTN) == 1)
4658	#else
4659	if (NTLN.NumCols() == 1)
4660	#endif
4661	{
4662	delete [] A;
4663	return CFList (F);
4664	}
4665	}
4666	}
4667
4668	int * zeroOneVecs;
4669	#ifdef HAVE_FLINT
4670	zeroOneVecs= extractZeroOneVecs (FLINTN);
4671	#else
4672	zeroOneVecs= extractZeroOneVecs (NTLN);
4673	#endif
4674
4675	bufF= F;
4676	bufUniFactors= factors;
4677	#ifdef HAVE_FLINT
4678	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, FLINTN);
4679	#else
4680	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
4681	#endif
4682	delete [] zeroOneVecs;
4683	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4684	{
4685	F= bufF;
4686	factors= bufUniFactors;
4687	delete [] A;
4688	return result;
4689	}
4690
4691	result= CFList();
4692	oldL2= oldL;
4693	oldL *= 2;
4694	if (oldL > l)
4695	{
4696	if (!hitBound)
4697	{
4698	oldL= l;
4699	hitBound= true;
4700	}
4701	else
4702	break;
4703	}
4704	}
4705	delete [] A;
4706	return result;
4707	}
4708
4709	#ifdef HAVE_FLINT
4710	CFList
4711	furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList&
4712	factors, int l, int liftBound, int d, int*
4713	bounds, nmod_mat_t FLINTN, CFList& diophant,
4714	CFMatrix& M, CFArray& Pi, CFArray& bufQ
4715	)
4716	#else
4717	CFList
4718	furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList&
4719	factors, int l, int liftBound, int d, int*
4720	bounds, mat_zz_p& NTLN, CFList& diophant,
4721	CFMatrix& M, CFArray& Pi, CFArray& bufQ
4722	)
4723	#endif
4724	{
4725	CanonicalForm LCF= LC (F, 1);
4726	CFList result;
4727	bool irreducible= false;
4728	CFList bufFactors= factors;
4729	CFArray *A = new CFArray [bufFactors.length()];
4730	bool useOldQs= false;
4731	bool hitBound= false;
4732	int oldL= l;
4733	int stepSize= 8; //TODO choose better step size?
4734	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
4735	#ifdef HAVE_FLINT
4736	if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4737	{
4738	nmod_mat_clear (FLINTN);
4739	nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
4740	for (long i=factors.length()-1; i >= 0; i--)
4741	nmod_mat_entry (FLINTN, i, i)= 1;
4742	}
4743	#else
4744	if (NTLN.NumRows() != factors.length()) //refined factors
4745	ident (NTLN, factors.length());
4746	#endif
4747	CFListIterator j;
4748	CFMatrix C;
4749	CFArray buf;
4750	#ifdef HAVE_FLINT
4751	long rank;
4752	nmod_mat_t FLINTC, FLINTK, null;
4753	#else
4754	mat_zz_p* NTLC, NTLK;
4755	#endif
4756	CanonicalForm bufF, truncF;
4757	Variable y= F.mvar();
4758	while (l <= liftBound)
4759	{
4760	bufFactors.insert (LCF);
4761	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
4762	bufFactors.insert (LCF);
4763	bufFactors.removeFirst();
4764	j= bufFactors;
4765	truncF= mod (F, power (y, l));
4766	if (useOldQs)
4767	{
4768	for (int i= 0; i < bufFactors.length(); i++, j++)
4769	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
4770	bufQ[i]);
4771	}
4772	else
4773	{
4774	for (int i= 0; i < bufFactors.length(); i++, j++)
4775	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
4776	}
4777	for (int i= 0; i < d; i++)
4778	{
4779	if (bounds [i] + 1 <= l/2)
4780	{
4781	int k= tmin (bounds [i] + 1, l/2);
4782	C= CFMatrix (l - k, bufFactors.length());
4783	for (int ii= 0; ii < bufFactors.length(); ii++)
4784	{
4785	if (A[ii].size() - 1 >= i)
4786	{
4787	buf= getCoeffs (A[ii] [i], k);
4788	writeInMatrix (C, buf, ii + 1, 0);
4789	}
4790	}
4791	#ifdef HAVE_FLINT
4792	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
4793	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4794	getCharacteristic());
4795	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4796	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4797	getCharacteristic());
4798	rank= nmod_mat_nullspace (null, FLINTK);
4799	nmod_mat_clear (FLINTK);
4800	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
4801	nmod_mat_clear (FLINTC);
4802	nmod_mat_init_set (FLINTC, FLINTN);
4803	nmod_mat_clear (FLINTN);
4804	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4805	getCharacteristic());
4806	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4807
4808	nmod_mat_clear (FLINTC);
4809	nmod_mat_window_clear (FLINTK);
4810	nmod_mat_clear (null);
4811	#else
4812	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
4813	NTLK= (NTLC)NTLN;
4814	transpose (NTLK, NTLK);
4815	kernel (NTLK, NTLK);
4816	transpose (NTLK, NTLK);
4817	NTLN *= NTLK;
4818	#endif
4819	#ifdef HAVE_FLINT
4820	if (nmod_mat_ncols (FLINTN) == 1)
4821	#else
4822	if (NTLN.NumCols() == 1)
4823	#endif
4824	{
4825	irreducible= true;
4826	break;
4827	}
4828	}
4829	}
4830
4831	#ifdef HAVE_FLINT
4832	if (nmod_mat_ncols (FLINTN) == 1)
4833	#else
4834	if (NTLN.NumCols() == 1)
4835	#endif
4836	{
4837	irreducible= true;
4838	break;
4839	}
4840
4841	#ifdef HAVE_FLINT
4842	int * zeroOneVecs= extractZeroOneVecs (FLINTN);
4843	#else
4844	int * zeroOneVecs= extractZeroOneVecs (NTLN);
4845	#endif
4846	bufF= F;
4847	#ifdef HAVE_FLINT
4848	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, FLINTN);
4849	#else
4850	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
4851	#endif
4852	delete [] zeroOneVecs;
4853	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
4854	{
4855	F= bufF;
4856	factors= bufFactors;
4857	delete [] A;
4858	return result;
4859	}
4860
4861	#ifdef HAVE_FLINT
4862	if (isReduced (FLINTN))
4863	#else
4864	if (isReduced (NTLN))
4865	#endif
4866	{
4867	int factorsFound= 0;
4868	bufF= F;
4869	#ifdef HAVE_FLINT
4870	int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
4871	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
4872	#else
4873	int* factorsFoundIndex= new int [NTLN.NumCols()];
4874	for (long i= 0; i < NTLN.NumCols(); i++)
4875	#endif
4876	factorsFoundIndex[i]= 0;
4877	#ifdef HAVE_FLINT
4878	if (l < liftBound)
4879	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
4880	factorsFoundIndex, FLINTN, false
4881	);
4882	else
4883	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
4884	degree (LCF), factorsFound, factorsFoundIndex,
4885	FLINTN, false
4886	);
4887
4888	if (nmod_mat_ncols (FLINTN) == result.length())
4889	#else
4890	if (l < liftBound)
4891	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
4892	factorsFoundIndex, NTLN, false
4893	);
4894	else
4895	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
4896	degree (LCF), factorsFound, factorsFoundIndex,
4897	NTLN, false
4898	);
4899
4900	if (NTLN.NumCols() == result.length())
4901	#endif
4902	{
4903	delete [] A;
4904	delete [] factorsFoundIndex;
4905	return result;
4906	}
4907	delete [] factorsFoundIndex;
4908	}
4909	result= CFList();
4910	oldL= l;
4911	stepSize *= 2;
4912	l += stepSize;
4913	if (l > liftBound)
4914	{
4915	if (!hitBound)
4916	{
4917	l= liftBound;
4918	hitBound= true;
4919	}
4920	else
4921	break;
4922	}
4923	}
4924	if (irreducible)
4925	{
4926	delete [] A;
4927	return CFList (F);
4928	}
4929	delete [] A;
4930	factors= bufFactors;
4931	return CFList();
4932	}
4933
4934	//Fq
4935	CFList
4936	furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList&
4937	factors, int l, int liftBound, int d, int*
4938	bounds, mat_zz_pE& NTLN, CFList& diophant,
4939	CFMatrix& M, CFArray& Pi, CFArray& bufQ
4940	)
4941	{
4942	CanonicalForm LCF= LC (F, 1);
4943	CFList result;
4944	bool irreducible= false;
4945	CFList bufFactors= factors;
4946	CFArray *A = new CFArray [bufFactors.length()];
4947	bool useOldQs= false;
4948	bool hitBound= false;
4949	int oldL= l;
4950	int stepSize= 8; //TODO choose better step size?
4951	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
4952	if (NTLN.NumRows() != factors.length()) //refined factors
4953	ident (NTLN, factors.length());
4954	CFListIterator j;
4955	CFArray buf;
4956	mat_zz_pE* NTLC, NTLK;
4957	CanonicalForm bufF, truncF;
4958	Variable y= F.mvar();
4959	while (l <= liftBound)
4960	{
4961	bufFactors.insert (LCF);
4962	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
4963	j= bufFactors;
4964	truncF= mod (F, power (y, l));
4965	if (useOldQs)
4966	{
4967	for (int i= 0; i < bufFactors.length(); i++, j++)
4968	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
4969	bufQ[i]);
4970	}
4971	else
4972	{
4973	for (int i= 0; i < bufFactors.length(); i++, j++)
4974	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
4975	}
4976	for (int i= 0; i < d; i++)
4977	{
4978	if (bounds [i] + 1 <= l/2)
4979	{
4980	int k= tmin (bounds [i] + 1, l/2);
4981	CFMatrix C= CFMatrix (l - k, bufFactors.length());
4982	for (int ii= 0; ii < bufFactors.length(); ii++)
4983	{
4984	if (A[ii].size() - 1 >= i)
4985	{
4986	buf= getCoeffs (A[ii] [i], k);
4987	writeInMatrix (C, buf, ii + 1, 0);
4988	}
4989	}
4990	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
4991	NTLK= (NTLC)NTLN;
4992	transpose (NTLK, NTLK);
4993	kernel (NTLK, NTLK);
4994	transpose (NTLK, NTLK);
4995	NTLN *= NTLK;
4996	if (NTLN.NumCols() == 1)
4997	{
4998	irreducible= true;
4999	break;
5000	}
5001	}
5002	}
5003	if (NTLN.NumCols() == 1)
5004	{
5005	irreducible= true;
5006	break;
5007	}
5008
5009	int * zeroOneVecs= extractZeroOneVecs (NTLN);
5010	bufF= F;
5011	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
5012	delete [] zeroOneVecs;
5013	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5014	{
5015	F= bufF;
5016	factors= bufFactors;
5017	delete [] A;
5018	return result;
5019	}
5020
5021	if (isReduced (NTLN))
5022	{
5023	int factorsFound= 0;
5024	bufF= F;
5025	int* factorsFoundIndex= new int [NTLN.NumCols()];
5026	for (long i= 0; i < NTLN.NumCols(); i++)
5027	factorsFoundIndex[i]= 0;
5028	if (l < liftBound)
5029	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
5030	factorsFoundIndex, NTLN, false
5031	);
5032	else
5033	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
5034	degree (LCF), factorsFound, factorsFoundIndex,
5035	NTLN, false
5036	);
5037	if (NTLN.NumCols() == result.length())
5038	{
5039	delete [] A;
5040	delete [] factorsFoundIndex;
5041	return result;
5042	}
5043	delete [] factorsFoundIndex;
5044	}
5045	result= CFList();
5046	oldL= l;
5047	stepSize *= 2;
5048	l += stepSize;
5049	if (l > liftBound)
5050	{
5051	if (!hitBound)
5052	{
5053	l= liftBound;
5054	hitBound= true;
5055	}
5056	else
5057	break;
5058	}
5059	}
5060	if (irreducible)
5061	{
5062	delete [] A;
5063	return CFList (F);
5064	}
5065	delete [] A;
5066	factors= bufFactors;
5067	return CFList();
5068	}
5069
5070	//over field extension
5071	CFList
5072	extFurtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList& factors, int l,
5073	int liftBound, int d, int* bounds,
5074	mat_zz_p& NTLN, CFList& diophant,
5075	CFMatrix& M, CFArray& Pi, CFArray& bufQ,
5076	const CanonicalForm& evaluation, const
5077	ExtensionInfo& info, CFList& source,
5078	CFList& dest
5079	)
5080	{
5081	CanonicalForm LCF= LC (F, 1);
5082	CFList result;
5083	bool irreducible= false;
5084	CFList bufFactors= factors;
5085	CFArray *A = new CFArray [bufFactors.length()];
5086	bool useOldQs= false;
5087	bool hitBound= false;
5088	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
5089	int degMipo= degree (getMipo (info.getAlpha()));
5090	Variable alpha= info.getAlpha();
5091	int oldL= l; //be careful
5092	int stepSize= 8;
5093	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l),2);
5094	Variable gamma= info.getBeta();
5095	CanonicalForm primElemAlpha= info.getGamma();
5096	CanonicalForm imPrimElemAlpha= info.getDelta();
5097	if (NTLN.NumRows() != factors.length()) //refined factors
5098	ident (NTLN, factors.length());
5099	Variable y= F.mvar();
5100	CanonicalForm powX, imBasis, bufF, truncF;
5101	CFMatrix Mat, C;
5102	CFIterator iter;
5103	mat_zz_p* NTLMat,*NTLC, NTLK;
5104	CFListIterator j;
5105	CFArray buf;
5106	while (l <= liftBound)
5107	{
5108	bufFactors.insert (LCF);
5109	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
5110
5111	if (GF)
5112	setCharacteristic (getCharacteristic());
5113
5114	powX= power (y-gamma, l);
5115	Mat= CFMatrix (ldegMipo, ldegMipo);
5116	for (int i= 0; i < l*degMipo; i++)
5117	{
5118
5119	imBasis= mod (power (y, i), powX);
5120	imBasis= imBasis (power (y, degMipo), y);
5121	imBasis= imBasis (y, gamma);
5122	iter= imBasis;
5123	for (; iter.hasTerms(); iter++)
5124	Mat (iter.exp()+ 1, i+1)= iter.coeff();
5125	}
5126
5127	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
5128	NTLMat= inv (NTLMat);
5129
5130	if (GF)
5131	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
5132
5133	j= bufFactors;
5134	truncF= mod (F, power (y, l));
5135	if (useOldQs)
5136	{
5137	for (int i= 0; i < bufFactors.length(); i++, j++)
5138	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5139	bufQ[i]);
5140	}
5141	else
5142	{
5143	for (int i= 0; i < bufFactors.length(); i++, j++)
5144	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5145	}
5146	for (int i= 0; i < d; i++)
5147	{
5148	if (bounds [i] + 1 <= l/2)
5149	{
5150	int k= tmin (bounds [i] + 1, l/2);
5151	C= CFMatrix (l*degMipo - k, bufFactors.length());
5152	for (int ii= 0; ii < bufFactors.length(); ii++)
5153	{
5154	if (A[ii].size() - 1 >= i)
5155	{
5156	if (GF)
5157	{
5158	A [ii] [i]= A [ii] [i] (y-evaluation, y);
5159	setCharacteristic (getCharacteristic());
5160	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
5161	if (alpha != gamma)
5162	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
5163	gamma, source, dest
5164	);
5165	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
5166	}
5167	else
5168	{
5169	A [ii] [i]= A [ii] [i] (y-evaluation, y);
5170	if (alpha != gamma)
5171	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
5172	gamma, source, dest
5173	);
5174	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
5175	}
5176	writeInMatrix (C, buf, ii + 1, 0);
5177	}
5178	if (GF)
5179	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
5180	}
5181
5182	if (GF)
5183	setCharacteristic(getCharacteristic());
5184	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
5185	NTLK= (NTLC)NTLN;
5186	transpose (NTLK, NTLK);
5187	kernel (NTLK, NTLK);
5188	transpose (NTLK, NTLK);
5189	NTLN *= NTLK;
5190	if (GF)
5191	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
5192
5193	if (NTLN.NumCols() == 1)
5194	{
5195	irreducible= true;
5196	break;
5197	}
5198	}
5199	}
5200	if (NTLN.NumCols() == 1)
5201	{
5202	irreducible= true;
5203	break;
5204	}
5205
5206	int * zeroOneVecs= extractZeroOneVecs (NTLN);
5207	bufF= F;
5208	result= extReconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN, info,
5209	evaluation
5210	);
5211	delete [] zeroOneVecs;
5212	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5213	{
5214	F= bufF;
5215	factors= bufFactors;
5216	delete [] A;
5217	return result;
5218	}
5219
5220	if (isReduced (NTLN))
5221	{
5222	int factorsFound= 0;
5223	bufF= F;
5224	int* factorsFoundIndex= new int [NTLN.NumCols()];
5225	for (long i= 0; i < NTLN.NumCols(); i++)
5226	factorsFoundIndex[i]= 0;
5227	if (l < degree (bufF) + 1 + degree (LCF))
5228	extReconstructionTry (result, bufF, bufFactors, l, factorsFound,
5229	factorsFoundIndex, NTLN, false, info, evaluation
5230	);
5231	else
5232	extReconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
5233	degree (LCF), factorsFound, factorsFoundIndex,
5234	NTLN, false, info, evaluation
5235	);
5236	if (NTLN.NumCols() == result.length())
5237	{
5238	delete [] A;
5239	delete [] factorsFoundIndex;
5240	return result;
5241	}
5242	delete [] factorsFoundIndex;
5243	}
5244	result= CFList();
5245	oldL= l;
5246	stepSize *= 2;
5247	l += stepSize;
5248	if (l > liftBound)
5249	{
5250	if (!hitBound)
5251	{
5252	l= liftBound;
5253	hitBound= true;
5254	}
5255	else
5256	break;
5257	}
5258	}
5259	if (irreducible)
5260	{
5261	delete [] A;
5262	Variable y= Variable (2);
5263	CanonicalForm tmp= F (y - evaluation, y);
5264	CFList source, dest;
5265	tmp= mapDown (tmp, info, source, dest);
5266	return CFList (tmp);
5267	}
5268	delete [] A;
5269	factors= bufFactors;
5270	return CFList();
5271	}
5272
5273	#ifdef HAVE_FLINT
5274	CFList
5275	furtherLiftingAndIncreasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int
5276	l, int liftBound, int d, int* bounds,
5277	nmod_mat_t FLINTN, CFList& diophant,
5278	CFMatrix& M, CFArray& Pi, CFArray& bufQ,
5279	const Variable& alpha
5280	)
5281	#else
5282	CFList
5283	furtherLiftingAndIncreasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int
5284	l, int liftBound, int d, int* bounds,
5285	mat_zz_p& NTLN, CFList& diophant,
5286	CFMatrix& M, CFArray& Pi, CFArray& bufQ,
5287	const Variable& alpha
5288	)
5289	#endif
5290	{
5291	CanonicalForm LCF= LC (F, 1);
5292	CFList result;
5293	bool irreducible= false;
5294	CFList bufFactors= factors;
5295	CFArray *A = new CFArray [bufFactors.length()];
5296	bool useOldQs= false;
5297	int extensionDeg= degree (getMipo (alpha));
5298	bool hitBound= false;
5299	int oldL= l;
5300	int stepSize= 8; //TODO choose better step size?
5301	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
5302	#ifdef HAVE_FLINT
5303	if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
5304	{
5305	nmod_mat_clear (FLINTN);
5306	nmod_mat_init(FLINTN,factors.length(),factors.length(),getCharacteristic());
5307	for (long i=factors.length()-1; i >= 0; i--)
5308	nmod_mat_entry (FLINTN, i, i)= 1;
5309	}
5310	#else
5311	if (NTLN.NumRows() != factors.length()) //refined factors
5312	ident (NTLN, factors.length());
5313	#endif
5314	CFListIterator j;
5315	CFMatrix C;
5316	#ifdef HAVE_FLINT
5317	long rank;
5318	nmod_mat_t FLINTC, FLINTK, null;
5319	#else
5320	mat_zz_p* NTLC, NTLK;
5321	#endif
5322	CanonicalForm bufF, truncF;
5323	Variable y= F.mvar();
5324	while (l <= liftBound)
5325	{
5326	bufFactors.insert (LCF);
5327	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
5328	j= bufFactors;
5329	truncF= mod (F, power (y, l));
5330	if (useOldQs)
5331	{
5332	for (int i= 0; i < bufFactors.length(); i++, j++)
5333	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5334	bufQ[i]);
5335	}
5336	else
5337	{
5338	for (int i= 0; i < bufFactors.length(); i++, j++)
5339	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5340	}
5341	for (int i= 0; i < d; i++)
5342	{
5343	if (bounds [i] + 1 <= l/2)
5344	{
5345	int k= tmin (bounds [i] + 1, l/2);
5346	C= CFMatrix ((l - k)*extensionDeg, bufFactors.length());
5347	for (int ii= 0; ii < bufFactors.length(); ii++)
5348	{
5349	CFArray buf;
5350	if (A[ii].size() - 1 >= i)
5351	{
5352	buf= getCoeffs (A[ii] [i], k, alpha);
5353	writeInMatrix (C, buf, ii + 1, 0);
5354	}
5355	}
5356	#ifdef HAVE_FLINT
5357	convertFacCFMatrix2nmod_mat_t (FLINTC, C);
5358	nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5359	getCharacteristic());
5360	nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5361	nmod_mat_init (null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5362	getCharacteristic());
5363	rank= nmod_mat_nullspace (null, FLINTK);
5364	nmod_mat_clear (FLINTK);
5365	nmod_mat_window_init (FLINTK, null, 0, 0, nmod_mat_nrows(null), rank);
5366	nmod_mat_clear (FLINTC);
5367	nmod_mat_init_set (FLINTC, FLINTN);
5368	nmod_mat_clear (FLINTN);
5369	nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5370	getCharacteristic());
5371	nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5372
5373	nmod_mat_clear (FLINTC);
5374	nmod_mat_window_clear (FLINTK);
5375	nmod_mat_clear (null);
5376	#else
5377	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
5378	NTLK= (NTLC)NTLN;
5379	transpose (NTLK, NTLK);
5380	kernel (NTLK, NTLK);
5381	transpose (NTLK, NTLK);
5382	NTLN *= NTLK;
5383	#endif
5384	#ifdef HAVE_FLINT
5385	if (nmod_mat_ncols (FLINTN) == 1)
5386	#else
5387	if (NTLN.NumCols() == 1)
5388	#endif
5389	{
5390	irreducible= true;
5391	break;
5392	}
5393	}
5394	}
5395	#ifdef HAVE_FLINT
5396	if (nmod_mat_ncols (FLINTN) == 1)
5397	#else
5398	if (NTLN.NumCols() == 1)
5399	#endif
5400	{
5401	irreducible= true;
5402	break;
5403	}
5404
5405	#ifdef HAVE_FLINT
5406	int * zeroOneVecs= extractZeroOneVecs (FLINTN);
5407	#else
5408	int * zeroOneVecs= extractZeroOneVecs (NTLN);
5409	#endif
5410	CanonicalForm bufF= F;
5411	#ifdef HAVE_FLINT
5412	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, FLINTN);
5413	#else
5414	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
5415	#endif
5416	delete [] zeroOneVecs;
5417	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5418	{
5419	F= bufF;
5420	factors= bufFactors;
5421	delete [] A;
5422	return result;
5423	}
5424
5425	#ifdef HAVE_FLINT
5426	if (isReduced (FLINTN))
5427	#else
5428	if (isReduced (NTLN))
5429	#endif
5430	{
5431	int factorsFound= 0;
5432	bufF= F;
5433	#ifdef HAVE_FLINT
5434	int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
5435	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5436	#else
5437	int* factorsFoundIndex= new int [NTLN.NumCols()];
5438	for (long i= 0; i < NTLN.NumCols(); i++)
5439	#endif
5440	factorsFoundIndex[i]= 0;
5441	#ifdef HAVE_FLINT
5442	if (l < degree (bufF) + 1 + degree (LCF))
5443	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
5444	factorsFoundIndex, FLINTN, false
5445	);
5446	else
5447	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
5448	degree (LCF), factorsFound, factorsFoundIndex,
5449	FLINTN, false
5450	);
5451	if (nmod_mat_ncols (FLINTN) == result.length())
5452	#else
5453	if (l < degree (bufF) + 1 + degree (LCF))
5454	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
5455	factorsFoundIndex, NTLN, false
5456	);
5457	else
5458	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
5459	degree (LCF), factorsFound, factorsFoundIndex,
5460	NTLN, false
5461	);
5462	if (NTLN.NumCols() == result.length())
5463	#endif
5464	{
5465	delete [] A;
5466	delete [] factorsFoundIndex;
5467	return result;
5468	}
5469	delete [] factorsFoundIndex;
5470	}
5471	result= CFList();
5472	oldL= l;
5473	stepSize *= 2;
5474	l += stepSize;
5475	if (l > liftBound)
5476	{
5477	if (!hitBound)
5478	{
5479	l= liftBound;
5480	hitBound= true;
5481	}
5482	else
5483	break;
5484	}
5485	}
5486	if (irreducible)
5487	{
5488	delete [] A;
5489	return CFList (F);
5490	}
5491	delete [] A;
5492	factors= bufFactors;
5493	return CFList();
5494	}
5495
5496	void
5497	refineAndRestartLift (const CanonicalForm& F, const mat_zz_p& NTLN, int
5498	liftBound, int l, CFList& factors, CFMatrix& M, CFArray&
5499	Pi, CFList& diophant
5500	)
5501	{
5502	CFList bufFactors;
5503	Variable y= Variable (2);
5504	CanonicalForm LCF= LC (F, 1);
5505	CFListIterator iter;
5506	CanonicalForm buf;
5507	for (long i= 1; i <= NTLN.NumCols(); i++)
5508	{
5509	iter= factors;
5510	buf= 1;
5511	for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
5512	{
5513	if (!IsZero (NTLN (j,i)))
5514	buf= mulNTL (buf, mod (iter.getItem(), y));
5515	}
5516	bufFactors.append (buf);
5517	}
5518	factors= bufFactors;
5519	M= CFMatrix (liftBound, factors.length());
5520	Pi= CFArray();
5521	diophant= CFList();
5522	factors.insert (LCF);
5523	henselLift12 (F, factors, l, Pi, diophant, M);
5524	}
5525
5526	#ifdef HAVE_FLINT
5527	void
5528	refineAndRestartLift (const CanonicalForm& F, const nmod_mat_t FLINTN, int
5529	liftBound, int l, CFList& factors, CFMatrix& M, CFArray&
5530	Pi, CFList& diophant
5531	)
5532	{
5533	CFList bufFactors;
5534	Variable y= Variable (2);
5535	CanonicalForm LCF= LC (F, 1);
5536	CFListIterator iter;
5537	CanonicalForm buf;
5538	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5539	{
5540	iter= factors;
5541	buf= 1;
5542	for (long j= 0; j < nmod_mat_nrows (FLINTN); j++, iter++)
5543	{
5544	if (!(nmod_mat_entry (FLINTN,j,i) == 0))
5545	buf= mulNTL (buf, mod (iter.getItem(), y));
5546	}
5547	bufFactors.append (buf);
5548	}
5549	factors= bufFactors;
5550	M= CFMatrix (liftBound, factors.length());
5551	Pi= CFArray();
5552	diophant= CFList();
5553	factors.insert (LCF);
5554	henselLift12 (F, factors, l, Pi, diophant, M);
5555	}
5556	#endif
5557
5558	void
5559	refineAndRestartLift (const CanonicalForm& F, const mat_zz_pE& NTLN, int
5560	liftBound, int l, CFList& factors, CFMatrix& M, CFArray&
5561	Pi, CFList& diophant
5562	)
5563	{
5564	CFList bufFactors;
5565	Variable y= Variable (2);
5566	CanonicalForm LCF= LC (F, 1);
5567	CFListIterator iter;
5568	CanonicalForm buf;
5569	for (long i= 1; i <= NTLN.NumCols(); i++)
5570	{
5571	iter= factors;
5572	buf= 1;
5573	for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
5574	{
5575	if (!IsZero (NTLN (j,i)))
5576	buf= mulNTL (buf, mod (iter.getItem(), y));
5577	}
5578	bufFactors.append (buf);
5579	}
5580	factors= bufFactors;
5581	M= CFMatrix (liftBound, factors.length());
5582	Pi= CFArray();
5583	diophant= CFList();
5584	factors.insert (LCF);
5585	henselLift12 (F, factors, l, Pi, diophant, M);
5586	}
5587
5588	#ifdef HAVE_FLINT
5589	CFList
5590	earlyReconstructionAndLifting (const CanonicalForm& F, const nmod_mat_t N,
5591	CanonicalForm& bufF, CFList& factors, int& l,
5592	int& factorsFound, bool beenInThres, CFMatrix& M,
5593	CFArray& Pi, CFList& diophant, bool symmetric,
5594	const CanonicalForm& evaluation
5595	)
5596	#else
5597	CFList
5598	earlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_p& N,
5599	CanonicalForm& bufF, CFList& factors, int& l,
5600	int& factorsFound, bool beenInThres, CFMatrix& M,
5601	CFArray& Pi, CFList& diophant, bool symmetric,
5602	const CanonicalForm& evaluation
5603	)
5604	#endif
5605	{
5606	int sizeOfLiftPre;
5607	int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
5608
5609	Variable y= F.mvar();
5610	factorsFound= 0;
5611	CanonicalForm LCF= LC (F, 1);
5612	CFList result;
5613	int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
5614	#ifdef HAVE_FLINT
5615	nmod_mat_t FLINTN;
5616	nmod_mat_init_set (FLINTN, N);
5617	int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
5618	for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5619	#else
5620	mat_zz_p NTLN= N;
5621	int * factorsFoundIndex= new int [NTLN.NumCols()];
5622	for (long i= 0; i < NTLN.NumCols(); i++)
5623	#endif
5624	factorsFoundIndex [i]= 0;
5625
5626	if (degree (F) + 1 > smallFactorDeg)
5627	{
5628	if (l < smallFactorDeg)
5629	{
5630	factors.insert (LCF);
5631	henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
5632	l= smallFactorDeg;
5633	}
5634	#ifdef HAVE_FLINT
5635	reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5636	factorsFoundIndex, FLINTN, beenInThres
5637	);
5638	if (result.length() == nmod_mat_ncols (FLINTN))
5639	{
5640	nmod_mat_clear (FLINTN);
5641	#else
5642	reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5643	factorsFoundIndex, NTLN, beenInThres
5644	);
5645	if (result.length() == NTLN.NumCols())
5646	{
5647	#endif
5648	delete [] liftPre;
5649	delete [] factorsFoundIndex;
5650	return result;
5651	}
5652	}
5653
5654	int i= sizeOfLiftPre - 1;
5655	int dummy= 1;
5656	if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
5657	{
5658	while (i > 0)
5659	{
5660	if (l < liftPre[i-1] + 1)
5661	{
5662	factors.insert (LCF);
5663	henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
5664	l= liftPre[i-1] + 1;
5665	}
5666	else
5667	{
5668	i--;
5669	if (i != 0)
5670	continue;
5671	}
5672	#ifdef HAVE_FLINT
5673	reconstructionTry (result, bufF, factors, l, factorsFound,
5674	factorsFoundIndex, FLINTN, beenInThres
5675	);
5676	if (result.length() == nmod_mat_ncols (FLINTN))
5677	{
5678	nmod_mat_clear (FLINTN);
5679	#else
5680	reconstructionTry (result, bufF, factors, l, factorsFound,
5681	factorsFoundIndex, NTLN, beenInThres
5682	);
5683	if (result.length() == NTLN.NumCols())
5684	{
5685	#endif
5686	delete [] liftPre;
5687	delete [] factorsFoundIndex;
5688	return result;
5689	}
5690	i--;
5691	}
5692	}
5693	else
5694	{
5695	i= 1;
5696	while (((degree (F,y)/4)*i+1) + 4 <= smallFactorDeg)
5697	i++;
5698	while (i < 5)
5699	{
5700	dummy= tmin (degree (F,y)+1, ((degree (F,y)/4)+1)*i+4);
5701	if (l < dummy)
5702	{
5703	factors.insert (LCF);
5704	henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
5705	l= dummy;
5706	if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
5707	LC (F,1).inCoeffDomain() &&
5708	(degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
5709	{
5710	Variable x= Variable (1);
5711	CanonicalForm g, h, gg, hh, multiplier1, multiplier2, check1, check2;
5712	int m= degree (F)/4+1;
5713	g= factors.getFirst();
5714	h= factors.getLast();
5715	g= mod (g, power (y,m));
5716	h= mod (h, power (y,m));
5717	g= g (y-evaluation, y);
5718	h= h (y-evaluation, y);
5719	gg= mod (swapvar (g,x,y),power (x,m));
5720	gg= gg (y + evaluation, y);
5721	multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
5722	gg= div (gg, power (y,m));
5723	gg= gg*power (y,m);
5724	hh= mod (swapvar (h,x,y),power (x,m));
5725	hh= hh (y + evaluation, y);
5726	multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
5727	hh= div (hh, power (y,m));
5728	hh= hh*power (y,m);
5729	gg= multiplier1*gg+mod (factors.getLast(), power (y,m));
5730	hh= multiplier2*hh+mod (factors.getFirst(), power (y,m));
5731	check1= gg (y-evaluation,y);
5732	check2= hh (y-evaluation,y);
5733	check1= swapvar (check1, x, y);
5734	if (check1/Lc (check1) == check2/Lc (check2))
5735	{
5736	#ifdef HAVE_FLINT
5737	nmod_mat_clear (FLINTN);
5738	#endif
5739	result.append (gg);
5740	result.append (hh);
5741	delete [] liftPre;
5742	delete [] factorsFoundIndex;
5743	return result;
5744	}
5745	}
5746	}
5747	else
5748	{
5749	i++;
5750	if (i < 5)
5751	continue;
5752	}
5753	#ifdef HAVE_FLINT
5754	reconstructionTry (result, bufF, factors, l, factorsFound,
5755	factorsFoundIndex, FLINTN, beenInThres
5756	);
5757	if (result.length() == nmod_mat_ncols (FLINTN))
5758	{
5759	nmod_mat_clear (FLINTN);
5760	#else
5761	reconstructionTry (result, bufF, factors, l, factorsFound,
5762	factorsFoundIndex, NTLN, beenInThres
5763	);
5764	if (result.length() == NTLN.NumCols())
5765	{
5766	#endif
5767	delete [] liftPre;
5768	delete [] factorsFoundIndex;
5769	return result;
5770	}
5771	i++;
5772	}
5773	}
5774
5775	#ifdef HAVE_FLINT
5776	nmod_mat_clear (FLINTN);
5777	#endif
5778	delete [] liftPre;
5779	delete [] factorsFoundIndex;
5780	return result;
5781	}
5782
5783	CFList
5784	earlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_pE& N,
5785	CanonicalForm& bufF, CFList& factors, int& l,
5786	int& factorsFound, bool beenInThres, CFMatrix& M,
5787	CFArray& Pi, CFList& diophant, bool symmetric,
5788	const CanonicalForm& evaluation
5789	)
5790	{
5791	int sizeOfLiftPre;
5792	int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
5793	Variable y= F.mvar();
5794	factorsFound= 0;
5795	CanonicalForm LCF= LC (F, 1);
5796	CFList result;
5797	int smallFactorDeg= 11;
5798	mat_zz_pE NTLN= N;
5799	int * factorsFoundIndex= new int [NTLN.NumCols()];
5800	for (long i= 0; i < NTLN.NumCols(); i++)
5801	factorsFoundIndex [i]= 0;
5802
5803	if (degree (F) + 1 > smallFactorDeg)
5804	{
5805	if (l < smallFactorDeg)
5806	{
5807	factors.insert (LCF);
5808	henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
5809	l= smallFactorDeg;
5810	}
5811	reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5812	factorsFoundIndex, NTLN, beenInThres
5813	);
5814	if (result.length() == NTLN.NumCols())
5815	{
5816	delete [] liftPre;
5817	delete [] factorsFoundIndex;
5818	return result;
5819	}
5820	}
5821
5822	int i= sizeOfLiftPre - 1;
5823	int dummy= 1;
5824	if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
5825	{
5826	while (i > 0)
5827	{
5828	if (l < liftPre[i-1] + 1)
5829	{
5830	factors.insert (LCF);
5831	henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
5832	l= liftPre[i-1] + 1;
5833	}
5834	else
5835	{
5836	i--;
5837	if (i != 0)
5838	continue;
5839	}
5840	reconstructionTry (result, bufF, factors, l, factorsFound,
5841	factorsFoundIndex, NTLN, beenInThres
5842	);
5843	if (result.length() == NTLN.NumCols())
5844	{
5845	delete [] liftPre;
5846	delete [] factorsFoundIndex;
5847	return result;
5848	}
5849	i--;
5850	}
5851	}
5852	else
5853	{
5854	i= 1;
5855	while ((degree (F,y)/4+1)*i + 4 <= smallFactorDeg)
5856	i++;
5857	while (i < 5)
5858	{
5859	dummy= tmin (degree (F,y)+1, (degree (F,y)/4+1)*i+4);
5860	if (l < dummy)
5861	{
5862	factors.insert (LCF);
5863	henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
5864	l= dummy;
5865	if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
5866	LC (F,1).inCoeffDomain() &&
5867	(degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
5868	{
5869	Variable x= Variable (1);
5870	CanonicalForm g, h, gg, hh, multiplier1, multiplier2, check1, check2;
5871	int m= degree (F)/4+1;
5872	g= factors.getFirst();
5873	h= factors.getLast();
5874	g= mod (g, power (y,m));
5875	h= mod (h, power (y,m));
5876	g= g (y-evaluation, y);
5877	h= h (y-evaluation, y);
5878	gg= mod (swapvar (g,x,y),power (x,m));
5879	gg= gg (y + evaluation, y);
5880	multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
5881	gg= div (gg, power (y,m));
5882	gg= gg*power (y,m);
5883	hh= mod (swapvar (h,x,y),power (x,m));
5884	hh= hh (y + evaluation, y);
5885	multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
5886	hh= div (hh, power (y,m));
5887	hh= hh*power (y,m);
5888	gg= multiplier1*gg+mod (factors.getLast(), power (y,m));
5889	hh= multiplier2*hh+mod (factors.getFirst(), power (y,m));
5890	check1= gg (y-evaluation,y);
5891	check2= hh (y-evaluation,y);
5892	check1= swapvar (check1, x, y);
5893	if (check1/Lc (check1) == check2/Lc (check2))
5894	{
5895	result.append (gg);
5896	result.append (hh);
5897	delete [] liftPre;
5898	delete [] factorsFoundIndex;
5899	return result;
5900	}
5901	}
5902	}
5903	else
5904	{
5905	i++;
5906	if (i < 5)
5907	continue;
5908	}
5909	reconstructionTry (result, bufF, factors, l, factorsFound,
5910	factorsFoundIndex, NTLN, beenInThres
5911	);
5912	if (result.length() == NTLN.NumCols())
5913	{
5914	delete [] liftPre;
5915	delete [] factorsFoundIndex;
5916	return result;
5917	}
5918	i++;
5919	}
5920	}
5921
5922	delete [] liftPre;
5923	delete [] factorsFoundIndex;
5924	return result;
5925	}
5926
5927	//over field extension
5928	CFList
5929	extEarlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_p& N,
5930	CanonicalForm& bufF, CFList& factors, int& l,
5931	int& factorsFound, bool beenInThres, CFMatrix&
5932	M, CFArray& Pi, CFList& diophant, const
5933	ExtensionInfo& info, const CanonicalForm&
5934	evaluation
5935	)
5936	{
5937	int sizeOfLiftPre;
5938	int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
5939	Variable y= F.mvar();
5940	factorsFound= 0;
5941	CanonicalForm LCF= LC (F, 1);
5942	CFList result;
5943	int smallFactorDeg= 11;
5944	mat_zz_p NTLN= N;
5945	int * factorsFoundIndex= new int [NTLN.NumCols()];
5946	for (long i= 0; i < NTLN.NumCols(); i++)
5947	factorsFoundIndex [i]= 0;
5948
5949	if (degree (F) + 1 > smallFactorDeg)
5950	{
5951	if (l < smallFactorDeg)
5952	{
5953	factors.insert (LCF);
5954	henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
5955	l= smallFactorDeg;
5956	}
5957	extReconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
5958	factorsFoundIndex, NTLN, beenInThres, info,
5959	evaluation
5960	);
5961	if (result.length() == NTLN.NumCols())
5962	{
5963	delete [] liftPre;
5964	delete [] factorsFoundIndex;
5965	return result;
5966	}
5967	}
5968
5969	int i= sizeOfLiftPre - 1;
5970	int dummy= 1;
5971	if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
5972	{
5973	while (i > 0)
5974	{
5975	if (l < liftPre[i-1] + 1)
5976	{
5977	factors.insert (LCF);
5978	henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
5979	l= liftPre[i-1] + 1;
5980	}
5981	else
5982	{
5983	i--;
5984	if (i != 0)
5985	continue;
5986	}
5987	extReconstructionTry (result, bufF, factors, l, factorsFound,
5988	factorsFoundIndex, NTLN, beenInThres, info,
5989	evaluation
5990	);
5991	if (result.length() == NTLN.NumCols())
5992	{
5993	delete [] liftPre;
5994	delete [] factorsFoundIndex;
5995	return result;
5996	}
5997	i--;
5998	}
5999	}
6000	else
6001	{