Context Navigation

source: git/factory/facFqFactorize.cc @ 15a879

spielwiese

Last change on this file since 15a879 was 15a879, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: pass to larger extension if over a small finite field
Property mode set to `100644`
File size: 94.0 KB

Line
1	/*****************************************************************************\
2	* Computer Algebra System SINGULAR
3	\*****************************************************************************/
4	/** @file facFqFactorize.cc
5	*
6	* This file implements functions for factoring a multivariate polynomial over
7	* a finite field.
8	*
9	* ABSTRACT: "Efficient Multivariate Factorization over Finite Fields" by
10	* L. Bernardin & M. Monagon. Precomputation of leading coefficients is
11	* described in "Sparse Hensel lifting" by E. Kaltofen
12	*
13	* @author Martin Lee
14	*
15	**/
16	/*****************************************************************************/
17
18	#include "config.h"
19
20	#include "cf_assert.h"
21	#include "debug.h"
22	#include "timing.h"
23
24	#include "facFqFactorizeUtil.h"
25	#include "facFqFactorize.h"
26	#include "cf_random.h"
27	#include "facHensel.h"
28	#include "cf_gcd_smallp.h"
29	#include "cf_map_ext.h"
30	#include "algext.h"
31	#include "facSparseHensel.h"
32	#include "facMul.h"
33
34	#ifdef HAVE_NTL
35	#include "NTLconvert.h"
36
37	TIMING_DEFINE_PRINT(fac_fq_bi_factorizer)
38	TIMING_DEFINE_PRINT(fac_fq_hensel_lift)
39	TIMING_DEFINE_PRINT(fac_fq_factor_recombination)
40
41	static inline
42	CanonicalForm
43	listGCD (const CFList& L);
44
45	static inline
46	CanonicalForm
47	myContent (const CanonicalForm& F)
48	{
49	Variable x= Variable (1);
50	CanonicalForm G= swapvar (F, F.mvar(), x);
51	CFList L;
52	for (CFIterator i= G; i.hasTerms(); i++)
53	L.append (i.coeff());
54	if (L.length() == 2)
55	return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
56	if (L.length() == 1)
57	return LC (F, x);
58	return swapvar (listGCD (L), F.mvar(), x);
59	}
60
61	static inline
62	CanonicalForm
63	listGCD (const CFList& L)
64	{
65	if (L.length() == 0)
66	return 0;
67	if (L.length() == 1)
68	return L.getFirst();
69	if (L.length() == 2)
70	return gcd (L.getFirst(), L.getLast());
71	else
72	{
73	CFList lHi, lLo;
74	CanonicalForm resultHi, resultLo;
75	int length= L.length()/2;
76	int j= 0;
77	for (CFListIterator i= L; j < length; i++, j++)
78	lHi.append (i.getItem());
79	lLo= Difference (L, lHi);
80	resultHi= listGCD (lHi);
81	resultLo= listGCD (lLo);
82	if (resultHi.isOne() \|\| resultLo.isOne())
83	return 1;
84	return gcd (resultHi, resultLo);
85	}
86	}
87
88	static inline
89	CanonicalForm
90	myContent (const CanonicalForm& F, const Variable& x)
91	{
92	if (degree (F, x) <= 0)
93	return 1;
94	CanonicalForm G= F;
95	bool swap= false;
96	if (x != F.mvar())
97	{
98	swap= true;
99	G= swapvar (F, x, F.mvar());
100	}
101	CFList L;
102	Variable alpha;
103	for (CFIterator i= G; i.hasTerms(); i++)
104	L.append (i.coeff());
105	if (L.length() == 2)
106	{
107	if (swap)
108	return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
109	else
110	return gcd (L.getFirst(), L.getLast());
111	}
112	if (L.length() == 1)
113	{
114	return LC (F, x);
115	}
116	if (swap)
117	return swapvar (listGCD (L), F.mvar(), x);
118	else
119	return listGCD (L);
120	}
121
122	CanonicalForm myCompress (const CanonicalForm& F, CFMap& N)
123	{
124	int n= F.level();
125	int * degsf= new int [n + 1];
126	int ** swap;
127	swap= new int* [n + 1];
128	for (int i= 0; i <= n; i++)
129	{
130	degsf[i]= 0;
131	swap [i]= new int [2];
132	swap [i] [0]= 0;
133	swap [i] [1]= 0;
134	}
135	int i= 1;
136	n= 1;
137	degsf= degrees (F, degsf);
138
139	CanonicalForm result= F;
140	while ( i <= F.level() )
141	{
142	while( degsf[i] == 0 ) i++;
143	swap[n][0]= i;
144	swap[n][1]= size (LC (F,i));
145	if (i != n)
146	result= swapvar (result, Variable (n), Variable(i));
147	n++; i++;
148	}
149
150	int buf1, buf2;
151	n--;
152
153	for (i= 1; i < n; i++)
154	{
155	for (int j= 1; j < n - i + 1; j++)
156	{
157	if (swap[j][1] > swap[j + 1][1])
158	{
159	buf1= swap [j + 1] [0];
160	buf2= swap [j + 1] [1];
161	swap[j + 1] [0]= swap[j] [0];
162	swap[j + 1] [1]= swap[j] [1];
163	swap[j][0]= buf1;
164	swap[j][1]= buf2;
165	result= swapvar (result, Variable (j + 1), Variable (j));
166	}
167	}
168	}
169
170	for (i= n; i > 0; i--)
171	{
172	if (i != swap[i] [0])
173	N.newpair (Variable (i), Variable (swap[i] [0]));
174	}
175
176	for (i= 0; i <= n; i++)
177	delete [] swap[i];
178	delete [] swap;
179
180	delete [] degsf;
181
182	return result;
183	}
184
185	CFList
186	extFactorRecombination (const CFList& factors, const CanonicalForm& F,
187	const CFList& M, const ExtensionInfo& info,
188	const CFList& evaluation)
189	{
190	Variable alpha= info.getAlpha();
191	Variable beta= info.getBeta();
192	CanonicalForm gamma= info.getGamma();
193	CanonicalForm delta= info.getDelta();
194	int k= info.getGFDegree();
195	CFList source, dest;
196	if (factors.length() == 1)
197	{
198	CanonicalForm buf= reverseShift (F, evaluation);
199	return CFList (mapDown (buf, info, source, dest));
200	}
201	if (factors.length() < 1)
202	return CFList();
203
204	int degMipoBeta= 1;
205	if (!k && beta.level() != 1)
206	degMipoBeta= degree (getMipo (beta));
207
208	CFList T, S;
209	T= factors;
210
211	int s= 1;
212	CFList result;
213	CanonicalForm buf;
214
215	buf= F;
216
217	Variable x= Variable (1);
218	CanonicalForm g, LCBuf= LC (buf, x);
219	CanonicalForm buf2, quot;
220	int * v= new int [T.length()];
221	for (int i= 0; i < T.length(); i++)
222	v[i]= 0;
223	bool noSubset= false;
224	CFArray TT;
225	TT= copy (factors);
226	bool recombination= false;
227	bool trueFactor= false;
228	while (T.length() >= 2*s)
229	{
230	while (noSubset == false)
231	{
232	if (T.length() == s)
233	{
234	delete [] v;
235	if (recombination)
236	{
237	T.insert (LCBuf);
238	g= prodMod (T, M);
239	T.removeFirst();
240	result.append (g/myContent (g));
241	g= reverseShift (g, evaluation);
242	g /= Lc (g);
243	appendTestMapDown (result, g, info, source, dest);
244	return result;
245	}
246	else
247	{
248	buf= reverseShift (buf, evaluation);
249	return CFList (buf);
250	}
251	}
252
253	S= subset (v, s, TT, noSubset);
254	if (noSubset) break;
255
256	S.insert (LCBuf);
257	g= prodMod (S, M);
258	S.removeFirst();
259	g /= myContent (g);
260	if (fdivides (g, buf, quot))
261	{
262	buf2= reverseShift (g, evaluation);
263	buf2 /= Lc (buf2);
264	if (!k && beta == x)
265	{
266	if (degree (buf2, alpha) < degMipoBeta)
267	{
268	appendTestMapDown (result, buf2, info, source, dest);
269	buf= quot;
270	LCBuf= LC (buf, x);
271	recombination= true;
272	trueFactor= true;
273	}
274	}
275	else
276	{
277	if (!isInExtension (buf2, gamma, k, delta, source, dest))
278	{
279	appendTestMapDown (result, buf2, info, source, dest);
280	buf /= g;
281	LCBuf= LC (buf, x);
282	recombination= true;
283	trueFactor= true;
284	}
285	}
286
287	if (trueFactor)
288	{
289	T= Difference (T, S);
290
291	if (T.length() < 2*s \|\| T.length() == s)
292	{
293	buf= reverseShift (buf, evaluation);
294	buf /= Lc (buf);
295	appendTestMapDown (result, buf, info, source, dest);
296	delete [] v;
297	return result;
298	}
299	trueFactor= false;
300	TT= copy (T);
301	indexUpdate (v, s, T.length(), noSubset);
302	if (noSubset) break;
303	}
304	}
305	}
306	s++;
307	if (T.length() < 2*s \|\| T.length() == s)
308	{
309	buf= reverseShift (buf, evaluation);
310	appendTestMapDown (result, buf, info, source, dest);
311	delete [] v;
312	return result;
313	}
314	for (int i= 0; i < T.length(); i++)
315	v[i]= 0;
316	noSubset= false;
317	}
318	if (T.length() < 2*s)
319	{
320	buf= reverseShift (F, evaluation);
321	appendMapDown (result, buf, info, source, dest);
322	}
323
324	delete [] v;
325	return result;
326	}
327
328	CFList
329	factorRecombination (const CanonicalForm& F, const CFList& factors,
330	const CFList& M)
331	{
332	if (factors.length() == 1)
333	return CFList(F);
334	if (factors.length() < 1)
335	return CFList();
336
337	CFList T, S;
338
339	T= factors;
340
341	int s= 1;
342	CFList result;
343	CanonicalForm LCBuf= LC (F, Variable (1));
344	CanonicalForm g, buf= F;
345	int * v= new int [T.length()];
346	for (int i= 0; i < T.length(); i++)
347	v[i]= 0;
348	bool noSubset= false;
349	CFArray TT;
350	TT= copy (factors);
351	Variable y= F.level() - 1;
352	bool recombination= false;
353	CanonicalForm h, quot;
354	while (T.length() >= 2*s)
355	{
356	while (noSubset == false)
357	{
358	if (T.length() == s)
359	{
360	delete [] v;
361	if (recombination)
362	{
363	T.insert (LC (buf));
364	g= prodMod (T, M);
365	result.append (g/myContent (g));
366	return result;
367	}
368	else
369	return CFList (F);
370	}
371	S= subset (v, s, TT, noSubset);
372	if (noSubset) break;
373	S.insert (LCBuf);
374	g= prodMod (S, M);
375	S.removeFirst();
376	g /= myContent (g);
377	if (fdivides (g, buf, quot))
378	{
379	recombination= true;
380	result.append (g);
381	buf= quot;
382	LCBuf= LC (buf, Variable(1));
383	T= Difference (T, S);
384	if (T.length() < 2*s \|\| T.length() == s)
385	{
386	result.append (buf);
387	delete [] v;
388	return result;
389	}
390	TT= copy (T);
391	indexUpdate (v, s, T.length(), noSubset);
392	if (noSubset) break;
393	}
394	}
395	s++;
396	if (T.length() < 2*s \|\| T.length() == s)
397	{
398	result.append (buf);
399	delete [] v;
400	return result;
401	}
402	for (int i= 0; i < T.length(); i++)
403	v[i]= 0;
404	noSubset= false;
405	}
406	if (T.length() < 2*s)
407	result.append (F);
408
409	delete [] v;
410	return result;
411	}
412
413	int
414	liftBoundAdaption (const CanonicalForm& F, const CFList& factors, bool&
415	success, const int deg, const CFList& MOD, const int bound)
416	{
417	int adaptedLiftBound= 0;
418	CanonicalForm buf= F;
419	Variable y= F.mvar();
420	Variable x= Variable (1);
421	CanonicalForm LCBuf= LC (buf, x);
422	CanonicalForm g, quot;
423	CFList M= MOD;
424	M.append (power (y, deg));
425	int d= bound;
426	int e= 0;
427	int nBuf;
428	for (CFListIterator i= factors; i.hasItem(); i++)
429	{
430	g= mulMod (i.getItem(), LCBuf, M);
431	g /= myContent (g);
432	if (fdivides (g, buf, quot))
433	{
434	nBuf= degree (g, y) + degree (LC (g, 1), y);
435	d -= nBuf;
436	e= tmax (e, nBuf);
437	buf= quot;
438	LCBuf= LC (buf, x);
439	}
440	}
441	adaptedLiftBound= d;
442
443	if (adaptedLiftBound < deg)
444	{
445	if (adaptedLiftBound < degree (F) + 1)
446	{
447	if (d == 1)
448	{
449	if (e + 1 > deg)
450	{
451	adaptedLiftBound= deg;
452	success= false;
453	}
454	else
455	{
456	success= true;
457	if (e + 1 < degree (F) + 1)
458	adaptedLiftBound= deg;
459	else
460	adaptedLiftBound= e + 1;
461	}
462	}
463	else
464	{
465	success= true;
466	adaptedLiftBound= deg;
467	}
468	}
469	else
470	{
471	success= true;
472	}
473	}
474	return adaptedLiftBound;
475	}
476
477	int
478	extLiftBoundAdaption (const CanonicalForm& F, const CFList& factors, bool&
479	success, const ExtensionInfo& info, const CFList& eval,
480	const int deg, const CFList& MOD, const int bound)
481	{
482	Variable alpha= info.getAlpha();
483	Variable beta= info.getBeta();
484	CanonicalForm gamma= info.getGamma();
485	CanonicalForm delta= info.getDelta();
486	int k= info.getGFDegree();
487	int adaptedLiftBound= 0;
488	CanonicalForm buf= F;
489	Variable y= F.mvar();
490	Variable x= Variable (1);
491	CanonicalForm LCBuf= LC (buf, x);
492	CanonicalForm g, gg, quot;
493	CFList M= MOD;
494	M.append (power (y, deg));
495	adaptedLiftBound= 0;
496	int d= bound;
497	int e= 0;
498	int nBuf;
499	int degMipoBeta= 1;
500	if (!k && beta.level() != 1)
501	degMipoBeta= degree (getMipo (beta));
502
503	CFList source, dest;
504	for (CFListIterator i= factors; i.hasItem(); i++)
505	{
506	g= mulMod (i.getItem(), LCBuf, M);
507	g /= myContent (g);
508	if (fdivides (g, buf, quot))
509	{
510	gg= reverseShift (g, eval);
511	gg /= Lc (gg);
512	if (!k && beta == x)
513	{
514	if (degree (gg, alpha) < degMipoBeta)
515	{
516	buf= quot;
517	nBuf= degree (g, y) + degree (LC (g, x), y);
518	d -= nBuf;
519	e= tmax (e, nBuf);
520	LCBuf= LC (buf, x);
521	}
522	}
523	else
524	{
525	if (!isInExtension (gg, gamma, k, delta, source, dest))
526	{
527	buf= quot;
528	nBuf= degree (g, y) + degree (LC (g, x), y);
529	d -= nBuf;
530	e= tmax (e, nBuf);
531	LCBuf= LC (buf, x);
532	}
533	}
534	}
535	}
536	adaptedLiftBound= d;
537
538	if (adaptedLiftBound < deg)
539	{
540	if (adaptedLiftBound < degree (F) + 1)
541	{
542	if (d == 1)
543	{
544	if (e + 1 > deg)
545	{
546	adaptedLiftBound= deg;
547	success= false;
548	}
549	else
550	{
551	success= true;
552	if (e + 1 < degree (F) + 1)
553	adaptedLiftBound= deg;
554	else
555	adaptedLiftBound= e + 1;
556	}
557	}
558	else
559	{
560	success= true;
561	adaptedLiftBound= deg;
562	}
563	}
564	else
565	{
566	success= true;
567	}
568	}
569
570	return adaptedLiftBound;
571	}
572
573	CFList
574	earlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound,
575	bool& success, const int deg, const CFList& MOD,
576	const int bound)
577	{
578	CFList result;
579	CFList T= factors;
580	CanonicalForm buf= F;
581	Variable y= F.mvar();
582	Variable x= Variable (1);
583	CanonicalForm LCBuf= LC (buf, x);
584	CanonicalForm g, quot;
585	CFList M= MOD;
586	M.append (power (y, deg));
587	adaptedLiftBound= 0;
588	int d= bound;
589	int e= 0;
590	int nBuf;
591	for (CFListIterator i= factors; i.hasItem(); i++)
592	{
593	g= mulMod (i.getItem(), LCBuf, M);
594	g /= myContent (g);
595	if (fdivides (g, buf, quot))
596	{
597	result.append (g);
598	nBuf= degree (g, y) + degree (LC (g, x), y);
599	d -= nBuf;
600	e= tmax (e, nBuf);
601	buf= quot;
602	LCBuf= LC (buf, x);
603	T= Difference (T, CFList (i.getItem()));
604	}
605	}
606	adaptedLiftBound= d;
607
608	if (adaptedLiftBound < deg)
609	{
610	if (adaptedLiftBound < degree (F) + 1)
611	{
612	if (d == 1)
613	adaptedLiftBound= tmin (e + 1, deg);
614	else
615	adaptedLiftBound= deg;
616	}
617	factors= T;
618	F= buf;
619	success= true;
620	}
621	return result;
622	}
623
624	CFList
625	extEarlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound,
626	bool& success, const ExtensionInfo& info, const CFList&
627	eval, const int deg, const CFList& MOD, const int bound)
628	{
629	Variable alpha= info.getAlpha();
630	Variable beta= info.getBeta();
631	CanonicalForm gamma= info.getGamma();
632	CanonicalForm delta= info.getDelta();
633	int k= info.getGFDegree();
634	CFList result;
635	CFList T= factors;
636	CanonicalForm buf= F;
637	Variable y= F.mvar();
638	Variable x= Variable (1);
639	CanonicalForm LCBuf= LC (buf, x);
640	CanonicalForm g, gg, quot;
641	CFList M= MOD;
642	M.append (power (y, deg));
643	adaptedLiftBound= 0;
644	int d= bound;
645	int e= 0;
646	int nBuf;
647	CFList source, dest;
648
649	int degMipoBeta= 1;
650	if (!k && beta.level() != 1)
651	degMipoBeta= degree (getMipo (beta));
652
653	for (CFListIterator i= factors; i.hasItem(); i++)
654	{
655	g= mulMod (i.getItem(), LCBuf, M);
656	g /= myContent (g);
657	if (fdivides (g, buf, quot))
658	{
659	gg= reverseShift (g, eval);
660	gg /= Lc (gg);
661	if (!k && beta == x)
662	{
663	if (degree (gg, alpha) < degMipoBeta)
664	{
665	appendTestMapDown (result, gg, info, source, dest);
666	buf= quot;
667	nBuf= degree (g, y) + degree (LC (g, x), y);
668	d -= nBuf;
669	e= tmax (e, nBuf);
670	LCBuf= LC (buf, x);
671	T= Difference (T, CFList (i.getItem()));
672	}
673	}
674	else
675	{
676	if (!isInExtension (gg, gamma, k, delta, source, dest))
677	{
678	appendTestMapDown (result, gg, info, source, dest);
679	buf= quot;
680	nBuf= degree (g, y) + degree (LC (g, x), y);
681	d -= nBuf;
682	e= tmax (e, nBuf);
683	LCBuf= LC (buf, x);
684	T= Difference (T, CFList (i.getItem()));
685	}
686	}
687	}
688	}
689	adaptedLiftBound= d;
690
691	if (adaptedLiftBound < deg)
692	{
693	if (adaptedLiftBound < degree (F) + 1)
694	{
695	if (d == 1)
696	adaptedLiftBound= tmin (e + 1, deg);
697	else
698	adaptedLiftBound= deg;
699	}
700	success= true;
701	factors= T;
702	F= buf;
703	}
704	return result;
705	}
706
707	#define CHAR_THRESHOLD 8
708	CFList
709	evalPoints (const CanonicalForm& F, CFList & eval, const Variable& alpha,
710	CFList& list, const bool& GF, bool& fail)
711	{
712	int k= F.level() - 1;
713	Variable x= Variable (1);
714	CFList result;
715	FFRandom genFF;
716	GFRandom genGF;
717	int p= getCharacteristic ();
718	if (p < CHAR_THRESHOLD && !GF && alpha.level() == 1)
719	{
720	fail= true;
721	return CFList();
722	}
723	double bound;
724	if (alpha != x)
725	{
726	bound= pow ((double) p, (double) degree (getMipo(alpha)));
727	bound *= (double) k;
728	}
729	else if (GF)
730	{
731	bound= pow ((double) p, (double) getGFDegree());
732	bound *= (double) k;
733	}
734	else
735	bound= pow ((double) p, (double) k);
736
737	CanonicalForm random;
738	CanonicalForm deriv_x, gcd_deriv;
739	do
740	{
741	random= 0;
742	// possible overflow if list.length() does not fit into a int
743	if (list.length() >= bound)
744	{
745	fail= true;
746	break;
747	}
748	for (int i= 0; i < k; i++)
749	{
750	if (list.isEmpty())
751	result.append (0);
752	else if (GF)
753	{
754	result.append (genGF.generate());
755	random += result.getLast()*power (x, i);
756	}
757	else if (alpha.level() != 1)
758	{
759	AlgExtRandomF genAlgExt (alpha);
760	result.append (genAlgExt.generate());
761	random += result.getLast()*power (x, i);
762	}
763	else
764	{
765	result.append (genFF.generate());
766	random += result.getLast()*power (x, i);
767	}
768	}
769	if (find (list, random))
770	{
771	result= CFList();
772	continue;
773	}
774	int l= F.level();
775	eval.insert (F);
776	bool bad= false;
777	for (CFListIterator i= result; i.hasItem(); i++, l--)
778	{
779	eval.insert (eval.getFirst()(i.getItem(), l));
780	if (degree (eval.getFirst(), l - 1) != degree (F, l - 1))
781	{
782	if (!find (list, random))
783	list.append (random);
784	result= CFList();
785	eval= CFList();
786	bad= true;
787	break;
788	}
789	}
790
791	if (bad)
792	continue;
793
794	if (degree (eval.getFirst()) != degree (F, 1))
795	{
796	if (!find (list, random))
797	list.append (random);
798	result= CFList();
799	eval= CFList();
800	continue;
801	}
802
803	deriv_x= deriv (eval.getFirst(), x);
804	gcd_deriv= gcd (eval.getFirst(), deriv_x);
805	if (degree (gcd_deriv) > 0)
806	{
807	if (!find (list, random))
808	list.append (random);
809	result= CFList();
810	eval= CFList();
811	continue;
812	}
813	CFListIterator i= eval;
814	i++;
815	CanonicalForm contentx= content (i.getItem(), x);
816	if (degree (contentx) > 0)
817	{
818	if (!find (list, random))
819	list.append (random);
820	result= CFList();
821	eval= CFList();
822	continue;
823	}
824
825	if (list.length() >= bound)
826	{
827	fail= true;
828	break;
829	}
830	} while (find (list, random));
831
832	if (!eval.isEmpty())
833	eval.removeFirst();
834
835	return result;
836	}
837
838	static inline
839	int newMainVariableSearch (CanonicalForm& A, CFList& Aeval, CFList&
840	evaluation, const Variable& alpha, const int lev,
841	CanonicalForm& g
842	)
843	{
844	Variable x= Variable (1);
845	CanonicalForm derivI, buf;
846	bool GF= (CFFactory::gettype() == GaloisFieldDomain);
847	int swapLevel= 0;
848	CFList list;
849	bool fail= false;
850	buf= A;
851	Aeval= CFList();
852	evaluation= CFList();
853	for (int i= lev; i <= A.level(); i++)
854	{
855	derivI= deriv (buf, Variable (i));
856	if (!derivI.isZero())
857	{
858	g= gcd (buf, derivI);
859	if (degree (g) > 0)
860	return -1;
861
862	buf= swapvar (buf, x, Variable (i));
863	Aeval= CFList();
864	evaluation= CFList();
865	fail= false;
866	evaluation= evalPoints (buf, Aeval, alpha, list, GF, fail);
867	if (!fail)
868	{
869	A= buf;
870	swapLevel= i;
871	break;
872	}
873	else
874	buf= A;
875	}
876	}
877	return swapLevel;
878	}
879
880	CanonicalForm lcmContent (const CanonicalForm& A, CFList& contentAi)
881	{
882	int i= A.level();
883	contentAi.append (myContent (A, i));
884	contentAi.append (myContent (A, i - 1));
885	CanonicalForm result= lcm (contentAi.getFirst(), contentAi.getLast());
886	for (i= i - 2; i > 0; i--)
887	{
888	contentAi.append (content (A, i));
889	result= lcm (result, contentAi.getLast());
890	}
891	return result;
892	}
893
894	CFList
895	henselLiftAndEarly (CanonicalForm& A, CFList& MOD, int*& liftBounds, bool&
896	earlySuccess, CFList& earlyFactors, const CFList& Aeval,
897	const CFList& biFactors, const CFList& evaluation,
898	const ExtensionInfo& info)
899	{
900	bool extension= info.isInExtension();
901	CFList bufFactors= biFactors;
902	bufFactors.insert (LC (Aeval.getFirst(), 1));
903
904	sortList (bufFactors, Variable (1));
905
906	CFList diophant;
907	CFArray Pi;
908	int smallFactorDeg= 11; //tunable parameter
909	CFList result;
910	int adaptedLiftBound= 0;
911	int liftBound= liftBounds[1];
912
913	earlySuccess= false;
914	CFList earlyReconstFactors;
915	CFListIterator j= Aeval;
916	j++;
917	CanonicalForm buf= j.getItem();
918	CFMatrix Mat= CFMatrix (liftBound, bufFactors.length() - 1);
919	MOD= CFList (power (Variable (2), liftBounds[0]));
920	if (smallFactorDeg >= liftBound)
921	{
922	result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
923	}
924	else if (smallFactorDeg >= degree (buf) + 1)
925	{
926	liftBounds[1]= degree (buf) + 1;
927	result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
928	if (Aeval.length() == 2)
929	{
930	if (!extension)
931	earlyFactors= earlyFactorDetect
932	(buf, result, adaptedLiftBound, earlySuccess,
933	degree (buf) + 1, MOD, liftBound);
934	else
935	earlyFactors= extEarlyFactorDetect
936	(buf, result, adaptedLiftBound, earlySuccess,
937	info, evaluation, degree
938	(buf) + 1, MOD, liftBound);
939	}
940	else
941	{
942	if (!extension)
943	adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
944	degree (buf) + 1, MOD, liftBound);
945	else
946	adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
947	evaluation, degree (buf) + 1,
948	MOD, liftBound);
949	}
950	if (!earlySuccess)
951	{
952	result.insert (LC (buf, 1));
953	liftBounds[1]= adaptedLiftBound;
954	liftBound= adaptedLiftBound;
955	henselLiftResume (buf, result, degree (buf) + 1, liftBound,
956	Pi, diophant, Mat, MOD);
957	}
958	else
959	liftBounds[1]= adaptedLiftBound;
960	}
961	else if (smallFactorDeg < degree (buf) + 1)
962	{
963	liftBounds[1]= smallFactorDeg;
964	result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
965	if (Aeval.length() == 2)
966	{
967	if (!extension)
968	earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
969	earlySuccess, smallFactorDeg, MOD,
970	liftBound);
971	else
972	earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
973	earlySuccess, info, evaluation,
974	smallFactorDeg, MOD, liftBound);
975	}
976	else
977	{
978	if (!extension)
979	adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
980	smallFactorDeg, MOD, liftBound);
981	else
982	adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
983	evaluation, smallFactorDeg, MOD,
984	liftBound);
985	}
986
987	if (!earlySuccess)
988	{
989	result.insert (LC (buf, 1));
990	henselLiftResume (buf, result, smallFactorDeg, degree (buf) + 1,
991	Pi, diophant, Mat, MOD);
992	if (Aeval.length() == 2)
993	{
994	if (!extension)
995	earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
996	earlySuccess, degree (buf) + 1,
997	MOD, liftBound);
998	else
999	earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
1000	earlySuccess, info, evaluation,
1001	degree (buf) + 1, MOD,
1002	liftBound);
1003	}
1004	else
1005	{
1006	if (!extension)
1007	adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1008	degree (buf) + 1, MOD,liftBound);
1009	else
1010	adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess,
1011	info, evaluation,
1012	degree (buf) + 1, MOD,
1013	liftBound);
1014	}
1015	if (!earlySuccess)
1016	{
1017	result.insert (LC (buf, 1));
1018	liftBounds[1]= adaptedLiftBound;
1019	liftBound= adaptedLiftBound;
1020	henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1021	Pi, diophant, Mat, MOD);
1022	}
1023	else
1024	liftBounds[1]= adaptedLiftBound;
1025	}
1026	else
1027	liftBounds[1]= adaptedLiftBound;
1028	}
1029
1030	MOD.append (power (Variable (3), liftBounds[1]));
1031
1032	if (Aeval.length() > 2)
1033	{
1034	CFListIterator j= Aeval;
1035	j++;
1036	CFList bufEval;
1037	bufEval.append (j.getItem());
1038	j++;
1039	int liftBoundsLength= Aeval.getLast().level() - 1;
1040	for (int i= 2; i <= liftBoundsLength && j.hasItem(); i++, j++)
1041	{
1042	earlySuccess= false;
1043	result.insert (LC (bufEval.getFirst(), 1));
1044	bufEval.append (j.getItem());
1045	liftBound= liftBounds[i];
1046	Mat= CFMatrix (liftBounds[i], result.length() - 1);
1047
1048	buf= j.getItem();
1049	if (smallFactorDeg >= liftBound)
1050	result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1051	liftBounds[i - 1], liftBounds[i]);
1052	else if (smallFactorDeg >= degree (buf) + 1)
1053	{
1054	result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1055	liftBounds[i - 1], degree (buf) + 1);
1056
1057	if (Aeval.length() == i + 1)
1058	{
1059	if (!extension)
1060	earlyFactors= earlyFactorDetect
1061	(buf, result, adaptedLiftBound, earlySuccess,
1062	degree (buf) + 1, MOD, liftBound);
1063	else
1064	earlyFactors= extEarlyFactorDetect
1065	(buf, result, adaptedLiftBound, earlySuccess,
1066	info, evaluation, degree (buf) + 1, MOD, liftBound);
1067	}
1068	else
1069	{
1070	if (!extension)
1071	adaptedLiftBound= liftBoundAdaption
1072	(buf, result, earlySuccess, degree (buf)
1073	+ 1, MOD, liftBound);
1074	else
1075	adaptedLiftBound= extLiftBoundAdaption
1076	(buf, result, earlySuccess, info, evaluation,
1077	degree (buf) + 1, MOD, liftBound);
1078	}
1079
1080	if (!earlySuccess)
1081	{
1082	result.insert (LC (buf, 1));
1083	liftBounds[i]= adaptedLiftBound;
1084	liftBound= adaptedLiftBound;
1085	henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1086	Pi, diophant, Mat, MOD);
1087	}
1088	else
1089	{
1090	liftBounds[i]= adaptedLiftBound;
1091	}
1092	}
1093	else if (smallFactorDeg < degree (buf) + 1)
1094	{
1095	result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1096	liftBounds[i - 1], smallFactorDeg);
1097
1098	if (Aeval.length() == i + 1)
1099	{
1100	if (!extension)
1101	earlyFactors= earlyFactorDetect
1102	(buf, result, adaptedLiftBound, earlySuccess,
1103	smallFactorDeg, MOD, liftBound);
1104	else
1105	earlyFactors= extEarlyFactorDetect
1106	(buf, result, adaptedLiftBound, earlySuccess,
1107	info, evaluation, smallFactorDeg, MOD, liftBound);
1108	}
1109	else
1110	{
1111	if (!extension)
1112	adaptedLiftBound= liftBoundAdaption
1113	(buf, result, earlySuccess,
1114	smallFactorDeg, MOD, liftBound);
1115	else
1116	adaptedLiftBound= extLiftBoundAdaption
1117	(buf, result, earlySuccess, info, evaluation,
1118	smallFactorDeg, MOD, liftBound);
1119	}
1120
1121	if (!earlySuccess)
1122	{
1123	result.insert (LC (buf, 1));
1124	henselLiftResume (buf, result, smallFactorDeg,
1125	degree (buf) + 1, Pi, diophant, Mat, MOD);
1126	if (Aeval.length() == i + 1)
1127	{
1128	if (!extension)
1129	earlyFactors= earlyFactorDetect
1130	(buf, result, adaptedLiftBound, earlySuccess,
1131	degree (buf) + 1, MOD, liftBound);
1132	else
1133	earlyFactors= extEarlyFactorDetect
1134	(buf, result, adaptedLiftBound, earlySuccess,
1135	info, evaluation, degree (buf) + 1, MOD,
1136	liftBound);
1137	}
1138	else
1139	{
1140	if (!extension)
1141	adaptedLiftBound= liftBoundAdaption
1142	(buf, result, earlySuccess, degree
1143	(buf) + 1, MOD, liftBound);
1144	else
1145	adaptedLiftBound= extLiftBoundAdaption
1146	(buf, result, earlySuccess, info, evaluation,
1147	degree (buf) + 1, MOD, liftBound);
1148	}
1149
1150	if (!earlySuccess)
1151	{
1152	result.insert (LC (buf, 1));
1153	liftBounds[i]= adaptedLiftBound;
1154	liftBound= adaptedLiftBound;
1155	henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1156	Pi, diophant, Mat, MOD);
1157	}
1158	else
1159	liftBounds[i]= adaptedLiftBound;
1160	}
1161	else
1162	liftBounds[i]= adaptedLiftBound;
1163	}
1164	MOD.append (power (Variable (i + 2), liftBounds[i]));
1165	bufEval.removeFirst();
1166	}
1167	bufFactors= result;
1168	}
1169	else
1170	bufFactors= result;
1171
1172	if (earlySuccess)
1173	A= buf;
1174	return result;
1175	}
1176
1177	void
1178	gcdFreeBasis (CFFList& factors1, CFFList& factors2)
1179	{
1180	CanonicalForm g;
1181	int k= factors1.length();
1182	int l= factors2.length();
1183	int n= 1;
1184	int m;
1185	CFFListIterator j;
1186	for (CFFListIterator i= factors1; (n < k && i.hasItem()); i++, n++)
1187	{
1188	m= 1;
1189	for (j= factors2; (m < l && j.hasItem()); j++, m++)
1190	{
1191	g= gcd (i.getItem().factor(), j.getItem().factor());
1192	if (degree (g,1) > 0)
1193	{
1194	j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
1195	i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp());
1196	factors1.append (CFFactor (g, i.getItem().exp()));
1197	factors2.append (CFFactor (g, j.getItem().exp()));
1198	}
1199	}
1200	}
1201	}
1202
1203	CFList
1204	distributeContent (const CFList& L, const CFList* differentSecondVarFactors,
1205	int length
1206	)
1207	{
1208	CFList l= L;
1209	CanonicalForm content= l.getFirst();
1210
1211	if (content.inCoeffDomain())
1212	return l;
1213
1214	if (l.length() == 1)
1215	{
1216	CFList result;
1217	for (int i= 0; i < length; i++)
1218	{
1219	if (differentSecondVarFactors[i].isEmpty())
1220	continue;
1221	if (result.isEmpty())
1222	{
1223	result= differentSecondVarFactors[i];
1224	for (CFListIterator iter= result; iter.hasItem(); iter++)
1225	content /= iter.getItem();
1226	}
1227	else
1228	{
1229	CFListIterator iter1= result;
1230	for (CFListIterator iter2= differentSecondVarFactors[i];iter2.hasItem();
1231	iter2++, iter1++)
1232	{
1233	iter1.getItem() *= iter2.getItem();
1234	content /= iter2.getItem();
1235	}
1236	}
1237	}
1238	result.insert (content);
1239	return result;
1240	}
1241
1242	Variable v;
1243	CFListIterator iter1, iter2;
1244	CanonicalForm tmp, g;
1245	CFList multiplier;
1246	for (int i= 0; i < length; i++)
1247	{
1248	if (differentSecondVarFactors[i].isEmpty())
1249	continue;
1250	iter1= l;
1251	iter1++;
1252
1253	tmp= 1;
1254	for (iter2= differentSecondVarFactors[i]; iter2.hasItem();
1255	iter2++, iter1++)
1256	{
1257	if (iter2.getItem().inCoeffDomain())
1258	{
1259	multiplier.append (1);
1260	continue;
1261	}
1262	v= iter2.getItem().mvar();
1263	if (degree (iter2.getItem()) == degree (iter1.getItem(),v))
1264	{
1265	multiplier.append (1);
1266	continue;
1267	}
1268	g= gcd (iter2.getItem(), content);
1269	if (!g.inCoeffDomain())
1270	{
1271	tmp *= g;
1272	multiplier.append (g);
1273	}
1274	else
1275	multiplier.append (1);
1276	}
1277	if (!tmp.isOne() && fdivides (tmp, content))
1278	{
1279	iter1= l;
1280	iter1++;
1281	content /= tmp;
1282	for (iter2= multiplier; iter2.hasItem(); iter1++, iter2++)
1283	iter1.getItem() *= iter2.getItem();
1284	}
1285	multiplier= CFList();
1286	}
1287
1288	l.removeFirst();
1289	l.insert (content);
1290	return l;
1291	}
1292
1293	int
1294	testFactors (const CanonicalForm& G, const CFList& uniFactors,
1295	const Variable& alpha, CanonicalForm& sqrfPartF, CFList& factors,
1296	CFFList*& bufSqrfFactors, CFList& evalSqrfPartF,
1297	const CFArray& evalPoint)
1298	{
1299	CanonicalForm tmp;
1300	CFListIterator j;
1301	for (CFListIterator i= uniFactors; i.hasItem(); i++)
1302	{
1303	tmp= i.getItem();
1304	if (i.hasItem())
1305	i++;
1306	else
1307	break;
1308	for (j= i; j.hasItem(); j++)
1309	{
1310	if (tmp == j.getItem())
1311	return 0;
1312	}
1313	}
1314
1315	CanonicalForm F= G;
1316	CFFList sqrfFactorization= squarefreeFactorization (F, alpha);
1317
1318	sqrfPartF= 1;
1319	for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
1320	sqrfPartF *= i.getItem().factor();
1321
1322	evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
1323
1324	CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
1325
1326	if (degree (test) != degree (sqrfPartF, 1) \|\| test.inCoeffDomain())
1327	return 0;
1328
1329	CFFList sqrfFactors;
1330	CFList tmp2;
1331	int k= 0;
1332	factors= uniFactors;
1333	CFFListIterator iter;
1334	for (CFListIterator i= factors; i.hasItem(); i++, k++)
1335	{
1336	tmp= 1;
1337	sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
1338
1339	for (iter= sqrfFactors; iter.hasItem(); iter++)
1340	{
1341	tmp2.append (iter.getItem().factor());
1342	tmp *= iter.getItem().factor();
1343	}
1344	i.getItem()= tmp/Lc(tmp);
1345	bufSqrfFactors [k]= sqrfFactors;
1346	}
1347
1348	for (int i= 0; i < factors.length() - 1; i++)
1349	{
1350	for (k= i + 1; k < factors.length(); k++)
1351	{
1352	gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
1353	}
1354	}
1355
1356	factors= CFList();
1357	for (int i= 0; i < uniFactors.length(); i++)
1358	{
1359	if (i == 0)
1360	{
1361	for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1362	{
1363	if (iter.getItem().factor().inCoeffDomain())
1364	continue;
1365	iter.getItem()= CFFactor (iter.getItem().factor()/
1366	Lc (iter.getItem().factor()),
1367	iter.getItem().exp());
1368	factors.append (iter.getItem().factor());
1369	}
1370	}
1371	else
1372	{
1373	for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1374	{
1375	if (iter.getItem().factor().inCoeffDomain())
1376	continue;
1377	iter.getItem()= CFFactor (iter.getItem().factor()/
1378	Lc (iter.getItem().factor()),
1379	iter.getItem().exp());
1380	if (!find (factors, iter.getItem().factor()))
1381	factors.append (iter.getItem().factor());
1382	}
1383	}
1384	}
1385
1386	test= prod (factors);
1387	tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
1388	if (test/Lc (test) != tmp/Lc (tmp))
1389	return 0;
1390	else
1391	return 1;
1392	}
1393
1394	CFList
1395	precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
1396	const Variable& alpha, const CFList& evaluation,
1397	CFList* & differentSecondVarLCs, int lSecondVarLCs,
1398	Variable& y
1399	)
1400	{
1401	y= Variable (1);
1402	if (LCF.inCoeffDomain())
1403	{
1404	CFList result;
1405	for (int i= 1; i <= LCFFactors.length() + 1; i++)
1406	result.append (1);
1407	return result;
1408	}
1409
1410	CFMap N, M;
1411	CFArray dummy= CFArray (2);
1412	dummy [0]= LCF;
1413	dummy [1]= Variable (2);
1414	compress (dummy, M, N);
1415	CanonicalForm F= M (LCF);
1416	if (LCF.isUnivariate())
1417	{
1418	CFList result;
1419	int LCFLevel= LCF.level();
1420	bool found= false;
1421	if (LCFLevel == 2)
1422	{
1423	//bivariate leading coefficients are already the true leading coefficients
1424	result= LCFFactors;
1425	found= true;
1426	}
1427	else
1428	{
1429	CFListIterator j;
1430	for (int i= 0; i < lSecondVarLCs; i++)
1431	{
1432	for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
1433	{
1434	if (j.getItem().level() == LCFLevel)
1435	{
1436	found= true;
1437	break;
1438	}
1439	}
1440	if (found)
1441	{
1442	result= differentSecondVarLCs [i];
1443	break;
1444	}
1445	}
1446	if (!found)
1447	result= LCFFactors;
1448	}
1449	if (found)
1450	result.insert (Lc (LCF));
1451	else
1452	{
1453	for (CFListIterator i= result; i.hasItem(); i++)
1454	i.getItem() *= LCF;
1455	result.insert (LCF);
1456	}
1457	return result;
1458	}
1459
1460	CFList factors= LCFFactors;
1461
1462	for (CFListIterator i= factors; i.hasItem(); i++)
1463	i.getItem()= M (i.getItem());
1464
1465	CanonicalForm sqrfPartF;
1466	CFFList * bufSqrfFactors= new CFFList [factors.length()];
1467	CFList evalSqrfPartF, bufFactors;
1468	CFArray evalPoint= CFArray (evaluation.length() - 1);
1469	CFArray buf= CFArray (evaluation.length());
1470	CFArray swap= CFArray (evaluation.length());
1471	CFListIterator iter= evaluation;
1472	CanonicalForm vars=getVars (LCF)*Variable (2);
1473	for (int i= evaluation.length() +1; i > 1; i--, iter++)
1474	{
1475	buf[i-2]=iter.getItem();
1476	if (degree (vars, i) > 0)
1477	swap[M(Variable (i)).level()-1]=buf[i-2];
1478	}
1479	buf= swap;
1480	for (int i= 0; i < evaluation.length() - 1; i++)
1481	evalPoint[i]= buf[i+1];
1482
1483	int pass= testFactors (F, factors, alpha, sqrfPartF,
1484	bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
1485
1486	bool foundDifferent= false;
1487	Variable z, x= y;
1488	int j= 0;
1489	if (!pass)
1490	{
1491	int lev= 0;
1492	// LCF is non-constant here
1493	CFList bufBufFactors;
1494	CanonicalForm bufF;
1495	for (int i= 0; i < lSecondVarLCs; i++)
1496	{
1497	if (!differentSecondVarLCs [i].isEmpty())
1498	{
1499	bool allConstant= true;
1500	for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
1501	{
1502	if (!iter.getItem().inCoeffDomain())
1503	{
1504	allConstant= false;
1505	y= Variable (iter.getItem().level());
1506	lev= M(y).level();
1507	}
1508	}
1509	if (allConstant)
1510	continue;
1511
1512	bufFactors= differentSecondVarLCs [i];
1513	for (iter= bufFactors; iter.hasItem(); iter++)
1514	iter.getItem()= swapvar (iter.getItem(), x, y);
1515	bufF= F;
1516	z= Variable (lev);
1517	bufF= swapvar (bufF, x, z);
1518	bufBufFactors= bufFactors;
1519	evalPoint= CFArray (evaluation.length() - 1);
1520	for (int k= 0; k < evaluation.length()-1; k++)
1521	{
1522	if (N (Variable (k+1)).level() != y.level())
1523	evalPoint[k]= buf[k+1];
1524	else
1525	evalPoint[k]= buf[0];
1526	}
1527	pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
1528	bufSqrfFactors, evalSqrfPartF, evalPoint);
1529	if (pass)
1530	{
1531	foundDifferent= true;
1532	F= bufF;
1533	CFList l= factors;
1534	for (iter= l; iter.hasItem(); iter++)
1535	iter.getItem()= swapvar (iter.getItem(), x, y);
1536	differentSecondVarLCs [i]= l;
1537	j= i;
1538	break;
1539	}
1540	if (!pass && i == lSecondVarLCs - 1)
1541	{
1542	CFList result;
1543	result.append (LCF);
1544	for (int k= 1; k <= factors.length(); k++)
1545	result.append (LCF);
1546	y= Variable (1);
1547	delete [] bufSqrfFactors;
1548	return result;
1549	}
1550	}
1551	}
1552	}
1553	if (!pass)
1554	{
1555	CFList result;
1556	result.append (LCF);
1557	for (int k= 1; k <= factors.length(); k++)
1558	result.append (LCF);
1559	y= Variable (1);
1560	delete [] bufSqrfFactors;
1561	return result;
1562	}
1563	else
1564	factors= bufFactors;
1565
1566	bufFactors= factors;
1567
1568	CFMap MM, NN;
1569	dummy [0]= sqrfPartF;
1570	dummy [1]= 1;
1571	compress (dummy, MM, NN);
1572	sqrfPartF= MM (sqrfPartF);
1573	CanonicalForm varsSqrfPartF= getVars (sqrfPartF);
1574	for (CFListIterator iter= factors; iter.hasItem(); iter++)
1575	iter.getItem()= MM (iter.getItem());
1576
1577	CFList evaluation2;
1578	for (int i= 2; i <= varsSqrfPartF.level(); i++)
1579	evaluation2.insert (evalPoint[NN (Variable (i)).level()-2]);
1580
1581	CFList interMedResult;
1582	CanonicalForm oldSqrfPartF= sqrfPartF;
1583	sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
1584	if (factors.length() > 1)
1585	{
1586	CanonicalForm LC1= LC (oldSqrfPartF, 1);
1587	CFList leadingCoeffs;
1588	for (int i= 0; i < factors.length(); i++)
1589	leadingCoeffs.append (LC1);
1590
1591	CFList LC1eval= evaluateAtEval (LC1, evaluation2, 2);
1592	CFList oldFactors= factors;
1593	for (CFListIterator i= oldFactors; i.hasItem(); i++)
1594	i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
1595
1596	bool success= false;
1597	CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
1598	CFList heuResult;
1599	if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
1600	LucksWangSparseHeuristic (oldSqrfPartFPowLC,
1601	oldFactors, 2, leadingCoeffs, heuResult))
1602	{
1603	interMedResult= recoverFactors (oldSqrfPartF, heuResult);
1604	if (oldFactors.length() == interMedResult.length())
1605	success= true;
1606	}
1607	if (!success)
1608	{
1609	LC1= LC (evalSqrfPartF.getFirst(), 1);
1610
1611	CFArray leadingCoeffs= CFArray (factors.length());
1612	for (int i= 0; i < factors.length(); i++)
1613	leadingCoeffs[i]= LC1;
1614
1615	for (CFListIterator i= factors; i.hasItem(); i++)
1616	i.getItem() *= LC1 (0,2)/Lc (i.getItem());
1617	factors.insert (1);
1618
1619	CanonicalForm
1620	newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
1621
1622	int liftBound= degree (newSqrfPartF,2) + 1;
1623
1624	CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
1625	CFArray Pi;
1626	CFList diophant;
1627	nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
1628	leadingCoeffs, false);
1629
1630	if (sqrfPartF.level() > 2)
1631	{
1632	int* liftBounds= new int [sqrfPartF.level() - 1];
1633	liftBounds [0]= liftBound;
1634	bool noOneToOne= false;
1635	CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
1636	LC1= LC (evalSqrfPartF.getLast(), 1);
1637	CFList LCs;
1638	for (int i= 0; i < factors.length(); i++)
1639	LCs.append (LC1);
1640	leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
1641	for (int i= sqrfPartF.level() - 1; i > 2; i--)
1642	{
1643	for (CFListIterator j= LCs; j.hasItem(); j++)
1644	j.getItem()= j.getItem() (0, i + 1);
1645	leadingCoeffs2 [i - 3]= LCs;
1646	}
1647	sqrfPartF *= power (LC1, factors.length()-1);
1648
1649	int liftBoundsLength= sqrfPartF.level() - 1;
1650	for (int i= 1; i < liftBoundsLength; i++)
1651	liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
1652	evalSqrfPartF= evaluateAtZero (sqrfPartF);
1653	evalSqrfPartF.removeFirst();
1654	factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
1655	diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
1656	delete [] leadingCoeffs2;
1657	delete [] liftBounds;
1658	}
1659	for (CFListIterator iter= factors; iter.hasItem(); iter++)
1660	iter.getItem()= reverseShift (iter.getItem(), evaluation2);
1661
1662	interMedResult=
1663	recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
1664	factors);
1665	}
1666	}
1667	else
1668	{
1669	CanonicalForm contF=content (oldSqrfPartF,1);
1670	factors= CFList (oldSqrfPartF/contF);
1671	interMedResult= recoverFactors (oldSqrfPartF, factors);
1672	}
1673
1674	for (CFListIterator iter= interMedResult; iter.hasItem(); iter++)
1675	iter.getItem()= NN (iter.getItem());
1676
1677	CFList result;
1678	CFFListIterator k;
1679	for (int i= 0; i < LCFFactors.length(); i++)
1680	{
1681	CanonicalForm tmp= 1;
1682	for (k= bufSqrfFactors[i]; k.hasItem(); k++)
1683	{
1684	int pos= findItem (bufFactors, k.getItem().factor());
1685	if (pos)
1686	tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
1687	}
1688	result.append (tmp);
1689	}
1690
1691	for (CFListIterator i= result; i.hasItem(); i++)
1692	{
1693	F /= i.getItem();
1694	if (foundDifferent)
1695	i.getItem()= swapvar (i.getItem(), x, z);
1696	i.getItem()= N (i.getItem());
1697	}
1698
1699	if (foundDifferent)
1700	{
1701	CFList l= differentSecondVarLCs [j];
1702	for (CFListIterator i= l; i.hasItem(); i++)
1703	i.getItem()= swapvar (i.getItem(), y, z);
1704	differentSecondVarLCs [j]= l;
1705	F= swapvar (F, x, z);
1706	}
1707
1708	result.insert (N (F));
1709
1710	result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1711
1712	if (!result.getFirst().inCoeffDomain())
1713	{
1714	CFListIterator i= result;
1715	CanonicalForm tmp;
1716	if (foundDifferent)
1717	i.getItem()= swapvar (i.getItem(), Variable (2), y);
1718
1719	tmp= i.getItem();
1720
1721	i++;
1722	for (; i.hasItem(); i++)
1723	{
1724	if (foundDifferent)
1725	i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
1726	else
1727	i.getItem() *= tmp;
1728	}
1729	}
1730	else
1731	y= Variable (1);
1732
1733	delete [] bufSqrfFactors;
1734
1735	return result;
1736	}
1737
1738	void
1739	evaluationWRTDifferentSecondVars (CFList*& Aeval, const CFList& evaluation,
1740	const CanonicalForm& A)
1741	{
1742	CanonicalForm tmp;
1743	CFList tmp2;
1744	CFListIterator iter;
1745	bool preserveDegree= true;
1746	int j;
1747	for (int i= A.level(); i > 2; i--)
1748	{
1749	tmp= A;
1750	tmp2= CFList();
1751	iter= evaluation;
1752	preserveDegree= true;
1753	for (j= A.level(); j > 1; j--, iter++)
1754	{
1755	if (j == i)
1756	continue;
1757	else
1758	{
1759	tmp= tmp (iter.getItem(), j);
1760	tmp2.insert (tmp);
1761	if ((degree (tmp, i) != degree (A, i)) \|\|
1762	(degree (tmp, 1) != degree (A, 1)))
1763	{
1764	preserveDegree= false;
1765	break;
1766	}
1767	if (!content(tmp).inCoeffDomain() \|\| !content(tmp,1).inCoeffDomain())
1768	{
1769	preserveDegree= false;
1770	break;
1771	}
1772	}
1773	}
1774	if (preserveDegree)
1775	Aeval [i - 3]= tmp2;
1776	else
1777	Aeval [i - 3]= CFList();
1778	}
1779	}
1780
1781	#endif
1782
1783	static inline
1784	CanonicalForm prodEval (const CFList& l, const CanonicalForm& evalPoint,
1785	const Variable& v)
1786	{
1787	CanonicalForm result= 1;
1788	for (CFListIterator i= l; i.hasItem(); i++)
1789	result *= i.getItem() (evalPoint, v);
1790	return result;
1791	}
1792
1793	//recombine bivariate factors in case one bivariate factorization yields less
1794	// factors than the other
1795	CFList
1796	recombination (const CFList& factors1, const CFList& factors2, int s, int thres,
1797	const CanonicalForm& evalPoint, const Variable& x)
1798	{
1799	CFList T, S;
1800
1801	T= factors1;
1802	CFList result;
1803	CanonicalForm buf;
1804	int * v= new int [T.length()];
1805	for (int i= 0; i < T.length(); i++)
1806	v[i]= 0;
1807	bool nosubset= false;
1808	CFArray TT;
1809	TT= copy (factors1);
1810	while (T.length() >= 2*s && s <= thres)
1811	{
1812	while (nosubset == false)
1813	{
1814	if (T.length() == s)
1815	{
1816	delete [] v;
1817	result.append (prod (T));
1818	return result;
1819	}
1820	S= subset (v, s, TT, nosubset);
1821	if (nosubset) break;
1822	buf= prodEval (S, evalPoint, x);
1823	buf /= Lc (buf);
1824	if (find (factors2, buf))
1825	{
1826	T= Difference (T, S);
1827	result.append (prod (S));
1828	TT= copy (T);
1829	indexUpdate (v, s, T.length(), nosubset);
1830	if (nosubset) break;
1831	}
1832	}
1833	s++;
1834	if (T.length() < 2*s \|\| T.length() == s)
1835	{
1836	delete [] v;
1837	result.append (prod (T));
1838	return result;
1839	}
1840	for (int i= 0; i < T.length(); i++)
1841	v[i]= 0;
1842	nosubset= false;
1843	}
1844
1845	delete [] v;
1846	if (T.length() < 2*s)
1847	{
1848	result.append (prod (T));
1849	return result;
1850	}
1851
1852	return result;
1853	}
1854
1855	#ifdef HAVE_NTL
1856	void
1857	factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
1858	const ExtensionInfo& info,
1859	int& minFactorsLength, bool& irred)
1860	{
1861	Variable x= Variable (1);
1862	minFactorsLength= 0;
1863	irred= false;
1864	CFList factors;
1865	Variable v;
1866	for (int j= 0; j < A.level() - 2; j++)
1867	{
1868	if (!Aeval[j].isEmpty())
1869	{
1870	v= Variable (Aeval[j].getFirst().level());
1871	if (CFFactory::gettype() == GaloisFieldDomain)
1872	factors= GFBiSqrfFactorize (Aeval[j].getFirst());
1873	else if (info.getAlpha().level() == 1)
1874	factors= FpBiSqrfFactorize (Aeval[j].getFirst());
1875	else
1876	factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
1877
1878	factors.removeFirst();
1879	if (minFactorsLength == 0)
1880	minFactorsLength= factors.length();
1881	else
1882	minFactorsLength= tmin (minFactorsLength, factors.length());
1883
1884	if (factors.length() == 1)
1885	{
1886	irred= true;
1887	return;
1888	}
1889	sortList (factors, x);
1890	Aeval [j]= factors;
1891	}
1892	}
1893	}
1894
1895	CFList conv (const CFArray & A)
1896	{
1897	CFList result;
1898	for (int i= A.max(); i >= A.min(); i--)
1899	result.insert (A[i]);
1900	return result;
1901	}
1902
1903
1904	void getLeadingCoeffs (const CanonicalForm& A, CFList*& Aeval,
1905	const CFList& uniFactors, const CFList& evaluation
1906	)
1907	{
1908	CFListIterator iter;
1909	CFList LCs;
1910	for (int j= 0; j < A.level() - 2; j++)
1911	{
1912	if (!Aeval[j].isEmpty())
1913	{
1914	LCs= CFList();
1915	for (iter= Aeval[j]; iter.hasItem(); iter++)
1916	LCs.append (LC (iter.getItem(), 1));
1917	//normalize (LCs);
1918	Aeval[j]= LCs;
1919	}
1920	}
1921	}
1922
1923	void sortByUniFactors (CFList*& Aeval, int AevalLength,
1924	const CFList& uniFactors, const CFList& evaluation
1925	)
1926	{
1927	CanonicalForm evalPoint;
1928	int i;
1929	CFListIterator iter, iter2;
1930	Variable v;
1931	CFList LCs, buf;
1932	CFArray l;
1933	int pos, index;
1934	for (int j= 0; j < AevalLength; j++)
1935	{
1936	if (!Aeval[j].isEmpty())
1937	{
1938	i= evaluation.length() + 1;
1939	for (iter= evaluation; iter.hasItem(); iter++, i--)
1940	{
1941	if (i == Aeval[j].getFirst().level())
1942	{
1943	evalPoint= iter.getItem();
1944	break;
1945	}
1946	}
1947
1948	v= Variable (i);
1949	if (Aeval[j].length() > uniFactors.length())
1950	Aeval[j]= recombination (Aeval[j], uniFactors, 1,
1951	Aeval[j].length() - uniFactors.length() + 1,
1952	evalPoint, v);
1953
1954	buf= buildUniFactors (Aeval[j], evalPoint, v);
1955	l= CFArray (uniFactors.length());
1956	index= 1;
1957	for (iter= buf; iter.hasItem(); iter++, index++)
1958	{
1959	pos= findItem (uniFactors, iter.getItem());
1960	if (pos)
1961	l[pos-1]= getItem (Aeval[j], index);
1962	}
1963	buf= conv (l);
1964	Aeval [j]= buf;
1965
1966	buf= buildUniFactors (Aeval[j], evalPoint, v);
1967	}
1968	}
1969	}
1970
1971	CFList
1972	buildUniFactors (const CFList& biFactors, const CanonicalForm& evalPoint,
1973	const Variable& y)
1974	{
1975	CFList result;
1976	CanonicalForm tmp;
1977	for (CFListIterator i= biFactors; i.hasItem(); i++)
1978	{
1979	tmp= mod (i.getItem(), y - evalPoint);
1980	tmp /= Lc (tmp);
1981	result.append (tmp);
1982	}
1983	return result;
1984	}
1985
1986	void refineBiFactors (const CanonicalForm& A, CFList& biFactors,
1987	CFList* const& Aeval, const CFList& evaluation,
1988	int minFactorsLength)
1989	{
1990	CFListIterator iter;
1991	CanonicalForm evalPoint;
1992	int i;
1993	Variable v;
1994	Variable y= Variable (2);
1995	CFList list;
1996	for (int j= 0; j < A.level() - 2; j++)
1997	{
1998	if (Aeval[j].length() == minFactorsLength)
1999	{
2000	i= A.level();
2001
2002	for (iter= evaluation; iter.hasItem(); iter++, i--)
2003	{
2004	if (i == Aeval[j].getFirst().level())
2005	{
2006	evalPoint= iter.getItem();
2007	break;
2008	}
2009	}
2010
2011	v= Variable (i);
2012	list= buildUniFactors (Aeval[j], evalPoint, v);
2013
2014	biFactors= recombination (biFactors, list, 1,
2015	biFactors.length() - list.length() + 1,
2016	evaluation.getLast(), y);
2017	return;
2018	}
2019	}
2020	}
2021
2022	void prepareLeadingCoeffs (CFList*& LCs, int n, const CFList& leadingCoeffs,
2023	const CFList& biFactors, const CFList& evaluation)
2024	{
2025	CFList l= leadingCoeffs;
2026	LCs [n-3]= l;
2027	CFListIterator j;
2028	CFListIterator iter= evaluation;
2029	for (int i= n - 1; i > 2; i--, iter++)
2030	{
2031	for (j= l; j.hasItem(); j++)
2032	j.getItem()= j.getItem() (iter.getItem(), i + 1);
2033	LCs [i - 3]= l;
2034	}
2035	l= LCs [0];
2036	for (CFListIterator i= l; i.hasItem(); i++)
2037	i.getItem()= i.getItem() (iter.getItem(), 3);
2038	CFListIterator ii= biFactors;
2039	CFList normalizeFactor;
2040	for (CFListIterator i= l; i.hasItem(); i++, ii++)
2041	normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
2042	for (int i= 0; i < n-2; i++)
2043	{
2044	ii= normalizeFactor;
2045	for (j= LCs [i]; j.hasItem(); j++, ii++)
2046	j.getItem() *= ii.getItem();
2047	}
2048	}
2049
2050	CFList
2051	extNonMonicFactorRecombination (const CFList& factors, const CanonicalForm& F,
2052	const ExtensionInfo& info)
2053	{
2054	Variable alpha= info.getAlpha();
2055	Variable beta= info.getBeta();
2056	CanonicalForm gamma= info.getGamma();
2057	CanonicalForm delta= info.getDelta();
2058	int k= info.getGFDegree();
2059	CFList source, dest;
2060
2061	int degMipoBeta= 1;
2062	if (!k && beta != Variable(1))
2063	degMipoBeta= degree (getMipo (beta));
2064
2065	CFList T, S;
2066	T= factors;
2067	int s= 1;
2068	CFList result;
2069	CanonicalForm quot, buf= F;
2070
2071	CanonicalForm g;
2072	CanonicalForm buf2;
2073	int * v= new int [T.length()];
2074	for (int i= 0; i < T.length(); i++)
2075	v[i]= 0;
2076	bool noSubset= false;
2077	CFArray TT;
2078	TT= copy (factors);
2079	bool recombination= false;
2080	bool trueFactor= false;
2081	while (T.length() >= 2*s)
2082	{
2083	while (noSubset == false)
2084	{
2085	if (T.length() == s)
2086	{
2087	delete [] v;
2088	if (recombination)
2089	{
2090	g= prod (T);
2091	T.removeFirst();
2092	result.append (g/myContent (g));
2093	g /= Lc (g);
2094	appendTestMapDown (result, g, info, source, dest);
2095	return result;
2096	}
2097	else
2098	return CFList (buf/myContent(buf));
2099	}
2100
2101	S= subset (v, s, TT, noSubset);
2102	if (noSubset) break;
2103
2104	g= prod (S);
2105	g /= myContent (g);
2106	if (fdivides (g, buf, quot))
2107	{
2108	buf2= g;
2109	buf2 /= Lc (buf2);
2110	if (!k && beta.level() == 1)
2111	{
2112	if (degree (buf2, alpha) < degMipoBeta)
2113	{
2114	appendTestMapDown (result, buf2, info, source, dest);
2115	buf= quot;
2116	recombination= true;
2117	trueFactor= true;
2118	}
2119	}
2120	else
2121	{
2122	if (!isInExtension (buf2, gamma, k, delta, source, dest))
2123	{
2124	appendTestMapDown (result, buf2, info, source, dest);
2125	buf= quot;
2126	recombination= true;
2127	trueFactor= true;
2128	}
2129	}
2130	if (trueFactor)
2131	{
2132	T= Difference (T, S);
2133
2134	if (T.length() < 2*s \|\| T.length() == s)
2135	{
2136	delete [] v;
2137	buf /= myContent (buf);
2138	buf /= Lc (buf);
2139	appendTestMapDown (result, buf, info, source, dest);
2140	return result;
2141	}
2142	trueFactor= false;
2143	TT= copy (T);
2144	indexUpdate (v, s, T.length(), noSubset);
2145	if (noSubset) break;
2146	}
2147	}
2148	}
2149	s++;
2150	if (T.length() < 2*s \|\| T.length() == s)
2151	{
2152	delete [] v;
2153	appendTestMapDown (result, buf/myContent(buf), info, source, dest);
2154	return result;
2155	}
2156	for (int i= 0; i < T.length(); i++)
2157	v[i]= 0;
2158	noSubset= false;
2159	}
2160	if (T.length() < 2*s)
2161	appendMapDown (result, F/myContent(F), info, source, dest);
2162
2163	delete [] v;
2164	return result;
2165	}
2166
2167	CFList
2168	extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
2169
2170	CFList
2171	multiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
2172	{
2173
2174	if (F.inCoeffDomain())
2175	return CFList (F);
2176
2177	// compress and find main Variable
2178	CFMap N;
2179	CanonicalForm A= myCompress (F, N);
2180
2181	A /= Lc (A); // make monic
2182
2183	Variable alpha= info.getAlpha();
2184	Variable beta= info.getBeta();
2185	CanonicalForm gamma= info.getGamma();
2186	CanonicalForm delta= info.getDelta();
2187	bool extension= info.isInExtension();
2188	bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2189	//univariate case
2190	if (F.isUnivariate())
2191	{
2192	if (extension == false)
2193	return uniFactorizer (F, alpha, GF);
2194	else
2195	{
2196	CFList source, dest;
2197	A= mapDown (F, info, source, dest);
2198	return uniFactorizer (A, beta, GF);
2199	}
2200	}
2201
2202	//bivariate case
2203	if (A.level() == 2)
2204	{
2205	CFList buf= biFactorize (F, info);
2206	return buf;
2207	}
2208
2209	Variable x= Variable (1);
2210	Variable y= Variable (2);
2211
2212	// remove content
2213	CFList contentAi;
2214	CanonicalForm lcmCont= lcmContent (A, contentAi);
2215	A /= lcmCont;
2216
2217	// trivial after content removal
2218	CFList contentAFactors;
2219	if (A.inCoeffDomain())
2220	{
2221	for (CFListIterator i= contentAi; i.hasItem(); i++)
2222	{
2223	if (i.getItem().inCoeffDomain())
2224	continue;
2225	else
2226	{
2227	lcmCont /= i.getItem();
2228	contentAFactors=
2229	Union (multiFactorize (lcmCont, info),
2230	multiFactorize (i.getItem(), info));
2231	break;
2232	}
2233	}
2234	decompress (contentAFactors, N);
2235	if (!extension)
2236	normalize (contentAFactors);
2237	return contentAFactors;
2238	}
2239
2240	// factorize content
2241	contentAFactors= multiFactorize (lcmCont, info);
2242
2243	// univariate after content removal
2244	CFList factors;
2245	if (A.isUnivariate ())
2246	{
2247	factors= uniFactorizer (A, alpha, GF);
2248	append (factors, contentAFactors);
2249	decompress (factors, N);
2250	return factors;
2251	}
2252
2253	// check main variable
2254	int swapLevel= 0;
2255	CanonicalForm derivZ;
2256	CanonicalForm gcdDerivZ;
2257	CanonicalForm bufA= A;
2258	Variable z;
2259	for (int i= 1; i <= A.level(); i++)
2260	{
2261	z= Variable (i);
2262	derivZ= deriv (bufA, z);
2263	if (derivZ.isZero())
2264	{
2265	if (i == 1)
2266	swapLevel= 1;
2267	else
2268	continue;
2269	}
2270	else
2271	{
2272	if (swapLevel == 1)
2273	{
2274	swapLevel= i;
2275	bufA= swapvar (A, x, z);
2276	}
2277	gcdDerivZ= gcd (bufA, derivZ);
2278	if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
2279	{
2280	CanonicalForm g= bufA/gcdDerivZ;
2281	CFList factorsG=
2282	Union (multiFactorize (g, info),
2283	multiFactorize (gcdDerivZ, info));
2284	appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2285	if (!extension)
2286	normalize (factorsG);
2287	return factorsG;
2288	}
2289	else
2290	{
2291	A= bufA;
2292	break;
2293	}
2294	}
2295	}
2296
2297
2298	CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
2299	bool fail= false;
2300	int swapLevel2= 0;
2301	int level;
2302	int factorNums= 3;
2303	CanonicalForm bivarEval;
2304	CFList biFactors, bufBiFactors;
2305	CanonicalForm evalPoly;
2306	int lift, bufLift, lengthAeval2= A.level()-2;
2307	double logarithm= (double) ilog2 (totaldegree (A));
2308	logarithm /= log2exp;
2309	logarithm= ceil (logarithm);
2310	if (factorNums < (int) logarithm)
2311	factorNums= (int) logarithm;
2312	CFList* bufAeval2= new CFList [lengthAeval2];
2313	CFList* Aeval2= new CFList [lengthAeval2];
2314	int counter;
2315	int differentSecondVar= 0;
2316	// several bivariate factorizations
2317	for (int i= 0; i < factorNums; i++)
2318	{
2319	counter= 0;
2320	bufA= A;
2321	bufAeval= CFList();
2322	bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
2323	evalPoly= 0;
2324
2325	if (fail && (i == 0))
2326	{
2327	if (!swapLevel)
2328	level= 2;
2329	else
2330	level= swapLevel + 1;
2331
2332	CanonicalForm g;
2333	swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
2334
2335	if (!swapLevel2) // need to pass to an extension
2336	{
2337	factors= extFactorize (A, info);
2338	appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
2339	normalize (factors);
2340	delete [] bufAeval2;
2341	delete [] Aeval2;
2342	return factors;
2343	}
2344	else
2345	{
2346	if (swapLevel2 == -1)
2347	{
2348	CFList factorsG=
2349	Union (multiFactorize (g, info),
2350	multiFactorize (A/g, info));
2351	appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2352	if (!extension)
2353	normalize (factorsG);
2354	delete [] bufAeval2;
2355	delete [] Aeval2;
2356	return factorsG;
2357	}
2358	fail= false;
2359	bufAeval= Aeval;
2360	bufA= A;
2361	bufEvaluation= evaluation;
2362	}
2363	}
2364	else if (fail && (i > 0))
2365	break;
2366
2367	bivarEval= bufEvaluation.getLast();
2368
2369	evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
2370
2371	for (int j= 0; j < lengthAeval2; j++)
2372	{
2373	if (!bufAeval2[j].isEmpty())
2374	counter++;
2375	}
2376
2377	bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
2378
2379	TIMING_START (fac_fq_bi_factorizer);
2380	if (!GF && alpha.level() == 1)
2381	bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
2382	else if (GF)
2383	bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
2384	else
2385	bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
2386	TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
2387	"time for bivariate factorization: ");
2388	bufBiFactors.removeFirst();
2389
2390	if (bufBiFactors.length() == 1)
2391	{
2392	if (extension)
2393	{
2394	CFList source, dest;
2395	A= mapDown (A, info, source, dest);
2396	}
2397	factors.append (A);
2398	appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2399	swapLevel2, x);
2400	if (!extension)
2401	normalize (factors);
2402	delete [] bufAeval2;
2403	delete [] Aeval2;
2404	return factors;
2405	}
2406
2407	if (i == 0)
2408	{
2409	Aeval= bufAeval;
2410	evaluation= bufEvaluation;
2411	biFactors= bufBiFactors;
2412	lift= bufLift;
2413	for (int j= 0; j < lengthAeval2; j++)
2414	Aeval2 [j]= bufAeval2 [j];
2415	differentSecondVar= counter;
2416	}
2417	else
2418	{
2419	if (bufBiFactors.length() < biFactors.length() \|\|
2420	((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) \|\|
2421	counter > differentSecondVar)
2422	{
2423	Aeval= bufAeval;
2424	evaluation= bufEvaluation;
2425	biFactors= bufBiFactors;
2426	lift= bufLift;
2427	for (int j= 0; j < lengthAeval2; j++)
2428	Aeval2 [j]= bufAeval2 [j];
2429	differentSecondVar= counter;
2430	}
2431	}
2432	int k= 0;
2433	for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
2434	evalPoly += j.getItem()*power (x, k);
2435	list.append (evalPoly);
2436	}
2437
2438	delete [] bufAeval2;
2439
2440	sortList (biFactors, x);
2441
2442	int minFactorsLength;
2443	bool irred= false;
2444	factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength,irred);
2445
2446	if (irred)
2447	{
2448	if (extension)
2449	{
2450	CFList source, dest;
2451	A= mapDown (A, info, source, dest);
2452	}
2453	factors.append (A);
2454	appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2455	swapLevel2, x);
2456	if (!extension)
2457	normalize (factors);
2458	delete [] Aeval2;
2459	return factors;
2460	}
2461
2462	if (minFactorsLength == 0)
2463	minFactorsLength= biFactors.length();
2464	else if (biFactors.length() > minFactorsLength)
2465	refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
2466	minFactorsLength= tmin (minFactorsLength, biFactors.length());
2467
2468	if (differentSecondVar == lengthAeval2)
2469	{
2470	bool zeroOccured= false;
2471	for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
2472	{
2473	if (iter.getItem().isZero())
2474	{
2475	zeroOccured= true;
2476	break;
2477	}
2478	}
2479	if (!zeroOccured)
2480	{
2481	factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
2482	minFactorsLength);
2483	if (factors.length() == biFactors.length())
2484	{
2485	if (extension)
2486	factors= extNonMonicFactorRecombination (factors, A, info);
2487
2488	appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2489	swapLevel2, x);
2490	if (!extension)
2491	normalize (factors);
2492	delete [] Aeval2;
2493	return factors;
2494	}
2495	else
2496	factors= CFList();
2497	//TODO case where factors.length() > 0
2498	}
2499	}
2500
2501	CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
2502
2503	sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation);
2504
2505	CFList * oldAeval= new CFList [lengthAeval2]; //TODO use bufAeval2 for this
2506	for (int i= 0; i < lengthAeval2; i++)
2507	oldAeval[i]= Aeval2[i];
2508
2509	getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
2510
2511	CFList biFactorsLCs;
2512	for (CFListIterator i= biFactors; i.hasItem(); i++)
2513	biFactorsLCs.append (LC (i.getItem(), 1));
2514
2515	Variable v;
2516	CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
2517	evaluation, Aeval2, lengthAeval2, v);
2518
2519	if (v.level() != 1)
2520	{
2521	A= swapvar (A, y, v);
2522	int i= A.level();
2523	CanonicalForm evalPoint;
2524	for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2525	{
2526	if (i == v.level())
2527	{
2528	evalPoint= iter.getItem();
2529	iter.getItem()= evaluation.getLast();
2530	evaluation.removeLast();
2531	evaluation.append (evalPoint);
2532	break;
2533	}
2534	}
2535	for (i= 0; i < lengthAeval2; i++)
2536	{
2537	if (oldAeval[i].isEmpty())
2538	continue;
2539	if (oldAeval[i].getFirst().level() == v.level())
2540	{
2541	CFArray tmp= copy (oldAeval[i]);
2542	oldAeval[i]= biFactors;
2543	for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
2544	iter.getItem()= swapvar (iter.getItem(), v, y);
2545	for (int ii= 0; ii < tmp.size(); ii++)
2546	tmp[ii]= swapvar (tmp[ii], v, y);
2547	CFArray tmp2= CFArray (tmp.size());
2548	CanonicalForm buf;
2549	for (int ii= 0; ii < tmp.size(); ii++)
2550	{
2551	buf= tmp[ii] (evaluation.getLast(),y);
2552	buf /= Lc (buf);
2553	tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
2554	}
2555	biFactors= CFList();
2556	for (int j= 0; j < tmp2.size(); j++)
2557	biFactors.append (tmp2[j]);
2558	}
2559	}
2560	}
2561
2562	CFListIterator iter;
2563	CanonicalForm oldA= A;
2564	CFList oldBiFactors= biFactors;
2565	if (!leadingCoeffs.getFirst().inCoeffDomain())
2566	{
2567	CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
2568	A *= tmp;
2569	tmp= leadingCoeffs.getFirst();
2570	iter= evaluation;
2571	for (int i= A.level(); i > 2; i--, iter++)
2572	tmp= tmp (iter.getItem(), i);
2573	if (!tmp.inCoeffDomain())
2574	{
2575	for (CFListIterator i= biFactors; i.hasItem(); i++)
2576	{
2577	i.getItem() *= tmp/LC (i.getItem(), 1);
2578	i.getItem() /= Lc (i.getItem());
2579	}
2580	}
2581	}
2582
2583	CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
2584	bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
2585	leadingCoeffs.removeFirst();
2586
2587	//prepare leading coefficients
2588	CFList* leadingCoeffs2= new CFList [lengthAeval2];
2589	prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors,
2590	evaluation);
2591
2592	Aeval= evaluateAtEval (A, evaluation, 2);
2593	CanonicalForm hh= Lc (Aeval.getFirst());
2594	for (iter= Aeval; iter.hasItem(); iter++)
2595	iter.getItem() /= hh;
2596
2597	A /= hh;
2598
2599	CFListIterator iter2;
2600	CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
2601	bufBiFactors= biFactors;
2602	bufA= A;
2603	CanonicalForm bufLCmultiplier= LCmultiplier;
2604	CanonicalForm testVars;
2605	if (!LCmultiplierIsConst)
2606	{
2607	testVars= Variable (2);
2608	for (int i= 0; i < lengthAeval2; i++)
2609	{
2610	if (!oldAeval[i].isEmpty())
2611	testVars *= oldAeval[i].getFirst().mvar();
2612	}
2613	}
2614	CFList bufFactors= CFList();
2615	bool LCheuristic= false;
2616	if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
2617	factors))
2618	{
2619	int check= biFactors.length();
2620	int * index= new int [factors.length()];
2621	CFList oldFactors= factors;
2622	factors= recoverFactors (A, factors, index);
2623
2624	if (check == factors.length())
2625	{
2626	if (extension)
2627	factors= extNonMonicFactorRecombination (factors, bufA, info);
2628
2629	if (v.level() != 1)
2630	{
2631	for (iter= factors; iter.hasItem(); iter++)
2632	iter.getItem()= swapvar (iter.getItem(), v, y);
2633	}
2634
2635	appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2636	swapLevel2, x);
2637	if (!extension)
2638	normalize (factors);
2639	delete [] index;
2640	delete [] Aeval2;
2641	return factors;
2642	}
2643	else if (factors.length() > 0)
2644	{
2645	int oneCount= 0;
2646	CFList l;
2647	for (int i= 0; i < check; i++)
2648	{
2649	if (index[i] == 1)
2650	{
2651	iter=biFactors;
2652	for (int j=1; j <= i-oneCount; j++)
2653	iter++;
2654	iter.remove (1);
2655	for (int j= 0; j < lengthAeval2; j++)
2656	{
2657	l= leadingCoeffs2[j];
2658	iter= l;
2659	for (int k=1; k <= i-oneCount; k++)
2660	iter++;
2661	iter.remove (1);
2662	leadingCoeffs2[j]=l;
2663	}
2664	oneCount++;
2665	}
2666	}
2667	bufFactors= factors;
2668	factors= CFList();
2669	}
2670	else if (!LCmultiplierIsConst && factors.length() == 0)
2671	{
2672	LCheuristic= true;
2673	factors= oldFactors;
2674	CanonicalForm cont;
2675	CFList contents, LCs;
2676	int index=1;
2677	bool foundTrueMultiplier= false;
2678	for (iter= factors; iter.hasItem(); iter++, index++)
2679	{
2680	cont= content (iter.getItem(), 1);
2681	cont= gcd (cont , LCmultiplier);
2682	contents.append (cont);
2683	if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
2684	{
2685	foundTrueMultiplier= true;
2686	int index2= 1;
2687	for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem(); iter2++,
2688	index2++)
2689	{
2690	if (index2 == index)
2691	continue;
2692	iter2.getItem() /= LCmultiplier;
2693	}
2694	A= oldA;
2695	leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
2696	for (int i= lengthAeval2-1; i > -1; i--)
2697	leadingCoeffs2[i]= CFList();
2698	prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs,
2699	biFactors, evaluation );
2700	Aeval= evaluateAtEval (A, evaluation, 2);
2701
2702	hh= Lc (Aeval.getFirst());
2703
2704	for (iter2= Aeval; iter2.hasItem(); iter2++)
2705	iter2.getItem() /= hh;
2706
2707	A /= hh;
2708	break;
2709	}
2710	else
2711	LCs.append (LC (iter.getItem()/cont, 1));
2712	}
2713	if (!foundTrueMultiplier)
2714	{
2715	index= 1;
2716	iter2= factors;
2717	bool foundMultiplier= false;
2718	for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2719	{
2720	if (fdivides (iter.getItem(), LCmultiplier))
2721	{
2722	if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
2723	!isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
2724	{
2725	int index2= 1;
2726	for (CFListIterator iter3= leadingCoeffs2[lengthAeval2-1];
2727	iter3.hasItem(); iter3++, index2++)
2728	{
2729	if (index2 == index)
2730	{
2731	iter3.getItem() /= LCmultiplier;
2732	break;
2733	}
2734	}
2735	A /= LCmultiplier;
2736	foundMultiplier= true;
2737	iter.getItem()= 1;
2738	}
2739	}
2740	}
2741	// coming from above: divide out more LCmultiplier if possible
2742	if (foundMultiplier)
2743	{
2744	foundMultiplier= false;
2745	index=1;
2746	iter2= factors;
2747	for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2748	{
2749	if (!iter.getItem().isOne() &&
2750	fdivides (iter.getItem(), LCmultiplier))
2751	{
2752	if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
2753	{
2754	int index2= 1;
2755	for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
2756	iter2++, index2++)
2757	{
2758	if (index2 == index)
2759	{
2760	iter2.getItem() /= iter.getItem();
2761	foundMultiplier= true;
2762	break;
2763	}
2764	}
2765	A /= iter.getItem();
2766	LCmultiplier /= iter.getItem();
2767	iter.getItem()= 1;
2768	}
2769	else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
2770	{
2771	//TODO maybe use a sqrffree decomposition of LCmultiplier as below
2772	Variable xx= Variable (2);
2773	CanonicalForm vars;
2774	vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2775	xx));
2776	for (int i= 0; i < lengthAeval2; i++)
2777	{
2778	if (oldAeval[i].isEmpty())
2779	continue;
2780	xx= oldAeval[i].getFirst().mvar();
2781	vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2782	xx));
2783	}
2784	if (myGetVars(content(getItem(leadingCoeffs2[lengthAeval2-1],index),1))
2785	/myGetVars (LCmultiplier) == vars)
2786	{
2787	int index2= 1;
2788	for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
2789	iter2++, index2++)
2790	{
2791	if (index2 == index)
2792	{
2793	iter2.getItem() /= LCmultiplier;
2794	foundMultiplier= true;
2795	break;
2796	}
2797	}
2798	A /= LCmultiplier;
2799	iter.getItem()= 1;
2800	}
2801	}
2802	}
2803	}
2804	}
2805	else
2806	{
2807	CanonicalForm pLCs= prod (LCs);
2808	if (fdivides (pLCs, LC (oldA,1)) && (LC(oldA,1)/pLCs).inCoeffDomain()) // check if the product of the lead coeffs of the primitive factors equals the lead coeff of the old A
2809	{
2810	A= oldA;
2811	iter2= leadingCoeffs2[lengthAeval2-1];
2812	for (iter= contents; iter.hasItem(); iter++, iter2++)
2813	iter2.getItem() /= iter.getItem();
2814	foundMultiplier= true;
2815	}
2816	if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
2817	{
2818	Variable xx;
2819	CFList vars1;
2820	CFFList sqrfMultiplier= sqrFree (LCmultiplier);
2821	if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
2822	sqrfMultiplier.removeFirst();
2823	sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
2824	xx= Variable (2);
2825	for (iter= oldBiFactors; iter.hasItem(); iter++)
2826	vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
2827	for (int i= 0; i < lengthAeval2; i++)
2828	{
2829	if (oldAeval[i].isEmpty())
2830	continue;
2831	xx= oldAeval[i].getFirst().mvar();
2832	iter2= vars1;
2833	for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
2834	iter2.getItem() *= power(xx,degree (LC (iter.getItem(),1), xx));
2835	}
2836	CanonicalForm tmp;
2837	iter2= vars1;
2838	for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++,
2839	iter2++)
2840	{
2841	tmp= iter.getItem()/LCmultiplier;
2842	for (int i=1; i <= tmp.level(); i++)
2843	{
2844	if (degree(tmp,i) > 0 &&
2845	(degree(iter2.getItem(),i) > degree (tmp,i)))
2846	iter2.getItem() /= power (Variable (i), degree (tmp,i));
2847	}
2848	}
2849	int multi;
2850	for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
2851	{
2852	multi= 0;
2853	for (iter= vars1; iter.hasItem(); iter++)
2854	{
2855	tmp= iter.getItem();
2856	while (fdivides (myGetVars (ii.getItem().factor()), tmp))
2857	{
2858	multi++;
2859	tmp /= myGetVars (ii.getItem().factor());
2860	}
2861	}
2862	if (multi == ii.getItem().exp())
2863	{
2864	index= 1;
2865	for (iter= vars1; iter.hasItem(); iter++, index++)
2866	{
2867	while (fdivides (myGetVars(ii.getItem().factor()),
2868	iter.getItem()
2869	)
2870	)
2871	{
2872	int index2= 1;
2873	for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
2874	iter2++, index2++)
2875	{
2876	if (index2 == index)
2877	continue;
2878	else
2879	{
2880	tmp= ii.getItem().factor();
2881	iter2.getItem() /= tmp;
2882	CFListIterator iter3= evaluation;
2883	for (int jj= A.level(); jj > 2; jj--, iter3++)
2884	tmp= tmp (iter3.getItem(), jj);
2885	if (!tmp.inCoeffDomain())
2886	{
2887	int index3= 1;
2888	for (iter3= biFactors; iter3.hasItem(); iter3++,
2889	index3++)
2890	{
2891	if (index3 == index2)
2892	{
2893	iter3.getItem() /= tmp;
2894	iter3.getItem() /= Lc (iter3.getItem());
2895	break;
2896	}
2897	}
2898	}
2899	A /= ii.getItem().factor();
2900	}
2901	}
2902	iter.getItem() /= getVars (ii.getItem().factor());
2903	}
2904	}
2905	}
2906	else
2907	{
2908	index= 1;
2909	for (iter= vars1; iter.hasItem(); iter++, index++)
2910	{
2911	if (!fdivides (myGetVars (ii.getItem().factor()),
2912	iter.getItem()
2913	)
2914	)
2915	{
2916	int index2= 1;
2917	for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
2918	iter2++, index2++)
2919	{
2920	if (index2 == index)
2921	{
2922	tmp= power (ii.getItem().factor(), ii.getItem().exp());
2923	iter2.getItem() /= tmp;
2924	A /= tmp;
2925	CFListIterator iter3= evaluation;
2926	for (int jj= A.level(); jj > 2; jj--, iter3++)
2927	tmp= tmp (iter3.getItem(), jj);
2928	if (!tmp.inCoeffDomain())
2929	{
2930	int index3= 1;
2931	for (iter3= biFactors; iter3.hasItem(); iter3++,
2932	index3++)
2933	{
2934	if (index3 == index2)
2935	{
2936	iter3.getItem() /= tmp;
2937	iter3.getItem() /= Lc (iter3.getItem());
2938	break;
2939	}
2940	}
2941	}
2942	}
2943	}
2944	}
2945	}
2946	}
2947	}
2948	}
2949	}
2950
2951	// patch everything together again
2952	leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
2953	for (int i= lengthAeval2-1; i > -1; i--)
2954	leadingCoeffs2[i]= CFList();
2955	prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
2956	evaluation);
2957	Aeval= evaluateAtEval (A, evaluation, 2);
2958
2959	hh= Lc (Aeval.getFirst());
2960
2961	for (CFListIterator i= Aeval; i.hasItem(); i++)
2962	i.getItem() /= hh;
2963
2964	A /= hh;
2965	}
2966	factors= CFList();
2967	if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
2968	{
2969	LCheuristic= false;
2970	A= bufA;
2971	biFactors= bufBiFactors;
2972	leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
2973	LCmultiplier= bufLCmultiplier;
2974	}
2975	}
2976	else
2977	factors= CFList();
2978	delete [] index;
2979	}
2980
2981	if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
2982	&& fdivides (getVars (LCmultiplier), testVars))
2983	{
2984	LCheuristic= true;
2985	int index;
2986	Variable xx;
2987	CFList vars1;
2988	CFFList sqrfMultiplier= sqrFree (LCmultiplier);
2989	if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
2990	sqrfMultiplier.removeFirst();
2991	sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
2992	xx= Variable (2);
2993	for (iter= oldBiFactors; iter.hasItem(); iter++)
2994	vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
2995	for (int i= 0; i < lengthAeval2; i++)
2996	{
2997	if (oldAeval[i].isEmpty())
2998	continue;
2999	xx= oldAeval[i].getFirst().mvar();
3000	iter2= vars1;
3001	for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
3002	iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
3003	}
3004	CanonicalForm tmp;
3005	iter2= vars1;
3006	for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++, iter2++)
3007	{
3008	tmp= iter.getItem()/LCmultiplier;
3009	for (int i=1; i <= tmp.level(); i++)
3010	{
3011	if (degree (tmp,i) > 0 && (degree (iter2.getItem(),i) > degree (tmp,i)))
3012	iter2.getItem() /= power (Variable (i), degree (tmp,i));
3013	}
3014	}
3015	int multi;
3016	for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
3017	{
3018	multi= 0;
3019	for (iter= vars1; iter.hasItem(); iter++)
3020	{
3021	tmp= iter.getItem();
3022	while (fdivides (myGetVars (ii.getItem().factor()), tmp))
3023	{
3024	multi++;
3025	tmp /= myGetVars (ii.getItem().factor());
3026	}
3027	}
3028	if (multi == ii.getItem().exp())
3029	{
3030	index= 1;
3031	for (iter= vars1; iter.hasItem(); iter++, index++)
3032	{
3033	while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
3034	{
3035	int index2= 1;
3036	for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();iter2++,
3037	index2++)
3038	{
3039	if (index2 == index)
3040	continue;
3041	else
3042	{
3043	tmp= ii.getItem().factor();
3044	iter2.getItem() /= tmp;
3045	CFListIterator iter3= evaluation;
3046	for (int jj= A.level(); jj > 2; jj--, iter3++)
3047	tmp= tmp (iter3.getItem(), jj);
3048	if (!tmp.inCoeffDomain())
3049	{
3050	int index3= 1;
3051	for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
3052	{
3053	if (index3 == index2)
3054	{
3055	iter3.getItem() /= tmp;
3056	iter3.getItem() /= Lc (iter3.getItem());
3057	break;
3058	}
3059	}
3060	}
3061	A /= ii.getItem().factor();
3062	}
3063	}
3064	iter.getItem() /= getVars (ii.getItem().factor());
3065	}
3066	}
3067	}
3068	else
3069	{
3070	index= 1;
3071	for (iter= vars1; iter.hasItem(); iter++, index++)
3072	{
3073	if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
3074	{
3075	int index2= 1;
3076	for (iter2= leadingCoeffs2[lengthAeval2-1];iter2.hasItem();iter2++,
3077	index2++)
3078	{
3079	if (index2 == index)
3080	{
3081	tmp= power (ii.getItem().factor(), ii.getItem().exp());
3082	iter2.getItem() /= tmp;
3083	A /= tmp;
3084	CFListIterator iter3= evaluation;
3085	for (int jj= A.level(); jj > 2; jj--, iter3++)
3086	tmp= tmp (iter3.getItem(), jj);
3087	if (!tmp.inCoeffDomain())
3088	{
3089	int index3= 1;
3090	for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
3091	{
3092	if (index3 == index2)
3093	{
3094	iter3.getItem() /= tmp;
3095	iter3.getItem() /= Lc (iter3.getItem());
3096	break;
3097	}
3098	}
3099	}
3100	}
3101	}
3102	}
3103	}
3104	}
3105	}
3106
3107	leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3108	for (int i= lengthAeval2-1; i > -1; i--)
3109	leadingCoeffs2[i]= CFList();
3110	prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
3111	evaluation);
3112	Aeval= evaluateAtEval (A, evaluation, 2);
3113
3114	hh= Lc (Aeval.getFirst());
3115
3116	for (CFListIterator i= Aeval; i.hasItem(); i++)
3117	i.getItem() /= hh;
3118
3119	A /= hh;
3120	}
3121
3122	tryAgainWithoutHeu:
3123	A= shift2Zero (A, Aeval, evaluation);
3124
3125	for (iter= biFactors; iter.hasItem(); iter++)
3126	iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3127
3128	for (int i= 0; i < lengthAeval2-1; i++)
3129	leadingCoeffs2[i]= CFList();
3130	for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
3131	{
3132	iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
3133	for (int i= A.level() - 4; i > -1; i--)
3134	{
3135	if (i + 1 == lengthAeval2-1)
3136	leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
3137	else
3138	leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
3139	}
3140	}
3141
3142	CFArray Pi;
3143	CFList diophant;
3144	int* liftBounds= new int [A.level() - 1];
3145	int liftBoundsLength= A.level() - 1;
3146	for (int i= 0; i < liftBoundsLength; i++)
3147	liftBounds [i]= degree (A, i + 2) + 1;
3148
3149	Aeval.removeFirst();
3150	bool noOneToOne= false;
3151	factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
3152	Pi, liftBounds, liftBoundsLength, noOneToOne);
3153
3154	if (!noOneToOne)
3155	{
3156	int check= factors.length();
3157	A= oldA;
3158	factors= recoverFactors (A, factors, evaluation);
3159	if (check != factors.length())
3160	noOneToOne= true;
3161	else
3162	factors= Union (factors, bufFactors);
3163
3164	if (extension && !noOneToOne)
3165	factors= extNonMonicFactorRecombination (factors, A, info);
3166	}
3167	if (noOneToOne)
3168	{
3169
3170	if (!LCmultiplierIsConst && LCheuristic)
3171	{
3172	A= bufA;
3173	biFactors= bufBiFactors;
3174	leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3175	delete [] liftBounds;
3176	LCheuristic= false;
3177	goto tryAgainWithoutHeu;
3178	//something probably went wrong in the heuristic
3179	}
3180
3181	A= shift2Zero (oldA, Aeval, evaluation);
3182	biFactors= oldBiFactors;
3183	for (iter= biFactors; iter.hasItem(); iter++)
3184	iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3185	CanonicalForm LCA= LC (Aeval.getFirst(), 1);
3186	CanonicalForm yToLift= power (y, lift);
3187	CFListIterator i= biFactors;
3188	lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
3189	i++;
3190
3191	for (; i.hasItem(); i++)
3192	lift= tmax (lift,
3193	degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
3194
3195	lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
3196
3197	i= biFactors;
3198	yToLift= power (y, lift);
3199	CanonicalForm dummy;
3200	for (; i.hasItem(); i++)
3201	{
3202	LCA= LC (i.getItem(), 1);
3203	extgcd (LCA, yToLift, LCA, dummy);
3204	i.getItem()= mod (i.getItem()*LCA, yToLift);
3205	}
3206
3207	liftBoundsLength= F.level() - 1;
3208	liftBounds= liftingBounds (A, lift);
3209
3210	CFList MOD;
3211	bool earlySuccess;
3212	CFList earlyFactors, liftedFactors;
3213	TIMING_START (fac_fq_hensel_lift);
3214	liftedFactors= henselLiftAndEarly
3215	(A, MOD, liftBounds, earlySuccess, earlyFactors,
3216	Aeval, biFactors, evaluation, info);
3217	TIMING_END_AND_PRINT (fac_fq_hensel_lift, "time for hensel lifting: ");
3218
3219	if (!extension)
3220	{
3221	TIMING_START (fac_fq_factor_recombination);
3222	factors= factorRecombination (A, liftedFactors, MOD);
3223	TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3224	"time for factor recombination: ");
3225	}
3226	else
3227	{
3228	TIMING_START (fac_fq_factor_recombination);
3229	factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
3230	TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3231	"time for factor recombination: ");
3232	}
3233
3234	if (earlySuccess)
3235	factors= Union (factors, earlyFactors);
3236	if (!extension)
3237	{
3238	for (CFListIterator i= factors; i.hasItem(); i++)
3239	{
3240	int kk= Aeval.getLast().level();
3241	for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
3242	{
3243	if (i.getItem().level() < kk)
3244	continue;
3245	i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
3246	}
3247	}
3248	}
3249	}
3250
3251	if (v.level() != 1)
3252	{
3253	for (CFListIterator iter= factors; iter.hasItem(); iter++)
3254	iter.getItem()= swapvar (iter.getItem(), v, y);
3255	}
3256
3257	swap (factors, swapLevel, swapLevel2, x);
3258	append (factors, contentAFactors);
3259	decompress (factors, N);
3260	if (!extension)
3261	normalize (factors);
3262
3263	delete[] liftBounds;
3264
3265	return factors;
3266	}
3267
3268	/// multivariate factorization over an extension of the initial field
3269	CFList
3270	extFactorize (const CanonicalForm& F, const ExtensionInfo& info)
3271	{
3272	CanonicalForm A= F;
3273
3274	Variable alpha= info.getAlpha();
3275	Variable beta= info.getBeta();
3276	int k= info.getGFDegree();
3277	char cGFName= info.getGFName();
3278	CanonicalForm delta= info.getDelta();
3279	bool GF= (CFFactory::gettype() == GaloisFieldDomain);
3280	Variable w= Variable (1);
3281
3282	CFList factors;
3283	if (!GF && alpha == w) // we are in F_p
3284	{
3285	CFList factors;
3286	bool extension= true;
3287	int p= getCharacteristic();
3288	if (p < 7)
3289	{
3290	if (p == 2)
3291	setCharacteristic (getCharacteristic(), 6, 'Z');
3292	else if (p == 3)
3293	setCharacteristic (getCharacteristic(), 4, 'Z');
3294	else if (p == 5)
3295	setCharacteristic (getCharacteristic(), 3, 'Z');
3296	ExtensionInfo info= ExtensionInfo (extension);
3297	A= A.mapinto();
3298	factors= multiFactorize (A, info);
3299
3300	CanonicalForm mipo= gf_mipo;
3301	setCharacteristic (getCharacteristic());
3302	Variable vBuf= rootOf (mipo.mapinto());
3303	for (CFListIterator j= factors; j.hasItem(); j++)
3304	j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3305	}
3306	else if (p >= 7 && p*p < (1<<16)) // pass to GF if possible
3307	{
3308	setCharacteristic (getCharacteristic(), 2, 'Z');
3309	ExtensionInfo info= ExtensionInfo (extension);
3310	A= A.mapinto();
3311	factors= multiFactorize (A, info);
3312
3313	CanonicalForm mipo= gf_mipo;
3314	setCharacteristic (getCharacteristic());
3315	Variable vBuf= rootOf (mipo.mapinto());
3316	for (CFListIterator j= factors; j.hasItem(); j++)
3317	j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3318	}
3319	else // not able to pass to GF, pass to F_p(\alpha)
3320	{
3321	CanonicalForm mipo= randomIrredpoly (2, w);
3322	Variable v= rootOf (mipo);
3323	ExtensionInfo info= ExtensionInfo (v);
3324	factors= multiFactorize (A, info);
3325	}
3326	return factors;
3327	}
3328	else if (!GF && (alpha != w)) // we are in F_p(\alpha)
3329	{
3330	if (k == 1) // need factorization over F_p
3331	{
3332	int extDeg= degree (getMipo (alpha));
3333	extDeg++;
3334	CanonicalForm mipo= randomIrredpoly (extDeg + 1, w);
3335	Variable v= rootOf (mipo);
3336	ExtensionInfo info= ExtensionInfo (v);
3337	factors= multiFactorize (A, info);
3338	}
3339	else
3340	{
3341	if (beta == w)
3342	{
3343	Variable v= chooseExtension (alpha, beta, k);
3344	CanonicalForm primElem, imPrimElem;
3345	bool primFail= false;
3346	Variable vBuf;
3347	primElem= primitiveElement (alpha, vBuf, primFail);
3348	ASSERT (!primFail, "failure in integer factorizer");
3349	if (primFail)
3350	; //ERROR
3351	else
3352	imPrimElem= mapPrimElem (primElem, vBuf, v);
3353
3354	CFList source, dest;
3355	CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
3356	source, dest);
3357	ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
3358	factors= multiFactorize (bufA, info);
3359	}
3360	else
3361	{
3362	Variable v= chooseExtension (alpha, beta, k);
3363	CanonicalForm primElem, imPrimElem;
3364	bool primFail= false;
3365	Variable vBuf;
3366	ASSERT (!primFail, "failure in integer factorizer");
3367	if (primFail)
3368	; //ERROR
3369	else
3370	imPrimElem= mapPrimElem (delta, beta, v);
3371
3372	CFList source, dest;
3373	CanonicalForm bufA= mapDown (A, info, source, dest);
3374	source= CFList();
3375	dest= CFList();
3376	bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
3377	ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
3378	factors= multiFactorize (bufA, info);
3379	}
3380	}
3381	return factors;
3382	}
3383	else // we are in GF (p^k)
3384	{
3385	int p= getCharacteristic();
3386	int extensionDeg= getGFDegree();
3387	bool extension= true;
3388	if (k == 1) // need factorization over F_p
3389	{
3390	extensionDeg++;
3391	if (pow ((double) p, (double) extensionDeg) < (1<<16))
3392	// pass to GF(p^k+1)
3393	{
3394	CanonicalForm mipo= gf_mipo;
3395	setCharacteristic (p);
3396	Variable vBuf= rootOf (mipo.mapinto());
3397	A= GF2FalphaRep (A, vBuf);
3398	setCharacteristic (p, extensionDeg, 'Z');
3399	ExtensionInfo info= ExtensionInfo (extension);
3400	factors= multiFactorize (A.mapinto(), info);
3401	}
3402	else // not able to pass to another GF, pass to F_p(\alpha)
3403	{
3404	CanonicalForm mipo= gf_mipo;
3405	setCharacteristic (p);
3406	Variable vBuf= rootOf (mipo.mapinto());
3407	A= GF2FalphaRep (A, vBuf);
3408	Variable v= chooseExtension (vBuf, beta, k);
3409	ExtensionInfo info= ExtensionInfo (v, extension);
3410	factors= multiFactorize (A, info);
3411	}
3412	}
3413	else // need factorization over GF (p^k)
3414	{
3415	if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
3416	// pass to GF(p^2k)
3417	{
3418	setCharacteristic (p, 2*extensionDeg, 'Z');
3419	ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
3420	factors= multiFactorize (GFMapUp (A, extensionDeg), info);
3421	setCharacteristic (p, extensionDeg, cGFName);
3422	}
3423	else // not able to pass to GF (p^2k), pass to F_p (\alpha)
3424	{
3425	CanonicalForm mipo= gf_mipo;
3426	setCharacteristic (p);
3427	Variable v1= rootOf (mipo.mapinto());
3428	A= GF2FalphaRep (A, v1);
3429	Variable v2= chooseExtension (v1, v1, k);
3430	CanonicalForm primElem, imPrimElem;
3431	bool primFail= false;
3432	Variable vBuf;
3433	primElem= primitiveElement (v1, v1, primFail);
3434	if (primFail)
3435	; //ERROR
3436	else
3437	imPrimElem= mapPrimElem (primElem, v1, v2);
3438	CFList source, dest;
3439	CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
3440	source, dest);
3441	ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
3442	factors= multiFactorize (bufA, info);
3443	setCharacteristic (p, k, cGFName);
3444	for (CFListIterator i= factors; i.hasItem(); i++)
3445	i.getItem()= Falpha2GFRep (i.getItem());
3446	}
3447	}
3448	return factors;
3449	}
3450	}
3451
3452	#endif
3453	/* HAVE_NTL */
3454

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

Download in other formats: