Context Navigation

facFqBivar.cc @ 0851b0

spielwiese

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