Context Navigation

source: git/factory/facFqBivar.cc @ 5079887

spielwiese

Last change on this file since 5079887 was e0af3ef, checked in by Martin Lee <martinlee84@…>, 12 years ago
fix: need polys over Z
Property mode set to `100644`
File size: 178.3 KB

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

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

Download in other formats: