Context Navigation

source: git/factory/facFqFactorize.cc @ 40094f

fieker-DuValspielwiese

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

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

Download in other formats: