Context Navigation

source: git/factory/facFqBivar.cc @ 621271b

spielwiese

Last change on this file since 621271b was 9d572a5, checked in by Martin Lee <martinlee84@…>, 12 years ago
fix: bug in bivariate factorization over non prime finite fields
Property mode set to `100644`
File size: 179.2 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: