Context Navigation

source: git/factory/facFqBivar.cc @ f047b56

spielwiese

Last change on this file since f047b56 was f047b56, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: deleted unnecessary divisibility test
Property mode set to `100644`
File size: 160.5 KB

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

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

Download in other formats: