Context Navigation

facFqBivar.cc @ 7032db

spielwiese

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