Context Navigation

source: git/factory/facFqBivar.cc @ 5df7d0

spielwiese

Last change on this file since 5df7d0 was 8c1a84, checked in by Martin Lee <martinlee84@…>, 13 years ago
updated docu and header git-svn-id: file:///usr/local/Singular/svn/trunk@14294 2c84dea3-7e68-4137-9b89-c4e89433aadc
Property mode set to `100644`
File size: 154.8 KB

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

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

Download in other formats: