Context Navigation

source: git/factory/facFqFactorize.cc @ 24a96f8

spielwiese

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

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

Download in other formats: