Context Navigation

source: git/factory/facFqFactorize.cc @ 9f7665

spielwiese

Last change on this file since 9f7665 was 9f7665, checked in by Oleksandr Motsak <motsak@…>, 10 years ago
Removed HAVE_CONFIG guards fix: fixed the inclusion of configure-generated *config.h's
Property mode set to `100644`
File size: 100.0 KB

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

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

Download in other formats: