Context Navigation

facFqBivar.cc @ b28747

spielwiese

Last change on this file since b28747 was b28747, checked in by Hans Schoenemann <hannes@…>, 3 years ago
fix: factrory with or w/o NTL, FLINT
Property mode set to `100644`
File size: 252.4 KB

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