Context Navigation

source: git/factory/facFqFactorize.cc @ 010a14

spielwiese

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

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

Download in other formats: