Context Navigation

source: git/factory/facFqBivar.cc @ 5ab7d6

spielwiese

Last change on this file since 5ab7d6 was 3ef0a0, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: fewer univariate factorizations if input is symmetric
Property mode set to `100644`
File size: 178.0 KB

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

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

Download in other formats: