Context Navigation

source: git/factory/facFqFactorize.cc @ 16f511

spielwiese

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

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

Download in other formats: