Context Navigation

source: git/factory/facFqBivar.cc @ 9ebec2

spielwiese

Last change on this file since 9ebec2 was 9ebec2, checked in by Martin Lee <martinlee84@…>, 12 years ago
fix: stupid bug in lattice recombination
Property mode set to `100644`
File size: 169.1 KB

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

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

Download in other formats: