Context Navigation

source: git/factory/facFqBivar.cc @ 050d1b

spielwiese

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

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

Download in other formats: