Context Navigation

facFqBivar.cc @ c1f4d51

spielwiese

Last change on this file since c1f4d51 was c1f4d51, checked in by Hans Schoenemann <hannes@…>, 3 years ago
factory: implement findMinPoly/mapPrimElem and related
Property mode set to `100644`
File size: 252.3 KB

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