Context Navigation

source: git/factory/facFqBivar.cc @ 38ffb7

spielwiese

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

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

Download in other formats: