Context Navigation

source: git/factory/facFqBivar.cc @ 34e062

spielwiese

Last change on this file since 34e062 was 34e062, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: added functions to compute better lifting precisions based on the shape of the Newton polygon
Property mode set to `100644`
File size: 157.3 KB

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

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

Download in other formats: