Context Navigation

source: git/factory/facFqBivar.cc @ b5c084

spielwiese

Last change on this file since b5c084 was 21b8f4c, checked in by Martin Lee <martinlee84@…>, 13 years ago
added new fdivides which also returns the quotient in case of divisibility replaced old fdivides where possible git-svn-id: file:///usr/local/Singular/svn/trunk@14344 2c84dea3-7e68-4137-9b89-c4e89433aadc
Property mode set to `100644`
File size: 155.1 KB

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

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

Download in other formats: