Context Navigation

source: git/factory/facFqBivar.cc @ 6f0279

spielwiese

Last change on this file since 6f0279 was 6f0279, checked in by Martin Lee <martinlee84@…>, 12 years ago
fix: wrong exit condition
Property mode set to `100644`
File size: 169.9 KB

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

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

Download in other formats: