Context Navigation

source: git/factory/facFqFactorize.cc @ 3426de2

spielwiese

Last change on this file since 3426de2 was 38ffb7, checked in by Martin Lee <martinlee84@…>, 13 years ago
code clean up in facFqBivar.cc, facFqFactorize.cc, facFactorize.cc git-svn-id: file:///usr/local/Singular/svn/trunk@14378 2c84dea3-7e68-4137-9b89-c4e89433aadc
Property mode set to `100644`
File size: 69.3 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	* @internal @version \$Id$
16	*
17	**/
18	/*****************************************************************************/
19
20	#include <config.h>
21
22	#include "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
34	#ifdef HAVE_NTL
35	#include <NTL/ZZ_pEX.h>
36	#include "NTLconvert.h"
37
38	TIMING_DEFINE_PRINT(fac_bi_factorizer);
39	TIMING_DEFINE_PRINT(fac_hensel_lift);
40	TIMING_DEFINE_PRINT(fac_factor_recombination);
41
42	static inline
43	CanonicalForm
44	listGCD (const CFList& L);
45
46	static inline
47	CanonicalForm
48	myContent (const CanonicalForm& F)
49	{
50	CanonicalForm G= swapvar (F, F.mvar(), Variable (1));
51	CFList L;
52	for (CFIterator i= G; i.hasTerms(); i++)
53	L.append (i.coeff());
54	if (L.length() == 2)
55	return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), Variable (1));
56	if (L.length() == 1)
57	return LC (F, Variable (1));
58	return swapvar (listGCD (L), F.mvar(), Variable (1));
59	}
60
61	static inline
62	CanonicalForm
63	listGCD (const CFList& L)
64	{
65	if (L.length() == 1)
66	return L.getFirst();
67	if (L.length() == 2)
68	return gcd (L.getFirst(), L.getLast());
69	else
70	{
71	CFList lHi, lLo;
72	CanonicalForm resultHi, resultLo;
73	int length= L.length()/2;
74	int j= 0;
75	for (CFListIterator i= L; j < length; i++, j++)
76	lHi.append (i.getItem());
77	lLo= Difference (L, lHi);
78	resultHi= listGCD (lHi);
79	resultLo= listGCD (lLo);
80	if (resultHi.isOne() \|\| resultLo.isOne())
81	return 1;
82	return gcd (resultHi, resultLo);
83	}
84	}
85
86	static inline
87	CanonicalForm
88	myContent (const CanonicalForm& F, const Variable& x)
89	{
90	if (degree (F, x) <= 0)
91	return 1;
92	CanonicalForm G= F;
93	bool swap= false;
94	if (x != F.mvar())
95	{
96	swap= true;
97	G= swapvar (F, x, F.mvar());
98	}
99	CFList L;
100	Variable alpha;
101	for (CFIterator i= G; i.hasTerms(); i++)
102	L.append (i.coeff());
103	if (L.length() == 2)
104	{
105	if (swap)
106	return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
107	else
108	return gcd (L.getFirst(), L.getLast());
109	}
110	if (L.length() == 1)
111	{
112	return LC (F, x);
113	}
114	if (swap)
115	return swapvar (listGCD (L), F.mvar(), x);
116	else
117	return listGCD (L);
118	}
119
120	CanonicalForm myCompress (const CanonicalForm& F, CFMap& N)
121	{
122	int n= F.level();
123	int * degsf= new int [n + 1];
124	int ** swap;
125	swap= new int* [n + 1];
126	for (int i= 0; i <= n; i++)
127	{
128	degsf[i]= 0;
129	swap [i]= new int [2];
130	swap [i] [0]= 0;
131	swap [i] [1]= 0;
132	}
133	int i= 1;
134	n= 1;
135	degsf= degrees (F, degsf);
136
137	CanonicalForm result= F;
138	while ( i <= F.level() )
139	{
140	while( degsf[i] == 0 ) i++;
141	swap[n][0]= i;
142	swap[n][1]= degsf[i];
143	if (i != n)
144	result= swapvar (result, Variable (n), Variable(i));
145	n++; i++;
146	}
147
148	int buf1, buf2;
149	n--;
150
151	for (i= 1; i < n; i++)
152	{
153	for (int j= 1; j < n - i + 1; j++)
154	{
155	if (swap[j][1] < swap[j + 1][1])
156	{
157	buf1= swap [j + 1] [0];
158	buf2= swap [j + 1] [1];
159	swap[j + 1] [0]= swap[j] [0];
160	swap[j + 1] [1]= swap[j] [1];
161	swap[j][0]= buf1;
162	swap[j][1]= buf2;
163	result= swapvar (result, Variable (j + 1), Variable (j));
164	}
165	}
166	}
167
168	for (i= n; i > 0; i--)
169	{
170	if (i != swap[i] [0])
171	N.newpair (Variable (i), Variable (swap[i] [0]));
172	}
173
174	for (i= 0; i <= n; i++)
175	delete [] swap[i];
176	delete [] swap;
177
178	delete [] degsf;
179
180	return result;
181	}
182
183	CFList
184	extFactorRecombination (const CFList& factors, const CanonicalForm& F,
185	const CFList& M, const ExtensionInfo& info,
186	const CFList& evaluation)
187	{
188	Variable alpha= info.getAlpha();
189	Variable beta= info.getBeta();
190	CanonicalForm gamma= info.getGamma();
191	CanonicalForm delta= info.getDelta();
192	int k= info.getGFDegree();
193	CFList source, dest;
194	if (factors.length() == 1)
195	{
196	CanonicalForm buf= reverseShift (F, evaluation);
197	return CFList (mapDown (buf, info, source, dest));
198	}
199	if (factors.length() < 1)
200	return CFList();
201
202	int degMipoBeta= 1;
203	if (!k && beta.level() != 1)
204	degMipoBeta= degree (getMipo (beta));
205
206	CFList T, S;
207	T= factors;
208
209	int s= 1;
210	CFList result;
211	CanonicalForm buf;
212
213	buf= F;
214
215	CanonicalForm g, LCBuf= LC (buf, Variable (1));
216	CanonicalForm buf2, quot;
217	int * v= new int [T.length()];
218	for (int i= 0; i < T.length(); i++)
219	v[i]= 0;
220	bool noSubset= false;
221	CFArray TT;
222	TT= copy (factors);
223	bool recombination= false;
224	bool trueFactor= false;
225	while (T.length() >= 2*s)
226	{
227	while (noSubset == false)
228	{
229	if (T.length() == s)
230	{
231	delete [] v;
232	if (recombination)
233	{
234	T.insert (LCBuf);
235	g= prodMod (T, M);
236	T.removeFirst();
237	result.append (g/myContent (g));
238	g= reverseShift (g, evaluation);
239	g /= Lc (g);
240	appendTestMapDown (result, g, info, source, dest);
241	return result;
242	}
243	else
244	{
245	buf= reverseShift (buf, evaluation);
246	return CFList (buf);
247	}
248	}
249
250	S= subset (v, s, TT, noSubset);
251	if (noSubset) break;
252
253	S.insert (LCBuf);
254	g= prodMod (S, M);
255	S.removeFirst();
256	g /= myContent (g);
257	if (fdivides (g, buf, quot))
258	{
259	buf2= reverseShift (g, evaluation);
260	buf2 /= Lc (buf2);
261	if (!k && beta == Variable (1))
262	{
263	if (degree (buf2, alpha) < degMipoBeta)
264	{
265	appendTestMapDown (result, buf2, info, source, dest);
266	buf= quot;
267	LCBuf= LC (buf, Variable (1));
268	recombination= true;
269	trueFactor= true;
270	}
271	}
272	else
273	{
274	if (!isInExtension (buf2, gamma, k, delta, source, dest))
275	{
276	appendTestMapDown (result, buf2, info, source, dest);
277	buf /= g;
278	LCBuf= LC (buf, Variable (1));
279	recombination= true;
280	trueFactor= true;
281	}
282	}
283
284	if (trueFactor)
285	{
286	T= Difference (T, S);
287
288	if (T.length() < 2*s \|\| T.length() == s)
289	{
290	buf= reverseShift (buf, evaluation);
291	buf /= Lc (buf);
292	appendTestMapDown (result, buf, info, source, dest);
293	delete [] v;
294	return result;
295	}
296	trueFactor= false;
297	TT= copy (T);
298	indexUpdate (v, s, T.length(), noSubset);
299	if (noSubset) break;
300	}
301	}
302	}
303	s++;
304	if (T.length() < 2*s \|\| T.length() == s)
305	{
306	buf= reverseShift (buf, evaluation);
307	appendTestMapDown (result, buf, info, source, dest);
308	delete [] v;
309	return result;
310	}
311	for (int i= 0; i < T.length(); i++)
312	v[i]= 0;
313	noSubset= false;
314	}
315	if (T.length() < 2*s)
316	{
317	buf= reverseShift (F, evaluation);
318	appendMapDown (result, buf, info, source, dest);
319	}
320
321	delete [] v;
322	return result;
323	}
324
325	CFList
326	factorRecombination (const CanonicalForm& F, const CFList& factors,
327	const CFList& M)
328	{
329	if (factors.length() == 1)
330	return CFList(F);
331	if (factors.length() < 1)
332	return CFList();
333
334	CFList T, S;
335
336	T= factors;
337
338	int s= 1;
339	CFList result;
340	CanonicalForm LCBuf= LC (F, Variable (1));
341	CanonicalForm g, buf= F;
342	int * v= new int [T.length()];
343	for (int i= 0; i < T.length(); i++)
344	v[i]= 0;
345	bool noSubset= false;
346	CFArray TT;
347	TT= copy (factors);
348	Variable y= F.level() - 1;
349	bool recombination= false;
350	CanonicalForm h, quot;
351	while (T.length() >= 2*s)
352	{
353	while (noSubset == false)
354	{
355	if (T.length() == s)
356	{
357	delete [] v;
358	if (recombination)
359	{
360	T.insert (LC (buf));
361	g= prodMod (T, M);
362	result.append (g/myContent (g));
363	return result;
364	}
365	else
366	return CFList (F);
367	}
368	S= subset (v, s, TT, noSubset);
369	if (noSubset) break;
370	S.insert (LCBuf);
371	g= prodMod (S, M);
372	S.removeFirst();
373	g /= myContent (g);
374	if (fdivides (g, buf, quot))
375	{
376	recombination= true;
377	result.append (g);
378	buf= quot;
379	LCBuf= LC (buf, Variable(1));
380	T= Difference (T, S);
381	if (T.length() < 2*s \|\| T.length() == s)
382	{
383	result.append (buf);
384	delete [] v;
385	return result;
386	}
387	TT= copy (T);
388	indexUpdate (v, s, T.length(), noSubset);
389	if (noSubset) break;
390	}
391	}
392	s++;
393	if (T.length() < 2*s \|\| T.length() == s)
394	{
395	result.append (buf);
396	delete [] v;
397	return result;
398	}
399	for (int i= 0; i < T.length(); i++)
400	v[i]= 0;
401	noSubset= false;
402	}
403	if (T.length() < 2*s)
404	result.append (F);
405
406	delete [] v;
407	return result;
408	}
409
410	int
411	liftBoundAdaption (const CanonicalForm& F, const CFList& factors, bool&
412	success, const int deg, const CFList& MOD, const int bound)
413	{
414	int adaptedLiftBound= 0;
415	CanonicalForm buf= F;
416	Variable y= F.mvar();
417	CanonicalForm LCBuf= LC (buf, Variable (1));
418	CanonicalForm g, quot;
419	CFList M= MOD;
420	M.append (power (y, deg));
421	int d= bound;
422	int e= 0;
423	int nBuf;
424	for (CFListIterator i= factors; i.hasItem(); i++)
425	{
426	g= mulMod (i.getItem(), LCBuf, M);
427	g /= myContent (g);
428	if (fdivides (g, buf, quot))
429	{
430	nBuf= degree (g, y) + degree (LC (g, 1), y);
431	d -= nBuf;
432	e= tmax (e, nBuf);
433	buf= quot;
434	LCBuf= LC (buf, Variable (1));
435	}
436	}
437	adaptedLiftBound= d;
438
439	if (adaptedLiftBound < deg)
440	{
441	if (adaptedLiftBound < degree (F) + 1)
442	{
443	if (d == 1)
444	{
445	if (e + 1 > deg)
446	{
447	adaptedLiftBound= deg;
448	success= false;
449	}
450	else
451	{
452	success= true;
453	if (e + 1 < degree (F) + 1)
454	adaptedLiftBound= deg;
455	else
456	adaptedLiftBound= e + 1;
457	}
458	}
459	else
460	{
461	success= true;
462	adaptedLiftBound= deg;
463	}
464	}
465	else
466	{
467	success= true;
468	}
469	}
470	return adaptedLiftBound;
471	}
472
473	int
474	extLiftBoundAdaption (const CanonicalForm& F, const CFList& factors, bool&
475	success, const ExtensionInfo& info, const CFList& eval,
476	const int deg, const CFList& MOD, const int bound)
477	{
478	Variable alpha= info.getAlpha();
479	Variable beta= info.getBeta();
480	CanonicalForm gamma= info.getGamma();
481	CanonicalForm delta= info.getDelta();
482	int k= info.getGFDegree();
483	int adaptedLiftBound= 0;
484	CanonicalForm buf= F;
485	Variable y= F.mvar();
486	CanonicalForm LCBuf= LC (buf, Variable (1));
487	CanonicalForm g, gg, quot;
488	CFList M= MOD;
489	M.append (power (y, deg));
490	adaptedLiftBound= 0;
491	int d= bound;
492	int e= 0;
493	int nBuf;
494	int degMipoBeta= 1;
495	if (!k && beta.level() != 1)
496	degMipoBeta= degree (getMipo (beta));
497
498	CFList source, dest;
499	for (CFListIterator i= factors; i.hasItem(); i++)
500	{
501	g= mulMod (i.getItem(), LCBuf, M);
502	g /= myContent (g);
503	if (fdivides (g, buf, quot))
504	{
505	gg= reverseShift (g, eval);
506	gg /= Lc (gg);
507	if (!k && beta == Variable (1))
508	{
509	if (degree (gg, alpha) < degMipoBeta)
510	{
511	buf= quot;
512	nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
513	d -= nBuf;
514	e= tmax (e, nBuf);
515	LCBuf= LC (buf, Variable (1));
516	}
517	}
518	else
519	{
520	if (!isInExtension (gg, gamma, k, delta, source, dest))
521	{
522	buf= quot;
523	nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
524	d -= nBuf;
525	e= tmax (e, nBuf);
526	LCBuf= LC (buf, Variable (1));
527	}
528	}
529	}
530	}
531	adaptedLiftBound= d;
532
533	if (adaptedLiftBound < deg)
534	{
535	if (adaptedLiftBound < degree (F) + 1)
536	{
537	if (d == 1)
538	{
539	if (e + 1 > deg)
540	{
541	adaptedLiftBound= deg;
542	success= false;
543	}
544	else
545	{
546	success= true;
547	if (e + 1 < degree (F) + 1)
548	adaptedLiftBound= deg;
549	else
550	adaptedLiftBound= e + 1;
551	}
552	}
553	else
554	{
555	success= true;
556	adaptedLiftBound= deg;
557	}
558	}
559	else
560	{
561	success= true;
562	}
563	}
564
565	return adaptedLiftBound;
566	}
567
568	CFList
569	earlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound,
570	bool& success, const int deg, const CFList& MOD,
571	const int bound)
572	{
573	CFList result;
574	CFList T= factors;
575	CanonicalForm buf= F;
576	Variable y= F.mvar();
577	CanonicalForm LCBuf= LC (buf, Variable (1));
578	CanonicalForm g, quot;
579	CFList M= MOD;
580	M.append (power (y, deg));
581	adaptedLiftBound= 0;
582	int d= bound;
583	int e= 0;
584	int nBuf;
585	for (CFListIterator i= factors; i.hasItem(); i++)
586	{
587	g= mulMod (i.getItem(), LCBuf, M);
588	g /= myContent (g);
589	if (fdivides (g, buf, quot))
590	{
591	result.append (g);
592	nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
593	d -= nBuf;
594	e= tmax (e, nBuf);
595	buf= quot;
596	LCBuf= LC (buf, Variable (1));
597	T= Difference (T, CFList (i.getItem()));
598	}
599	}
600	adaptedLiftBound= d;
601
602	if (adaptedLiftBound < deg)
603	{
604	if (adaptedLiftBound < degree (F) + 1)
605	{
606	if (d == 1)
607	adaptedLiftBound= tmin (e + 1, deg);
608	else
609	adaptedLiftBound= deg;
610	}
611	factors= T;
612	F= buf;
613	success= true;
614	}
615	return result;
616	}
617
618	CFList
619	extEarlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound,
620	bool& success, const ExtensionInfo& info, const CFList&
621	eval, const int deg, const CFList& MOD, const int bound)
622	{
623	Variable alpha= info.getAlpha();
624	Variable beta= info.getBeta();
625	CanonicalForm gamma= info.getGamma();
626	CanonicalForm delta= info.getDelta();
627	int k= info.getGFDegree();
628	CFList result;
629	CFList T= factors;
630	CanonicalForm buf= F;
631	Variable y= F.mvar();
632	CanonicalForm LCBuf= LC (buf, Variable (1));
633	CanonicalForm g, gg, quot;
634	CFList M= MOD;
635	M.append (power (y, deg));
636	adaptedLiftBound= 0;
637	int d= bound;
638	int e= 0;
639	int nBuf;
640	CFList source, dest;
641
642	int degMipoBeta= 1;
643	if (!k && beta.level() != 1)
644	degMipoBeta= degree (getMipo (beta));
645
646	for (CFListIterator i= factors; i.hasItem(); i++)
647	{
648	g= mulMod (i.getItem(), LCBuf, M);
649	g /= myContent (g);
650	if (fdivides (g, buf, quot))
651	{
652	gg= reverseShift (g, eval);
653	gg /= Lc (gg);
654	if (!k && beta == Variable (1))
655	{
656	if (degree (gg, alpha) < degMipoBeta)
657	{
658	appendTestMapDown (result, gg, info, source, dest);
659	buf= quot;
660	nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
661	d -= nBuf;
662	e= tmax (e, nBuf);
663	LCBuf= LC (buf, Variable (1));
664	T= Difference (T, CFList (i.getItem()));
665	}
666	}
667	else
668	{
669	if (!isInExtension (gg, gamma, k, delta, source, dest))
670	{
671	appendTestMapDown (result, gg, info, source, dest);
672	buf= quot;
673	nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
674	d -= nBuf;
675	e= tmax (e, nBuf);
676	LCBuf= LC (buf, Variable (1));
677	T= Difference (T, CFList (i.getItem()));
678	}
679	}
680	}
681	}
682	adaptedLiftBound= d;
683
684	if (adaptedLiftBound < deg)
685	{
686	if (adaptedLiftBound < degree (F) + 1)
687	{
688	if (d == 1)
689	adaptedLiftBound= tmin (e + 1, deg);
690	else
691	adaptedLiftBound= deg;
692	}
693	success= true;
694	factors= T;
695	F= buf;
696	}
697	return result;
698	}
699
700	CFList
701	evalPoints (const CanonicalForm& F, CFList & eval, const Variable& alpha,
702	CFList& list, const bool& GF, bool& fail)
703	{
704	int k= F.level() - 1;
705	Variable x= Variable (1);
706	CFList result;
707	FFRandom genFF;
708	GFRandom genGF;
709	int p= getCharacteristic ();
710	double bound;
711	if (alpha != Variable (1))
712	{
713	bound= pow ((double) p, (double) degree (getMipo(alpha)));
714	bound= pow ((double) bound, (double) k);
715	}
716	else if (GF)
717	{
718	bound= pow ((double) p, (double) getGFDegree());
719	bound= pow ((double) bound, (double) k);
720	}
721	else
722	bound= pow ((double) p, (double) k);
723
724	CanonicalForm random;
725	CanonicalForm deriv_x, gcd_deriv;
726	do
727	{
728	random= 0;
729	// possible overflow if list.length() does not fit into a int
730	if (list.length() >= bound)
731	{
732	fail= true;
733	break;
734	}
735	for (int i= 0; i < k; i++)
736	{
737	if (list.isEmpty())
738	result.append (0);
739	else if (GF)
740	{
741	result.append (genGF.generate());
742	random += result.getLast()*power (x, i);
743	}
744	else if (alpha.level() != 1)
745	{
746	AlgExtRandomF genAlgExt (alpha);
747	result.append (genAlgExt.generate());
748	random += result.getLast()*power (x, i);
749	}
750	else
751	{
752	result.append (genFF.generate());
753	random += result.getLast()*power (x, i);
754	}
755	}
756	if (find (list, random))
757	{
758	result= CFList();
759	continue;
760	}
761	int l= F.level();
762	eval.insert (F);
763	bool bad= false;
764	for (CFListIterator i= result; i.hasItem(); i++, l--)
765	{
766	eval.insert (eval.getFirst()(i.getItem(), l));
767	if (degree (eval.getFirst(), l - 1) != degree (F, l - 1))
768	{
769	if (!find (list, random))
770	list.append (random);
771	result= CFList();
772	eval= CFList();
773	bad= true;
774	break;
775	}
776	}
777
778	if (bad)
779	continue;
780
781	if (degree (eval.getFirst()) != degree (F, 1))
782	{
783	if (!find (list, random))
784	list.append (random);
785	result= CFList();
786	eval= CFList();
787	continue;
788	}
789
790	deriv_x= deriv (eval.getFirst(), x);
791	gcd_deriv= gcd (eval.getFirst(), deriv_x);
792	if (degree (gcd_deriv) > 0)
793	{
794	if (!find (list, random))
795	list.append (random);
796	result= CFList();
797	eval= CFList();
798	continue;
799	}
800	CFListIterator i= eval;
801	i++;
802	CanonicalForm contentx= content (i.getItem(), x);
803	if (degree (contentx) > 0)
804	{
805	if (!find (list, random))
806	list.append (random);
807	result= CFList();
808	eval= CFList();
809	continue;
810	}
811
812	if (list.length() >= bound)
813	{
814	fail= true;
815	break;
816	}
817	} while (find (list, random));
818
819	if (!eval.isEmpty())
820	eval.removeFirst();
821
822	return result;
823	}
824
825	static inline
826	int newMainVariableSearch (CanonicalForm& A, CFList& Aeval, CFList&
827	evaluation, const Variable& alpha, const int lev,
828	CanonicalForm& g
829	)
830	{
831	Variable x= Variable (1);
832	CanonicalForm derivI, buf;
833	bool GF= (CFFactory::gettype() == GaloisFieldDomain);
834	int swapLevel= 0;
835	CFList list;
836	bool fail= false;
837	buf= A;
838	Aeval= CFList();
839	evaluation= CFList();
840	for (int i= lev; i <= A.level(); i++)
841	{
842	derivI= deriv (buf, Variable (i));
843	if (!derivI.isZero())
844	{
845	g= gcd (buf, derivI);
846	if (degree (g) > 0)
847	return -1;
848
849	buf= swapvar (buf, x, Variable (i));
850	Aeval= CFList();
851	evaluation= CFList();
852	fail= false;
853	evaluation= evalPoints (buf, Aeval, alpha, list, GF, fail);
854	if (!fail)
855	{
856	A= buf;
857	swapLevel= i;
858	break;
859	}
860	else
861	buf= A;
862	}
863	}
864	return swapLevel;
865	}
866
867	CanonicalForm lcmContent (const CanonicalForm& A, CFList& contentAi)
868	{
869	int i= A.level();
870	contentAi.append (myContent (A, i));
871	contentAi.append (myContent (A, i - 1));
872	CanonicalForm result= lcm (contentAi.getFirst(), contentAi.getLast());
873	for (i= i - 2; i > 0; i--)
874	{
875	contentAi.append (content (A, i));
876	result= lcm (result, contentAi.getLast());
877	}
878	return result;
879	}
880
881	CFList
882	henselLiftAndEarly (CanonicalForm& A, CFList& MOD, int*& liftBounds, bool&
883	earlySuccess, CFList& earlyFactors, const CFList& Aeval,
884	const CFList& biFactors, const CFList& evaluation,
885	const ExtensionInfo& info)
886	{
887	bool extension= info.isInExtension();
888	CFList bufFactors= biFactors;
889	bufFactors.insert (LC (Aeval.getFirst(), 1));
890
891	sortList (bufFactors, Variable (1));
892
893	CFList diophant;
894	CFArray Pi;
895	int smallFactorDeg= 11; //tunable parameter
896	CFList result;
897	int adaptedLiftBound= 0;
898	int liftBound= liftBounds[1];
899
900	earlySuccess= false;
901	CFList earlyReconstFactors;
902	CFListIterator j= Aeval;
903	j++;
904	CanonicalForm buf= j.getItem();
905	CFMatrix Mat= CFMatrix (liftBound, bufFactors.length() - 1);
906	MOD= CFList (power (Variable (2), liftBounds[0]));
907	if (smallFactorDeg >= liftBound)
908	{
909	result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
910	}
911	else if (smallFactorDeg >= degree (buf) + 1)
912	{
913	liftBounds[1]= degree (buf) + 1;
914	result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
915	if (Aeval.length() == 2)
916	{
917	if (!extension)
918	earlyFactors= earlyFactorDetect
919	(buf, result, adaptedLiftBound, earlySuccess,
920	degree (buf) + 1, MOD, liftBound);
921	else
922	earlyFactors= extEarlyFactorDetect
923	(buf, result, adaptedLiftBound, earlySuccess,
924	info, evaluation, degree
925	(buf) + 1, MOD, liftBound);
926	}
927	else
928	{
929	if (!extension)
930	adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
931	degree (buf) + 1, MOD, liftBound);
932	else
933	adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
934	evaluation, degree (buf) + 1,
935	MOD, liftBound);
936	}
937	if (!earlySuccess)
938	{
939	result.insert (LC (buf, 1));
940	liftBounds[1]= adaptedLiftBound;
941	liftBound= adaptedLiftBound;
942	henselLiftResume (buf, result, degree (buf) + 1, liftBound,
943	Pi, diophant, Mat, MOD);
944	}
945	else
946	liftBounds[1]= adaptedLiftBound;
947	}
948	else if (smallFactorDeg < degree (buf) + 1)
949	{
950	liftBounds[1]= smallFactorDeg;
951	result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
952	if (Aeval.length() == 2)
953	{
954	if (!extension)
955	earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
956	earlySuccess, smallFactorDeg, MOD,
957	liftBound);
958	else
959	earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
960	earlySuccess, info, evaluation,
961	smallFactorDeg, MOD, liftBound);
962	}
963	else
964	{
965	if (!extension)
966	adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
967	smallFactorDeg, MOD, liftBound);
968	else
969	adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
970	evaluation, smallFactorDeg, MOD,
971	liftBound);
972	}
973
974	if (!earlySuccess)
975	{
976	result.insert (LC (buf, 1));
977	henselLiftResume (buf, result, smallFactorDeg, degree (buf) + 1,
978	Pi, diophant, Mat, MOD);
979	if (Aeval.length() == 2)
980	{
981	if (!extension)
982	earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
983	earlySuccess, degree (buf) + 1,
984	MOD, liftBound);
985	else
986	earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
987	earlySuccess, info, evaluation,
988	degree (buf) + 1, MOD,
989	liftBound);
990	}
991	else
992	{
993	if (!extension)
994	adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
995	degree (buf) + 1, MOD,liftBound);
996	else
997	adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess,
998	info, evaluation,
999	degree (buf) + 1, MOD,
1000	liftBound);
1001	}
1002	if (!earlySuccess)
1003	{
1004	result.insert (LC (buf, 1));
1005	liftBounds[1]= adaptedLiftBound;
1006	liftBound= adaptedLiftBound;
1007	henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1008	Pi, diophant, Mat, MOD);
1009	}
1010	else
1011	liftBounds[1]= adaptedLiftBound;
1012	}
1013	else
1014	liftBounds[1]= adaptedLiftBound;
1015	}
1016
1017	MOD.append (power (Variable (3), liftBounds[1]));
1018
1019	if (Aeval.length() > 2)
1020	{
1021	CFListIterator j= Aeval;
1022	j++;
1023	CFList bufEval;
1024	bufEval.append (j.getItem());
1025	j++;
1026	int liftBoundsLength= Aeval.getLast().level() - 1;
1027	for (int i= 2; i <= liftBoundsLength && j.hasItem(); i++, j++)
1028	{
1029	earlySuccess= false;
1030	result.insert (LC (bufEval.getFirst(), 1));
1031	bufEval.append (j.getItem());
1032	liftBound= liftBounds[i];
1033	Mat= CFMatrix (liftBounds[i], result.length() - 1);
1034
1035	buf= j.getItem();
1036	if (smallFactorDeg >= liftBound)
1037	result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1038	liftBounds[i - 1], liftBounds[i]);
1039	else if (smallFactorDeg >= degree (buf) + 1)
1040	{
1041	result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1042	liftBounds[i - 1], degree (buf) + 1);
1043
1044	if (Aeval.length() == i + 1)
1045	{
1046	if (!extension)
1047	earlyFactors= earlyFactorDetect
1048	(buf, result, adaptedLiftBound, earlySuccess,
1049	degree (buf) + 1, MOD, liftBound);
1050	else
1051	earlyFactors= extEarlyFactorDetect
1052	(buf, result, adaptedLiftBound, earlySuccess,
1053	info, evaluation, degree (buf) + 1, MOD, liftBound);
1054	}
1055	else
1056	{
1057	if (!extension)
1058	adaptedLiftBound= liftBoundAdaption
1059	(buf, result, earlySuccess, degree (buf)
1060	+ 1, MOD, liftBound);
1061	else
1062	adaptedLiftBound= extLiftBoundAdaption
1063	(buf, result, earlySuccess, info, evaluation,
1064	degree (buf) + 1, MOD, liftBound);
1065	}
1066
1067	if (!earlySuccess)
1068	{
1069	result.insert (LC (buf, 1));
1070	liftBounds[i]= adaptedLiftBound;
1071	liftBound= adaptedLiftBound;
1072	henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1073	Pi, diophant, Mat, MOD);
1074	}
1075	else
1076	{
1077	liftBounds[i]= adaptedLiftBound;
1078	}
1079	}
1080	else if (smallFactorDeg < degree (buf) + 1)
1081	{
1082	result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1083	liftBounds[i - 1], smallFactorDeg);
1084
1085	if (Aeval.length() == i + 1)
1086	{
1087	if (!extension)
1088	earlyFactors= earlyFactorDetect
1089	(buf, result, adaptedLiftBound, earlySuccess,
1090	smallFactorDeg, MOD, liftBound);
1091	else
1092	earlyFactors= extEarlyFactorDetect
1093	(buf, result, adaptedLiftBound, earlySuccess,
1094	info, evaluation, smallFactorDeg, MOD, liftBound);
1095	}
1096	else
1097	{
1098	if (!extension)
1099	adaptedLiftBound= liftBoundAdaption
1100	(buf, result, earlySuccess,
1101	smallFactorDeg, MOD, liftBound);
1102	else
1103	adaptedLiftBound= extLiftBoundAdaption
1104	(buf, result, earlySuccess, info, evaluation,
1105	smallFactorDeg, MOD, liftBound);
1106	}
1107
1108	if (!earlySuccess)
1109	{
1110	result.insert (LC (buf, 1));
1111	henselLiftResume (buf, result, smallFactorDeg,
1112	degree (buf) + 1, Pi, diophant, Mat, MOD);
1113	if (Aeval.length() == i + 1)
1114	{
1115	if (!extension)
1116	earlyFactors= earlyFactorDetect
1117	(buf, result, adaptedLiftBound, earlySuccess,
1118	degree (buf) + 1, MOD, liftBound);
1119	else
1120	earlyFactors= extEarlyFactorDetect
1121	(buf, result, adaptedLiftBound, earlySuccess,
1122	info, evaluation, degree (buf) + 1, MOD,
1123	liftBound);
1124	}
1125	else
1126	{
1127	if (!extension)
1128	adaptedLiftBound= liftBoundAdaption
1129	(buf, result, earlySuccess, degree
1130	(buf) + 1, MOD, liftBound);
1131	else
1132	adaptedLiftBound= extLiftBoundAdaption
1133	(buf, result, earlySuccess, info, evaluation,
1134	degree (buf) + 1, MOD, liftBound);
1135	}
1136
1137	if (!earlySuccess)
1138	{
1139	result.insert (LC (buf, 1));
1140	liftBounds[i]= adaptedLiftBound;
1141	liftBound= adaptedLiftBound;
1142	henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1143	Pi, diophant, Mat, MOD);
1144	}
1145	else
1146	liftBounds[i]= adaptedLiftBound;
1147	}
1148	else
1149	liftBounds[i]= adaptedLiftBound;
1150	}
1151	MOD.append (power (Variable (i + 2), liftBounds[i]));
1152	bufEval.removeFirst();
1153	}
1154	bufFactors= result;
1155	}
1156	else
1157	bufFactors= result;
1158
1159	if (earlySuccess)
1160	A= buf;
1161	return result;
1162	}
1163
1164	CFList
1165	leadingCoeffReconstruction (const CanonicalForm& F, const CFList& factors,
1166	const CFList& M)
1167	{
1168	CanonicalForm quot, buf= F;
1169	CanonicalForm LCBuf= LC (buf, 1);
1170
1171	CFList result;
1172
1173	CanonicalForm tmp;
1174	for (CFListIterator i= factors; i.hasItem(); i++)
1175	{
1176	tmp= i.getItem();
1177	tmp= mulMod (tmp, LCBuf, M);
1178	tmp= tmp/content (tmp, 1);
1179	if (fdivides (tmp, buf, quot))
1180	{
1181	buf= quot;
1182	result.append (tmp);
1183	LCBuf= LC (buf, 1);
1184	}
1185	else //no one-to-one correspondence
1186	return CFList();
1187	}
1188
1189	return result;
1190	}
1191
1192	void
1193	gcdFreeBasis (CFFList& factors1, CFFList& factors2)
1194	{
1195	CanonicalForm g;
1196	int k= factors1.length();
1197	int l= factors2.length();
1198	int n= 1;
1199	int m;
1200	CFFListIterator j;
1201	for (CFFListIterator i= factors1; (n < k && i.hasItem()); i++, n++)
1202	{
1203	m= 1;
1204	for (j= factors2; (m < l && j.hasItem()); j++, m++)
1205	{
1206	g= gcd (i.getItem().factor(), j.getItem().factor());
1207	if (degree (g) > 0)
1208	{
1209	j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
1210	i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp());
1211	factors1.append (CFFactor (g, i.getItem().exp()));
1212	factors2.append (CFFactor (g, j.getItem().exp()));
1213	}
1214	}
1215	}
1216	}
1217
1218	CFList
1219	distributeContent (const CFList& L, const CFList* differentSecondVarFactors,
1220	int length
1221	)
1222	{
1223	CFList l= L;
1224	CanonicalForm content= l.getFirst();
1225
1226	if (content.inCoeffDomain())
1227	return l;
1228
1229	if (l.length() == 1)
1230	{
1231	CFList result;
1232	for (int i= 0; i < length; i++)
1233	{
1234	if (differentSecondVarFactors[i].isEmpty())
1235	continue;
1236	if (result.isEmpty())
1237	{
1238	result= differentSecondVarFactors[i];
1239	for (CFListIterator iter= result; iter.hasItem(); iter++)
1240	content /= iter.getItem();
1241	}
1242	else
1243	{
1244	CFListIterator iter1= result;
1245	for (CFListIterator iter2= differentSecondVarFactors[i]; iter2.hasItem();
1246	iter2++, iter1++)
1247	{
1248	iter1.getItem() *= iter2.getItem();
1249	content /= iter2.getItem();
1250	}
1251	}
1252	}
1253	result.insert (content);
1254	return result;
1255	}
1256
1257	Variable v;
1258	CFListIterator iter1;
1259	CanonicalForm tmp, g;
1260	for (int i= 0; i < length; i++)
1261	{
1262	if (differentSecondVarFactors[i].isEmpty())
1263	continue;
1264	iter1= l;
1265	iter1++;
1266
1267	v= Variable (i + 3);
1268	for (CFListIterator iter2= differentSecondVarFactors[i]; iter2.hasItem();
1269	iter2++, iter1++)
1270	{
1271	if (degree (iter2.getItem(),v) == degree (iter1.getItem(),v))
1272	continue;
1273	tmp= iter1.getItem();
1274	for (int j= tmp.level(); j > 1; j--)
1275	{
1276	if (j == i + 3)
1277	continue;
1278	tmp= tmp (0, j);
1279	}
1280	g= gcd (iter2.getItem(), content);
1281	if (degree (g) > 0)
1282	{
1283	iter2.getItem() /= tmp;
1284	content /= g;
1285	iter1.getItem() *= g;
1286	}
1287	}
1288	}
1289
1290	l.removeFirst();
1291	l.insert (content);
1292	return l;
1293	}
1294
1295	CFList evaluateAtZero (const CanonicalForm& F)
1296	{
1297	CFList result;
1298	CanonicalForm buf= F;
1299	result.insert (buf);
1300	for (int i= F.level(); i > 2; i--)
1301	{
1302	buf= buf (0, i);
1303	result.insert (buf);
1304	}
1305	return result;
1306	}
1307
1308	int
1309	testFactors (const CanonicalForm& G, const CFList& uniFactors,
1310	const Variable& alpha, CanonicalForm& sqrfPartF, CFList& factors,
1311	CFFList*& bufSqrfFactors, CFList& evalSqrfPartF)
1312	{
1313	CanonicalForm tmp;
1314	CFListIterator j;
1315	for (CFListIterator i= uniFactors; i.hasItem(); i++)
1316	{
1317	tmp= i.getItem();
1318	if (i.hasItem())
1319	i++;
1320	else
1321	break;
1322	for (j= i; j.hasItem(); j++)
1323	{
1324	if (tmp == j.getItem())
1325	return 0;
1326	}
1327	}
1328
1329	CanonicalForm F= G;
1330	CFFList sqrfFactorization= squarefreeFactorization (F, alpha);
1331
1332	sqrfPartF= 1;
1333	for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
1334	sqrfPartF *= i.getItem().factor();
1335
1336	evalSqrfPartF= evaluateAtZero (sqrfPartF);
1337
1338	CanonicalForm test= evalSqrfPartF.getFirst() (0, 2);
1339
1340	if (degree (test) != degree (sqrfPartF, 1))
1341	return 0;
1342
1343	CFFList sqrfFactors;
1344	CFList tmp2;
1345	int k= 0;
1346	factors= uniFactors;
1347	CFFListIterator iter;
1348	for (CFListIterator i= factors; i.hasItem(); i++, k++)
1349	{
1350	tmp= 1;
1351	sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
1352
1353	for (iter= sqrfFactors; iter.hasItem(); iter++)
1354	{
1355	tmp2.append (iter.getItem().factor());
1356	tmp *= iter.getItem().factor();
1357	}
1358	i.getItem()= tmp/Lc(tmp);
1359	bufSqrfFactors [k]= sqrfFactors;
1360	}
1361
1362	for (int i= 0; i < factors.length() - 1; i++)
1363	{
1364	for (k= i + 1; k < factors.length(); k++)
1365	{
1366	gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
1367	}
1368	}
1369
1370	factors= CFList();
1371	for (int i= 0; i < uniFactors.length(); i++)
1372	{
1373	if (i == 0)
1374	{
1375	for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1376	{
1377	iter.getItem()= CFFactor (iter.getItem().factor()/
1378	Lc (iter.getItem().factor()),
1379	iter.getItem().exp());
1380	factors.append (iter.getItem().factor());
1381	}
1382	}
1383	else
1384	{
1385	for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1386	{
1387	iter.getItem()= CFFactor (iter.getItem().factor()/
1388	Lc (iter.getItem().factor()),
1389	iter.getItem().exp());
1390	if (!find (factors, iter.getItem().factor()))
1391	factors.append (iter.getItem().factor());
1392	}
1393	}
1394	}
1395
1396	test= prod (factors);
1397	tmp= evalSqrfPartF.getFirst() (0,2);
1398	if (test/Lc (test) != tmp/Lc (tmp))
1399	return 0;
1400	else
1401	return 1;
1402	}
1403
1404	CFList
1405	precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
1406	const Variable& alpha, const CFList& evaluation,
1407	CFList* & differentSecondVarLCs, int length,
1408	Variable& y
1409	)
1410	{
1411	y= Variable (1);
1412	if (LCF.inCoeffDomain())
1413	{
1414	CFList result;
1415	for (int i= 1; i <= LCFFactors.length() + 1; i++)
1416	result.append (1);
1417	return result;
1418	}
1419
1420	CFMap N;
1421	CanonicalForm F= compress (LCF, N);
1422	if (LCF.isUnivariate())
1423	{
1424	CFList result;
1425	int LCFLevel= LCF.level();
1426	bool found= false;
1427	if (LCFLevel == 2)
1428	{
1429	//bivariate leading coefficients are already the true leading coefficients
1430	result= LCFFactors;
1431	Variable v= Variable (LCF.mvar());
1432	CanonicalForm bla= 1;
1433	for (CFListIterator i= result; i.hasItem(); i++)
1434	{
1435	i.getItem()= i.getItem() (v+evaluation.getLast(), v);
1436	bla *= Lc (i.getItem());
1437	}
1438	found= true;
1439	}
1440	else
1441	{
1442	CFListIterator j;
1443	for (int i= 0; i < length; i++)
1444	{
1445	for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
1446	{
1447	if (j.getItem().level() == LCFLevel)
1448	{
1449	found= true;
1450	break;
1451	}
1452	}
1453	if (found)
1454	{
1455	result= differentSecondVarLCs [i];
1456	break;
1457	}
1458	}
1459	if (!found)
1460	result= LCFFactors;
1461	}
1462	if (found)
1463	result.insert (Lc (LCF));
1464	else
1465	result.append (LCF);
1466	return result;
1467	}
1468
1469	CFList factors= LCFFactors;
1470
1471	CFMap dummy;
1472	for (CFListIterator i= factors; i.hasItem(); i++)
1473	{
1474	i.getItem()= compress (i.getItem(), dummy);
1475	i.getItem()= i.getItem() (Variable (1) + evaluation.getLast(), Variable (1));
1476	}
1477
1478	CanonicalForm sqrfPartF;
1479	CFFList * bufSqrfFactors= new CFFList [factors.length()];
1480	CFList evalSqrfPartF;
1481	CFList bufFactors;
1482	int pass= testFactors (F, factors, alpha, sqrfPartF,
1483	bufFactors, bufSqrfFactors, evalSqrfPartF);
1484
1485	bool foundDifferent= false;
1486	Variable z;
1487	Variable x= y;
1488	int j= 0;
1489	if (!pass)
1490	{
1491	int lev;
1492	// LCF is non-constant here
1493	for (int i= 1; i <= LCF.level(); i++)
1494	{
1495	if(degree (LCF, i) > 0)
1496	{
1497	lev= i - 1;
1498	break;
1499	}
1500	}
1501	CFListIterator iter;
1502	CFList bufBufFactors;
1503	CanonicalForm bufF;
1504	for (int i= 0; i < length; i++)
1505	{
1506	if (!differentSecondVarLCs [i].isEmpty())
1507	{
1508	bool allConstant= true;
1509	for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
1510	{
1511	if (!iter.getItem().inCoeffDomain())
1512	{
1513	allConstant= false;
1514	y= Variable (iter.getItem().level());
1515	}
1516	}
1517	if (allConstant)
1518	continue;
1519
1520	bufFactors= differentSecondVarLCs [i];
1521	for (iter= bufFactors; iter.hasItem(); iter++)
1522	iter.getItem()= swapvar (iter.getItem(), x, y);
1523	bufF= F;
1524	z= Variable (y.level() - lev);
1525	bufF= swapvar (bufF, x, z);
1526	bufBufFactors= bufFactors;
1527	pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
1528	bufSqrfFactors, evalSqrfPartF);
1529	if (pass)
1530	{
1531	foundDifferent= true;
1532	F= bufF;
1533	CFList l= factors;
1534	for (iter= l; iter.hasItem(); iter++)
1535	iter.getItem()= swapvar (iter.getItem(), x, y);
1536	differentSecondVarLCs [i]= l;
1537	j= i;
1538	break;
1539	}
1540	if (!pass && i == length - 1)
1541	{
1542	CFList result;
1543	result.append (LCF);
1544	for (int k= 1; k <= factors.length(); k++)
1545	result.append (LCF);
1546	y= Variable (1);
1547	return result;
1548	}
1549	}
1550	}
1551	}
1552	if (!pass)
1553	{
1554	CFList result;
1555	result.append (LCF);
1556	for (int k= 1; k <= factors.length(); k++)
1557	result.append (LCF);
1558	y= Variable (1);
1559	return result;
1560	}
1561	else
1562	factors= bufFactors;
1563
1564	int liftBound= degree (sqrfPartF,2) + degree (LC (sqrfPartF, 1), 2) + 1;
1565
1566	int* liftBounds= liftingBounds (sqrfPartF, liftBound);
1567
1568	bufFactors= factors;
1569	factors.insert (LC (evalSqrfPartF.getFirst(), 1));
1570	CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
1571	CFArray Pi;
1572	CFList diophant;
1573	henselLift12 (evalSqrfPartF.getFirst(), factors, liftBound, Pi, diophant, M, false);
1574
1575	if (sqrfPartF.level() > 2)
1576	factors= henselLift (evalSqrfPartF, factors, liftBounds,
1577	sqrfPartF.level() - 1, false);
1578
1579	CFList MOD;
1580	for (int i= 0; i < sqrfPartF.level() - 1; i++)
1581	MOD.append (power (Variable (i + 2), liftBounds [i]));
1582
1583	CFList interMedResult= leadingCoeffReconstruction (evalSqrfPartF.getLast(),
1584	factors, MOD);
1585
1586	CFList result;
1587	CFFListIterator k;
1588	for (int i= 0; i < LCFFactors.length(); i++)
1589	{
1590	CanonicalForm tmp= 1;
1591	for (k= bufSqrfFactors[i]; k.hasItem(); k++)
1592	{
1593	int pos= findItem (bufFactors, k.getItem().factor());
1594	if (pos)
1595	tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
1596	}
1597	result.append (tmp);
1598	}
1599
1600	for (CFListIterator i= result; i.hasItem(); i++)
1601	{
1602	F /= i.getItem();
1603	if (foundDifferent)
1604	i.getItem()= swapvar (i.getItem(), x, z);
1605	i.getItem()= N (i.getItem());
1606	}
1607
1608	if (foundDifferent)
1609	{
1610	CFList l= differentSecondVarLCs [j];
1611	for (CFListIterator i= l; i.hasItem(); i++)
1612	i.getItem()= swapvar (i.getItem(), y, z);
1613	differentSecondVarLCs [j]= l;
1614	F= swapvar (F, x, z);
1615	}
1616
1617	result.insert (N (F));
1618
1619	result= distributeContent (result, differentSecondVarLCs, length);
1620
1621	if (!result.getFirst().inCoeffDomain())
1622	{
1623	CFListIterator i= result;
1624	CanonicalForm tmp;
1625	if (foundDifferent)
1626	i.getItem()= swapvar (i.getItem(), Variable (2), y);
1627
1628	tmp= i.getItem();
1629
1630	i++;
1631	for (; i.hasItem(); i++)
1632	{
1633	if (foundDifferent)
1634	i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
1635	else
1636	i.getItem() *= tmp;
1637	}
1638	}
1639	else
1640	y= Variable (1);
1641
1642	return result;
1643	}
1644
1645	void
1646	evaluationWRTDifferentSecondVars (CFList*& Aeval, const CFList& evaluation,
1647	const CanonicalForm& A)
1648	{
1649	CanonicalForm tmp;
1650	CFList tmp2;
1651	CFListIterator iter;
1652	for (int i= A.level(); i > 2; i--)
1653	{
1654	tmp= A;
1655	tmp2= CFList();
1656	iter= evaluation;
1657	bool preserveDegree= true;
1658	for (int j= A.level(); j > 1; j--, iter++)
1659	{
1660	if (j == i)
1661	continue;
1662	else
1663	{
1664	tmp= tmp (iter.getItem(), j);
1665	tmp2.insert (tmp);
1666	if ((degree (tmp, i) != degree (A, i)) \|\|
1667	(degree (tmp, 1) != degree (A, 1)))
1668	{
1669	preserveDegree= false;
1670	break;
1671	}
1672	if (!content(tmp).inCoeffDomain() \|\| !content(tmp,1).inCoeffDomain())
1673	{
1674	preserveDegree= false;
1675	break;
1676	}
1677	}
1678	}
1679	if (preserveDegree)
1680	Aeval [i - 3]= tmp2;
1681	else
1682	Aeval [i - 3]= CFList();
1683	}
1684	}
1685
1686	static inline
1687	CanonicalForm prodEval (const CFList& l, const CanonicalForm& evalPoint,
1688	const Variable& v)
1689	{
1690	CanonicalForm result= 1;
1691	for (CFListIterator i= l; i.hasItem(); i++)
1692	result *= i.getItem() (evalPoint, v);
1693	return result;
1694	}
1695
1696	//recombine bivariate factors in case one bivariate factorization yields less
1697	// factors than the other
1698	CFList
1699	recombination (const CFList& factors1, const CFList& factors2, int s, int thres,
1700	const CanonicalForm& evalPoint, const Variable& x)
1701	{
1702	CFList T, S;
1703
1704	T= factors1;
1705	CFList result;
1706	CanonicalForm buf;
1707	int * v= new int [T.length()];
1708	for (int i= 0; i < T.length(); i++)
1709	v[i]= 0;
1710	bool nosubset= false;
1711	CFArray TT;
1712	TT= copy (factors1);
1713	while (T.length() >= 2*s && s <= thres)
1714	{
1715	while (nosubset == false)
1716	{
1717	if (T.length() == s)
1718	{
1719	delete [] v;
1720	result.append (prod (T));
1721	return result;
1722	}
1723	S= subset (v, s, TT, nosubset);
1724	if (nosubset) break;
1725	buf= prodEval (S, evalPoint, x);
1726	buf /= Lc (buf);
1727	if (find (factors2, buf))
1728	{
1729	T= Difference (T, S);
1730	result.append (prod (S));
1731	TT= copy (T);
1732	indexUpdate (v, s, T.length(), nosubset);
1733	if (nosubset) break;
1734	}
1735	}
1736	s++;
1737	if (T.length() < 2*s \|\| T.length() == s)
1738	{
1739	delete [] v;
1740	result.append (prod (T));
1741	return result;
1742	}
1743	for (int i= 0; i < T.length(); i++)
1744	v[i]= 0;
1745	nosubset= false;
1746	}
1747
1748	delete [] v;
1749	if (T.length() < 2*s)
1750	{
1751	result.append (prod (T));
1752	return result;
1753	}
1754
1755	return result;
1756	}
1757
1758	void
1759	factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
1760	const ExtensionInfo& info,
1761	int& minFactorsLength, bool& irred)
1762	{
1763	Variable x= Variable (1);
1764	minFactorsLength= 0;
1765	irred= false;
1766	CFList factors;
1767	Variable v;
1768	for (int j= 0; j < A.level() - 2; j++)
1769	{
1770	if (!Aeval[j].isEmpty())
1771	{
1772	v= Variable (Aeval[j].getFirst().level());
1773	if (CFFactory::gettype() == GaloisFieldDomain)
1774	factors= GFBiSqrfFactorize (Aeval[j].getFirst());
1775	else if (info.getAlpha().level() == 1)
1776	factors= FpBiSqrfFactorize (Aeval[j].getFirst());
1777	else
1778	factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
1779
1780	factors.removeFirst();
1781	if (minFactorsLength == 0)
1782	minFactorsLength= factors.length();
1783	else
1784	minFactorsLength= tmin (minFactorsLength, factors.length());
1785
1786	if (factors.length() == 1)
1787	{
1788	irred= true;
1789	return;
1790	}
1791	sortList (factors, x);
1792	Aeval [j]= factors;
1793	}
1794	}
1795	}
1796
1797	void getLeadingCoeffs (const CanonicalForm& A, CFList*& Aeval,
1798	const CFList& uniFactors, const CFList& evaluation
1799	)
1800	{
1801	CanonicalForm evalPoint;
1802	int i;
1803	CFListIterator iter, iter2;
1804	Variable v;
1805	CFList l, LCs;
1806	CanonicalForm buf;
1807	for (int j= 0; j < A.level() - 2; j++)
1808	{
1809	if (!Aeval[j].isEmpty())
1810	{
1811	i= A.level();
1812	for (iter= evaluation; iter.hasItem(); iter++, i--)
1813	{
1814	if (i == Aeval[j].getFirst().level())
1815	{
1816	evalPoint= iter.getItem();
1817	break;
1818	}
1819	}
1820
1821	v= Variable (i);
1822	if (Aeval[j].length() > uniFactors.length())
1823	Aeval[j]= recombination (Aeval[j], uniFactors, 1,
1824	Aeval[j].length() - uniFactors.length() + 1,
1825	evalPoint, v);
1826
1827	l= CFList();
1828	for (iter= uniFactors; iter.hasItem(); iter++)
1829	{
1830	for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
1831	{
1832	buf= mod (iter2.getItem(), v - evalPoint);
1833	buf /= Lc (buf);
1834	if (iter.getItem() == buf)
1835	{
1836	l.append (iter2.getItem());
1837	break;
1838	}
1839	}
1840	}
1841	Aeval [j]= l;
1842
1843	LCs= CFList();
1844	for (iter= Aeval[j]; iter.hasItem(); iter++)
1845	LCs.append (LC (iter.getItem() (v + evalPoint, v), 1));
1846	normalize (LCs);
1847	Aeval[j]= LCs;
1848	}
1849	}
1850	}
1851
1852	CFList
1853	buildUniFactors (const CFList& biFactors, const CanonicalForm& evalPoint,
1854	const Variable& y)
1855	{
1856	CFList result;
1857	CanonicalForm tmp;
1858	for (CFListIterator i= biFactors; i.hasItem(); i++)
1859	{
1860	tmp= mod (i.getItem(), y - evalPoint);
1861	tmp /= Lc (tmp);
1862	result.append (tmp);
1863	}
1864	return result;
1865	}
1866
1867	void refineBiFactors (const CanonicalForm& A, CFList& biFactors,
1868	CFList* const& Aeval, const CFList& evaluation,
1869	int minFactorsLength)
1870	{
1871	CFListIterator iter;
1872	CanonicalForm evalPoint;
1873	int i;
1874	Variable v;
1875	Variable y= Variable (2);
1876	CFList list;
1877	for (int j= 0; j < A.level() - 2; j++)
1878	{
1879	if (Aeval[j].length() == minFactorsLength)
1880	{
1881	i= A.level();
1882
1883	for (iter= evaluation; iter.hasItem(); iter++, i--)
1884	{
1885	if (i == Aeval[j].getFirst().level())
1886	{
1887	evalPoint= iter.getItem();
1888	break;
1889	}
1890	}
1891
1892	v= Variable (i);
1893	list= buildUniFactors (Aeval[j], evalPoint, v);
1894
1895	biFactors= recombination (biFactors, list, 1,
1896	biFactors.length() - list.length() + 1,
1897	evaluation.getLast(), y);
1898	return;
1899	}
1900	}
1901	}
1902
1903	void prepareLeadingCoeffs (CFList*& LCs, int n, const CFList& leadingCoeffs,
1904	const CFList& biFactors)
1905	{
1906	CFList l= leadingCoeffs;
1907	LCs [n-3]= l;
1908	CFListIterator j;
1909	for (int i= n - 1; i > 2; i--)
1910	{
1911	for (j= l; j.hasItem(); j++)
1912	j.getItem()= j.getItem() (0, i + 1);
1913	LCs [i - 3]= l;
1914	}
1915	l= LCs [0];
1916	for (CFListIterator i= l; i.hasItem(); i++)
1917	i.getItem()= i.getItem() (0, 3);
1918	CFListIterator ii= biFactors;
1919	CFList normalizeFactor;
1920	for (CFListIterator i= l; i.hasItem(); i++, ii++)
1921	normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
1922	for (int i= 0; i < n-2; i++)
1923	{
1924	ii= normalizeFactor;
1925	for (j= LCs [i]; j.hasItem(); j++, ii++)
1926	j.getItem() *= ii.getItem();
1927	}
1928	}
1929
1930	CFList recoverFactors (const CanonicalForm& F, const CFList& factors)
1931	{
1932	CFList result;
1933	CanonicalForm tmp;
1934	for (CFListIterator i= factors; i.hasItem(); i++)
1935	{
1936	tmp= i.getItem() / content (i.getItem(), 1);
1937	if (fdivides (tmp, F))
1938	result.append (tmp);
1939	}
1940	return result;
1941	}
1942
1943	CFList
1944	extNonMonicFactorRecombination (const CFList& factors, const CanonicalForm& F,
1945	const ExtensionInfo& info,
1946	const CFList& evaluation)
1947	{
1948	Variable alpha= info.getAlpha();
1949	Variable beta= info.getBeta();
1950	CanonicalForm gamma= info.getGamma();
1951	CanonicalForm delta= info.getDelta();
1952	int k= info.getGFDegree();
1953	CFList source, dest;
1954
1955	int degMipoBeta= 1;
1956	if (!k && beta != Variable(1))
1957	degMipoBeta= degree (getMipo (beta));
1958
1959	CFList T, S;
1960	T= factors;
1961	int s= 1;
1962	CFList result;
1963	CanonicalForm quot, buf= F;
1964
1965	CanonicalForm g;
1966	CanonicalForm buf2;
1967	int * v= new int [T.length()];
1968	for (int i= 0; i < T.length(); i++)
1969	v[i]= 0;
1970	bool noSubset= false;
1971	CFArray TT;
1972	TT= copy (factors);
1973	bool recombination= false;
1974	bool trueFactor= false;
1975	while (T.length() >= 2*s)
1976	{
1977	while (noSubset == false)
1978	{
1979	if (T.length() == s)
1980	{
1981	delete [] v;
1982	if (recombination)
1983	{
1984	g= prod (T);
1985	T.removeFirst();
1986	result.append (g/myContent (g));
1987	g= reverseShift (g, evaluation);
1988	g /= Lc (g);
1989	appendTestMapDown (result, g, info, source, dest);
1990	return result;
1991	}
1992	else
1993	{
1994	buf= reverseShift (buf, evaluation);
1995	return CFList (buf);
1996	}
1997	}
1998
1999	S= subset (v, s, TT, noSubset);
2000	if (noSubset) break;
2001
2002	g= prod (S);
2003	g /= myContent (g);
2004	if (fdivides (g, buf, quot))
2005	{
2006	buf2= reverseShift (g, evaluation);
2007	buf2 /= Lc (buf2);
2008	if (!k && beta == Variable (1))
2009	{
2010	if (degree (buf2, alpha) < degMipoBeta)
2011	{
2012	appendTestMapDown (result, buf2, info, source, dest);
2013	buf= quot;
2014	recombination= true;
2015	trueFactor= true;
2016	}
2017	}
2018	else
2019	{
2020	if (!isInExtension (buf2, gamma, k, delta, source, dest))
2021	{
2022	appendTestMapDown (result, buf2, info, source, dest);
2023	buf= quot;
2024	recombination= true;
2025	trueFactor= true;
2026	}
2027	}
2028	if (trueFactor)
2029	{
2030	T= Difference (T, S);
2031
2032	if (T.length() < 2*s \|\| T.length() == s)
2033	{
2034	delete [] v;
2035	buf= reverseShift (buf, evaluation);
2036	buf /= Lc (buf);
2037	appendTestMapDown (result, buf, info, source, dest);
2038	return result;
2039	}
2040	trueFactor= false;
2041	TT= copy (T);
2042	indexUpdate (v, s, T.length(), noSubset);
2043	if (noSubset) break;
2044	}
2045	}
2046	}
2047	s++;
2048	if (T.length() < 2*s \|\| T.length() == s)
2049	{
2050	delete [] v;
2051	buf= reverseShift (buf, evaluation);
2052	appendTestMapDown (result, buf, info, source, dest);
2053	return result;
2054	}
2055	for (int i= 0; i < T.length(); i++)
2056	v[i]= 0;
2057	noSubset= false;
2058	}
2059	if (T.length() < 2*s)
2060	{
2061	buf= reverseShift (F, evaluation);
2062	appendMapDown (result, buf, info, source, dest);
2063	}
2064
2065	delete [] v;
2066	return result;
2067	}
2068
2069	CFList
2070	extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
2071
2072	CFList
2073	multiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
2074	{
2075
2076	if (F.inCoeffDomain())
2077	return CFList (F);
2078
2079	// compress and find main Variable
2080	CFMap N;
2081	CanonicalForm A= myCompress (F, N);
2082
2083	A /= Lc (A); // make monic
2084
2085	Variable alpha= info.getAlpha();
2086	Variable beta= info.getBeta();
2087	CanonicalForm gamma= info.getGamma();
2088	CanonicalForm delta= info.getDelta();
2089	bool extension= info.isInExtension();
2090	bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2091	//univariate case
2092	if (F.isUnivariate())
2093	{
2094	if (extension == false)
2095	return uniFactorizer (F, alpha, GF);
2096	else
2097	{
2098	CFList source, dest;
2099	A= mapDown (F, info, source, dest);
2100	return uniFactorizer (A, beta, GF);
2101	}
2102	}
2103
2104	//bivariate case
2105	if (A.level() == 2)
2106	{
2107	CFList buf= biFactorize (F, info);
2108	return buf;
2109	}
2110
2111	Variable x= Variable (1);
2112	Variable y= Variable (2);
2113
2114	// remove content
2115	CFList contentAi;
2116	CanonicalForm lcmCont= lcmContent (A, contentAi);
2117	A /= lcmCont;
2118
2119	// trivial after content removal
2120	CFList contentAFactors;
2121	if (A.inCoeffDomain())
2122	{
2123	for (CFListIterator i= contentAi; i.hasItem(); i++)
2124	{
2125	if (i.getItem().inCoeffDomain())
2126	continue;
2127	else
2128	{
2129	lcmCont /= i.getItem();
2130	contentAFactors=
2131	Union (multiFactorize (lcmCont, info),
2132	multiFactorize (i.getItem(), info));
2133	break;
2134	}
2135	}
2136	decompress (contentAFactors, N);
2137	normalize (contentAFactors);
2138	return contentAFactors;
2139	}
2140
2141	// factorize content
2142	contentAFactors= multiFactorize (lcmCont, info);
2143
2144	// univariate after content removal
2145	CFList factors;
2146	if (A.isUnivariate ())
2147	{
2148	factors= uniFactorizer (A, alpha, GF);
2149	append (factors, contentAFactors);
2150	decompress (factors, N);
2151	return factors;
2152	}
2153
2154	// check main variable
2155	int swapLevel= 0;
2156	CanonicalForm derivZ;
2157	CanonicalForm gcdDerivZ;
2158	CanonicalForm bufA= A;
2159	Variable z;
2160	for (int i= 1; i <= A.level(); i++)
2161	{
2162	z= Variable (i);
2163	derivZ= deriv (bufA, z);
2164	if (derivZ.isZero())
2165	{
2166	if (i == 1)
2167	swapLevel= 1;
2168	else
2169	continue;
2170	}
2171	else
2172	{
2173	if (swapLevel == 1)
2174	{
2175	swapLevel= i;
2176	bufA= swapvar (A, x, z);
2177	}
2178	gcdDerivZ= gcd (bufA, derivZ);
2179	if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
2180	{
2181	CanonicalForm g= bufA/gcdDerivZ;
2182	CFList factorsG=
2183	Union (multiFactorize (g, info),
2184	multiFactorize (gcdDerivZ, info));
2185	appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2186	normalize (factorsG);
2187	return factorsG;
2188	}
2189	else
2190	{
2191	A= bufA;
2192	break;
2193	}
2194	}
2195	}
2196
2197
2198	CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
2199	bool fail= false;
2200	int swapLevel2= 0;
2201	int level;
2202	int factorNums= 3;
2203	CanonicalForm bivarEval;
2204	CFList biFactors, bufBiFactors;
2205	CanonicalForm evalPoly;
2206	int lift, bufLift;
2207	double logarithm= (double) ilog2 (totaldegree (A));
2208	logarithm /= log2exp;
2209	logarithm= ceil (logarithm);
2210	if (factorNums < (int) logarithm)
2211	factorNums= (int) logarithm;
2212	CFList* bufAeval2= new CFList [A.level() - 2];
2213	CFList* Aeval2= new CFList [A.level() - 2];
2214	int counter;
2215	int differentSecondVar= 0;
2216	// several bivariate factorizations
2217	for (int i= 0; i < factorNums; i++)
2218	{
2219	counter= 0;
2220	bufA= A;
2221	bufAeval= CFList();
2222	bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
2223	evalPoly= 0;
2224
2225	if (fail && (i == 0))
2226	{
2227	if (!swapLevel)
2228	level= 2;
2229	else
2230	level= swapLevel + 1;
2231
2232	CanonicalForm g;
2233	swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
2234
2235	if (!swapLevel2) // need to pass to an extension
2236	{
2237	factors= extFactorize (A, info);
2238	appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
2239	normalize (factors);
2240	delete [] bufAeval2;
2241	delete [] Aeval2;
2242	return factors;
2243	}
2244	else
2245	{
2246	if (swapLevel2 == -1)
2247	{
2248	CFList factorsG=
2249	Union (multiFactorize (g, info),
2250	multiFactorize (A/g, info));
2251	appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
2252	normalize (factorsG);
2253	delete [] bufAeval2;
2254	delete [] Aeval2;
2255	return factorsG;
2256	}
2257	fail= false;
2258	bufAeval= Aeval;
2259	bufA= A;
2260	bufEvaluation= evaluation;
2261	}
2262	}
2263	else if (fail && (i > 0))
2264	break;
2265
2266	bivarEval= bufEvaluation.getLast();
2267
2268	evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
2269
2270	for (int j= 0; j < A.level() - 1; j++)
2271	{
2272	if (!bufAeval2[j].isEmpty())
2273	counter++;
2274	}
2275
2276	bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
2277
2278	TIMING_START (fac_bi_factorizer);
2279	if (!GF && alpha.level() == 1)
2280	bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
2281	else if (GF)
2282	bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
2283	else
2284	bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
2285	TIMING_END_AND_PRINT (fac_bi_factorizer,
2286	"time for bivariate factorization: ");
2287	bufBiFactors.removeFirst();
2288
2289	if (bufBiFactors.length() == 1)
2290	{
2291	if (extension)
2292	{
2293	CFList source, dest;
2294	A= mapDown (A, info, source, dest);
2295	}
2296	factors.append (A);
2297	appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2298	swapLevel2, x);
2299	normalize (factors);
2300	delete [] bufAeval2;
2301	delete [] Aeval2;
2302	return factors;
2303	}
2304
2305	if (i == 0)
2306	{
2307	Aeval= bufAeval;
2308	evaluation= bufEvaluation;
2309	biFactors= bufBiFactors;
2310	lift= bufLift;
2311	for (int j= 0; j < A.level() - 2; j++)
2312	Aeval2 [j]= bufAeval2 [j];
2313	differentSecondVar= counter;
2314	}
2315	else
2316	{
2317	if (bufBiFactors.length() < biFactors.length() \|\|
2318	((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) \|\|
2319	counter > differentSecondVar)
2320	{
2321	Aeval= bufAeval;
2322	evaluation= bufEvaluation;
2323	biFactors= bufBiFactors;
2324	lift= bufLift;
2325	for (int j= 0; j < A.level() - 2; j++)
2326	Aeval2 [j]= bufAeval2 [j];
2327	differentSecondVar= counter;
2328	}
2329	}
2330	int k= 0;
2331	for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
2332	evalPoly += j.getItem()*power (x, k);
2333	list.append (evalPoly);
2334	}
2335
2336	delete [] bufAeval2;
2337
2338	sortList (biFactors, x);
2339
2340	int minFactorsLength;
2341	bool irred= false;
2342	factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength, irred);
2343
2344	if (irred)
2345	{
2346	if (extension)
2347	{
2348	CFList source, dest;
2349	A= mapDown (A, info, source, dest);
2350	}
2351	factors.append (A);
2352	appendSwapDecompress (factors, contentAFactors, N, swapLevel,
2353	swapLevel2, x);
2354	normalize (factors);
2355	delete [] Aeval2;
2356	return factors;
2357	}
2358
2359	if (minFactorsLength == 0)
2360	minFactorsLength= biFactors.length();
2361	else if (biFactors.length() > minFactorsLength)
2362	refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
2363
2364	CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
2365
2366	CFList * oldAeval= new CFList [A.level() - 2]; //TODO use bufAeval2 for this
2367	for (int i= 0; i < A.level() - 2; i++)
2368	oldAeval[i]= Aeval2[i];
2369
2370	getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
2371
2372	CFList biFactorsLCs;
2373	for (CFListIterator i= biFactors; i.hasItem(); i++)
2374	biFactorsLCs.append (LC (i.getItem(), 1));
2375
2376
2377	//shifting to zero
2378	A= shift2Zero (A, Aeval, evaluation);
2379
2380	CanonicalForm hh= Lc (Aeval.getFirst());
2381
2382	for (CFListIterator i= Aeval; i.hasItem(); i++)
2383	i.getItem() /= hh;
2384
2385	A /= hh;
2386
2387	Variable v;
2388	CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
2389	evaluation, Aeval2, A.level() - 2, v);
2390
2391	if (v.level() != 1)
2392	{
2393	A= swapvar (A, y, v);
2394	for (int i= 0; i < A.level() - 2; i++)
2395	{
2396	if (oldAeval[i].isEmpty())
2397	continue;
2398	if (oldAeval[i].getFirst().level() == v.level())
2399	{
2400	biFactors= CFList();
2401	for (CFListIterator iter= oldAeval [i]; iter.hasItem(); iter++)
2402	biFactors.append (swapvar (iter.getItem(), v, y));
2403	}
2404	}
2405	int i= A.level();
2406	CanonicalForm evalPoint;
2407	for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2408	{
2409	if (i == v.level())
2410	{
2411	evalPoint= iter.getItem();
2412	iter.getItem()= evaluation.getLast();
2413	evaluation.removeLast();
2414	evaluation.append (evalPoint);
2415	break;
2416	}
2417	}
2418	Aeval= evaluateAtZero (A);
2419	}
2420
2421	CFListIterator iter= biFactors;
2422	for (; iter.hasItem(); iter++)
2423	iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
2424
2425	CanonicalForm oldA= A;
2426	CFList oldBiFactors= biFactors;
2427	if (!leadingCoeffs.getFirst().inCoeffDomain())
2428	{
2429	CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
2430	A *= tmp;
2431	Aeval= evaluateAtZero (A);
2432	tmp= leadingCoeffs.getFirst();
2433	for (int i= A.level(); i > 2; i--)
2434	tmp= tmp (0, i);
2435	if (!tmp.inCoeffDomain())
2436	{
2437	for (CFListIterator i= biFactors; i.hasItem(); i++)
2438	{
2439	i.getItem() *= tmp/LC (i.getItem(), 1);
2440	i.getItem() /= Lc (i.getItem());
2441	}
2442	}
2443	hh= Lc (Aeval.getFirst());
2444	for (CFListIterator i= Aeval; i.hasItem(); i++)
2445	i.getItem() /= hh;
2446
2447	A /= hh;
2448	}
2449
2450	leadingCoeffs.removeFirst();
2451
2452	//prepare leading coefficients
2453	CFList* leadingCoeffs2= new CFList [A.level() - 2];
2454	prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors);
2455
2456	CFArray Pi;
2457	CFList diophant;
2458	int* liftBounds= new int [A.level() - 1];
2459	int liftBoundsLength= A.level() - 1;
2460	for (int i= 0; i < liftBoundsLength; i++)
2461	liftBounds [i]= degree (A, i + 2) + 1;
2462
2463	Aeval.removeFirst();
2464	bool noOneToOne= false;
2465	factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
2466	Pi, liftBounds, liftBoundsLength, noOneToOne);
2467
2468	if (!noOneToOne)
2469	{
2470	int check= factors.length();
2471	factors= recoverFactors (A, factors);
2472	if (check != factors.length())
2473	noOneToOne= true;
2474
2475	if (extension && !noOneToOne)
2476	factors= extNonMonicFactorRecombination (factors, oldA, info, evaluation);
2477	}
2478	if (noOneToOne)
2479	{
2480	A= oldA;
2481	Aeval= evaluateAtZero (A);
2482	biFactors= oldBiFactors;
2483	CanonicalForm LCA= LC (Aeval.getFirst(), 1);
2484	CanonicalForm yToLift= power (y, lift);
2485	CFListIterator i= biFactors;
2486	lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
2487	i++;
2488
2489	for (; i.hasItem(); i++)
2490	lift= tmax (lift, degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
2491
2492	lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
2493
2494	i= biFactors;
2495	yToLift= power (y, lift);
2496	CanonicalForm dummy;
2497	for (; i.hasItem(); i++)
2498	{
2499	LCA= LC (i.getItem(), 1);
2500	extgcd (LCA, yToLift, LCA, dummy);
2501	i.getItem()= mod (i.getItem()*LCA, yToLift);
2502	}
2503
2504	liftBoundsLength= F.level() - 1;
2505	liftBounds= liftingBounds (A, lift);
2506
2507	CFList MOD;
2508	bool earlySuccess;
2509	CFList earlyFactors;
2510	TIMING_START (fac_hensel_lift);
2511	CFList liftedFactors= henselLiftAndEarly
2512	(A, MOD, liftBounds, earlySuccess, earlyFactors,
2513	Aeval, biFactors, evaluation, info);
2514	TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
2515
2516	if (!extension)
2517	{
2518	TIMING_START (fac_factor_recombination);
2519	factors= factorRecombination (A, liftedFactors, MOD);
2520	TIMING_END_AND_PRINT (fac_factor_recombination,
2521	"time for factor recombination: ");
2522	}
2523	else
2524	{
2525	TIMING_START (fac_factor_recombination);
2526	factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
2527	TIMING_END_AND_PRINT (fac_factor_recombination,
2528	"time for factor recombination: ");
2529	}
2530
2531	if (earlySuccess)
2532	factors= Union (factors, earlyFactors);
2533	}
2534
2535	if (!extension)
2536	{
2537	for (CFListIterator i= factors; i.hasItem(); i++)
2538	{
2539	int kk= Aeval.getLast().level();
2540	for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
2541	{
2542	if (i.getItem().level() < kk)
2543	continue;
2544	i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
2545	}
2546	}
2547	}
2548
2549	if (v.level() != 1)
2550	{
2551	for (CFListIterator iter= factors; iter.hasItem(); iter++)
2552	iter.getItem()= swapvar (iter.getItem(), v, y);
2553	}
2554
2555	swap (factors, swapLevel, swapLevel2, x);
2556	append (factors, contentAFactors);
2557	decompress (factors, N);
2558	normalize (factors);
2559
2560	delete[] liftBounds;
2561
2562	return factors;
2563	}
2564
2565	/// multivariate factorization over an extension of the initial field
2566	CFList
2567	extFactorize (const CanonicalForm& F, const ExtensionInfo& info)
2568	{
2569	CanonicalForm A= F;
2570
2571	Variable alpha= info.getAlpha();
2572	Variable beta= info.getBeta();
2573	int k= info.getGFDegree();
2574	char cGFName= info.getGFName();
2575	CanonicalForm delta= info.getDelta();
2576	bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2577	Variable w= Variable (1);
2578
2579	CFList factors;
2580	if (!GF && alpha == w) // we are in F_p
2581	{
2582	CFList factors;
2583	bool extension= true;
2584	int p= getCharacteristic();
2585	if (p*p < (1<<16)) // pass to GF if possible
2586	{
2587	setCharacteristic (getCharacteristic(), 2, 'Z');
2588	ExtensionInfo info= ExtensionInfo (extension);
2589	A= A.mapinto();
2590	factors= multiFactorize (A, info);
2591
2592	Variable vBuf= rootOf (gf_mipo);
2593	setCharacteristic (getCharacteristic());
2594	for (CFListIterator j= factors; j.hasItem(); j++)
2595	j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
2596	}
2597	else // not able to pass to GF, pass to F_p(\alpha)
2598	{
2599	CanonicalForm mipo= randomIrredpoly (2, Variable (1));
2600	Variable v= rootOf (mipo);
2601	ExtensionInfo info= ExtensionInfo (v);
2602	factors= multiFactorize (A, info);
2603	}
2604	return factors;
2605	}
2606	else if (!GF && (alpha != w)) // we are in F_p(\alpha)
2607	{
2608	if (k == 1) // need factorization over F_p
2609	{
2610	int extDeg= degree (getMipo (alpha));
2611	extDeg++;
2612	CanonicalForm mipo= randomIrredpoly (extDeg + 1, Variable (1));
2613	Variable v= rootOf (mipo);
2614	ExtensionInfo info= ExtensionInfo (v);
2615	factors= biFactorize (A, info);
2616	}
2617	else
2618	{
2619	if (beta == Variable (1))
2620	{
2621	Variable v= chooseExtension (alpha, beta, k);
2622	CanonicalForm primElem, imPrimElem;
2623	bool primFail= false;
2624	Variable vBuf;
2625	primElem= primitiveElement (alpha, vBuf, primFail);
2626	ASSERT (!primFail, "failure in integer factorizer");
2627	if (primFail)
2628	; //ERROR
2629	else
2630	imPrimElem= mapPrimElem (primElem, vBuf, v);
2631
2632	CFList source, dest;
2633	CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
2634	source, dest);
2635	ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
2636	factors= biFactorize (bufA, info);
2637	}
2638	else
2639	{
2640	Variable v= chooseExtension (alpha, beta, k);
2641	CanonicalForm primElem, imPrimElem;
2642	bool primFail= false;
2643	Variable vBuf;
2644	ASSERT (!primFail, "failure in integer factorizer");
2645	if (primFail)
2646	; //ERROR
2647	else
2648	imPrimElem= mapPrimElem (delta, beta, v);
2649
2650	CFList source, dest;
2651	CanonicalForm bufA= mapDown (A, info, source, dest);
2652	source= CFList();
2653	dest= CFList();
2654	bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
2655	ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
2656	factors= biFactorize (bufA, info);
2657	}
2658	}
2659	return factors;
2660	}
2661	else // we are in GF (p^k)
2662	{
2663	int p= getCharacteristic();
2664	int extensionDeg= getGFDegree();
2665	bool extension= true;
2666	if (k == 1) // need factorization over F_p
2667	{
2668	extensionDeg++;
2669	if (pow ((double) p, (double) extensionDeg) < (1<<16))
2670	// pass to GF(p^k+1)
2671	{
2672	setCharacteristic (p);
2673	Variable vBuf= rootOf (gf_mipo);
2674	A= GF2FalphaRep (A, vBuf);
2675	setCharacteristic (p, extensionDeg, 'Z');
2676	ExtensionInfo info= ExtensionInfo (extension);
2677	factors= multiFactorize (A.mapinto(), info);
2678	}
2679	else // not able to pass to another GF, pass to F_p(\alpha)
2680	{
2681	setCharacteristic (p);
2682	Variable vBuf= rootOf (gf_mipo);
2683	A= GF2FalphaRep (A, vBuf);
2684	Variable v= chooseExtension (vBuf, beta, k);
2685	ExtensionInfo info= ExtensionInfo (v, extension);
2686	factors= multiFactorize (A, info);
2687	}
2688	}
2689	else // need factorization over GF (p^k)
2690	{
2691	if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
2692	// pass to GF(p^2k)
2693	{
2694	setCharacteristic (p, 2*extensionDeg, 'Z');
2695	ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
2696	factors= multiFactorize (GFMapUp (A, extensionDeg), info);
2697	setCharacteristic (p, extensionDeg, cGFName);
2698	}
2699	else // not able to pass to GF (p^2k), pass to F_p (\alpha)
2700	{
2701	setCharacteristic (p);
2702	Variable v1= rootOf (gf_mipo);
2703	A= GF2FalphaRep (A, v1);
2704	Variable v2= chooseExtension (v1, v1, k);
2705	CanonicalForm primElem, imPrimElem;
2706	bool primFail= false;
2707	Variable vBuf;
2708	primElem= primitiveElement (v1, v1, primFail);
2709	if (primFail)
2710	; //ERROR
2711	else
2712	imPrimElem= mapPrimElem (primElem, v1, v2);
2713	CFList source, dest;
2714	CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
2715	source, dest);
2716	ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
2717	factors= multiFactorize (bufA, info);
2718	setCharacteristic (p, k, cGFName);
2719	for (CFListIterator i= factors; i.hasItem(); i++)
2720	i.getItem()= Falpha2GFRep (i.getItem());
2721	}
2722	}
2723	return factors;
2724	}
2725	}
2726
2727	#endif
2728	/* HAVE_NTL */
2729

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

Download in other formats: