Context Navigation

source: git/factory/facFqBivar.cc @ 69c882

spielwiese

Last change on this file since 69c882 was 69c882, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: delete factors already found by early factor detection chg: use "smaller" polynomial for factor recombination
Property mode set to `100644`
File size: 162.0 KB

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

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

Download in other formats: