Context Navigation

facFqBivar.cc @ 188d2fb

spielwiese

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