Context Navigation

facFqBivar.cc @ bffe62

spielwiese

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