Context Navigation

source: git/factory/facFqFactorize.cc @ 1b88d5

spielwiese

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

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

Download in other formats: