Context Navigation

facFqBivar.cc @ 3c25c9

spielwiese

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