Context Navigation

facFqBivar.cc @ 1a3011e

spielwiese

Last change on this file since 1a3011e was 1a3011e, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: avoid double checking of factors during henselLiftAndEarly chg: lower liftBound in bivariate factorization
Property mode set to `100644`
File size: 162.5 KB

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