Context Navigation

source: git/factory/facFqBivar.cc @ 5335ba

spielwiese

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

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

Download in other formats: