Context Navigation

source: git/factory/facFqBivar.cc @ 542864

spielwiese

Last change on this file since 542864 was 542864, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: use irreducibility criterion
Property mode set to `100644`
File size: 172.1 KB

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

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

Download in other formats: