Context Navigation

source: git/factory/facFqBivar.cc @ 1a9dc5

spielwiese

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

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

Download in other formats: