Context Navigation

source: git/factory/facFqFactorize.cc @ 5ce0932

fieker-DuValspielwiese

Last change on this file since 5ce0932 was 03f640, checked in by Martin Lee <martinlee84@…>, 10 years ago
chg: added pruning of alg extensions
Property mode set to `100644`
File size: 103.6 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	result.append (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	appendTestMapDown (result, buf/myContent(buf), info, source, dest);
2507	return result;
2508	}
2509	for (int i= 0; i < T.length(); i++)
2510	v[i]= 0;
2511	noSubset= false;
2512	}
2513	if (T.length() < 2*s)
2514	appendMapDown (result, F/myContent(F), info, source, dest);
2515
2516	delete [] v;
2517	return result;
2518	}
2519
2520	void
2521	changeSecondVariable (CanonicalForm& A, CFList& biFactors, CFList& evaluation,
2522	CFList*& oldAeval, int lengthAeval2,
2523	const CFList& uniFactors, const Variable& w)
2524	{
2525	Variable y= Variable (2);
2526	A= swapvar (A, y, w);
2527	int i= A.level();
2528	CanonicalForm evalPoint;
2529	for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2530	{
2531	if (i == w.level())
2532	{
2533	evalPoint= iter.getItem();
2534	iter.getItem()= evaluation.getLast();
2535	evaluation.removeLast();
2536	evaluation.append (evalPoint);
2537	break;
2538	}
2539	}
2540	for (i= 0; i < lengthAeval2; i++)
2541	{
2542	if (oldAeval[i].isEmpty())
2543	continue;
2544	if (oldAeval[i].getFirst().level() == w.level())
2545	{
2546	CFArray tmp= copy (oldAeval[i]);
2547	oldAeval[i]= biFactors;
2548	for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
2549	iter.getItem()= swapvar (iter.getItem(), w, y);
2550	for (int ii= 0; ii < tmp.size(); ii++)
2551	tmp[ii]= swapvar (tmp[ii], w, y);
2552	CFArray tmp2= CFArray (tmp.size());
2553	CanonicalForm buf;
2554	for (int ii= 0; ii < tmp.size(); ii++)
2555	{
2556	buf= tmp[ii] (evaluation.getLast(),y);
2557	buf /= Lc (buf);
2558	tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
2559	}
2560	biFactors= CFList();
2561	for (int j= 0; j < tmp2.size(); j++)
2562	biFactors.append (tmp2[j]);
2563	}
2564	}
2565	}
2566
2567	void
2568	distributeLCmultiplier (CanonicalForm& A, CFList& leadingCoeffs,
2569	CFList& biFactors, const CFList& evaluation,
2570	const CanonicalForm& LCmultipler)
2571	{
2572	CanonicalForm tmp= power (LCmultipler, biFactors.length() - 1);
2573	A *= tmp;
2574	tmp= LCmultipler;
2575	CFListIterator iter= leadingCoeffs;
2576	for (;iter.hasItem(); iter++)
2577	iter.getItem() *= LCmultipler;
2578	iter= evaluation;
2579	for (int i= A.level(); i > 2; i--, iter++)
2580	tmp= tmp (iter.getItem(), i);
2581	if (!tmp.inCoeffDomain())
2582	{
2583	for (CFListIterator i= biFactors; i.hasItem(); i++)
2584	{
2585	i.getItem() *= tmp/LC (i.getItem(), 1);
2586	i.getItem() /= Lc (i.getItem());
2587	}
2588	}
2589	}
2590
2591	void
2592	LCHeuristic (CanonicalForm& A, const CanonicalForm& LCmultiplier,
2593	CFList& biFactors, CFList& leadingCoeffs, const CFList oldAeval,
2594	int lengthAeval, const CFList& evaluation,
2595	const CFList& oldBiFactors)
2596	{
2597	CFListIterator iter, iter2;
2598	int index;
2599	Variable xx;
2600	CFList vars1;
2601	CFFList sqrfMultiplier= sqrFree (LCmultiplier);
2602	if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
2603	sqrfMultiplier.removeFirst();
2604	sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
2605	xx= Variable (2);
2606	for (iter= oldBiFactors; iter.hasItem(); iter++)
2607	vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
2608	for (int i= 0; i < lengthAeval; i++)
2609	{
2610	if (oldAeval[i].isEmpty())
2611	continue;
2612	xx= oldAeval[i].getFirst().mvar();
2613	iter2= vars1;
2614	for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
2615	iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
2616	}
2617	CanonicalForm tmp;
2618	iter2= vars1;
2619	for (iter= leadingCoeffs[lengthAeval-1]; iter.hasItem(); iter++, iter2++)
2620	{
2621	tmp= iter.getItem()/LCmultiplier;
2622	for (int i=1; i <= tmp.level(); i++)
2623	{
2624	if (degree (tmp,i) > 0 && (degree (iter2.getItem(),i) > degree (tmp,i)))
2625	iter2.getItem() /= power (Variable (i), degree (tmp,i));
2626	}
2627	}
2628	int multi;
2629	for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
2630	{
2631	multi= 0;
2632	for (iter= vars1; iter.hasItem(); iter++)
2633	{
2634	tmp= iter.getItem();
2635	while (fdivides (myGetVars (ii.getItem().factor()), tmp))
2636	{
2637	multi++;
2638	tmp /= myGetVars (ii.getItem().factor());
2639	}
2640	}
2641	if (multi == ii.getItem().exp())
2642	{
2643	index= 1;
2644	for (iter= vars1; iter.hasItem(); iter++, index++)
2645	{
2646	while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2647	{
2648	int index2= 1;
2649	for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();iter2++,
2650	index2++)
2651	{
2652	if (index2 == index)
2653	continue;
2654	else
2655	{
2656	tmp= ii.getItem().factor();
2657	iter2.getItem() /= tmp;
2658	CFListIterator iter3= evaluation;
2659	for (int jj= A.level(); jj > 2; jj--, iter3++)
2660	tmp= tmp (iter3.getItem(), jj);
2661	if (!tmp.inCoeffDomain())
2662	{
2663	int index3= 1;
2664	for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2665	{
2666	if (index3 == index2)
2667	{
2668	iter3.getItem() /= tmp;
2669	iter3.getItem() /= Lc (iter3.getItem());
2670	break;
2671	}
2672	}
2673	}
2674	A /= ii.getItem().factor();
2675	}
2676	}
2677	iter.getItem() /= getVars (ii.getItem().factor());
2678	}
2679	}
2680	}
2681	else
2682	{
2683	index= 1;
2684	for (iter= vars1; iter.hasItem(); iter++, index++)
2685	{
2686	if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2687	{
2688	int index2= 1;
2689	for (iter2= leadingCoeffs[lengthAeval-1];iter2.hasItem();iter2++,
2690	index2++)
2691	{
2692	if (index2 == index)
2693	{
2694	tmp= power (ii.getItem().factor(), ii.getItem().exp());
2695	iter2.getItem() /= tmp;
2696	A /= tmp;
2697	CFListIterator iter3= evaluation;
2698	for (int jj= A.level(); jj > 2; jj--, iter3++)
2699	tmp= tmp (iter3.getItem(), jj);
2700	if (!tmp.inCoeffDomain())
2701	{
2702	int index3= 1;
2703	for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2704	{
2705	if (index3 == index2)
2706	{
2707	iter3.getItem() /= tmp;
2708	iter3.getItem() /= Lc (iter3.getItem());
2709	break;
2710	}
2711	}
2712	}
2713	}
2714	}
2715	}
2716	}
2717	}
2718	}
2719	}
2720
2721	void
2722	LCHeuristicCheck (const CFList& LCs, const CFList& contents, CanonicalForm& A,
2723	const CanonicalForm& oldA, CFList& leadingCoeffs,
2724	bool& foundTrueMultiplier)
2725	{
2726	CanonicalForm pLCs= prod (LCs);
2727	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
2728	{
2729	A= oldA;
2730	CFListIterator iter2= leadingCoeffs;
2731	for (CFListIterator iter= contents; iter.hasItem(); iter++, iter2++)
2732	iter2.getItem() /= iter.getItem();
2733	foundTrueMultiplier= true;
2734	}
2735	}
2736
2737	void
2738	LCHeuristic2 (const CanonicalForm& LCmultiplier, const CFList& factors,
2739	CFList& leadingCoeffs, CFList& contents, CFList& LCs,
2740	bool& foundTrueMultiplier)
2741	{
2742	CanonicalForm cont;
2743	int index= 1;
2744	CFListIterator iter2;
2745	for (CFListIterator iter= factors; iter.hasItem(); iter++, index++)
2746	{
2747	cont= content (iter.getItem(), 1);
2748	cont= gcd (cont, LCmultiplier);
2749	contents.append (cont);
2750	if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
2751	{
2752	foundTrueMultiplier= true;
2753	int index2= 1;
2754	for (iter2= leadingCoeffs; iter2.hasItem(); iter2++, index2++)
2755	{
2756	if (index2 == index)
2757	continue;
2758	iter2.getItem() /= LCmultiplier;
2759	}
2760	break;
2761	}
2762	else
2763	LCs.append (LC (iter.getItem()/cont, 1));
2764	}
2765	}
2766
2767	void
2768	LCHeuristic3 (const CanonicalForm& LCmultiplier, const CFList& factors,
2769	const CFList& oldBiFactors, const CFList& contents,
2770	const CFList* oldAeval, CanonicalForm& A, CFList*& leadingCoeffs,
2771	int lengthAeval, bool& foundMultiplier)
2772	{
2773	int index= 1;
2774	CFListIterator iter, iter2= factors;
2775	for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2776	{
2777	if (fdivides (iter.getItem(), LCmultiplier))
2778	{
2779	if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
2780	!isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
2781	{
2782	Variable xx= Variable (2);
2783	CanonicalForm vars;
2784	vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2785	xx));
2786	for (int i= 0; i < lengthAeval; i++)
2787	{
2788	if (oldAeval[i].isEmpty())
2789	continue;
2790	xx= oldAeval[i].getFirst().mvar();
2791	vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2792	xx));
2793	}
2794	if (vars.level() <= 2)
2795	{
2796	int index2= 1;
2797	for (CFListIterator iter3= leadingCoeffs[lengthAeval-1];
2798	iter3.hasItem(); iter3++, index2++)
2799	{
2800	if (index2 == index)
2801	{
2802	iter3.getItem() /= LCmultiplier;
2803	break;
2804	}
2805	}
2806	A /= LCmultiplier;
2807	foundMultiplier= true;
2808	iter.getItem()= 1;
2809	}
2810	}
2811	}
2812	}
2813	}
2814
2815	void
2816	LCHeuristic4 (const CFList& oldBiFactors, const CFList* oldAeval,
2817	const CFList& contents, const CFList& factors,
2818	const CanonicalForm& testVars, int lengthAeval,
2819	CFList*& leadingCoeffs, CanonicalForm& A,
2820	CanonicalForm& LCmultiplier, bool& foundMultiplier)
2821	{
2822	int index=1;
2823	CFListIterator iter, iter2= factors;
2824	for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2825	{
2826	if (!iter.getItem().isOne() &&
2827	fdivides (iter.getItem(), LCmultiplier))
2828	{
2829	if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
2830	{
2831	int index2= 1;
2832	for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2833	iter2++, index2++)
2834	{
2835	if (index2 == index)
2836	{
2837	iter2.getItem() /= iter.getItem();
2838	foundMultiplier= true;
2839	break;
2840	}
2841	}
2842	A /= iter.getItem();
2843	LCmultiplier /= iter.getItem();
2844	iter.getItem()= 1;
2845	}
2846	else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
2847	{
2848	Variable xx= Variable (2);
2849	CanonicalForm vars;
2850	vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2851	xx));
2852	for (int i= 0; i < lengthAeval; i++)
2853	{
2854	if (oldAeval[i].isEmpty())
2855	continue;
2856	xx= oldAeval[i].getFirst().mvar();
2857	vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2858	xx));
2859	}
2860	if (myGetVars(content(getItem(leadingCoeffs[lengthAeval-1],index),1))
2861	/myGetVars (LCmultiplier) == vars)
2862	{
2863	int index2= 1;
2864	for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2865	iter2++, index2++)
2866	{
2867	if (index2 == index)
2868	{
2869	iter2.getItem() /= LCmultiplier;
2870	foundMultiplier= true;
2871	break;
2872	}
2873	}
2874	A /= LCmultiplier;
2875	iter.getItem()= 1;
2876	}
2877	}
2878	}
2879	}
2880	}
2881
2882	CFList
2883	extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
2884
2885	CFList
2886	multiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
2887	{
2888	if (F.inCoeffDomain())
2889	return CFList (F);
2890
2891	TIMING_START (fac_fq_preprocess_and_content);
2892	// compress and find main Variable
2893	CFMap N;
2894	TIMING_START (fac_fq_compress)
2895	CanonicalForm A= myCompress (F, N);
2896	TIMING_END_AND_PRINT (fac_fq_compress, "time to compress poly over Fq: ")
2897
2898	A /= Lc (A); // make monic
2899
2900	Variable alpha= info.getAlpha();
2901	Variable beta= info.getBeta();
2902	CanonicalForm gamma= info.getGamma();
2903	CanonicalForm delta= info.getDelta();
2904	bool extension= info.isInExtension();
2905	bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2906	//univariate case
2907	if (F.isUnivariate())
2908	{
2909	if (extension == false)
2910	return uniFactorizer (F, alpha, GF);
2911	else
2912	{
2913	CFList source, dest;
2914	A= mapDown (F, info, source, dest);
2915	return uniFactorizer (A, beta, GF);
2916	}
2917	}
2918
2919	//bivariate case
2920	if (A.level() == 2)
2921	{
2922	CFList buf= biFactorize (F, info);
2923	return buf;
2924	}
2925
2926	Variable x= Variable (1);
2927	Variable y= Variable (2);
2928
2929	// remove content
2930	TIMING_START (fac_fq_content);
2931	CFList contentAi;
2932	CanonicalForm lcmCont= lcmContent (A, contentAi);
2933	A /= lcmCont;
2934	TIMING_END_AND_PRINT (fac_fq_content, "time to extract content over Fq: ");
2935
2936	// trivial after content removal
2937	CFList contentAFactors;
2938	if (A.inCoeffDomain())
2939	{
2940	for (CFListIterator i= contentAi; i.hasItem(); i++)
2941	{
2942	if (i.getItem().inCoeffDomain())
2943	continue;
2944	else
2945	{
2946	lcmCont /= i.getItem();
2947	contentAFactors=
2948	Union (multiFactorize (lcmCont, info),
2949	multiFactorize (i.getItem(), info));
2950	break;
2951	}
2952	}
2953	decompress (contentAFactors, N);
2954	if (!extension)
2955	normalize (contentAFactors);
2956	return contentAFactors;
2957	}
2958
2959	// factorize content
2960	TIMING_START (fac_fq_content);
2961	contentAFactors= multiFactorize (lcmCont, info);
2962	TIMING_END_AND_PRINT (fac_fq_content, "time to factor content over Fq: ");
2963
2964	// univariate after content removal
2965	CFList factors;
2966	if (A.isUnivariate ())
2967	{
2968	factors= uniFactorizer (A, alpha, GF);
2969	append (factors, contentAFactors);
2970	decompress (factors, N);
2971	return factors;
2972	}
2973
2974	// check main variable
2975	TIMING_START (fac_fq_check_mainvar);
2976	int swapLevel= 0;
2977	CanonicalForm derivZ;
2978	CanonicalForm gcdDerivZ;
2979	CanonicalForm bufA= A;
2980	Variable z;
2981	for (int i= 1; i <= A.level(); i++)
2982	{
2983	z= Variable (i);
2984	derivZ= deriv (bufA, z);
2985	if (derivZ.isZero())
2986	{
2987	if (i == 1)
2988	swapLevel= 1;
2989	else
2990	continue;
2991	}
2992	else
2993	{
2994	gcdDerivZ= gcd (bufA, derivZ);
2995	if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
2996	{
2997	CanonicalForm g= bufA/gcdDerivZ;
2998	CFList factorsG=
2999	Union (multiFactorize (g, info),
3000	multiFactorize (gcdDerivZ, info));
3001	appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
3002	if (!extension)
3003	normalize (factorsG);
3004	return factorsG;
3005	}
3006	else
3007	{
3008	if (swapLevel == 1)
3009	{
3010	swapLevel= i;
3011	bufA= swapvar (A, x, z);
3012	}
3013	A= bufA;
3014	break;
3015	}
3016	}
3017	}
3018	TIMING_END_AND_PRINT (fac_fq_check_mainvar,
3019	"time to check main var over Fq: ");
3020	TIMING_END_AND_PRINT (fac_fq_preprocess_and_content,
3021	"time to preprocess poly and extract content over Fq: ");
3022
3023	CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
3024	bool fail= false;
3025	int swapLevel2= 0;
3026	//int level;
3027	int factorNums= 3;
3028	CFList biFactors, bufBiFactors;
3029	CanonicalForm evalPoly;
3030	int lift, bufLift, lengthAeval2= A.level()-2;
3031	double logarithm= (double) ilog2 (totaldegree (A));
3032	logarithm /= log2exp;
3033	logarithm= ceil (logarithm);
3034	if (factorNums < (int) logarithm)
3035	factorNums= (int) logarithm;
3036	CFList* bufAeval2= new CFList [lengthAeval2];
3037	CFList* Aeval2= new CFList [lengthAeval2];
3038	int counter;
3039	int differentSecondVar= 0;
3040	// several bivariate factorizations
3041	TIMING_START (fac_fq_bifactor_total);
3042	for (int i= 0; i < factorNums; i++)
3043	{
3044	counter= 0;
3045	bufA= A;
3046	bufAeval= CFList();
3047	TIMING_START (fac_fq_evaluation);
3048	bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
3049	TIMING_END_AND_PRINT (fac_fq_evaluation,
3050	"time to find evaluation point over Fq: ");
3051	evalPoly= 0;
3052
3053	if (fail && (i == 0))
3054	{
3055	/*if (!swapLevel) //uncomment to reenable search for new main variable
3056	level= 2;
3057	else
3058	level= swapLevel + 1;*/
3059
3060	//CanonicalForm g;
3061	//swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
3062
3063	/*if (!swapLevel2) // need to pass to an extension
3064	{*/
3065	factors= extFactorize (A, info);
3066	appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
3067	normalize (factors);
3068	delete [] bufAeval2;
3069	delete [] Aeval2;
3070	return factors;
3071	/*}
3072	else
3073	{
3074	if (swapLevel2 == -1)
3075	{
3076	CFList factorsG=
3077	Union (multiFactorize (g, info),
3078	multiFactorize (A/g, info));
3079	appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
3080	if (!extension)
3081	normalize (factorsG);
3082	delete [] bufAeval2;
3083	delete [] Aeval2;
3084	return factorsG;
3085	}
3086	fail= false;
3087	bufAeval= Aeval;
3088	bufA= A;
3089	bufEvaluation= evaluation;
3090	}*/ //end uncomment
3091	}
3092	else if (fail && (i > 0))
3093	break;
3094
3095	TIMING_START (fac_fq_evaluation);
3096	evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
3097	TIMING_END_AND_PRINT (fac_fq_evaluation,
3098	"time for evaluation wrt diff second vars over Fq: ");
3099
3100	for (int j= 0; j < lengthAeval2; j++)
3101	{
3102	if (!bufAeval2[j].isEmpty())
3103	counter++;
3104	}
3105
3106	bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
3107
3108	TIMING_START (fac_fq_bi_factorizer);
3109	if (!GF && alpha.level() == 1)
3110	bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
3111	else if (GF)
3112	bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
3113	else
3114	bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
3115	TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
3116	"time for bivariate factorization: ");
3117	bufBiFactors.removeFirst();
3118
3119	if (bufBiFactors.length() == 1)
3120	{
3121	if (extension)
3122	{
3123	CFList source, dest;
3124	A= mapDown (A, info, source, dest);
3125	}
3126	factors.append (A);
3127	appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3128	swapLevel2, x);
3129	if (!extension)
3130	normalize (factors);
3131	delete [] bufAeval2;
3132	delete [] Aeval2;
3133	return factors;
3134	}
3135
3136	if (i == 0)
3137	{
3138	Aeval= bufAeval;
3139	evaluation= bufEvaluation;
3140	biFactors= bufBiFactors;
3141	lift= bufLift;
3142	for (int j= 0; j < lengthAeval2; j++)
3143	Aeval2 [j]= bufAeval2 [j];
3144	differentSecondVar= counter;
3145	}
3146	else
3147	{
3148	if (bufBiFactors.length() < biFactors.length() \|\|
3149	((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) \|\|
3150	counter > differentSecondVar)
3151	{
3152	Aeval= bufAeval;
3153	evaluation= bufEvaluation;
3154	biFactors= bufBiFactors;
3155	lift= bufLift;
3156	for (int j= 0; j < lengthAeval2; j++)
3157	Aeval2 [j]= bufAeval2 [j];
3158	differentSecondVar= counter;
3159	}
3160	}
3161	int k= 0;
3162	for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
3163	evalPoly += j.getItem()*power (x, k);
3164	list.append (evalPoly);
3165	}
3166
3167	delete [] bufAeval2;
3168
3169	sortList (biFactors, x);
3170
3171	int minFactorsLength;
3172	bool irred= false;
3173	TIMING_START (fac_fq_bi_factorizer);
3174	factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength,irred);
3175	TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
3176	"time for bivariate factorization wrt diff second vars over Fq: ");
3177
3178	TIMING_END_AND_PRINT (fac_fq_bifactor_total,
3179	"total time for eval and bivar factors over Fq: ");
3180	if (irred)
3181	{
3182	if (extension)
3183	{
3184	CFList source, dest;
3185	A= mapDown (A, info, source, dest);
3186	}
3187	factors.append (A);
3188	appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3189	swapLevel2, x);
3190	if (!extension)
3191	normalize (factors);
3192	delete [] Aeval2;
3193	return factors;
3194	}
3195
3196	if (minFactorsLength == 0)
3197	minFactorsLength= biFactors.length();
3198	else if (biFactors.length() > minFactorsLength)
3199	refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
3200	minFactorsLength= tmin (minFactorsLength, biFactors.length());
3201
3202	CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
3203
3204	sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
3205
3206	minFactorsLength= tmin (minFactorsLength, biFactors.length());
3207
3208	if (minFactorsLength == 1)
3209	{
3210	if (extension)
3211	{
3212	CFList source, dest;
3213	A= mapDown (A, info, source, dest);
3214	}
3215	factors.append (A);
3216	appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3217	swapLevel2, x);
3218	if (!extension)
3219	normalize (factors);
3220	delete [] Aeval2;
3221	return factors;
3222	}
3223
3224	if (differentSecondVar == lengthAeval2)
3225	{
3226	bool zeroOccured= false;
3227	for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
3228	{
3229	if (iter.getItem().isZero())
3230	{
3231	zeroOccured= true;
3232	break;
3233	}
3234	}
3235	if (!zeroOccured)
3236	{
3237	factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
3238	minFactorsLength);
3239	if (factors.length() == biFactors.length())
3240	{
3241	if (extension)
3242	factors= extNonMonicFactorRecombination (factors, A, info);
3243
3244	appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3245	swapLevel2, x);
3246	if (!extension)
3247	normalize (factors);
3248	delete [] Aeval2;
3249	return factors;
3250	}
3251	else
3252	factors= CFList();
3253	//TODO case where factors.length() > 0
3254	}
3255	}
3256
3257	CFList * oldAeval= new CFList [lengthAeval2]; //TODO use bufAeval2 for this
3258	for (int i= 0; i < lengthAeval2; i++)
3259	oldAeval[i]= Aeval2[i];
3260
3261	getLeadingCoeffs (A, Aeval2);
3262
3263	CFList biFactorsLCs;
3264	for (CFListIterator i= biFactors; i.hasItem(); i++)
3265	biFactorsLCs.append (LC (i.getItem(), 1));
3266
3267	Variable v;
3268	TIMING_START (fac_fq_precompute_leadcoeff);
3269	CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
3270	evaluation, Aeval2, lengthAeval2, v);
3271
3272	if (v.level() != 1)
3273	changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
3274	uniFactors, v);
3275
3276	CanonicalForm oldA= A;
3277	CFList oldBiFactors= biFactors;
3278
3279	CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
3280	bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
3281	leadingCoeffs.removeFirst();
3282
3283	if (!LCmultiplierIsConst)
3284	distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
3285
3286	//prepare leading coefficients
3287	CFList* leadingCoeffs2= new CFList [lengthAeval2];
3288	prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
3289	biFactors, evaluation);
3290
3291	CFListIterator iter;
3292	CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
3293	bufBiFactors= biFactors;
3294	bufA= A;
3295	CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
3296	if (!LCmultiplierIsConst)
3297	{
3298	testVars= Variable (2);
3299	for (int i= 0; i < lengthAeval2; i++)
3300	{
3301	if (!oldAeval[i].isEmpty())
3302	testVars *= oldAeval[i].getFirst().mvar();
3303	}
3304	}
3305	TIMING_END_AND_PRINT(fac_fq_precompute_leadcoeff,
3306	"time to precompute LC over Fq: ");
3307
3308	TIMING_START (fac_fq_luckswang);
3309	CFList bufFactors= CFList();
3310	bool LCheuristic= false;
3311	if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
3312	factors))
3313	{
3314	int check= biFactors.length();
3315	int * index= new int [factors.length()];
3316	CFList oldFactors= factors;
3317	factors= recoverFactors (A, factors, index);
3318
3319	if (check == factors.length())
3320	{
3321	if (extension)
3322	factors= extNonMonicFactorRecombination (factors, bufA, info);
3323
3324	if (v.level() != 1)
3325	{
3326	for (iter= factors; iter.hasItem(); iter++)
3327	iter.getItem()= swapvar (iter.getItem(), v, y);
3328	}
3329
3330	appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3331	swapLevel2, x);
3332	if (!extension)
3333	normalize (factors);
3334	delete [] index;
3335	delete [] Aeval2;
3336	TIMING_END_AND_PRINT (fac_fq_luckswang,
3337	"time for successful LucksWang over Fq: ");
3338	return factors;
3339	}
3340	else if (factors.length() > 0)
3341	{
3342	int oneCount= 0;
3343	CFList l;
3344	for (int i= 0; i < check; i++)
3345	{
3346	if (index[i] == 1)
3347	{
3348	iter=biFactors;
3349	for (int j=1; j <= i-oneCount; j++)
3350	iter++;
3351	iter.remove (1);
3352	for (int j= 0; j < lengthAeval2; j++)
3353	{
3354	l= leadingCoeffs2[j];
3355	iter= l;
3356	for (int k=1; k <= i-oneCount; k++)
3357	iter++;
3358	iter.remove (1);
3359	leadingCoeffs2[j]=l;
3360	}
3361	oneCount++;
3362	}
3363	}
3364	bufFactors= factors;
3365	factors= CFList();
3366	}
3367	else if (!LCmultiplierIsConst && factors.length() == 0)
3368	{
3369	LCheuristic= true;
3370	factors= oldFactors;
3371	CFList contents, LCs;
3372	bool foundTrueMultiplier= false;
3373	LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
3374	contents, LCs, foundTrueMultiplier);
3375	if (foundTrueMultiplier)
3376	{
3377	A= oldA;
3378	leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3379	for (int i= lengthAeval2-1; i > -1; i--)
3380	leadingCoeffs2[i]= CFList();
3381	prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
3382	leadingCoeffs, biFactors, evaluation);
3383	}
3384	else
3385	{
3386	bool foundMultiplier= false;
3387	LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
3388	A, leadingCoeffs2, lengthAeval2, foundMultiplier);
3389
3390	// coming from above: divide out more LCmultiplier if possible
3391	if (foundMultiplier)
3392	{
3393	foundMultiplier= false;
3394	LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
3395	lengthAeval2, leadingCoeffs2, A, LCmultiplier,
3396	foundMultiplier);
3397	}
3398	else
3399	{
3400	LCHeuristicCheck (LCs, contents, A, oldA,
3401	leadingCoeffs2[lengthAeval2-1], foundMultiplier);
3402	if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
3403	{
3404	LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
3405	lengthAeval2, evaluation, oldBiFactors);
3406	}
3407	}
3408
3409	// patch everything together again
3410	leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3411	for (int i= lengthAeval2-1; i > -1; i--)
3412	leadingCoeffs2[i]= CFList();
3413	prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
3414	biFactors, evaluation);
3415	}
3416	factors= CFList();
3417	if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
3418	{
3419	LCheuristic= false;
3420	A= bufA;
3421	biFactors= bufBiFactors;
3422	leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3423	LCmultiplier= bufLCmultiplier;
3424	}
3425	}
3426	else
3427	factors= CFList();
3428	delete [] index;
3429	}
3430	TIMING_END_AND_PRINT (fac_fq_luckswang, "time for LucksWang over Fq: ");
3431
3432	TIMING_START (fac_fq_lcheuristic);
3433	if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
3434	&& fdivides (getVars (LCmultiplier), testVars))
3435	{
3436	LCheuristic= true;
3437	LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
3438	lengthAeval2, evaluation, oldBiFactors);
3439
3440	leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3441	for (int i= lengthAeval2-1; i > -1; i--)
3442	leadingCoeffs2[i]= CFList();
3443	prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
3444	biFactors, evaluation);
3445
3446	if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
3447	{
3448	LCheuristic= false;
3449	A= bufA;
3450	biFactors= bufBiFactors;
3451	leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3452	LCmultiplier= bufLCmultiplier;
3453	}
3454	}
3455	TIMING_END_AND_PRINT (fac_fq_lcheuristic, "time for Lc heuristic over Fq: ");
3456
3457	tryAgainWithoutHeu:
3458	TIMING_START (fac_fq_shift_to_zero);
3459	A= shift2Zero (A, Aeval, evaluation);
3460
3461	for (iter= biFactors; iter.hasItem(); iter++)
3462	iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3463
3464	for (int i= 0; i < lengthAeval2-1; i++)
3465	leadingCoeffs2[i]= CFList();
3466	for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
3467	{
3468	iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
3469	for (int i= A.level() - 4; i > -1; i--)
3470	{
3471	if (i + 1 == lengthAeval2-1)
3472	leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
3473	else
3474	leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
3475	}
3476	}
3477	TIMING_END_AND_PRINT (fac_fq_shift_to_zero,
3478	"time to shift evaluation point to zero: ");
3479
3480	CFArray Pi;
3481	CFList diophant;
3482	int* liftBounds= new int [A.level() - 1];
3483	int liftBoundsLength= A.level() - 1;
3484	for (int i= 0; i < liftBoundsLength; i++)
3485	liftBounds [i]= degree (A, i + 2) + 1;
3486
3487	Aeval.removeFirst();
3488	bool noOneToOne= false;
3489	TIMING_START (fac_fq_hensel_lift);
3490	factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
3491	Pi, liftBounds, liftBoundsLength, noOneToOne);
3492	TIMING_END_AND_PRINT (fac_fq_hensel_lift,
3493	"time for non monic hensel lifting over Fq: ");
3494
3495	if (!noOneToOne)
3496	{
3497	int check= factors.length();
3498	A= oldA;
3499	TIMING_START (fac_fq_recover_factors);
3500	factors= recoverFactors (A, factors, evaluation);
3501	TIMING_END_AND_PRINT (fac_fq_recover_factors,
3502	"time to recover factors over Fq: ");
3503	if (check != factors.length())
3504	noOneToOne= true;
3505	else
3506	factors= Union (factors, bufFactors);
3507
3508	if (extension && !noOneToOne)
3509	factors= extNonMonicFactorRecombination (factors, A, info);
3510	}
3511	if (noOneToOne)
3512	{
3513	if (!LCmultiplierIsConst && LCheuristic)
3514	{
3515	A= bufA;
3516	biFactors= bufBiFactors;
3517	leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3518	delete [] liftBounds;
3519	LCheuristic= false;
3520	goto tryAgainWithoutHeu;
3521	//something probably went wrong in the heuristic
3522	}
3523
3524	A= shift2Zero (oldA, Aeval, evaluation);
3525	biFactors= oldBiFactors;
3526	for (iter= biFactors; iter.hasItem(); iter++)
3527	iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3528	CanonicalForm LCA= LC (Aeval.getFirst(), 1);
3529	CanonicalForm yToLift= power (y, lift);
3530	CFListIterator i= biFactors;
3531	lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
3532	i++;
3533
3534	for (; i.hasItem(); i++)
3535	lift= tmax (lift,
3536	degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
3537
3538	lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
3539
3540	i= biFactors;
3541	yToLift= power (y, lift);
3542	CanonicalForm dummy;
3543	for (; i.hasItem(); i++)
3544	{
3545	LCA= LC (i.getItem(), 1);
3546	extgcd (LCA, yToLift, LCA, dummy);
3547	i.getItem()= mod (i.getItem()*LCA, yToLift);
3548	}
3549
3550	liftBoundsLength= F.level() - 1;
3551	liftBounds= liftingBounds (A, lift);
3552
3553	CFList MOD;
3554	bool earlySuccess;
3555	CFList earlyFactors, liftedFactors;
3556	TIMING_START (fac_fq_hensel_lift);
3557	liftedFactors= henselLiftAndEarly
3558	(A, MOD, liftBounds, earlySuccess, earlyFactors,
3559	Aeval, biFactors, evaluation, info);
3560	TIMING_END_AND_PRINT (fac_fq_hensel_lift,
3561	"time for hensel lifting over Fq: ");
3562
3563	if (!extension)
3564	{
3565	TIMING_START (fac_fq_factor_recombination);
3566	factors= factorRecombination (A, liftedFactors, MOD);
3567	TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3568	"time for factor recombination: ");
3569	}
3570	else
3571	{
3572	TIMING_START (fac_fq_factor_recombination);
3573	factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
3574	TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3575	"time for factor recombination: ");
3576	}
3577
3578	if (earlySuccess)
3579	factors= Union (factors, earlyFactors);
3580	if (!extension)
3581	{
3582	for (CFListIterator i= factors; i.hasItem(); i++)
3583	{
3584	int kk= Aeval.getLast().level();
3585	for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
3586	{
3587	if (i.getItem().level() < kk)
3588	continue;
3589	i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
3590	}
3591	}
3592	}
3593	}
3594
3595	if (v.level() != 1)
3596	{
3597	for (CFListIterator iter= factors; iter.hasItem(); iter++)
3598	iter.getItem()= swapvar (iter.getItem(), v, y);
3599	}
3600
3601	swap (factors, swapLevel, swapLevel2, x);
3602	append (factors, contentAFactors);
3603	decompress (factors, N);
3604	if (!extension)
3605	normalize (factors);
3606
3607	delete[] liftBounds;
3608
3609	return factors;
3610	}
3611
3612	/// multivariate factorization over an extension of the initial field
3613	CFList
3614	extFactorize (const CanonicalForm& F, const ExtensionInfo& info)
3615	{
3616	CanonicalForm A= F;
3617
3618	Variable alpha= info.getAlpha();
3619	Variable beta= info.getBeta();
3620	int k= info.getGFDegree();
3621	char cGFName= info.getGFName();
3622	CanonicalForm delta= info.getDelta();
3623	bool GF= (CFFactory::gettype() == GaloisFieldDomain);
3624	Variable w= Variable (1);
3625
3626	CFList factors;
3627	if (!GF && alpha == w) // we are in F_p
3628	{
3629	CFList factors;
3630	bool extension= true;
3631	int p= getCharacteristic();
3632	if (p < 7)
3633	{
3634	if (p == 2)
3635	setCharacteristic (getCharacteristic(), 6, 'Z');
3636	else if (p == 3)
3637	setCharacteristic (getCharacteristic(), 4, 'Z');
3638	else if (p == 5)
3639	setCharacteristic (getCharacteristic(), 3, 'Z');
3640	ExtensionInfo info= ExtensionInfo (extension);
3641	A= A.mapinto();
3642	factors= multiFactorize (A, info);
3643
3644	CanonicalForm mipo= gf_mipo;
3645	setCharacteristic (getCharacteristic());
3646	Variable vBuf= rootOf (mipo.mapinto());
3647	for (CFListIterator j= factors; j.hasItem(); j++)
3648	j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3649	prune (vBuf);
3650	}
3651	else if (p >= 7 && p*p < (1<<16)) // pass to GF if possible
3652	{
3653	setCharacteristic (getCharacteristic(), 2, 'Z');
3654	ExtensionInfo info= ExtensionInfo (extension);
3655	A= A.mapinto();
3656	factors= multiFactorize (A, info);
3657
3658	CanonicalForm mipo= gf_mipo;
3659	setCharacteristic (getCharacteristic());
3660	Variable vBuf= rootOf (mipo.mapinto());
3661	for (CFListIterator j= factors; j.hasItem(); j++)
3662	j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3663	prune (vBuf);
3664	}
3665	else // not able to pass to GF, pass to F_p(\alpha)
3666	{
3667	CanonicalForm mipo= randomIrredpoly (2, w);
3668	Variable v= rootOf (mipo);
3669	ExtensionInfo info= ExtensionInfo (v);
3670	factors= multiFactorize (A, info);
3671	prune (v);
3672	}
3673	return factors;
3674	}
3675	else if (!GF && (alpha != w)) // we are in F_p(\alpha)
3676	{
3677	if (k == 1) // need factorization over F_p
3678	{
3679	int extDeg= degree (getMipo (alpha));
3680	extDeg++;
3681	CanonicalForm mipo= randomIrredpoly (extDeg, w);
3682	Variable v= rootOf (mipo);
3683	ExtensionInfo info= ExtensionInfo (v);
3684	factors= multiFactorize (A, info);
3685	prune (v);
3686	}
3687	else
3688	{
3689	if (beta == w)
3690	{
3691	Variable v= chooseExtension (alpha, beta, k);
3692	CanonicalForm primElem, imPrimElem;
3693	bool primFail= false;
3694	Variable vBuf;
3695	primElem= primitiveElement (alpha, vBuf, primFail);
3696	ASSERT (!primFail, "failure in integer factorizer");
3697	if (primFail)
3698	; //ERROR
3699	else
3700	imPrimElem= mapPrimElem (primElem, vBuf, v);
3701
3702	CFList source, dest;
3703	CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
3704	source, dest);
3705	ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
3706	factors= multiFactorize (bufA, info);
3707	prune (v);
3708	}
3709	else
3710	{
3711	Variable v= chooseExtension (alpha, beta, k);
3712	CanonicalForm primElem, imPrimElem;
3713	bool primFail= false;
3714	Variable vBuf;
3715	ASSERT (!primFail, "failure in integer factorizer");
3716	if (primFail)
3717	; //ERROR
3718	else
3719	imPrimElem= mapPrimElem (delta, beta, v);
3720
3721	CFList source, dest;
3722	CanonicalForm bufA= mapDown (A, info, source, dest);
3723	source= CFList();
3724	dest= CFList();
3725	bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
3726	ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
3727	factors= multiFactorize (bufA, info);
3728	prune (v);
3729	}
3730	}
3731	return factors;
3732	}
3733	else // we are in GF (p^k)
3734	{
3735	int p= getCharacteristic();
3736	int extensionDeg= getGFDegree();
3737	bool extension= true;
3738	if (k == 1) // need factorization over F_p
3739	{
3740	extensionDeg++;
3741	if (pow ((double) p, (double) extensionDeg) < (1<<16))
3742	// pass to GF(p^k+1)
3743	{
3744	CanonicalForm mipo= gf_mipo;
3745	setCharacteristic (p);
3746	Variable vBuf= rootOf (mipo.mapinto());
3747	A= GF2FalphaRep (A, vBuf);
3748	setCharacteristic (p, extensionDeg, 'Z');
3749	ExtensionInfo info= ExtensionInfo (extension);
3750	factors= multiFactorize (A.mapinto(), info);
3751	prune (vBuf);
3752	}
3753	else // not able to pass to another GF, pass to F_p(\alpha)
3754	{
3755	CanonicalForm mipo= gf_mipo;
3756	setCharacteristic (p);
3757	Variable vBuf= rootOf (mipo.mapinto());
3758	A= GF2FalphaRep (A, vBuf);
3759	Variable v= chooseExtension (vBuf, beta, k);
3760	ExtensionInfo info= ExtensionInfo (v, extension);
3761	factors= multiFactorize (A, info);
3762	prune (vBuf);
3763	}
3764	}
3765	else // need factorization over GF (p^k)
3766	{
3767	if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
3768	// pass to GF(p^2k)
3769	{
3770	setCharacteristic (p, 2*extensionDeg, 'Z');
3771	ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
3772	factors= multiFactorize (GFMapUp (A, extensionDeg), info);
3773	setCharacteristic (p, extensionDeg, cGFName);
3774	}
3775	else // not able to pass to GF (p^2k), pass to F_p (\alpha)
3776	{
3777	CanonicalForm mipo= gf_mipo;
3778	setCharacteristic (p);
3779	Variable v1= rootOf (mipo.mapinto());
3780	A= GF2FalphaRep (A, v1);
3781	Variable v2= chooseExtension (v1, v1, k);
3782	CanonicalForm primElem, imPrimElem;
3783	bool primFail= false;
3784	Variable vBuf;
3785	primElem= primitiveElement (v1, v1, primFail);
3786	if (primFail)
3787	; //ERROR
3788	else
3789	imPrimElem= mapPrimElem (primElem, v1, v2);
3790	CFList source, dest;
3791	CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
3792	source, dest);
3793	ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
3794	factors= multiFactorize (bufA, info);
3795	setCharacteristic (p, k, cGFName);
3796	for (CFListIterator i= factors; i.hasItem(); i++)
3797	i.getItem()= Falpha2GFRep (i.getItem());
3798	prune (v1);
3799	}
3800	}
3801	return factors;
3802	}
3803	}
3804
3805	#endif
3806	/* HAVE_NTL */

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

Download in other formats: