Context Navigation

facFqBivar.cc @ 18a660

spielwiese

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