Context Navigation

source: git/factory/facFqBivar.cc @ 11bf82

spielwiese

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

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

Download in other formats: