Context Navigation

source: git/factory/facFqBivar.cc @ 978ce3

spielwiese

Last change on this file since 978ce3 was 978ce3, checked in by Martin Lee <martinlee84@…>, 12 years ago
fix: multiple definitions with --enable-timing
Property mode set to `100644`
File size: 172.2 KB

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

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

Download in other formats: