Context Navigation

facFqBivar.cc @ d1dc39

spielwiese

Last change on this file since d1dc39 was d1dc39, checked in by Martin Lee <martinlee84@…>, 11 years ago
fix: deleted unused variables
Property mode set to `100644`
File size: 169.9 KB

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