Context Navigation

source: git/factory/facFqBivar.cc @ 2f6b737

fieker-DuValspielwiese

Last change on this file since 2f6b737 was f9da5e, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg/fix: handling of minpolys over Q[t]\Z[t]
Property mode set to `100644`
File size: 168.8 KB

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

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

Download in other formats: