Context Navigation

source: git/factory/facFqBivar.cc @ 2b76ff

fieker-DuValspielwiese

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

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

Download in other formats: