Context Navigation

source: git/factory/facFqBivar.cc @ 5079887

spielwiese

Last change on this file since 5079887 was e0af3ef, checked in by Martin Lee <martinlee84@…>, 12 years ago
fix: need polys over Z
Property mode set to `100644`
File size: 178.3 KB

Rev	Line
[7bf145]	1	/*****************************************************************************\
[806c18]	2	* Computer Algebra System SINGULAR
[7bf145]	3	\*****************************************************************************/
	4	/** @file facFqBivar.cc
[806c18]	5	*
[7bf145]	6	* This file provides functions for factorizing a bivariate polynomial over
[806c18]	7	* \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF, based on "Modern Computer
	8	* Algebra, Chapter 15" by J. von zur Gathen & J. Gerhard and "Factoring
	9	* multivariate polynomials over a finite field" by L. Bernardin.
[8c1a84]	10	* Factor Recombination is described in "Factoring polynomials over global
	11	* fields" by K. Belabas, M. van Hoeij, J. Klueners, A. Steel
[7bf145]	12	*
	13	*
	14	* @author Martin Lee
	15	*
	16	**/
	17	/*****************************************************************************/
	18
[e4fe2b]	19	#include "config.h"
[7bf145]	20
[650f2d8]	21	#include "cf_assert.h"
[7bf145]	22	#include "debug.h"
	23	#include "timing.h"
	24
	25	#include "canonicalform.h"
	26	#include "cf_defs.h"
	27	#include "cf_map_ext.h"
	28	#include "cf_random.h"
	29	#include "facHensel.h"
[0e2e23]	30	#include "facMul.h"
[7bf145]	31	#include "cf_map.h"
	32	#include "cf_gcd_smallp.h"
[11bf82]	33	#include "facFqBivarUtil.h"
[7bf145]	34	#include "facFqBivar.h"
[11bf82]	35	#include "cfNewtonPolygon.h"
[f9da5e]	36	#include "algext.h"
[7bf145]	37
	38	#ifdef HAVE_NTL
[da68804]	39	#include "NTLconvert.h"
[7bf145]	40
[18a660]	41	#ifdef HAVE_FLINT
	42	#include "FLINTconvert.h"
	43	#endif
	44
[978ce3]	45	TIMING_DEFINE_PRINT(fac_fq_uni_factorizer)
	46	TIMING_DEFINE_PRINT(fac_fq_bi_hensel_lift)
	47	TIMING_DEFINE_PRINT(fac_fq_bi_factor_recombination)
[7bf145]	48
[ad0177]	49	CanonicalForm prodMod0 (const CFList& L, const CanonicalForm& M, const modpk& b)
[7bf145]	50	{
	51	if (L.isEmpty())
	52	return 1;
	53	else if (L.length() == 1)
	54	return mod (L.getFirst()(0, 1) , M);
	55	else if (L.length() == 2)
[ad0177]	56	return mod (mulNTL (L.getFirst()(0, 1),L.getLast()(0, 1), b), M);
[7bf145]	57	else
	58	{
	59	int l= L.length()/2;
	60	CFListIterator i= L;
	61	CFList tmp1, tmp2;
	62	CanonicalForm buf1, buf2;
[806c18]	63	for (int j= 1; j <= l; j++, i++)
[7bf145]	64	tmp1.append (i.getItem());
	65	tmp2= Difference (L, tmp1);
[ad0177]	66	buf1= prodMod0 (tmp1, M, b);
	67	buf2= prodMod0 (tmp2, M, b);
	68	return mod (mulNTL (buf1,buf2, b), M);
[7bf145]	69	}
	70	}
	71
[806c18]	72	CanonicalForm evalPoint (const CanonicalForm& F, CanonicalForm & eval,
[7bf145]	73	const Variable& alpha, CFList& list, const bool& GF,
[806c18]	74	bool& fail)
[7bf145]	75	{
	76	fail= false;
	77	Variable x= Variable(2);
[a54114]	78	Variable y= Variable(1);
[7bf145]	79	FFRandom genFF;
	80	GFRandom genGF;
	81	CanonicalForm random, mipo;
	82	double bound;
	83	int p= getCharacteristic ();
[1372ae]	84	if (alpha.level() != 1)
[7bf145]	85	{
	86	mipo= getMipo (alpha);
	87	int d= degree (mipo);
	88	bound= ipower (p, d);
	89	}
[806c18]	90	else if (GF)
[7bf145]	91	{
	92	int d= getGFDegree();
	93	bound= ipower (p, d);
	94	}
	95	else
	96	bound= p;
	97
[11bf82]	98	random= 0;
[806c18]	99	do
[7bf145]	100	{
	101	if (list.length() >= bound)
	102	{
	103	fail= true;
	104	break;
	105	}
[8db258]	106	if (list.isEmpty())
	107	random= 0;
	108	else if (GF)
[11bf82]	109	{
	110	if (list.length() == 1)
	111	random= getGFGenerator();
	112	else
	113	random= genGF.generate();
	114	}
	115	else if (list.length() < p \|\| alpha.level() == 1)
[7bf145]	116	random= genFF.generate();
[806c18]	117	else if (alpha != x && list.length() >= p)
[7bf145]	118	{
[11bf82]	119	if (list.length() == p)
	120	random= alpha;
	121	else
	122	{
	123	AlgExtRandomF genAlgExt (alpha);
	124	random= genAlgExt.generate();
	125	}
[7bf145]	126	}
	127	if (find (list, random)) continue;
	128	eval= F (random, x);
[a54114]	129	if (degree (eval) != degree (F, y))
[7bf145]	130	{ //leading coeff vanishes
	131	if (!find (list, random))
	132	list.append (random);
	133	continue;
	134	}
[806c18]	135	if (degree (gcd (deriv (eval, eval.mvar()), eval), eval.mvar()) > 0)
[7bf145]	136	{ //evaluated polynomial is not squarefree
	137	if (!find (list, random))
	138	list.append (random);
	139	continue;
	140	}
	141	} while (find (list, random));
	142
	143	return random;
	144	}
	145
[806c18]	146	CFList
	147	uniFactorizer (const CanonicalForm& A, const Variable& alpha, const bool& GF)
[7bf145]	148	{
	149	Variable x= A.mvar();
[18a660]	150	if (A.inCoeffDomain())
	151	return CFList();
	152	ASSERT (A.isUnivariate(),
[050d1b]	153	"univariate polynomial expected or constant expected");
[7bf145]	154	CFFList factorsA;
[9a12097]	155	zz_p::init (getCharacteristic());
[806c18]	156	if (GF)
[7bf145]	157	{
	158	int k= getGFDegree();
	159	char cGFName= gf_name;
[0a7d0ca]	160	CanonicalForm mipo= gf_mipo;
[806c18]	161	setCharacteristic (getCharacteristic());
[0a7d0ca]	162	Variable beta= rootOf (mipo.mapinto());
[806c18]	163	CanonicalForm buf= GF2FalphaRep (A, beta);
[7bf145]	164	if (getCharacteristic() > 2)
	165	{
[9a12097]	166	zz_pX NTLMipo= convertFacCF2NTLzzpX (mipo.mapinto());
	167	zz_pE::init (NTLMipo);
	168	zz_pEX NTLA= convertFacCF2NTLzz_pEX (buf, NTLMipo);
[7bf145]	169	MakeMonic (NTLA);
[9a12097]	170	vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
	171	zz_pE multi= to_zz_pE (1);
	172	factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
[7bf145]	173	x, beta);
	174	}
	175	else
	176	{
[0a7d0ca]	177	GF2X NTLMipo= convertFacCF2NTLGF2X (mipo.mapinto());
[7bf145]	178	GF2E::init (NTLMipo);
	179	GF2EX NTLA= convertFacCF2NTLGF2EX (buf, NTLMipo);
	180	MakeMonic (NTLA);
	181	vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
	182	GF2E multi= to_GF2E (1);
	183	factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
	184	x, beta);
	185	}
	186	setCharacteristic (getCharacteristic(), k, cGFName);
[806c18]	187	for (CFFListIterator i= factorsA; i.hasItem(); i++)
[7bf145]	188	{
	189	buf= i.getItem().factor();
	190	buf= Falpha2GFRep (buf);
	191	i.getItem()= CFFactor (buf, i.getItem().exp());
	192	}
[806c18]	193	}
[1372ae]	194	else if (alpha.level() != 1)
[7bf145]	195	{
	196	if (getCharacteristic() > 2)
	197	{
[9a12097]	198	zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
	199	zz_pE::init (NTLMipo);
	200	zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
[7bf145]	201	MakeMonic (NTLA);
[9a12097]	202	vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
	203	zz_pE multi= to_zz_pE (1);
	204	factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
[7bf145]	205	x, alpha);
	206	}
	207	else
	208	{
	209	GF2X NTLMipo= convertFacCF2NTLGF2X (getMipo (alpha));
[806c18]	210	GF2E::init (NTLMipo);
[7bf145]	211	GF2EX NTLA= convertFacCF2NTLGF2EX (A, NTLMipo);
	212	MakeMonic (NTLA);
	213	vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
	214	GF2E multi= to_GF2E (1);
[806c18]	215	factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
[7bf145]	216	x, alpha);
[806c18]	217	}
[7bf145]	218	}
[806c18]	219	else
[7bf145]	220	{
[18a660]	221	#ifdef HAVE_FLINT
	222	nmod_poly_t FLINTA;
	223	convertFacCF2nmod_poly_t (FLINTA, A);
	224	nmod_poly_factor_t result;
	225	nmod_poly_factor_init (result);
	226	mp_limb_t leadingCoeff= nmod_poly_factor (result, FLINTA);
	227	factorsA= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, x);
	228	if (factorsA.getFirst().factor().inCoeffDomain())
	229	factorsA.removeFirst();
	230	nmod_poly_factor_clear (result);
	231	nmod_poly_clear (FLINTA);
	232	#else
[7bf145]	233	if (getCharacteristic() > 2)
	234	{
[9a12097]	235	zz_pX NTLA= convertFacCF2NTLzzpX (A);
[7bf145]	236	MakeMonic (NTLA);
[9a12097]	237	vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
	238	zz_p multi= to_zz_p (1);
	239	factorsA= convertNTLvec_pair_zzpX_long2FacCFFList (NTLFactorsA, multi,
[7bf145]	240	x);
	241	}
	242	else
	243	{
	244	GF2X NTLA= convertFacCF2NTLGF2X (A);
	245	vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
	246	GF2 multi= to_GF2 (1);
[806c18]	247	factorsA= convertNTLvec_pair_GF2X_long2FacCFFList (NTLFactorsA, multi,
[7bf145]	248	x);
	249	}
[18a660]	250	#endif
[7bf145]	251	}
	252	CFList uniFactors;
[806c18]	253	for (CFFListIterator i= factorsA; i.hasItem(); i++)
[7bf145]	254	uniFactors.append (i.getItem().factor());
	255	return uniFactors;
[806c18]	256	}
	257
	258	/// naive factor recombination as decribed in "Factoring
	259	/// multivariate polynomials over a finite field" by L Bernardin.
	260	CFList
[11bf82]	261	extFactorRecombination (CFList& factors, CanonicalForm& F,
[09609a]	262	const CanonicalForm& N, const ExtensionInfo& info,
[11bf82]	263	DegreePattern& degs, const CanonicalForm& eval, int s,
	264	int thres)
[806c18]	265	{
[7bf145]	266	if (factors.length() == 0)
[11bf82]	267	{
	268	F= 1;
[7bf145]	269	return CFList();
[11bf82]	270	}
[e0af3ef]	271	if (F.inCoeffDomain())
	272	return CFList();
[7bf145]	273
	274	Variable alpha= info.getAlpha();
	275	Variable beta= info.getBeta();
	276	CanonicalForm gamma= info.getGamma();
	277	CanonicalForm delta= info.getDelta();
	278	int k= info.getGFDegree();
	279
[09609a]	280	CanonicalForm M= N;
	281	int l= degree (N);
[7bf145]	282	Variable y= F.mvar();
[a54114]	283	Variable x= Variable (1);
[7bf145]	284	CFList source, dest;
[806c18]	285	if (degs.getLength() <= 1 \|\| factors.length() == 1)
[11bf82]	286	{
	287	CFList result= CFList(mapDown (F(y-eval, y), info, source, dest));
	288	F= 1;
	289	return result;
	290	}
[806c18]	291
	292	DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, M) == F " <<
[27ab36]	293	(mod (LC (F, 1)prodMod (factors, M), M)/Lc (mod (LC (F, 1)prodMod (factors, M), M)) == F/Lc (F)));
[ac8e1a]	294	int degMipoBeta= 1;
	295	if (!k && beta.level() != 1)
[7bf145]	296	degMipoBeta= degree (getMipo (beta));
	297
	298	CFList T, S, Diff;
	299	T= factors;
	300
	301	CFList result;
[21b8f4c]	302	CanonicalForm buf, buf2, quot;
[11bf82]	303
	304	buf= F;
[7bf145]	305
[a54114]	306	CanonicalForm g, LCBuf= LC (buf, x);
[1673386]	307	int * v= new int [T.length()];
[7bf145]	308	for (int i= 0; i < T.length(); i++)
	309	v[i]= 0;
	310
	311	CFArray TT;
[806c18]	312	DegreePattern bufDegs1, bufDegs2;
[7bf145]	313	bufDegs1= degs;
	314	int subsetDeg;
[806c18]	315	TT= copy (factors);
[7bf145]	316	bool nosubset= false;
	317	bool recombination= false;
[93134c]	318	bool trueFactor= false;
[bbb3fbf]	319	CanonicalForm test;
	320	CanonicalForm buf0= buf (0, x)*LCBuf;
[11bf82]	321	while (T.length() >= 2*s && s <= thres)
[7bf145]	322	{
[806c18]	323	while (nosubset == false)
[7bf145]	324	{
[806c18]	325	if (T.length() == s)
[7bf145]	326	{
[1673386]	327	delete [] v;
[806c18]	328	if (recombination)
[7bf145]	329	{
	330	T.insert (LCBuf);
	331	g= prodMod (T, M);
	332	T.removeFirst();
	333	g /= content(g);
	334	g= g (y - eval, y);
	335	g /= Lc (g);
	336	appendTestMapDown (result, g, info, source, dest);
[11bf82]	337	F= 1;
[7bf145]	338	return result;
	339	}
	340	else
	341	{
	342	appendMapDown (result, F (y - eval, y), info, source, dest);
[11bf82]	343	F= 1;
[7bf145]	344	return result;
	345	}
	346	}
	347	S= subset (v, s, TT, nosubset);
	348	if (nosubset) break;
	349	subsetDeg= subsetDegree (S);
	350	// skip those combinations that are not possible
[806c18]	351	if (!degs.find (subsetDeg))
[7bf145]	352	continue;
[806c18]	353	else
	354	{
[bbb3fbf]	355	test= prodMod0 (S, M);
	356	test *= LCBuf;
	357	test = mod (test, M);
	358	if (fdivides (test, buf0))
[7bf145]	359	{
[bbb3fbf]	360	S.insert (LCBuf);
	361	g= prodMod (S, M);
	362	S.removeFirst();
	363	g /= content (g, x);
	364	if (fdivides (g, buf, quot))
[f047b56]	365	{
[bbb3fbf]	366	buf2= g (y - eval, y);
	367	buf2 /= Lc (buf2);
	368
	369	if (!k && beta.level() == 1)
[7bf145]	370	{
[bbb3fbf]	371	if (degree (buf2, alpha) < degMipoBeta)
	372	{
	373	buf= quot;
	374	LCBuf= LC (buf, x);
	375	recombination= true;
	376	appendTestMapDown (result, buf2, info, source, dest);
	377	trueFactor= true;
	378	}
[7bf145]	379	}
[bbb3fbf]	380	else
[7bf145]	381	{
[bbb3fbf]	382	if (!isInExtension (buf2, gamma, k, delta, source, dest))
[7bf145]	383	{
[bbb3fbf]	384	buf= quot;
	385	LCBuf= LC (buf, x);
	386	recombination= true;
	387	appendTestMapDown (result, buf2, info, source, dest);
	388	trueFactor= true;
[f047b56]	389	}
[bbb3fbf]	390	}
	391	if (trueFactor)
	392	{
	393	T= Difference (T, S);
	394	l -= degree (g);
	395	M= power (y, l);
	396	buf0= buf (0, x)*LCBuf;
	397
	398	// compute new possible degree pattern
	399	bufDegs2= DegreePattern (T);
	400	bufDegs1.intersect (bufDegs2);
	401	bufDegs1.refine ();
	402	if (T.length() < 2*s \|\| T.length() == s \|\|
	403	bufDegs1.getLength() == 1)
[f047b56]	404	{
[bbb3fbf]	405	delete [] v;
	406	if (recombination)
	407	{
	408	appendTestMapDown (result, buf (y - eval, y), info, source,
	409	dest);
	410	F= 1;
	411	return result;
	412	}
	413	else
	414	{
	415	appendMapDown (result, F (y - eval, y), info, source, dest);
	416	F= 1;
	417	return result;
	418	}
[7bf145]	419	}
[bbb3fbf]	420	trueFactor= false;
	421	TT= copy (T);
	422	indexUpdate (v, s, T.length(), nosubset);
	423	if (nosubset) break;
[7bf145]	424	}
	425	}
	426	}
	427	}
	428	}
	429	s++;
[806c18]	430	if (T.length() < 2*s \|\| T.length() == s)
[7bf145]	431	{
[1673386]	432	delete [] v;
[7bf145]	433	if (recombination)
	434	{
	435	appendTestMapDown (result, buf (y - eval, y), info, source, dest);
[11bf82]	436	F= 1;
[7bf145]	437	return result;
	438	}
	439	else
	440	{
	441	appendMapDown (result, F (y - eval, y), info, source, dest);
[11bf82]	442	F= 1;
[7bf145]	443	return result;
	444	}
	445	}
	446	for (int i= 0; i < T.length(); i++)
	447	v[i]= 0;
	448	nosubset= false;
	449	}
[806c18]	450	if (T.length() < 2*s)
[11bf82]	451	{
[7bf145]	452	appendMapDown (result, F (y - eval, y), info, source, dest);
[11bf82]	453	F= 1;
	454	delete [] v;
	455	return result;
	456	}
	457
	458	if (s > thres)
	459	{
	460	factors= T;
	461	F= buf;
	462	degs= bufDegs1;
	463	}
[7bf145]	464
[1673386]	465	delete [] v;
[806c18]	466	return result;
	467	}
[7bf145]	468
[806c18]	469	/// naive factor recombination as decribed in "Factoring
	470	/// multivariate polynomials over a finite field" by L Bernardin.
	471	CFList
[11bf82]	472	factorRecombination (CFList& factors, CanonicalForm& F,
[09609a]	473	const CanonicalForm& N, DegreePattern& degs, int s,
[d9357b]	474	int thres, const modpk& b
[11bf82]	475	)
[7bf145]	476	{
	477	if (factors.length() == 0)
[11bf82]	478	{
	479	F= 1;
[7bf145]	480	return CFList ();
[11bf82]	481	}
[e0af3ef]	482	if (F.inCoeffDomain())
	483	return CFList();
[806c18]	484	if (degs.getLength() <= 1 \|\| factors.length() == 1)
[11bf82]	485	{
	486	CFList result= CFList (F);
	487	F= 1;
	488	return result;
	489	}
[27ab36]	490	#ifdef DEBUGOUTPUT
	491	if (b.getp() == 0)
	492	DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
	493	(mod (LC (F, 1)prodMod (factors, N),N)/Lc (mod (LC (F, 1)prodMod (factors, N),N)) == F/Lc(F)));
	494	else
	495	DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
	496	(mod (b(LC (F, 1)prodMod (factors, N)),N)/Lc (mod (b(LC (F, 1)prodMod (factors, N)),N)) == F/Lc(F)));
	497	#endif
[e0af3ef]	498
[7bf145]	499	CFList T, S;
	500
[09609a]	501	CanonicalForm M= N;
	502	int l= degree (N);
[7bf145]	503	T= factors;
	504	CFList result;
[a54114]	505	Variable y= Variable (2);
	506	Variable x= Variable (1);
	507	CanonicalForm LCBuf= LC (F, x);
[21b8f4c]	508	CanonicalForm g, quot, buf= F;
[1673386]	509	int * v= new int [T.length()];
[7bf145]	510	for (int i= 0; i < T.length(); i++)
	511	v[i]= 0;
	512	bool nosubset= false;
	513	CFArray TT;
	514	DegreePattern bufDegs1, bufDegs2;
	515	bufDegs1= degs;
	516	int subsetDeg;
	517	TT= copy (factors);
	518	bool recombination= false;
[bbb3fbf]	519	CanonicalForm test;
[e0af3ef]	520	bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) \|\|
	521	getCharacteristic() > 0;
[188d2fb]	522	if (!isRat)
	523	On (SW_RATIONAL);
	524	CanonicalForm buf0= mulNTL (buf (0, x), LCBuf);
	525	if (!isRat)
	526	Off (SW_RATIONAL);
[11bf82]	527	while (T.length() >= 2*s && s <= thres)
[7bf145]	528	{
[806c18]	529	while (nosubset == false)
[7bf145]	530	{
[806c18]	531	if (T.length() == s)
[7bf145]	532	{
[1673386]	533	delete [] v;
[7bf145]	534	if (recombination)
	535	{
	536	T.insert (LCBuf);
	537	g= prodMod (T, M);
[eb481b]	538	if (b.getp() != 0)
	539	g= b(g);
[7bf145]	540	T.removeFirst();
[a54114]	541	result.append (g/content (g, x));
[11bf82]	542	F= 1;
[7bf145]	543	return result;
	544	}
	545	else
[11bf82]	546	{
	547	result= CFList (F);
	548	F= 1;
	549	return result;
	550	}
[7bf145]	551	}
	552	S= subset (v, s, TT, nosubset);
	553	if (nosubset) break;
	554	subsetDeg= subsetDegree (S);
	555	// skip those combinations that are not possible
[806c18]	556	if (!degs.find (subsetDeg))
[7bf145]	557	continue;
[806c18]	558	else
	559	{
[f9da5e]	560	if (!isRat)
	561	On (SW_RATIONAL);
	562	test= prodMod0 (S, M);
	563	if (!isRat)
	564	{
	565	test *= bCommonDen (test);
	566	Off (SW_RATIONAL);
	567	}
[ad0177]	568	test= mulNTL (test, LCBuf, b);
	569	test= mod (test, M);
	570	if (uniFdivides (test, buf0))
[7bf145]	571	{
[f9da5e]	572	if (!isRat)
	573	On (SW_RATIONAL);
[bbb3fbf]	574	S.insert (LCBuf);
	575	g= prodMod (S, M);
	576	S.removeFirst();
[f9da5e]	577	if (!isRat)
	578	{
	579	g *= bCommonDen(g);
	580	Off (SW_RATIONAL);
	581	}
[eb481b]	582	if (b.getp() != 0)
	583	g= b(g);
[ad0177]	584	if (!isRat)
	585	On (SW_RATIONAL);
[f9da5e]	586	g /= content (g, x);
[bbb3fbf]	587	if (fdivides (g, buf, quot))
[7bf145]	588	{
[bbb3fbf]	589	recombination= true;
	590	result.append (g);
[e0af3ef]	591	if (b.getp() != 0)
	592	buf= quot*bCommonDen (quot);
	593	else
	594	buf= quot;
[bbb3fbf]	595	LCBuf= LC (buf, x);
	596	T= Difference (T, S);
	597	l -= degree (g);
	598	M= power (y, l);
[188d2fb]	599	buf0= mulNTL (buf (0, x), LCBuf);
[ad0177]	600	if (!isRat)
	601	Off (SW_RATIONAL);
[bbb3fbf]	602	// compute new possible degree pattern
	603	bufDegs2= DegreePattern (T);
	604	bufDegs1.intersect (bufDegs2);
	605	bufDegs1.refine ();
	606	if (T.length() < 2*s \|\| T.length() == s \|\|
	607	bufDegs1.getLength() == 1)
[f047b56]	608	{
[bbb3fbf]	609	delete [] v;
	610	if (recombination)
	611	{
	612	result.append (buf);
	613	F= 1;
	614	return result;
	615	}
	616	else
	617	{
	618	result= CFList (F);
	619	F= 1;
	620	return result;
	621	}
[7bf145]	622	}
[bbb3fbf]	623	TT= copy (T);
	624	indexUpdate (v, s, T.length(), nosubset);
	625	if (nosubset) break;
[806c18]	626	}
[ad0177]	627	if (!isRat)
	628	Off (SW_RATIONAL);
[7bf145]	629	}
	630	}
	631	}
	632	s++;
[806c18]	633	if (T.length() < 2*s \|\| T.length() == s)
[7bf145]	634	{
[1673386]	635	delete [] v;
[7bf145]	636	if (recombination)
	637	{
	638	result.append (buf);
[11bf82]	639	F= 1;
[7bf145]	640	return result;
	641	}
	642	else
[11bf82]	643	{
	644	result= CFList (F);
	645	F= 1;
	646	return result;
	647	}
[7bf145]	648	}
	649	for (int i= 0; i < T.length(); i++)
	650	v[i]= 0;
	651	nosubset= false;
	652	}
[11bf82]	653	delete [] v;
[806c18]	654	if (T.length() < 2*s)
[11bf82]	655	{
[7bf145]	656	result.append (F);
[11bf82]	657	F= 1;
	658	return result;
	659	}
	660
	661	if (s > thres)
	662	{
	663	factors= T;
	664	F= buf;
	665	degs= bufDegs1;
	666	}
[7bf145]	667
[806c18]	668	return result;
	669	}
[7bf145]	670
[11bf82]	671	Variable chooseExtension (const Variable & alpha, const Variable& beta, int k)
[7bf145]	672	{
[11bf82]	673	zz_p::init (getCharacteristic());
	674	zz_pX NTLIrredpoly;
[7a1151]	675	int i=1, m= 2;
[11bf82]	676	// extension of F_p needed
	677	if (alpha.level() == 1 && beta.level() == 1 && k == 1)
	678	{
	679	i= 1;
	680	m= 2;
	681	} //extension of F_p(alpha) needed but want to factorize over F_p
	682	else if (alpha.level() != 1 && beta.level() == 1 && k == 1)
	683	{
	684	i= 1;
	685	m= degree (getMipo (alpha)) + 1;
	686	} //extension of F_p(alpha) needed for first time
	687	else if (alpha.level() != 1 && beta.level() == 1 && k != 1)
	688	{
[7bf145]	689	i= 2;
[11bf82]	690	m= degree (getMipo (alpha));
	691	}
	692	else if (alpha.level() != 1 && beta.level() != 1 && k != 1)
	693	{
	694	m= degree (getMipo (beta));
	695	i= degree (getMipo (alpha))/m + 1;
	696	}
	697	BuildIrred (NTLIrredpoly, i*m);
	698	CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
[7bf145]	699	return rootOf (newMipo);
	700	}
	701
[1a3011e]	702	void
	703	earlyFactorDetection (CFList& reconstructedFactors, CanonicalForm& F, CFList&
	704	factors, int& adaptedLiftBound, int*& factorsFoundIndex,
[d9357b]	705	DegreePattern& degs, bool& success, int deg,
	706	const modpk& b)
[7bf145]	707	{
	708	DegreePattern bufDegs1= degs;
	709	DegreePattern bufDegs2;
	710	CFList T= factors;
	711	CanonicalForm buf= F;
[a54114]	712	Variable x= Variable (1);
[21b8f4c]	713	CanonicalForm g, quot;
[7bf145]	714	CanonicalForm M= power (F.mvar(), deg);
	715	adaptedLiftBound= 0;
[1a3011e]	716	int d= degree (F), l= 0;
[188d2fb]	717	bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) \|\| getCharacteristic() > 0;
	718	if (!isRat)
	719	On (SW_RATIONAL);
[e0af3ef]	720	if (b.getp() != 0)
	721	buf *= bCommonDen (buf);
	722	CanonicalForm LCBuf= LC (buf, x);
[41fea7]	723	CanonicalForm buf0= mulNTL (buf (0,x), LCBuf);
	724	CanonicalForm buf1= mulNTL (buf (1,x), LCBuf);
[188d2fb]	725	if (!isRat)
	726	Off (SW_RATIONAL);
[de222e]	727	CanonicalForm test0, test1;
[188d2fb]	728
[1a3011e]	729	for (CFListIterator i= factors; i.hasItem(); i++, l++)
[7bf145]	730	{
[1a3011e]	731	if (!bufDegs1.find (degree (i.getItem(), 1)) \|\| factorsFoundIndex[l] == 1)
[7bf145]	732	continue;
	733	else
	734	{
[de222e]	735	test1= mod (mulNTL (i.getItem() (1,x), LCBuf, b), M);
	736	if (uniFdivides (test1, buf1))
[7bf145]	737	{
[de222e]	738	test0= mod (mulNTL (i.getItem() (0,x), LCBuf, b), M);
	739	if (uniFdivides (test0, buf0))
[7bf145]	740	{
[f9da5e]	741	if (!isRat)
	742	On (SW_RATIONAL);
[de222e]	743	g= mulMod2 (i.getItem(), LCBuf, M);
[f9da5e]	744	if (!isRat)
	745	{
	746	g *= bCommonDen(g);
	747	Off (SW_RATIONAL);
	748	}
[de222e]	749	if (b.getp() != 0)
	750	g= b(g);
[ad0177]	751	if (!isRat)
	752	On (SW_RATIONAL);
[f9da5e]	753	g /= content (g, x);
[de222e]	754	if (fdivides (g, buf, quot))
	755	{
	756	reconstructedFactors.append (g);
	757	factorsFoundIndex[l]= 1;
[e0af3ef]	758	if (b.getp() != 0)
	759	buf= quot*bCommonDen(quot);
	760	else
	761	buf= quot;
[de222e]	762	d -= degree (g);
	763	LCBuf= LC (buf, x);
[41fea7]	764	buf0= mulNTL (buf (0,x), LCBuf);
	765	buf1= mulNTL (buf (1,x), LCBuf);
[188d2fb]	766	if (!isRat)
	767	Off (SW_RATIONAL);
[de222e]	768	T= Difference (T, CFList (i.getItem()));
	769	F= buf;
	770
	771	// compute new possible degree pattern
	772	bufDegs2= DegreePattern (T);
	773	bufDegs1.intersect (bufDegs2);
	774	bufDegs1.refine ();
	775	if (bufDegs1.getLength() <= 1)
	776	{
[e0af3ef]	777	if (!buf.inCoeffDomain())
	778	reconstructedFactors.append (buf);
[de222e]	779	break;
	780	}
	781	}
[ad0177]	782	if (!isRat)
	783	Off (SW_RATIONAL);
[7bf145]	784	}
	785	}
	786	}
	787	}
	788	adaptedLiftBound= d + 1;
[db65ada]	789	if (adaptedLiftBound < deg)
[7bf145]	790	{
	791	degs= bufDegs1;
[69c882]	792	success= true;
[7bf145]	793	}
	794	if (bufDegs1.getLength() <= 1)
	795	degs= bufDegs1;
	796	}
	797
[1a3011e]	798	void
	799	extEarlyFactorDetection (CFList& reconstructedFactors, CanonicalForm& F, CFList&
	800	factors,int& adaptedLiftBound, int*& factorsFoundIndex,
	801	DegreePattern& degs, bool& success, const
	802	ExtensionInfo& info, const CanonicalForm& eval, int deg
	803	)
[7bf145]	804	{
	805	Variable alpha= info.getAlpha();
	806	Variable beta= info.getBeta();
	807	CanonicalForm gamma= info.getGamma();
	808	CanonicalForm delta= info.getDelta();
	809	int k= info.getGFDegree();
	810	DegreePattern bufDegs1= degs, bufDegs2;
[806c18]	811	CFList result;
[7bf145]	812	CFList T= factors;
	813	Variable y= F.mvar();
[a54114]	814	Variable x= Variable (1);
	815	CanonicalForm buf= F, LCBuf= LC (buf, x), g, buf2;
[7bf145]	816	CanonicalForm M= power (y, deg);
	817	adaptedLiftBound= 0;
[93134c]	818	bool trueFactor= false;
[1a3011e]	819	int d= degree (F), l= 0;
[7bf145]	820	CFList source, dest;
[ac8e1a]	821	int degMipoBeta= 1;
	822	if (!k && beta.level() != 1)
[7bf145]	823	degMipoBeta= degree (getMipo (beta));
[21b8f4c]	824	CanonicalForm quot;
[1a3011e]	825	for (CFListIterator i= factors; i.hasItem(); i++, l++)
[7bf145]	826	{
[1a3011e]	827	if (!bufDegs1.find (degree (i.getItem(), 1)) \|\| factorsFoundIndex[l] == 1)
[7bf145]	828	continue;
	829	else
	830	{
[f047b56]	831	g= mulMod2 (i.getItem(), LCBuf, M);
	832	g /= content (g, x);
	833	if (fdivides (g, buf, quot))
[7bf145]	834	{
[f047b56]	835	buf2= g (y - eval, y);
	836	buf2 /= Lc (buf2);
[806c18]	837
[f047b56]	838	if (!k && beta == x)
	839	{
	840	if (degree (buf2, alpha) < degMipoBeta)
[7bf145]	841	{
[1a3011e]	842	appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
	843	factorsFoundIndex[l]= 1;
[f047b56]	844	buf= quot;
	845	d -= degree (g);
	846	LCBuf= LC (buf, x);
	847	trueFactor= true;
[7bf145]	848	}
[f047b56]	849	}
	850	else
	851	{
	852	if (!isInExtension (buf2, gamma, k, delta, source, dest))
[7bf145]	853	{
[1a3011e]	854	appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
	855	factorsFoundIndex[l]= 1;
[f047b56]	856	buf= quot;
	857	d -= degree (g);
	858	LCBuf= LC (buf, x);
	859	trueFactor= true;
[806c18]	860	}
[f047b56]	861	}
	862	if (trueFactor)
	863	{
	864	T= Difference (T, CFList (i.getItem()));
[69c882]	865	F= buf;
[93134c]	866
[f047b56]	867	// compute new possible degree pattern
	868	bufDegs2= DegreePattern (T);
	869	bufDegs1.intersect (bufDegs2);
	870	bufDegs1.refine ();
	871	trueFactor= false;
	872	if (bufDegs1.getLength() <= 1)
	873	{
[e0af3ef]	874	if (!buf.inCoeffDomain())
	875	{
	876	buf= buf (y - eval, y);
	877	buf /= Lc (buf);
	878	appendMapDown (reconstructedFactors, buf, info, source, dest);
	879	}
[f047b56]	880	break;
[7bf145]	881	}
	882	}
	883	}
	884	}
	885	}
	886	adaptedLiftBound= d + 1;
	887	if (adaptedLiftBound < deg)
	888	{
	889	degs= bufDegs1;
[69c882]	890	success= true;
[7bf145]	891	}
	892	if (bufDegs1.getLength() <= 1)
	893	degs= bufDegs1;
	894	}
	895
[34e062]	896	int*
	897	getCombinations (int * rightSide, int sizeOfRightSide, int& sizeOfOutput,
	898	int degreeLC)
	899	{
	900	Variable x= Variable (1);
	901	int p= getCharacteristic();
	902	int d= getGFDegree();
	903	char cGFName= gf_name;
	904	setCharacteristic(0);
	905	CanonicalForm buf= 1;
	906	for (int i= 0; i < sizeOfRightSide; i++)
	907	buf *= (power (x, rightSide [i]) + 1);
	908
	909	int j= 0;
	910	for (CFIterator i= buf; i.hasTerms(); i++, j++)
	911	{
	912	if (i.exp() < degreeLC)
	913	{
	914	j++;
	915	break;
	916	}
	917	}
	918
	919	ASSERT ( j > 1, "j > 1 expected" );
	920
	921	int* result = new int [j - 1];
	922	sizeOfOutput= j - 1;
	923
	924	int i= 0;
	925	for (CFIterator m = buf; i < j - 1; i++, m++)
	926	result [i]= m.exp();
	927
	928	if (d > 1)
	929	setCharacteristic (p, d, cGFName);
	930	else
	931	setCharacteristic (p);
	932	return result;
	933	}
	934
	935	int *
	936	getLiftPrecisions (const CanonicalForm& F, int& sizeOfOutput, int degreeLC)
	937	{
	938	int sizeOfNewtonPoly;
	939	int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPoly);
	940	int sizeOfRightSide;
	941	int * rightSide= getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
	942	int * result= getCombinations(rightSide, sizeOfRightSide, sizeOfOutput,
	943	degreeLC);
	944	delete [] rightSide;
	945	for (int i= 0; i < sizeOfNewtonPoly; i++)
	946	delete [] newtonPolyg[i];
	947	delete [] newtonPolyg;
	948	return result;
	949	}
	950
[1a3011e]	951	void
[69c882]	952	deleteFactors (CFList& factors, int* factorsFoundIndex)
[1a3011e]	953	{
[69c882]	954	CFList result;
	955	int i= 0;
	956	for (CFListIterator iter= factors; iter.hasItem(); iter++, i++)
[1a3011e]	957	{
[69c882]	958	if (factorsFoundIndex[i] == 1)
	959	continue;
[1a3011e]	960	else
[69c882]	961	result.append (iter.getItem());
[1a3011e]	962	}
[69c882]	963	factors= result;
[1a3011e]	964	}
	965
[7bf145]	966	CFList
[806c18]	967	henselLiftAndEarly (CanonicalForm& A, bool& earlySuccess, CFList&
[7bf145]	968	earlyFactors, DegreePattern& degs, int& liftBound,
[806c18]	969	const CFList& uniFactors, const ExtensionInfo& info,
[69fdf90]	970	const CanonicalForm& eval, modpk& b)
[7bf145]	971	{
	972	Variable alpha= info.getAlpha();
	973	Variable beta= info.getBeta();
	974	CanonicalForm gamma= info.getGamma();
	975	CanonicalForm delta= info.getDelta();
	976	bool extension= info.isInExtension();
	977
[69076c]	978	int sizeOfLiftPre;
	979	int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
	980
[7bf145]	981	Variable x= Variable (1);
	982	Variable y= Variable (2);
	983	CFArray Pi;
	984	CFList diophant;
	985	CFList bufUniFactors= uniFactors;
[eb481b]	986	CanonicalForm bufA= A;
	987	CanonicalForm lcA0= 0;
[f9da5e]	988	bool mipoHasDen= false;
[eb481b]	989	if (getCharacteristic() == 0 && b.getp() != 0)
	990	{
[41fea7]	991	if (alpha.level() == 1)
	992	{
	993	lcA0= lc (A (0, 2));
	994	A *= b.inverse (lcA0);
	995	A= b (A);
	996	for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
	997	i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
	998	}
	999	else
	1000	{
	1001	lcA0= Lc (A (0,2));
[f9da5e]	1002	On (SW_RATIONAL);
	1003	mipoHasDen= !bCommonDen(getMipo(alpha)).isOne();
	1004	Off (SW_RATIONAL);
	1005	CanonicalForm lcA0inverse= b.inverse (lcA0);
[41fea7]	1006	A *= lcA0inverse;
	1007	A= b (A);
	1008	// Lc of bufUniFactors is in Z
	1009	for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
	1010	i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
	1011	}
[eb481b]	1012	}
[7bf145]	1013	bufUniFactors.insert (LC (A, x));
	1014	CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1);
	1015	earlySuccess= false;
	1016	int newLiftBound= 0;
[69076c]	1017
	1018	int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
	1019	int dummy;
[1a3011e]	1020	int * factorsFoundIndex= new int [uniFactors.length()];
	1021	for (int i= 0; i < uniFactors.length(); i++)
	1022	factorsFoundIndex [i]= 0;
	1023
[f9da5e]	1024	CFList bufBufUniFactors;
	1025	Variable v= alpha;
[69076c]	1026	if (smallFactorDeg >= liftBound \|\| degree (A,y) <= 4)
[69fdf90]	1027	henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M, b, true);
[69076c]	1028	else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
[7bf145]	1029	{
[69fdf90]	1030	henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
[f9da5e]	1031	if (mipoHasDen)
	1032	{
	1033	for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
	1034	if (hasFirstAlgVar (iter.getItem(), v))
	1035	break;
	1036	if (v != alpha)
	1037	{
	1038	bufBufUniFactors= bufUniFactors;
	1039	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
	1040	iter.getItem()= replacevar (iter.getItem(), v, alpha);
	1041	A= replacevar (A, alpha, v);
	1042	}
	1043	}
	1044
[7bf145]	1045	if (!extension)
[f9da5e]	1046	{
	1047	if (v==alpha)
	1048	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
	1049	factorsFoundIndex, degs, earlySuccess,
	1050	smallFactorDeg, b);
	1051	else
	1052	earlyFactorDetection(earlyFactors, bufA, bufBufUniFactors, newLiftBound,
	1053	factorsFoundIndex, degs, earlySuccess,
	1054	smallFactorDeg, b);
	1055	}
[7bf145]	1056	else
[69c882]	1057	extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
[1a3011e]	1058	factorsFoundIndex, degs, earlySuccess, info,
	1059	eval, smallFactorDeg);
[69076c]	1060	if (degs.getLength() > 1 && !earlySuccess &&
	1061	smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
[7bf145]	1062	{
[69076c]	1063	if (newLiftBound >= liftPre[sizeOfLiftPre-1]+1)
[7bf145]	1064	{
[69076c]	1065	bufUniFactors.insert (LC (A, x));
	1066	henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
[eb481b]	1067	liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M, b);
[f9da5e]	1068	if (v!=alpha)
	1069	{
	1070	bufBufUniFactors= bufUniFactors;
	1071	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
	1072	iter.getItem()= replacevar (iter.getItem(), v, alpha);
	1073	}
[69076c]	1074	if (!extension)
[f9da5e]	1075	{
	1076	if (v==alpha)
[69c882]	1077	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
[1a3011e]	1078	factorsFoundIndex, degs, earlySuccess,
[eb481b]	1079	liftPre[sizeOfLiftPre-1] + 1, b);
[f9da5e]	1080	else
	1081	earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
	1082	factorsFoundIndex, degs, earlySuccess,
	1083	liftPre[sizeOfLiftPre-1] + 1, b);
	1084	}
[69076c]	1085	else
[f9da5e]	1086	extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
[1a3011e]	1087	factorsFoundIndex, degs, earlySuccess, info,
	1088	eval, liftPre[sizeOfLiftPre-1] + 1);
[7bf145]	1089	}
	1090	}
	1091	else if (earlySuccess)
	1092	liftBound= newLiftBound;
[69076c]	1093
	1094	int i= sizeOfLiftPre - 1;
	1095	while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
	1096	{
	1097	if (newLiftBound >= liftPre[i] + 1)
	1098	{
	1099	bufUniFactors.insert (LC (A, x));
	1100	henselLiftResume12 (A, bufUniFactors, liftPre[i] + 1,
[eb481b]	1101	liftPre[i-1] + 1, Pi, diophant, M, b);
[f9da5e]	1102	if (v!=alpha)
	1103	{
	1104	bufBufUniFactors= bufUniFactors;
	1105	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
	1106	iter.getItem()= replacevar (iter.getItem(), v, alpha);
	1107	}
[69076c]	1108	if (!extension)
[f9da5e]	1109	{
	1110	if (v==alpha)
[69c882]	1111	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
[1a3011e]	1112	factorsFoundIndex, degs, earlySuccess,
[eb481b]	1113	liftPre[i-1] + 1, b);
[f9da5e]	1114	else
	1115	earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
	1116	factorsFoundIndex, degs, earlySuccess,
	1117	liftPre[i-1] + 1, b);
	1118	}
[69076c]	1119	else
[f9da5e]	1120	extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
[1a3011e]	1121	factorsFoundIndex, degs, earlySuccess, info,
	1122	eval, liftPre[i-1] + 1);
[69076c]	1123	}
	1124	else
	1125	{
	1126	liftBound= newLiftBound;
	1127	break;
	1128	}
	1129	i--;
	1130	}
	1131	if (earlySuccess)
	1132	liftBound= newLiftBound;
	1133	//after here all factors are lifted to liftPre[sizeOfLiftPre-1]
[7bf145]	1134	}
[69076c]	1135	else
[806c18]	1136	{
[69fdf90]	1137	henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
[f9da5e]	1138	if (mipoHasDen)
	1139	{
	1140	for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
	1141	if (hasFirstAlgVar (iter.getItem(), v))
	1142	break;
	1143	if (v != alpha)
	1144	{
	1145	bufBufUniFactors= bufUniFactors;
	1146	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
	1147	iter.getItem()= replacevar (iter.getItem(), v, alpha);
	1148	A= replacevar (A, alpha, v);
	1149	}
	1150	}
[7bf145]	1151	if (!extension)
[f9da5e]	1152	{
	1153	if (v==alpha)
[69c882]	1154	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
[1a3011e]	1155	factorsFoundIndex, degs, earlySuccess,
[eb481b]	1156	smallFactorDeg, b);
[f9da5e]	1157	else
	1158	earlyFactorDetection (earlyFactors, bufA, bufBufUniFactors, newLiftBound,
	1159	factorsFoundIndex, degs, earlySuccess,
	1160	smallFactorDeg, b);
	1161	}
[7bf145]	1162	else
[69c882]	1163	extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
[1a3011e]	1164	factorsFoundIndex, degs, earlySuccess, info,
	1165	eval, smallFactorDeg);
[69076c]	1166	int i= 1;
	1167	while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
	1168	i++;
	1169	dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
	1170	if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
[7bf145]	1171	{
	1172	bufUniFactors.insert (LC (A, x));
[69076c]	1173	henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
[eb481b]	1174	dummy, Pi, diophant, M, b);
[f9da5e]	1175	if (v!=alpha)
	1176	{
	1177	bufBufUniFactors= bufUniFactors;
	1178	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
	1179	iter.getItem()= replacevar (iter.getItem(), v, alpha);
	1180	}
[7bf145]	1181	if (!extension)
[f9da5e]	1182	{
	1183	if (v==alpha)
[69c882]	1184	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
[eb481b]	1185	factorsFoundIndex, degs, earlySuccess, dummy, b);
[f9da5e]	1186	else
	1187	earlyFactorDetection (earlyFactors, bufA,bufBufUniFactors, newLiftBound,
	1188	factorsFoundIndex, degs, earlySuccess, dummy, b);
	1189	}
[7bf145]	1190	else
[f9da5e]	1191	extEarlyFactorDetection (earlyFactors, bufA,bufUniFactors, newLiftBound,
[1a3011e]	1192	factorsFoundIndex, degs, earlySuccess, info,
	1193	eval, dummy);
[69076c]	1194	}
	1195	while (degs.getLength() > 1 && !earlySuccess && i < 4)
	1196	{
	1197	if (newLiftBound >= dummy)
[7bf145]	1198	{
[69076c]	1199	bufUniFactors.insert (LC (A, x));
	1200	dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
	1201	henselLiftResume12 (A, bufUniFactors, (degree (A,y)/4)*i + 4,
[eb481b]	1202	dummy, Pi, diophant, M, b);
[f9da5e]	1203	if (v!=alpha)
	1204	{
	1205	bufBufUniFactors= bufUniFactors;
	1206	for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
	1207	iter.getItem()= replacevar (iter.getItem(), v, alpha);
	1208	}
[69076c]	1209	if (!extension)
[f9da5e]	1210	{
	1211	if (v==alpha)
[69c882]	1212	earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
[eb481b]	1213	factorsFoundIndex, degs, earlySuccess, dummy,b);
[f9da5e]	1214	else
	1215	earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
	1216	factorsFoundIndex, degs, earlySuccess, dummy,b);
	1217	}
[69076c]	1218	else
[f9da5e]	1219	extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
[1a3011e]	1220	factorsFoundIndex, degs, earlySuccess, info,
	1221	eval, dummy);
[7bf145]	1222	}
[69076c]	1223	else
	1224	{
[7bf145]	1225	liftBound= newLiftBound;
[69076c]	1226	break;
	1227	}
	1228	i++;
[7bf145]	1229	}
[69076c]	1230	if (earlySuccess)
[7bf145]	1231	liftBound= newLiftBound;
	1232	}
[69076c]	1233
[69c882]	1234	A= bufA;
	1235	if (earlyFactors.length() > 0 && degs.getLength() > 1)
	1236	{
	1237	liftBound= degree (A,y) + 1;
	1238	earlySuccess= true;
	1239	deleteFactors (bufUniFactors, factorsFoundIndex);
	1240	}
	1241
[1a3011e]	1242	delete [] factorsFoundIndex;
[69076c]	1243	delete [] liftPre;
	1244
[7bf145]	1245	return bufUniFactors;
	1246	}
	1247
[69fdf90]	1248	CFList
	1249	henselLiftAndEarly (CanonicalForm& A, bool& earlySuccess, CFList&
	1250	earlyFactors, DegreePattern& degs, int& liftBound,
	1251	const CFList& uniFactors, const ExtensionInfo& info,
	1252	const CanonicalForm& eval)
	1253	{
	1254	modpk dummy= modpk();
	1255	return henselLiftAndEarly (A, earlySuccess, earlyFactors, degs, liftBound,
	1256	uniFactors, info, eval, dummy);
	1257	}
	1258
[11bf82]	1259	long isReduced (const mat_zz_p& M)
[7bf145]	1260	{
[11bf82]	1261	long i, j, nonZero;
	1262	for (i = 1; i <= M.NumRows(); i++)
[7bf145]	1263	{
[11bf82]	1264	nonZero= 0;
	1265	for (j = 1; j <= M.NumCols(); j++)
[7bf145]	1266	{
[11bf82]	1267	if (!IsZero (M (i,j)))
	1268	nonZero++;
[7bf145]	1269	}
[11bf82]	1270	if (nonZero != 1)
	1271	return 0;
[7bf145]	1272	}
[11bf82]	1273	return 1;
	1274	}
[7bf145]	1275
[11bf82]	1276	long isReduced (const mat_zz_pE& M)
	1277	{
	1278	long i, j, nonZero;
	1279	for (i = 1; i <= M.NumRows(); i++)
[806c18]	1280	{
[11bf82]	1281	nonZero= 0;
	1282	for (j = 1; j <= M.NumCols(); j++)
	1283	{
	1284	if (!IsZero (M (i,j)))
[c1b9927]	1285	nonZero++;
[11bf82]	1286	}
	1287	if (nonZero != 1)
	1288	return 0;
[7bf145]	1289	}
[11bf82]	1290	return 1;
	1291	}
[7bf145]	1292
[11bf82]	1293	int * extractZeroOneVecs (const mat_zz_p& M)
	1294	{
	1295	long i, j;
	1296	bool nonZeroOne= false;
	1297	int * result= new int [M.NumCols()];
	1298	for (i = 1; i <= M.NumCols(); i++)
[7bf145]	1299	{
[11bf82]	1300	for (j = 1; j <= M.NumRows(); j++)
	1301	{
	1302	if (!(IsOne (M (j,i)) \|\| IsZero (M (j,i))))
	1303	{
	1304	nonZeroOne= true;
	1305	break;
	1306	}
	1307	}
	1308	if (!nonZeroOne)
	1309	result [i - 1]= 1;
	1310	else
	1311	result [i - 1]= 0;
	1312	nonZeroOne= false;
[7bf145]	1313	}
[11bf82]	1314	return result;
	1315	}
[7bf145]	1316
[11bf82]	1317	int * extractZeroOneVecs (const mat_zz_pE& M)
	1318	{
	1319	long i, j;
	1320	bool nonZeroOne= false;
	1321	int * result= new int [M.NumCols()];
	1322	for (i = 1; i <= M.NumCols(); i++)
[7bf145]	1323	{
[11bf82]	1324	for (j = 1; j <= M.NumRows(); j++)
[7bf145]	1325	{
[11bf82]	1326	if (!(IsOne (M (j,i)) \|\| IsZero (M (j,i))))
	1327	{
	1328	nonZeroOne= true;
	1329	break;
	1330	}
[7bf145]	1331	}
[11bf82]	1332	if (!nonZeroOne)
	1333	result [i - 1]= 1;
	1334	else
	1335	result [i - 1]= 0;
	1336	nonZeroOne= false;
[7bf145]	1337	}
[11bf82]	1338	return result;
	1339	}
	1340
	1341	void
	1342	reconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const CFList&
	1343	factors, const int liftBound, int& factorsFound, int*&
	1344	factorsFoundIndex, mat_zz_pE& N, bool beenInThres
	1345	)
	1346	{
	1347	Variable y= Variable (2);
	1348	Variable x= Variable (1);
	1349	CanonicalForm yToL= power (y, liftBound);
[3ed6758]	1350	if (factors.length() == 2)
	1351	{
[773d28]	1352	CanonicalForm tmp1, tmp2, tmp3;
[3ed6758]	1353	tmp1= factors.getFirst();
	1354	tmp2= factors.getLast();
	1355	tmp1 *= LC (F, x);
	1356	tmp1= mod (tmp1, yToL);
	1357	tmp1 /= content (tmp1, x);
	1358	tmp2 *= LC (F, x);
	1359	tmp2= mod (tmp2, yToL);
	1360	tmp2 /= content (tmp2, x);
[773d28]	1361	tmp3 = tmp1*tmp2;
	1362	if (tmp3/Lc (tmp3) == F/Lc (F))
[3ed6758]	1363	{
	1364	factorsFound++;
	1365	F= 1;
	1366	reconstructedFactors.append (tmp1);
	1367	reconstructedFactors.append (tmp2);
	1368	return;
	1369	}
	1370	}
[38ffb7]	1371	CanonicalForm quot, buf;
	1372	CFListIterator iter;
[11bf82]	1373	for (long i= 1; i <= N.NumCols(); i++)
[7bf145]	1374	{
[11bf82]	1375	if (factorsFoundIndex [i - 1] == 1)
	1376	continue;
[38ffb7]	1377	iter= factors;
[11bf82]	1378	if (beenInThres)
[7bf145]	1379	{
[11bf82]	1380	int count= 1;
	1381	while (count < i)
	1382	{
	1383	count++;
	1384	iter++;
	1385	}
	1386	buf= iter.getItem();
[7bf145]	1387	}
[11bf82]	1388	else
[806c18]	1389	{
[11bf82]	1390	buf= 1;
	1391	for (long j= 1; j <= N.NumRows(); j++, iter++)
	1392	{
	1393	if (!IsZero (N (j,i)))
	1394	buf= mulMod2 (buf, iter.getItem(), yToL);
	1395	}
	1396	}
	1397	buf *= LC (F, x);
	1398	buf= mod (buf, yToL);
	1399	buf /= content (buf, x);
[21b8f4c]	1400	if (fdivides (buf, F, quot))
[11bf82]	1401	{
	1402	factorsFoundIndex[i - 1]= 1;
	1403	factorsFound++;
[21b8f4c]	1404	F= quot;
[11bf82]	1405	F /= Lc (F);
	1406	reconstructedFactors.append (buf);
	1407	}
	1408	if (degree (F) <= 0)
	1409	return;
	1410	if (factorsFound + 1 == N.NumCols())
	1411	{
	1412	reconstructedFactors.append (F);
	1413	return;
[7bf145]	1414	}
	1415	}
[11bf82]	1416	}
[7bf145]	1417
[11bf82]	1418	void
	1419	reconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const CFList&
	1420	factors, const int liftBound, int& factorsFound, int*&
	1421	factorsFoundIndex, mat_zz_p& N, bool beenInThres
	1422	)
	1423	{
	1424	Variable y= Variable (2);
[c1b9927]	1425	Variable x= Variable (1);
[11bf82]	1426	CanonicalForm yToL= power (y, liftBound);
[3ed6758]	1427	if (factors.length() == 2)
	1428	{
[773d28]	1429	CanonicalForm tmp1, tmp2, tmp3;
[3ed6758]	1430	tmp1= factors.getFirst();
	1431	tmp2= factors.getLast();
	1432	tmp1 *= LC (F, x);
	1433	tmp1= mod (tmp1, yToL);
	1434	tmp1 /= content (tmp1, x);
	1435	tmp2 *= LC (F, x);
	1436	tmp2= mod (tmp2, yToL);
	1437	tmp2 /= content (tmp2, x);
[773d28]	1438	tmp3 = tmp1*tmp2;
	1439	if (tmp3/Lc (tmp3) == F/Lc (F))
[3ed6758]	1440	{
	1441	factorsFound++;
	1442	F= 1;
	1443	reconstructedFactors.append (tmp1);
	1444	reconstructedFactors.append (tmp2);
	1445	return;
	1446	}
	1447	}
	1448	CanonicalForm quot, buf;
[38ffb7]	1449	CFListIterator iter;
[11bf82]	1450	for (long i= 1; i <= N.NumCols(); i++)
[7bf145]	1451	{
[11bf82]	1452	if (factorsFoundIndex [i - 1] == 1)
	1453	continue;
[38ffb7]	1454	iter= factors;
[11bf82]	1455	if (beenInThres)
[7bf145]	1456	{
[11bf82]	1457	int count= 1;
	1458	while (count < i)
	1459	{
	1460	count++;
	1461	iter++;
	1462	}
	1463	buf= iter.getItem();
[7bf145]	1464	}
[11bf82]	1465	else
[7bf145]	1466	{
[11bf82]	1467	buf= 1;
	1468	for (long j= 1; j <= N.NumRows(); j++, iter++)
[806c18]	1469	{
[11bf82]	1470	if (!IsZero (N (j,i)))
	1471	buf= mulMod2 (buf, iter.getItem(), yToL);
[7bf145]	1472	}
	1473	}
[11bf82]	1474	buf *= LC (F, x);
	1475	buf= mod (buf, yToL);
	1476	buf /= content (buf, x);
[21b8f4c]	1477	if (fdivides (buf, F, quot))
[7bf145]	1478	{
[11bf82]	1479	factorsFoundIndex[i - 1]= 1;
	1480	factorsFound++;
[21b8f4c]	1481	F= quot;
[11bf82]	1482	F /= Lc (F);
	1483	reconstructedFactors.append (buf);
[7bf145]	1484	}
[11bf82]	1485	if (degree (F) <= 0)
	1486	return;
	1487	if (factorsFound + 1 == N.NumCols())
	1488	{
	1489	reconstructedFactors.append (F);
	1490	return;
	1491	}
	1492	}
	1493	}
[7bf145]	1494
[11bf82]	1495	CFList
	1496	reconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, int
	1497	precision, const mat_zz_pE& N
	1498	)
	1499	{
	1500	Variable y= Variable (2);
	1501	Variable x= Variable (1);
	1502	CanonicalForm F= G;
	1503	CanonicalForm yToL= power (y, precision);
[38ffb7]	1504	CanonicalForm quot, buf;
	1505	CFList result, factorsConsidered;
[11bf82]	1506	CFList bufFactors= factors;
[38ffb7]	1507	CFListIterator iter;
[11bf82]	1508	for (long i= 1; i <= N.NumCols(); i++)
	1509	{
	1510	if (zeroOneVecs [i - 1] == 0)
	1511	continue;
[38ffb7]	1512	iter= factors;
	1513	buf= 1;
[11bf82]	1514	factorsConsidered= CFList();
	1515	for (long j= 1; j <= N.NumRows(); j++, iter++)
	1516	{
	1517	if (!IsZero (N (j,i)))
	1518	{
	1519	factorsConsidered.append (iter.getItem());
	1520	buf= mulMod2 (buf, iter.getItem(), yToL);
	1521	}
	1522	}
	1523	buf *= LC (F, x);
	1524	buf= mod (buf, yToL);
	1525	buf /= content (buf, x);
[21b8f4c]	1526	if (fdivides (buf, F, quot))
[11bf82]	1527	{
[21b8f4c]	1528	F= quot;
[11bf82]	1529	F /= Lc (F);
	1530	result.append (buf);
	1531	bufFactors= Difference (bufFactors, factorsConsidered);
	1532	}
	1533	if (degree (F) <= 0)
	1534	{
	1535	G= F;
	1536	factors= bufFactors;
	1537	return result;
	1538	}
	1539	}
	1540	G= F;
	1541	factors= bufFactors;
	1542	return result;
	1543	}
	1544
	1545	CFList
	1546	monicReconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs,
	1547	int precision, const mat_zz_pE& N
	1548	)
	1549	{
	1550	Variable y= Variable (2);
	1551	Variable x= Variable (1);
	1552	CanonicalForm F= G;
	1553	CanonicalForm yToL= power (y, precision);
[38ffb7]	1554	CanonicalForm quot, buf, buf2;
[11bf82]	1555	CFList result;
	1556	CFList bufFactors= factors;
	1557	CFList factorsConsidered;
[38ffb7]	1558	CFListIterator iter;
[11bf82]	1559	for (long i= 1; i <= N.NumCols(); i++)
	1560	{
	1561	if (zeroOneVecs [i - 1] == 0)
	1562	continue;
[38ffb7]	1563	iter= factors;
	1564	buf= 1;
[11bf82]	1565	factorsConsidered= CFList();
	1566	for (long j= 1; j <= N.NumRows(); j++, iter++)
	1567	{
	1568	if (!IsZero (N (j,i)))
	1569	{
	1570	factorsConsidered.append (iter.getItem());
	1571	buf= mulMod2 (buf, iter.getItem(), yToL);
	1572	}
	1573	}
[38ffb7]	1574	buf2= buf;
[11bf82]	1575	buf *= LC (F, x);
	1576	buf= mod (buf, yToL);
	1577	buf /= content (buf, x);
[21b8f4c]	1578	if (fdivides (buf, F, quot))
[11bf82]	1579	{
[21b8f4c]	1580	F= quot;
[11bf82]	1581	F /= Lc (F);
	1582	result.append (buf2);
	1583	bufFactors= Difference (bufFactors, factorsConsidered);
	1584	}
	1585	if (degree (F) <= 0)
	1586	{
	1587	G= F;
	1588	factors= bufFactors;
	1589	return result;
	1590	}
	1591	}
	1592	G= F;
	1593	factors= bufFactors;
	1594	return result;
	1595	}
	1596
	1597	CFList
	1598	extReconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs, int
	1599	precision, const mat_zz_p& N, const ExtensionInfo& info,
	1600	const CanonicalForm& evaluation
	1601	)
	1602	{
	1603	Variable y= Variable (2);
	1604	Variable x= Variable (1);
	1605	Variable alpha= info.getAlpha();
	1606	Variable beta= info.getBeta();
	1607	int k= info.getGFDegree();
	1608	CanonicalForm gamma= info.getGamma();
	1609	CanonicalForm delta= info.getDelta();
	1610	CanonicalForm F= G;
	1611	CanonicalForm yToL= power (y, precision);
	1612	CFList result;
	1613	CFList bufFactors= factors;
	1614	CFList factorsConsidered;
[38ffb7]	1615	CanonicalForm buf2, quot, buf;
	1616	CFListIterator iter;
[11bf82]	1617	for (long i= 1; i <= N.NumCols(); i++)
	1618	{
	1619	if (zeroOneVecs [i - 1] == 0)
	1620	continue;
[38ffb7]	1621	iter= factors;
	1622	buf= 1;
[11bf82]	1623	factorsConsidered= CFList();
	1624	for (long j= 1; j <= N.NumRows(); j++, iter++)
	1625	{
	1626	if (!IsZero (N (j,i)))
	1627	{
	1628	factorsConsidered.append (iter.getItem());
	1629	buf= mulMod2 (buf, iter.getItem(), yToL);
	1630	}
	1631	}
	1632	buf *= LC (F, x);
	1633	buf= mod (buf, yToL);
	1634	buf /= content (buf, x);
	1635	buf2= buf (y-evaluation, y);
[a54114]	1636	if (!k && beta == x)
[11bf82]	1637	{
	1638	if (degree (buf2, alpha) < 1)
	1639	{
[21b8f4c]	1640	if (fdivides (buf, F, quot))
[11bf82]	1641	{
[21b8f4c]	1642	F= quot;
[11bf82]	1643	F /= Lc (F);
	1644	result.append (buf2);
	1645	bufFactors= Difference (bufFactors, factorsConsidered);
	1646	}
	1647	}
	1648	}
	1649	else
	1650	{
	1651	CFList source, dest;
[c1b9927]	1652
[11bf82]	1653	if (!isInExtension (buf2, gamma, k, delta, source, dest))
	1654	{
[21b8f4c]	1655	if (fdivides (buf, F, quot))
[11bf82]	1656	{
[21b8f4c]	1657	F= quot;
[11bf82]	1658	F /= Lc (F);
	1659	result.append (buf2);
	1660	bufFactors= Difference (bufFactors, factorsConsidered);
	1661	}
	1662	}
	1663	}
	1664	if (degree (F) <= 0)
	1665	{
	1666	G= F;
	1667	factors= bufFactors;
	1668	return result;
	1669	}
	1670	}
	1671	G= F;
	1672	factors= bufFactors;
	1673	return result;
	1674	}
	1675
	1676	CFList
	1677	reconstruction (CanonicalForm& G, CFList& factors, int* zeroOneVecs,
	1678	int precision, const mat_zz_p& N)
	1679	{
	1680	Variable y= Variable (2);
	1681	Variable x= Variable (1);
	1682	CanonicalForm F= G;
	1683	CanonicalForm yToL= power (y, precision);
[38ffb7]	1684	CanonicalForm quot, buf;
[11bf82]	1685	CFList result;
	1686	CFList bufFactors= factors;
	1687	CFList factorsConsidered;
[38ffb7]	1688	CFListIterator iter;
[11bf82]	1689	for (long i= 1; i <= N.NumCols(); i++)
	1690	{
	1691	if (zeroOneVecs [i - 1] == 0)
	1692	continue;
[38ffb7]	1693	iter= factors;
	1694	buf= 1;
[11bf82]	1695	factorsConsidered= CFList();
	1696	for (long j= 1; j <= N.NumRows(); j++, iter++)
	1697	{
	1698	if (!IsZero (N (j,i)))
	1699	{
	1700	factorsConsidered.append (iter.getItem());
	1701	buf= mulMod2 (buf, iter.getItem(), yToL);
	1702	}
	1703	}
	1704	buf *= LC (F, x);
	1705	buf= mod (buf, yToL);
	1706	buf /= content (buf, x);
[21b8f4c]	1707	if (fdivides (buf, F, quot))
[11bf82]	1708	{
[21b8f4c]	1709	F= quot;
[11bf82]	1710	F /= Lc (F);
	1711	result.append (buf);
	1712	bufFactors= Difference (bufFactors, factorsConsidered);
	1713	}
	1714	if (degree (F) <= 0)
	1715	{
	1716	G= F;
	1717	factors= bufFactors;
	1718	return result;
	1719	}
	1720	}
	1721	G= F;
	1722	factors= bufFactors;
	1723	return result;
	1724	}
	1725
	1726	void
[c1b9927]	1727	extReconstructionTry (CFList& reconstructedFactors, CanonicalForm& F, const
[11bf82]	1728	CFList& factors, const int liftBound, int& factorsFound,
	1729	int*& factorsFoundIndex, mat_zz_p& N, bool beenInThres,
	1730	const ExtensionInfo& info, const CanonicalForm& evaluation
	1731	)
	1732	{
	1733	Variable y= Variable (2);
	1734	Variable x= Variable (1);
	1735	Variable alpha= info.getAlpha();
	1736	Variable beta= info.getBeta();
	1737	int k= info.getGFDegree();
	1738	CanonicalForm gamma= info.getGamma();
	1739	CanonicalForm delta= info.getDelta();
	1740	CanonicalForm yToL= power (y, liftBound);
	1741	CFList source, dest;
[3ed6758]	1742	if (factors.length() == 2)
	1743	{
[773d28]	1744	CanonicalForm tmp1, tmp2, tmp3;
[3ed6758]	1745	tmp1= factors.getFirst();
	1746	tmp2= factors.getLast();
	1747	tmp1 *= LC (F, x);
	1748	tmp1= mod (tmp1, yToL);
	1749	tmp1 /= content (tmp1, x);
	1750	tmp2 *= LC (F, x);
	1751	tmp2= mod (tmp2, yToL);
	1752	tmp2 /= content (tmp2, x);
[773d28]	1753	tmp3 = tmp1*tmp2;
	1754	if (tmp3/Lc (tmp3) == F/Lc (F))
[3ed6758]	1755	{
	1756	tmp1= tmp1 (y - evaluation, y);
	1757	tmp2= tmp2 (y - evaluation, y);
[773d28]	1758	if (!k && beta == x && degree (tmp2, alpha) < 1 &&
	1759	degree (tmp1, alpha) < 1)
	1760	{
	1761	factorsFound++;
	1762	F= 1;
	1763	tmp1= mapDown (tmp1, info, source, dest);
	1764	tmp2= mapDown (tmp2, info, source, dest);
	1765	reconstructedFactors.append (tmp1);
	1766	reconstructedFactors.append (tmp2);
	1767	return;
	1768	}
	1769	else if (!isInExtension (tmp2, gamma, k, delta, source, dest) &&
	1770	!isInExtension (tmp1, gamma, k, delta, source, dest))
	1771	{
	1772	factorsFound++;
	1773	F= 1;
	1774	tmp1= mapDown (tmp1, info, source, dest);
	1775	tmp2= mapDown (tmp2, info, source, dest);
	1776	reconstructedFactors.append (tmp1);
	1777	reconstructedFactors.append (tmp2);
	1778	return;
	1779	}
[3ed6758]	1780	}
	1781	}
	1782	CanonicalForm quot, buf, buf2;
[38ffb7]	1783	CFListIterator iter;
[11bf82]	1784	for (long i= 1; i <= N.NumCols(); i++)
	1785	{
	1786	if (factorsFoundIndex [i - 1] == 1)
	1787	continue;
[38ffb7]	1788	iter= factors;
[11bf82]	1789	if (beenInThres)
	1790	{
	1791	int count= 1;
	1792	while (count < i)
	1793	{
	1794	count++;
	1795	iter++;
	1796	}
	1797	buf= iter.getItem();
	1798	}
	1799	else
	1800	{
	1801	buf= 1;
	1802	for (long j= 1; j <= N.NumRows(); j++, iter++)
	1803	{
	1804	if (!IsZero (N (j,i)))
	1805	buf= mulMod2 (buf, iter.getItem(), yToL);
	1806	}
	1807	}
	1808	buf *= LC (F, x);
	1809	buf= mod (buf, yToL);
	1810	buf /= content (buf, x);
	1811	buf2= buf (y - evaluation, y);
[a54114]	1812	if (!k && beta == x)
[11bf82]	1813	{
	1814	if (degree (buf2, alpha) < 1)
	1815	{
[21b8f4c]	1816	if (fdivides (buf, F, quot))
[11bf82]	1817	{
	1818	factorsFoundIndex[i - 1]= 1;
	1819	factorsFound++;
[21b8f4c]	1820	F= quot;
[11bf82]	1821	F /= Lc (F);
	1822	buf2= mapDown (buf2, info, source, dest);
	1823	reconstructedFactors.append (buf2);
	1824	}
	1825	}
	1826	}
	1827	else
	1828	{
	1829	if (!isInExtension (buf2, gamma, k, delta, source, dest))
	1830	{
[21b8f4c]	1831	if (fdivides (buf, F, quot))
[11bf82]	1832	{
	1833	factorsFoundIndex[i - 1]= 1;
	1834	factorsFound++;
[21b8f4c]	1835	F= quot;
[11bf82]	1836	F /= Lc (F);
	1837	buf2= mapDown (buf2, info, source, dest);
	1838	reconstructedFactors.append (buf2);
	1839	}
	1840	}
	1841	}
	1842	if (degree (F) <= 0)
	1843	return;
	1844	if (factorsFound + 1 == N.NumCols())
	1845	{
	1846	CanonicalForm tmp= F (y - evaluation, y);
	1847	tmp= mapDown (tmp, info, source, dest);
	1848	reconstructedFactors.append (tmp);
	1849	return;
	1850	}
	1851	}
	1852	}
	1853
	1854	//over Fp
	1855	int
	1856	liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds, int
	1857	start, int liftBound, int minBound, CFList& factors,
	1858	mat_zz_p& NTLN, CFList& diophant, CFMatrix& M, CFArray&
	1859	Pi, CFArray& bufQ, bool& irreducible
	1860	)
	1861	{
	1862	CanonicalForm LCF= LC (F, 1);
	1863	CFArray *A= new CFArray [factors.length() - 1];
	1864	bool wasInBounds= false;
	1865	bool hitBound= false;
	1866	int l= (minBound+1)*2;
	1867	int stepSize= 2;
	1868	int oldL= l/2;
	1869	bool reduced= false;
[38ffb7]	1870	mat_zz_p NTLK, *NTLC;
	1871	CFMatrix C;
	1872	CFArray buf;
	1873	CFListIterator j;
[5335ba]	1874	CanonicalForm truncF;
	1875	Variable y= F.mvar();
[11bf82]	1876	while (l <= liftBound)
	1877	{
	1878	if (start)
	1879	{
	1880	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
	1881	start= 0;
	1882	}
	1883	else
	1884	{
	1885	if (wasInBounds)
	1886	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
	1887	else
	1888	henselLift12 (F, factors, l, Pi, diophant, M);
	1889	}
	1890
	1891	factors.insert (LCF);
[38ffb7]	1892	j= factors;
[11bf82]	1893	j++;
	1894
[5335ba]	1895	truncF= mod (F, power (y, l));
[11bf82]	1896	for (int i= 0; i < factors.length() - 1; i++, j++)
	1897	{
	1898	if (!wasInBounds)
[5335ba]	1899	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
[11bf82]	1900	else
[5335ba]	1901	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
	1902	bufQ[i]);
[11bf82]	1903	}
	1904
	1905	for (int i= 0; i < sizeBounds; i++)
	1906	{
	1907	if (bounds [i] + 1 <= l/2)
	1908	{
	1909	wasInBounds= true;
	1910	int k= tmin (bounds [i] + 1, l/2);
[38ffb7]	1911	C= CFMatrix (l - k, factors.length() - 1);
[11bf82]	1912	for (int ii= 0; ii < factors.length() - 1; ii++)
	1913	{
	1914	if (A[ii].size() - 1 >= i)
[9ebec2]	1915	{
[11bf82]	1916	buf= getCoeffs (A[ii] [i], k);
[9ebec2]	1917	writeInMatrix (C, buf, ii + 1, 0);
	1918	}
[11bf82]	1919	}
[38ffb7]	1920	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
	1921	NTLK= (NTLC)NTLN;
[11bf82]	1922	transpose (NTLK, NTLK);
	1923	kernel (NTLK, NTLK);
	1924	transpose (NTLK, NTLK);
	1925	NTLN *= NTLK;
	1926
	1927	if (NTLN.NumCols() == 1)
	1928	{
	1929	irreducible= true;
	1930	break;
	1931	}
[3426de2]	1932	if (isReduced (NTLN) && l > (minBound+1)*2)
[11bf82]	1933	{
	1934	reduced= true;
	1935	break;
	1936	}
	1937	}
	1938	}
	1939
	1940	if (irreducible)
	1941	break;
	1942	if (reduced)
	1943	break;
	1944	oldL= l;
	1945	l += stepSize;
	1946	stepSize *= 2;
	1947	if (l > liftBound)
	1948	{
	1949	if (!hitBound)
	1950	{
	1951	l= liftBound;
	1952	hitBound= true;
	1953	}
	1954	else
	1955	break;
	1956	}
	1957	}
	1958	delete [] A;
	1959	return l;
	1960	}
	1961
	1962	//over field extension
	1963	int
	1964	extLiftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds,
	1965	int liftBound, int minBound, int start, CFList&
	1966	factors, mat_zz_p& NTLN, CFList& diophant,
	1967	CFMatrix& M, CFArray& Pi, CFArray& bufQ, bool&
	1968	irreducible, const CanonicalForm& evaluation, const
	1969	ExtensionInfo& info, CFList& source, CFList& dest
	1970	)
	1971	{
	1972	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
	1973	CanonicalForm LCF= LC (F, 1);
	1974	CFArray *A= new CFArray [factors.length() - 1];
	1975	bool wasInBounds= false;
	1976	bool hitBound= false;
	1977	int degMipo;
	1978	Variable alpha;
	1979	alpha= info.getAlpha();
	1980	degMipo= degree (getMipo (alpha));
	1981
	1982	Variable gamma= info.getBeta();
	1983	CanonicalForm primElemAlpha= info.getGamma();
	1984	CanonicalForm imPrimElemAlpha= info.getDelta();
	1985
	1986	int stepSize= 2;
	1987	int l= ((minBound+1)/degMipo+1)*2;
	1988	l= tmax (l, 2);
	1989	if (start > l)
	1990	l= start;
	1991	int oldL= l/2;
	1992	bool reduced= false;
[38ffb7]	1993	Variable y= F.mvar();
	1994	Variable x= Variable (1);
[5335ba]	1995	CanonicalForm powX, imBasis, truncF;
[38ffb7]	1996	CFMatrix Mat, C;
	1997	CFArray buf;
	1998	CFIterator iter;
	1999	mat_zz_p* NTLMat, *NTLC, NTLK;
	2000	CFListIterator j;
[11bf82]	2001	while (l <= liftBound)
	2002	{
	2003	if (start)
	2004	{
	2005	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
	2006	start= 0;
	2007	}
	2008	else
	2009	{
	2010	if (wasInBounds)
	2011	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
	2012	else
	2013	henselLift12 (F, factors, l, Pi, diophant, M);
	2014	}
	2015
	2016	factors.insert (LCF);
	2017
	2018	if (GF)
	2019	setCharacteristic (getCharacteristic());
	2020
[38ffb7]	2021	powX= power (y-gamma, l);
	2022	Mat= CFMatrix (ldegMipo, ldegMipo);
[11bf82]	2023	for (int i= 0; i < l*degMipo; i++)
	2024	{
[38ffb7]	2025	imBasis= mod (power (y, i), powX);
[11bf82]	2026	imBasis= imBasis (power (y, degMipo), y);
	2027	imBasis= imBasis (y, gamma);
[38ffb7]	2028	iter= imBasis;
[11bf82]	2029	for (; iter.hasTerms(); iter++)
	2030	Mat (iter.exp()+ 1, i+1)= iter.coeff();
	2031	}
	2032
[38ffb7]	2033	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
[11bf82]	2034	NTLMat= inv (NTLMat);
	2035
	2036	if (GF)
	2037	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
	2038
[38ffb7]	2039	j= factors;
[11bf82]	2040	j++;
	2041
[5335ba]	2042	truncF= mod (F, power (y, l));
[11bf82]	2043	for (int i= 0; i < factors.length() - 1; i++, j++)
	2044	{
	2045	if (!wasInBounds)
[5335ba]	2046	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
[11bf82]	2047	else
[5335ba]	2048	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
	2049	bufQ[i]);
[11bf82]	2050	}
	2051
	2052	for (int i= 0; i < sizeBounds; i++)
	2053	{
	2054	if (bounds [i] + 1 <= (l/2)*degMipo)
	2055	{
	2056	wasInBounds= true;
	2057	int k= tmin (bounds [i] + 1, (l/2)*degMipo);
[38ffb7]	2058	C= CFMatrix (l*degMipo - k, factors.length() - 1);
[11bf82]	2059
	2060	for (int ii= 0; ii < factors.length() - 1; ii++)
	2061	{
	2062	if (A[ii].size() - 1 >= i)
	2063	{
	2064	if (GF)
	2065	{
	2066	A [ii] [i]= A [ii] [i] (y-evaluation, y);
	2067	setCharacteristic (getCharacteristic());
	2068	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
	2069	if (alpha != gamma)
	2070	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
	2071	gamma, source, dest
	2072	);
	2073	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
	2074	}
	2075	else
	2076	{
	2077	A [ii] [i]= A [ii] [i] (y-evaluation, y);
	2078	if (alpha != gamma)
	2079	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
	2080	gamma, source, dest
	2081	);
	2082	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
	2083	}
[9ebec2]	2084	writeInMatrix (C, buf, ii + 1, 0);
[11bf82]	2085	}
	2086	if (GF)
	2087	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
	2088	}
	2089
	2090	if (GF)
	2091	setCharacteristic(getCharacteristic());
	2092
[38ffb7]	2093	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
	2094	NTLK= (NTLC)NTLN;
[11bf82]	2095	transpose (NTLK, NTLK);
	2096	kernel (NTLK, NTLK);
	2097	transpose (NTLK, NTLK);
	2098	NTLN *= NTLK;
	2099
	2100	if (GF)
	2101	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
	2102
	2103	if (NTLN.NumCols() == 1)
	2104	{
	2105	irreducible= true;
	2106	break;
	2107	}
[6f0279]	2108	if (isReduced (NTLN))
[11bf82]	2109	{
	2110	reduced= true;
	2111	break;
	2112	}
	2113	}
	2114	}
	2115
	2116	if (NTLN.NumCols() == 1)
	2117	{
	2118	irreducible= true;
	2119	break;
	2120	}
	2121	if (reduced)
	2122	break;
	2123	oldL= l;
	2124	l += stepSize;
	2125	stepSize *= 2;
	2126	if (l > liftBound)
	2127	{
	2128	if (!hitBound)
	2129	{
	2130	l= liftBound;
	2131	hitBound= true;
	2132	}
	2133	else
	2134	break;
	2135	}
	2136	}
	2137	delete [] A;
	2138	return l;
	2139	}
	2140
	2141	// over Fq
	2142	int
	2143	liftAndComputeLattice (const CanonicalForm& F, int* bounds, int sizeBounds,
	2144	int start, int liftBound, int minBound, CFList& factors,
	2145	mat_zz_pE& NTLN, CFList& diophant, CFMatrix& M, CFArray&
	2146	Pi, CFArray& bufQ, bool& irreducible
	2147	)
	2148	{
	2149	CanonicalForm LCF= LC (F, 1);
	2150	CFArray *A= new CFArray [factors.length() - 1];
	2151	bool wasInBounds= false;
	2152	bool hitBound= false;
	2153	int l= (minBound+1)*2;
	2154	int stepSize= 2;
	2155	int oldL= l/2;
	2156	bool reduced= false;
[38ffb7]	2157	CFListIterator j;
	2158	mat_zz_pE* NTLC, NTLK;
	2159	CFArray buf;
	2160	CFMatrix C;
[5335ba]	2161	Variable y= F.mvar();
	2162	CanonicalForm truncF;
[11bf82]	2163	while (l <= liftBound)
	2164	{
	2165	if (start)
	2166	{
	2167	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
	2168	start= 0;
	2169	}
	2170	else
	2171	{
	2172	if (wasInBounds)
	2173	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
	2174	else
	2175	henselLift12 (F, factors, l, Pi, diophant, M);
	2176	}
	2177
	2178	factors.insert (LCF);
[38ffb7]	2179	j= factors;
[11bf82]	2180	j++;
	2181
[5335ba]	2182	truncF= mod (F, power (y,l));
[11bf82]	2183	for (int i= 0; i < factors.length() - 1; i++, j++)
	2184	{
	2185	if (l == (minBound+1)*2)
	2186	{
[5335ba]	2187	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
[11bf82]	2188	}
	2189	else
	2190	{
[5335ba]	2191	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
[11bf82]	2192	bufQ[i]
	2193	);
	2194	}
	2195	}
	2196
	2197	for (int i= 0; i < sizeBounds; i++)
	2198	{
	2199	if (bounds [i] + 1 <= l/2)
	2200	{
	2201	wasInBounds= true;
	2202	int k= tmin (bounds [i] + 1, l/2);
[38ffb7]	2203	C= CFMatrix (l - k, factors.length() - 1);
[11bf82]	2204	for (int ii= 0; ii < factors.length() - 1; ii++)
	2205	{
[38ffb7]	2206
[11bf82]	2207	if (A[ii].size() - 1 >= i)
[9ebec2]	2208	{
[11bf82]	2209	buf= getCoeffs (A[ii] [i], k);
[9ebec2]	2210	writeInMatrix (C, buf, ii + 1, 0);
	2211	}
[11bf82]	2212	}
	2213
[38ffb7]	2214	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
	2215	NTLK= (NTLC)NTLN;
[11bf82]	2216	transpose (NTLK, NTLK);
	2217	kernel (NTLK, NTLK);
	2218	transpose (NTLK, NTLK);
	2219	NTLN *= NTLK;
	2220
	2221	if (NTLN.NumCols() == 1)
	2222	{
	2223	irreducible= true;
	2224	break;
	2225	}
[3426de2]	2226	if (isReduced (NTLN) && l > (minBound+1)*2)
[11bf82]	2227	{
	2228	reduced= true;
	2229	break;
	2230	}
	2231	}
	2232	}
	2233
	2234	if (NTLN.NumCols() == 1)
	2235	{
	2236	irreducible= true;
	2237	break;
	2238	}
	2239	if (reduced)
	2240	break;
	2241	oldL= l;
	2242	l += stepSize;
	2243	stepSize *= 2;
	2244	if (l > liftBound)
	2245	{
	2246	if (!hitBound)
	2247	{
	2248	l= liftBound;
	2249	hitBound= true;
	2250	}
	2251	else
	2252	break;
	2253	}
	2254	}
	2255	delete [] A;
	2256	return l;
	2257	}
	2258
	2259	int
	2260	liftAndComputeLatticeFq2Fp (const CanonicalForm& F, int* bounds, int sizeBounds,
	2261	int start, int liftBound, int minBound, CFList&
	2262	factors, mat_zz_p& NTLN, CFList& diophant, CFMatrix&
	2263	M, CFArray& Pi, CFArray& bufQ, bool& irreducible,
	2264	const Variable& alpha
	2265	)
	2266	{
	2267	CanonicalForm LCF= LC (F, 1);
	2268	CFArray *A= new CFArray [factors.length() - 1];
	2269	bool wasInBounds= false;
	2270	int l= (minBound+1)*2;
	2271	int oldL= l/2;
	2272	int stepSize= 2;
	2273	bool hitBound= false;
	2274	int extensionDeg= degree (getMipo (alpha));
	2275	bool reduced= false;
[38ffb7]	2276	CFListIterator j;
	2277	CFMatrix C;
	2278	CFArray buf;
	2279	mat_zz_p* NTLC, NTLK;
[5335ba]	2280	Variable y= F.mvar();
	2281	CanonicalForm truncF;
[11bf82]	2282	while (l <= liftBound)
	2283	{
	2284	if (start)
	2285	{
	2286	henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
	2287	start= 0;
	2288	}
	2289	else
	2290	{
	2291	if (wasInBounds)
	2292	henselLiftResume12 (F, factors, oldL, l, Pi, diophant, M);
	2293	else
	2294	henselLift12 (F, factors, l, Pi, diophant, M);
	2295	}
	2296
	2297	factors.insert (LCF);
[38ffb7]	2298	j= factors;
[11bf82]	2299	j++;
	2300
[5335ba]	2301	truncF= mod (F, power (y,l));
[11bf82]	2302	for (int i= 0; i < factors.length() - 1; i++, j++)
	2303	{
	2304	if (l == (minBound+1)*2)
	2305	{
[5335ba]	2306	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
[11bf82]	2307	}
	2308	else
	2309	{
[5335ba]	2310	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
[11bf82]	2311	bufQ[i]
	2312	);
	2313	}
	2314	}
	2315
	2316	for (int i= 0; i < sizeBounds; i++)
	2317	{
	2318	if (bounds [i] + 1 <= l/2)
	2319	{
	2320	wasInBounds= true;
	2321	int k= tmin (bounds [i] + 1, l/2);
[38ffb7]	2322	C= CFMatrix ((l - k)*extensionDeg, factors.length() - 1);
[11bf82]	2323	for (int ii= 0; ii < factors.length() - 1; ii++)
	2324	{
	2325	if (A[ii].size() - 1 >= i)
[9ebec2]	2326	{
[11bf82]	2327	buf= getCoeffs (A[ii] [i], k, alpha);
[9ebec2]	2328	writeInMatrix (C, buf, ii + 1, 0);
	2329	}
[11bf82]	2330	}
	2331
[38ffb7]	2332	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
	2333	NTLK= (NTLC)NTLN;
[11bf82]	2334	transpose (NTLK, NTLK);
	2335	kernel (NTLK, NTLK);
	2336	transpose (NTLK, NTLK);
	2337	NTLN *= NTLK;
	2338
	2339	if (NTLN.NumCols() == 1)
	2340	{
	2341	irreducible= true;
	2342	break;
	2343	}
[3426de2]	2344	if (isReduced (NTLN) && l > (minBound+1)*2)
[11bf82]	2345	{
	2346	reduced= true;
	2347	break;
	2348	}
	2349	}
	2350	}
	2351
	2352	if (NTLN.NumCols() == 1)
	2353	{
	2354	irreducible= true;
	2355	break;
	2356	}
	2357	if (reduced)
	2358	break;
	2359	oldL= l;
	2360	l += stepSize;
	2361	stepSize *= 2;
	2362	if (l > liftBound)
	2363	{
	2364	if (!hitBound)
	2365	{
	2366	l= liftBound;
	2367	hitBound= true;
	2368	}
	2369	else
	2370	break;
	2371	}
	2372	}
	2373	delete [] A;
	2374	return l;
	2375	}
	2376
	2377	CFList
	2378	increasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
	2379	int oldNumCols, int oldL, int precision
	2380	)
	2381	{
	2382	int d;
[542864]	2383	bool isIrreducible= false;
	2384	int* bounds= computeBounds (F, d, isIrreducible);
	2385	if (isIrreducible)
	2386	{
	2387	delete [] bounds;
	2388	CanonicalForm G= F;
	2389	F= 1;
	2390	return CFList (G);
	2391	}
[11bf82]	2392	CFArray * A= new CFArray [factors.length()];
	2393	CFArray bufQ= CFArray (factors.length());
	2394	mat_zz_p NTLN;
	2395	ident (NTLN, factors.length());
	2396	int minBound= bounds[0];
	2397	for (int i= 1; i < d; i++)
	2398	{
	2399	if (bounds[i] != 0)
	2400	minBound= tmin (minBound, bounds[i]);
	2401	}
	2402	int l= tmax (2*(minBound + 1), oldL);
	2403	int oldL2= l/2;
	2404	int stepSize= 2;
	2405	bool useOldQs= false;
	2406	bool hitBound= false;
[38ffb7]	2407	CFListIterator j;
	2408	CFMatrix C;
	2409	CFArray buf;
	2410	mat_zz_p* NTLC, NTLK;
[5335ba]	2411	Variable y= F.mvar();
	2412	CanonicalForm truncF;
[11bf82]	2413	while (l <= precision)
	2414	{
[38ffb7]	2415	j= factors;
[5335ba]	2416	truncF= mod (F, power (y,l));
[11bf82]	2417	if (useOldQs)
	2418	{
	2419	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	2420	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
[11bf82]	2421	bufQ[i]
	2422	);
	2423	}
	2424	else
	2425	{
	2426	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	2427	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
[11bf82]	2428	}
	2429	useOldQs= true;
	2430	for (int i= 0; i < d; i++)
	2431	{
	2432	if (bounds [i] + 1 <= l/2)
	2433	{
	2434	int k= tmin (bounds [i] + 1, l/2);
[38ffb7]	2435	C= CFMatrix (l - k, factors.length());
[11bf82]	2436	for (int ii= 0; ii < factors.length(); ii++)
	2437	{
	2438	if (A[ii].size() - 1 >= i)
[9ebec2]	2439	{
[11bf82]	2440	buf= getCoeffs (A[ii] [i], k);
[9ebec2]	2441	writeInMatrix (C, buf, ii + 1, 0);
	2442	}
[11bf82]	2443	}
[38ffb7]	2444	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
	2445	NTLK= (NTLC)NTLN;
[11bf82]	2446	transpose (NTLK, NTLK);
	2447	kernel (NTLK, NTLK);
	2448	transpose (NTLK, NTLK);
	2449	NTLN *= NTLK;
	2450	if (NTLN.NumCols() == 1)
	2451	{
	2452	delete [] A;
	2453	delete [] bounds;
	2454	CanonicalForm G= F;
	2455	F= 1;
	2456	return CFList (G);
	2457	}
	2458	}
	2459	}
	2460
	2461	if (NTLN.NumCols() < oldNumCols - factorsFound)
	2462	{
	2463	if (isReduced (NTLN))
	2464	{
	2465	int * factorsFoundIndex= new int [NTLN.NumCols()];
	2466	for (long i= 0; i < NTLN.NumCols(); i++)
	2467	factorsFoundIndex[i]= 0;
	2468	int factorsFound2= 0;
	2469	CFList result;
	2470	CanonicalForm bufF= F;
	2471	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
	2472	factorsFoundIndex, NTLN, false
	2473	);
[38ffb7]	2474	if (result.length() == NTLN.NumCols())
[11bf82]	2475	{
	2476	delete [] factorsFoundIndex;
	2477	delete [] A;
	2478	delete [] bounds;
[3d0075]	2479	F= 1;
[11bf82]	2480	return result;
	2481	}
	2482	delete [] factorsFoundIndex;
	2483	}
	2484	else if (l == precision)
	2485	{
	2486	CanonicalForm bufF= F;
	2487	int * zeroOne= extractZeroOneVecs (NTLN);
	2488	CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
	2489	F= bufF;
	2490	delete [] zeroOne;
	2491	delete [] A;
	2492	delete [] bounds;
	2493	return result;
	2494	}
	2495	}
	2496	oldL2= l;
	2497	l += stepSize;
	2498	stepSize *= 2;
	2499	if (l > precision)
	2500	{
	2501	if (!hitBound)
	2502	{
	2503	l= precision;
	2504	hitBound= true;
	2505	}
	2506	else
	2507	break;
	2508	}
	2509	}
	2510	delete [] bounds;
	2511	delete [] A;
	2512	return CFList();
	2513	}
	2514
	2515	CFList
	2516	increasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
[0349c20]	2517	int oldNumCols, int oldL, const Variable&,
[11bf82]	2518	int precision
	2519	)
	2520	{
	2521	int d;
[542864]	2522	bool isIrreducible= false;
	2523	int* bounds= computeBounds (F, d, isIrreducible);
	2524	if (isIrreducible)
	2525	{
	2526	delete [] bounds;
	2527	CanonicalForm G= F;
	2528	F= 1;
	2529	return CFList (G);
	2530	}
[11bf82]	2531	CFArray * A= new CFArray [factors.length()];
	2532	CFArray bufQ= CFArray (factors.length());
	2533	mat_zz_pE NTLN;
	2534	ident (NTLN, factors.length());
	2535	int minBound= bounds[0];
	2536	for (int i= 1; i < d; i++)
	2537	{
	2538	if (bounds[i] != 0)
	2539	minBound= tmin (minBound, bounds[i]);
	2540	}
	2541	int l= tmax (2*(minBound + 1), oldL);
	2542	int oldL2= l/2;
	2543	int stepSize= 2;
	2544	bool useOldQs= false;
	2545	bool hitBound= false;
[38ffb7]	2546	CFListIterator j;
	2547	CFMatrix C;
	2548	mat_zz_pE* NTLC, NTLK;
	2549	CFArray buf;
[5335ba]	2550	Variable y= F.mvar();
	2551	CanonicalForm truncF;
[11bf82]	2552	while (l <= precision)
	2553	{
[38ffb7]	2554	j= factors;
[5335ba]	2555	truncF= mod (F, power (y,l));
[11bf82]	2556	if (useOldQs)
	2557	{
	2558	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	2559	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
[11bf82]	2560	bufQ[i]
	2561	);
	2562	}
	2563	else
	2564	{
	2565	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	2566	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
[11bf82]	2567	}
	2568	useOldQs= true;
	2569	for (int i= 0; i < d; i++)
	2570	{
	2571	if (bounds [i] + 1 <= l/2)
	2572	{
	2573	int k= tmin (bounds [i] + 1, l/2);
[38ffb7]	2574	C= CFMatrix (l - k, factors.length());
[11bf82]	2575	for (int ii= 0; ii < factors.length(); ii++)
	2576	{
	2577	if (A[ii].size() - 1 >= i)
[9ebec2]	2578	{
[11bf82]	2579	buf= getCoeffs (A[ii] [i], k);
[9ebec2]	2580	writeInMatrix (C, buf, ii + 1, 0);
	2581	}
[11bf82]	2582	}
[38ffb7]	2583	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
	2584	NTLK= (NTLC)NTLN;
[11bf82]	2585	transpose (NTLK, NTLK);
	2586	kernel (NTLK, NTLK);
	2587	transpose (NTLK, NTLK);
	2588	NTLN *= NTLK;
	2589	if (NTLN.NumCols() == 1)
	2590	{
	2591	delete [] A;
	2592	delete [] bounds;
[542864]	2593	CanonicalForm G= F;
	2594	F= 1;
	2595	return CFList (G);
[11bf82]	2596	}
	2597	}
	2598	}
	2599
	2600	if (NTLN.NumCols() < oldNumCols - factorsFound)
	2601	{
	2602	if (isReduced (NTLN))
	2603	{
	2604	int * factorsFoundIndex= new int [NTLN.NumCols()];
	2605	for (long i= 0; i < NTLN.NumCols(); i++)
	2606	factorsFoundIndex[i]= 0;
	2607	int factorsFound2= 0;
	2608	CFList result;
	2609	CanonicalForm bufF= F;
	2610	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
	2611	factorsFoundIndex, NTLN, false);
	2612	if (result.length() == NTLN.NumCols())
	2613	{
	2614	delete [] factorsFoundIndex;
	2615	delete [] A;
	2616	delete [] bounds;
[3d0075]	2617	F= 1;
[11bf82]	2618	return result;
	2619	}
	2620	delete [] factorsFoundIndex;
	2621	}
	2622	else if (l == precision)
	2623	{
	2624	CanonicalForm bufF= F;
	2625	int * zeroOne= extractZeroOneVecs (NTLN);
	2626	CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
	2627	F= bufF;
	2628	delete [] zeroOne;
	2629	delete [] A;
	2630	delete [] bounds;
	2631	return result;
	2632	}
	2633	}
	2634	oldL2= l;
	2635	l += stepSize;
	2636	stepSize *= 2;
	2637	if (l > precision)
	2638	{
	2639	if (!hitBound)
	2640	{
	2641	l= precision;
	2642	hitBound= true;
	2643	}
	2644	else
	2645	break;
	2646	}
	2647	}
	2648	delete [] bounds;
	2649	delete [] A;
	2650	return CFList();
	2651	}
	2652
	2653	//over field extension
	2654	CFList
	2655	extIncreasePrecision (CanonicalForm& F, CFList& factors, int factorsFound,
	2656	int oldNumCols, int oldL, const CanonicalForm& evaluation,
	2657	const ExtensionInfo& info, CFList& source, CFList& dest,
	2658	int precision
	2659	)
	2660	{
	2661	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
	2662	int degMipo= degree (getMipo (info.getAlpha()));
	2663	Variable alpha= info.getAlpha();
	2664	int d;
[542864]	2665	bool isIrreducible= false;
	2666	int* bounds= computeBounds (F, d, isIrreducible);
	2667	if (isIrreducible)
	2668	{
	2669	delete [] bounds;
	2670	CanonicalForm G= F;
	2671	F= 1;
	2672	return CFList (G);
	2673	}
[11bf82]	2674
	2675	CFArray * A= new CFArray [factors.length()];
	2676	CFArray bufQ= CFArray (factors.length());
	2677	zz_p::init (getCharacteristic());
	2678	mat_zz_p NTLN;
	2679	ident (NTLN, factors.length());
	2680	int minBound= bounds[0];
	2681	for (int i= 1; i < d; i++)
	2682	{
	2683	if (bounds[i] != 0)
	2684	minBound= tmin (minBound, bounds[i]);
	2685	}
	2686	int l= tmax (oldL, 2*((minBound+1)/degMipo+1));
	2687	int oldL2= l/2;
	2688	int stepSize= 2;
	2689	bool useOldQs= false;
	2690	bool hitBound= false;
	2691	Variable gamma= info.getBeta();
	2692	CanonicalForm primElemAlpha= info.getGamma();
	2693	CanonicalForm imPrimElemAlpha= info.getDelta();
[38ffb7]	2694	CFListIterator j;
	2695	Variable y= F.mvar();
[5335ba]	2696	CanonicalForm powX, imBasis, truncF;
[38ffb7]	2697	CFMatrix Mat, C;
	2698	CFIterator iter;
	2699	mat_zz_p* NTLMat,*NTLC, NTLK;
	2700	CFArray buf;
[11bf82]	2701	while (l <= precision)
	2702	{
[38ffb7]	2703	j= factors;
[11bf82]	2704	if (GF)
	2705	setCharacteristic (getCharacteristic());
[38ffb7]	2706	powX= power (y-gamma, l);
	2707	Mat= CFMatrix (ldegMipo, ldegMipo);
[11bf82]	2708	for (int i= 0; i < l*degMipo; i++)
	2709	{
[38ffb7]	2710	imBasis= mod (power (y, i), powX);
[11bf82]	2711	imBasis= imBasis (power (y, degMipo), y);
	2712	imBasis= imBasis (y, gamma);
[38ffb7]	2713	iter= imBasis;
[11bf82]	2714	for (; iter.hasTerms(); iter++)
	2715	Mat (iter.exp()+ 1, i+1)= iter.coeff();
	2716	}
	2717
[38ffb7]	2718	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
[11bf82]	2719	NTLMat= inv (NTLMat);
	2720	if (GF)
	2721	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
	2722
[5335ba]	2723	truncF= mod (F, power (y, l));
[11bf82]	2724	if (useOldQs)
	2725	{
	2726	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	2727	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
[11bf82]	2728	bufQ[i]
	2729	);
	2730	}
	2731	else
	2732	{
	2733	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	2734	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
[11bf82]	2735	}
	2736	useOldQs= true;
	2737	for (int i= 0; i < d; i++)
	2738	{
	2739	if (bounds [i] + 1 <= (l/2)*degMipo)
	2740	{
	2741	int k= tmin (bounds [i] + 1, (l/2)*degMipo);
[38ffb7]	2742	C= CFMatrix (l*degMipo - k, factors.length());
[11bf82]	2743	for (int ii= 0; ii < factors.length(); ii++)
	2744	{
	2745	if (A[ii].size() - 1 >= i)
	2746	{
	2747	if (GF)
	2748	{
	2749	A[ii] [i]= A [ii] [i] (y-evaluation, y);
	2750	setCharacteristic (getCharacteristic());
	2751	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
	2752	if (alpha != gamma)
	2753	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
	2754	gamma, source, dest
	2755	);
	2756	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
	2757	}
	2758	else
	2759	{
	2760	A [ii] [i]= A [ii] [i] (y-evaluation, y);
	2761	if (alpha != gamma)
	2762	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
	2763	gamma, source, dest
	2764	);
	2765	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
	2766	}
[9ebec2]	2767	writeInMatrix (C, buf, ii + 1, 0);
[11bf82]	2768	}
	2769	if (GF)
	2770	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
	2771	}
	2772
	2773	if (GF)
	2774	setCharacteristic(getCharacteristic());
	2775
[38ffb7]	2776	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
	2777	NTLK= (NTLC)NTLN;
[11bf82]	2778	transpose (NTLK, NTLK);
	2779	kernel (NTLK, NTLK);
	2780	transpose (NTLK, NTLK);
	2781	NTLN *= NTLK;
	2782
	2783	if (GF)
	2784	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
	2785
	2786	if (NTLN.NumCols() == 1)
	2787	{
	2788	Variable y= Variable (2);
	2789	CanonicalForm tmp= F (y - evaluation, y);
	2790	CFList source, dest;
	2791	tmp= mapDown (tmp, info, source, dest);
	2792	delete [] A;
	2793	delete [] bounds;
[542864]	2794	F= 1;
[11bf82]	2795	return CFList (tmp);
	2796	}
	2797	}
	2798	}
	2799
	2800	if (NTLN.NumCols() < oldNumCols - factorsFound)
	2801	{
	2802	if (isReduced (NTLN))
	2803	{
[38ffb7]	2804	int * factorsFoundIndex= new int [NTLN.NumCols()];
	2805	for (long i= 0; i < NTLN.NumCols(); i++)
	2806	factorsFoundIndex[i]= 0;
	2807	int factorsFound2= 0;
	2808	CFList result;
	2809	CanonicalForm bufF= F;
	2810	extReconstructionTry (result, bufF, factors,degree (F)+1, factorsFound2,
	2811	factorsFoundIndex, NTLN, false, info, evaluation
	2812	);
	2813	if (result.length() == NTLN.NumCols())
	2814	{
	2815	delete [] factorsFoundIndex;
	2816	delete [] A;
	2817	delete [] bounds;
[3d0075]	2818	F= 1;
[38ffb7]	2819	return result;
	2820	}
[11bf82]	2821	delete [] factorsFoundIndex;
	2822	}
	2823	else if (l == precision)
	2824	{
	2825	CanonicalForm bufF= F;
	2826	int * zeroOne= extractZeroOneVecs (NTLN);
	2827	CFList result= extReconstruction (bufF, factors, zeroOne, precision,
	2828	NTLN, info, evaluation
	2829	);
	2830	F= bufF;
	2831	delete [] zeroOne;
	2832	delete [] A;
	2833	delete [] bounds;
	2834	return result;
	2835	}
	2836	}
	2837	oldL2= l;
	2838	l += stepSize;
	2839	stepSize *= 2;
	2840	if (l > precision)
	2841	{
	2842	if (!hitBound)
	2843	{
	2844	hitBound= true;
	2845	l= precision;
	2846	}
	2847	else
	2848	break;
	2849	}
	2850	}
	2851	delete [] bounds;
	2852	delete [] A;
	2853	return CFList();
	2854	}
	2855
	2856	CFList
	2857	increasePrecision2 (const CanonicalForm& F, CFList& factors,
	2858	const Variable& alpha, int precision)
	2859	{
	2860	int d;
[542864]	2861	bool isIrreducible= false;
	2862	int* bounds= computeBounds (F, d, isIrreducible);
	2863	if (isIrreducible)
	2864	{
	2865	delete [] bounds;
	2866	return CFList (F);
	2867	}
[11bf82]	2868	CFArray * A= new CFArray [factors.length()];
	2869	CFArray bufQ= CFArray (factors.length());
	2870	zz_p::init (getCharacteristic());
	2871	zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
	2872	zz_pE::init (NTLMipo);
	2873	mat_zz_pE NTLN;
	2874	ident (NTLN, factors.length());
	2875	int minBound= bounds[0];
	2876	for (int i= 1; i < d; i++)
	2877	{
	2878	if (bounds[i] != 0)
	2879	minBound= tmin (minBound, bounds[i]);
	2880	}
	2881	int l= tmin (2*(minBound + 1), precision);
	2882	int oldL= l/2;
	2883	int stepSize= 2;
	2884	bool useOldQs= false;
	2885	bool hitBound= false;
[38ffb7]	2886	CFListIterator j;
	2887	CFMatrix C;
	2888	CFArray buf;
	2889	mat_zz_pE* NTLC, NTLK;
[5335ba]	2890	Variable y= F.mvar();
	2891	CanonicalForm truncF;
[11bf82]	2892	while (l <= precision)
	2893	{
[38ffb7]	2894	j= factors;
[5335ba]	2895	truncF= mod (F, power (y, l));
[11bf82]	2896	if (useOldQs)
	2897	{
	2898	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	2899	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i], bufQ[i]);
[11bf82]	2900	}
	2901	else
	2902	{
	2903	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	2904	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
[11bf82]	2905	}
	2906	useOldQs= true;
	2907	for (int i= 0; i < d; i++)
	2908	{
	2909	if (bounds [i] + 1 <= l/2)
	2910	{
	2911	int k= tmin (bounds [i] + 1, l/2);
[38ffb7]	2912	C= CFMatrix (l - k, factors.length());
[11bf82]	2913	for (int ii= 0; ii < factors.length(); ii++)
	2914	{
	2915	if (A[ii].size() - 1 >= i)
[9ebec2]	2916	{
[11bf82]	2917	buf= getCoeffs (A[ii] [i], k);
[9ebec2]	2918	writeInMatrix (C, buf, ii + 1, 0);
	2919	}
[11bf82]	2920	}
[38ffb7]	2921	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
	2922	NTLK= (NTLC)NTLN;
[11bf82]	2923	transpose (NTLK, NTLK);
	2924	kernel (NTLK, NTLK);
	2925	transpose (NTLK, NTLK);
	2926	NTLN *= NTLK;
	2927	if (NTLN.NumCols() == 1)
	2928	{
	2929	delete [] A;
	2930	delete [] bounds;
	2931	return CFList (F);
	2932	}
	2933	}
	2934	}
	2935
	2936	if (isReduced (NTLN) \|\| l == precision)
	2937	{
	2938	CanonicalForm bufF= F;
	2939	int * zeroOne= extractZeroOneVecs (NTLN);
	2940	CFList bufFactors= factors;
	2941	CFList result= monicReconstruction (bufF, factors, zeroOne, precision,
	2942	NTLN
	2943	);
	2944	if (result.length() != NTLN.NumCols() && l != precision)
	2945	factors= bufFactors;
	2946	if (result.length() == NTLN.NumCols())
	2947	{
	2948	delete [] zeroOne;
	2949	delete [] A;
	2950	delete [] bounds;
	2951	return result;
	2952	}
	2953	if (l == precision)
	2954	{
	2955	delete [] zeroOne;
	2956	delete [] A;
	2957	delete [] bounds;
	2958	return Union (result, factors);
	2959	}
	2960	}
	2961	oldL= l;
	2962	l += stepSize;
	2963	stepSize *= 2;
	2964	if (l > precision)
	2965	{
	2966	if (!hitBound)
	2967	{
	2968	l= precision;
	2969	hitBound= true;
	2970	}
	2971	else
	2972	break;
	2973	}
	2974	}
	2975	delete [] bounds;
	2976	delete [] A;
	2977	return CFList();
	2978	}
	2979
	2980	CFList
	2981	increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int factorsFound,
	2982	int oldNumCols, int oldL, const Variable& alpha,
	2983	int precision
	2984	)
	2985	{
	2986	int d;
[542864]	2987	bool isIrreducible= false;
	2988	int* bounds= computeBounds (F, d, isIrreducible);
	2989	if (isIrreducible)
	2990	{
	2991	delete [] bounds;
	2992	CanonicalForm G= F;
	2993	F= 1;
	2994	return CFList (G);
	2995	}
[11bf82]	2996	int extensionDeg= degree (getMipo (alpha));
	2997	CFArray * A= new CFArray [factors.length()];
	2998	CFArray bufQ= CFArray (factors.length());
	2999	mat_zz_p NTLN;
	3000	ident (NTLN, factors.length());
	3001	int minBound= bounds[0];
	3002	for (int i= 1; i < d; i++)
	3003	{
	3004	if (bounds[i] != 0)
	3005	minBound= tmin (minBound, bounds[i]);
	3006	}
	3007	int l= tmax (2*(minBound + 1), oldL);
	3008	int oldL2= l/2;
	3009	int stepSize= 2;
	3010	bool useOldQs= false;
	3011	bool hitBound= false;
[38ffb7]	3012	CFListIterator j;
	3013	CFMatrix C;
	3014	mat_zz_p* NTLC, NTLK;
	3015	CFArray buf;
[5335ba]	3016	Variable y= F.mvar();
	3017	CanonicalForm truncF;
[11bf82]	3018	while (l <= precision)
	3019	{
[38ffb7]	3020	j= factors;
[5335ba]	3021	truncF= mod (F, power (y, l));
[11bf82]	3022	if (useOldQs)
	3023	{
	3024	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	3025	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
[11bf82]	3026	bufQ[i]
	3027	);
	3028	}
	3029	else
	3030	{
	3031	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	3032	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
[11bf82]	3033	}
	3034	useOldQs= true;
	3035	for (int i= 0; i < d; i++)
	3036	{
	3037	if (bounds [i] + 1 <= l/2)
	3038	{
	3039	int k= tmin (bounds [i] + 1, l/2);
[38ffb7]	3040	C= CFMatrix ((l - k)*extensionDeg, factors.length());
[11bf82]	3041	for (int ii= 0; ii < factors.length(); ii++)
	3042	{
	3043	if (A[ii].size() - 1 >= i)
[9ebec2]	3044	{
[11bf82]	3045	buf= getCoeffs (A[ii] [i], k, alpha);
[9ebec2]	3046	writeInMatrix (C, buf, ii + 1, 0);
	3047	}
[11bf82]	3048	}
[38ffb7]	3049	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
	3050	NTLK= (NTLC)NTLN;
[11bf82]	3051	transpose (NTLK, NTLK);
	3052	kernel (NTLK, NTLK);
	3053	transpose (NTLK, NTLK);
	3054	NTLN *= NTLK;
	3055	if (NTLN.NumCols() == 1)
	3056	{
	3057	delete [] A;
	3058	delete [] bounds;
[542864]	3059	CanonicalForm G= F;
	3060	F= 1;
	3061	return CFList (G);
[11bf82]	3062	}
	3063	}
	3064	}
	3065
	3066	if (NTLN.NumCols() < oldNumCols - factorsFound)
	3067	{
	3068	if (isReduced (NTLN))
	3069	{
	3070	int * factorsFoundIndex= new int [NTLN.NumCols()];
	3071	for (long i= 0; i < NTLN.NumCols(); i++)
	3072	factorsFoundIndex[i]= 0;
	3073	int factorsFound2= 0;
	3074	CFList result;
	3075	CanonicalForm bufF= F;
	3076	reconstructionTry (result, bufF, factors, degree (F) + 1, factorsFound2,
	3077	factorsFoundIndex, NTLN, false
	3078	);
	3079	if (result.length() == NTLN.NumCols())
	3080	{
	3081	delete [] factorsFoundIndex;
	3082	delete [] A;
	3083	delete [] bounds;
[3d0075]	3084	F= 1;
[11bf82]	3085	return result;
	3086	}
	3087	delete [] factorsFoundIndex;
	3088	}
	3089	else if (l == precision)
	3090	{
	3091	CanonicalForm bufF= F;
	3092	int * zeroOne= extractZeroOneVecs (NTLN);
	3093	CFList result= reconstruction (bufF, factors, zeroOne, precision, NTLN);
	3094	F= bufF;
	3095	delete [] zeroOne;
	3096	delete [] A;
	3097	delete [] bounds;
	3098	return result;
	3099	}
	3100	}
	3101	oldL2= l;
	3102	l += stepSize;
	3103	stepSize *= 2;
	3104	if (l > precision)
	3105	{
	3106	if (!hitBound)
	3107	{
	3108	hitBound= true;
	3109	l= precision;
	3110	}
	3111	else
	3112	break;
	3113	}
	3114	}
	3115	delete [] bounds;
	3116	delete [] A;
	3117	return CFList();
	3118	}
	3119
	3120	CFList
	3121	increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int
	3122	l, int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN
	3123	)
	3124	{
	3125	CFList result= CFList();
	3126	CFArray * A= new CFArray [factors.length()];
	3127	int oldL2= oldL/2;
	3128	bool hitBound= false;
	3129	if (NTLN.NumRows() != factors.length()) //refined factors
	3130	{
	3131	ident (NTLN, factors.length());
	3132	bufQ= CFArray (factors.length());
	3133	}
	3134	bool useOldQs= false;
[38ffb7]	3135	CFListIterator j;
	3136	CFMatrix C;
	3137	CFArray buf;
	3138	mat_zz_p* NTLC, NTLK;
[5335ba]	3139	CanonicalForm bufF, truncF;
[38ffb7]	3140	CFList bufUniFactors;
[5335ba]	3141	Variable y= F.mvar();
[11bf82]	3142	while (oldL <= l)
	3143	{
[38ffb7]	3144	j= factors;
[5335ba]	3145	truncF= mod (F, power (y, oldL));
[11bf82]	3146	if (useOldQs)
	3147	{
	3148	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	3149	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
[11bf82]	3150	bufQ[i]
	3151	);
	3152	}
	3153	else
	3154	{
	3155	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	3156	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
[11bf82]	3157	}
	3158	useOldQs= true;
	3159
	3160	for (int i= 0; i < d; i++)
	3161	{
	3162	if (bounds [i] + 1 <= oldL/2)
	3163	{
	3164	int k= tmin (bounds [i] + 1, oldL/2);
[38ffb7]	3165	C= CFMatrix (oldL - k, factors.length());
[11bf82]	3166	for (int ii= 0; ii < factors.length(); ii++)
	3167	{
	3168	if (A[ii].size() - 1 >= i)
[9ebec2]	3169	{
[11bf82]	3170	buf= getCoeffs (A[ii] [i], k);
[9ebec2]	3171	writeInMatrix (C, buf, ii + 1, 0);
	3172	}
[11bf82]	3173	}
[38ffb7]	3174	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
	3175	NTLK= (NTLC)NTLN;
[11bf82]	3176	transpose (NTLK, NTLK);
	3177	kernel (NTLK, NTLK);
	3178	transpose (NTLK, NTLK);
	3179	NTLN *= NTLK;
	3180	if (NTLN.NumCols() == 1)
	3181	{
	3182	delete [] A;
	3183	return CFList (F);
	3184	}
	3185	}
	3186	}
	3187	if (NTLN.NumCols() == 1)
	3188	{
	3189	delete [] A;
	3190	return CFList (F);
	3191	}
	3192	int * zeroOneVecs;
	3193	zeroOneVecs= extractZeroOneVecs (NTLN);
[38ffb7]	3194	bufF= F;
	3195	bufUniFactors= factors;
[11bf82]	3196	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
	3197	delete [] zeroOneVecs;
	3198	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < oldL && result.length() > 0)
	3199	{
[c1b9927]	3200	F= bufF;
[11bf82]	3201	factors= bufUniFactors;
	3202	delete [] A;
	3203	return result;
	3204	}
	3205
	3206	result= CFList();
	3207	oldL2= oldL;
	3208	oldL *= 2;
	3209	if (oldL > l)
	3210	{
	3211	if (!hitBound)
	3212	{
	3213	oldL= l;
	3214	hitBound= true;
	3215	}
	3216	else
	3217	break;
	3218	}
	3219	}
	3220	delete [] A;
	3221	return result;
	3222	}
	3223
	3224	CFList
	3225	increasePrecision (CanonicalForm& F, CFList& factors, int oldL, int
	3226	l, int d, int* bounds, CFArray& bufQ, mat_zz_pE& NTLN
	3227	)
	3228	{
	3229	CFList result= CFList();
	3230	CFArray * A= new CFArray [factors.length()];
	3231	int oldL2= oldL/2;
	3232	bool hitBound= false;
	3233	bool useOldQs= false;
	3234	if (NTLN.NumRows() != factors.length()) //refined factors
	3235	ident (NTLN, factors.length());
[38ffb7]	3236	CFListIterator j;
	3237	CFMatrix C;
	3238	CFArray buf;
	3239	mat_zz_pE* NTLC, NTLK;
[5335ba]	3240	CanonicalForm bufF, truncF;
[38ffb7]	3241	CFList bufUniFactors;
[5335ba]	3242	Variable y= F.mvar();
[11bf82]	3243	while (oldL <= l)
	3244	{
[38ffb7]	3245	j= factors;
[5335ba]	3246	truncF= mod (F, power (y, oldL));
[11bf82]	3247	if (useOldQs)
	3248	{
	3249	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	3250	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
[11bf82]	3251	bufQ[i]
	3252	);
	3253	}
	3254	else
	3255	{
	3256	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	3257	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
[11bf82]	3258	}
	3259	useOldQs= true;
	3260
	3261	for (int i= 0; i < d; i++)
	3262	{
	3263	if (bounds [i] + 1 <= oldL/2)
	3264	{
	3265	int k= tmin (bounds [i] + 1, oldL/2);
[38ffb7]	3266	C= CFMatrix (oldL - k, factors.length());
[11bf82]	3267	for (int ii= 0; ii < factors.length(); ii++)
	3268	{
	3269	if (A[ii].size() - 1 >= i)
[9ebec2]	3270	{
[11bf82]	3271	buf= getCoeffs (A[ii] [i], k);
[9ebec2]	3272	writeInMatrix (C, buf, ii + 1, 0);
	3273	}
[11bf82]	3274	}
[38ffb7]	3275	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
	3276	NTLK= (NTLC)NTLN;
[11bf82]	3277	transpose (NTLK, NTLK);
	3278	kernel (NTLK, NTLK);
	3279	transpose (NTLK, NTLK);
	3280	NTLN *= NTLK;
	3281	if (NTLN.NumCols() == 1)
	3282	{
	3283	delete [] A;
	3284	return CFList (F);
	3285	}
	3286	}
	3287	}
	3288	if (NTLN.NumCols() == 1)
	3289	{
	3290	delete [] A;
	3291	return CFList (F);
	3292	}
	3293
	3294	int * zeroOneVecs;
	3295	zeroOneVecs= extractZeroOneVecs (NTLN);
[38ffb7]	3296	bufF= F;
	3297	bufUniFactors= factors;
[11bf82]	3298	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
	3299	delete [] zeroOneVecs;
	3300	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
	3301	{
[c1b9927]	3302	F= bufF;
[11bf82]	3303	factors= bufUniFactors;
	3304	delete [] A;
	3305	return result;
	3306	}
	3307
	3308	result= CFList();
	3309	oldL2= oldL;
	3310	oldL *= 2;
	3311	if (oldL > l)
	3312	{
	3313	if (!hitBound)
	3314	{
	3315	oldL= l;
	3316	hitBound= true;
	3317	}
	3318	else
	3319	break;
	3320	}
	3321	}
	3322	delete [] A;
	3323	return result;
	3324	}
	3325
	3326	//over field extension
	3327	CFList
	3328	extIncreasePrecision (CanonicalForm& F, CFList& factors, int oldL, int l, int d,
	3329	int* bounds, CFArray& bufQ, mat_zz_p& NTLN, const
	3330	CanonicalForm& evaluation, const ExtensionInfo& info,
	3331	CFList& source, CFList& dest
	3332	)
	3333	{
	3334	CFList result= CFList();
	3335	CFArray * A= new CFArray [factors.length()];
	3336	int oldL2= oldL/2; //be careful
	3337	bool hitBound= false;
	3338	bool useOldQs= false;
	3339	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
	3340	int degMipo= degree (getMipo (info.getAlpha()));
	3341	Variable alpha= info.getAlpha();
	3342
	3343	Variable gamma= info.getBeta();
	3344	CanonicalForm primElemAlpha= info.getGamma();
	3345	CanonicalForm imPrimElemAlpha= info.getDelta();
	3346	if (NTLN.NumRows() != factors.length()) //refined factors
	3347	ident (NTLN, factors.length());
[38ffb7]	3348	Variable y= F.mvar();
	3349	CFListIterator j;
[5335ba]	3350	CanonicalForm powX, imBasis, bufF, truncF;
[38ffb7]	3351	CFMatrix Mat, C;
	3352	CFIterator iter;
	3353	mat_zz_p* NTLMat;
	3354	CFArray buf;
	3355	mat_zz_p* NTLC, NTLK;
	3356	CFList bufUniFactors;
[11bf82]	3357	while (oldL <= l)
	3358	{
[38ffb7]	3359	j= factors;
[11bf82]	3360	if (GF)
	3361	setCharacteristic (getCharacteristic());
[38ffb7]	3362
	3363	powX= power (y-gamma, oldL);
	3364	Mat= CFMatrix (oldLdegMipo, oldLdegMipo);
[11bf82]	3365	for (int i= 0; i < oldL*degMipo; i++)
	3366	{
[38ffb7]	3367	imBasis= mod (power (y, i), powX);
[11bf82]	3368	imBasis= imBasis (power (y, degMipo), y);
	3369	imBasis= imBasis (y, gamma);
[38ffb7]	3370	iter= imBasis;
[11bf82]	3371	for (; iter.hasTerms(); iter++)
	3372	Mat (iter.exp()+ 1, i+1)= iter.coeff();
	3373	}
	3374
[38ffb7]	3375	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
[11bf82]	3376	NTLMat= inv (NTLMat);
	3377	if (GF)
	3378	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
	3379
[5335ba]	3380	truncF= mod (F, power (y, oldL));
[11bf82]	3381	if (useOldQs)
	3382	{
	3383	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	3384	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
[11bf82]	3385	bufQ[i]);
	3386	}
	3387	else
	3388	{
	3389	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	3390	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
[11bf82]	3391	}
	3392	useOldQs= true;
	3393
	3394	for (int i= 0; i < d; i++)
	3395	{
	3396	if (bounds [i] + 1 <= oldL/2)
	3397	{
	3398	int k= tmin (bounds [i] + 1, oldL/2);
[38ffb7]	3399	C= CFMatrix (oldL*degMipo - k, factors.length());
[11bf82]	3400	for (int ii= 0; ii < factors.length(); ii++)
	3401	{
	3402	if (A[ii].size() - 1 >= i)
	3403	{
	3404	if (GF)
	3405	{
	3406	A [ii] [i]= A [ii] [i] (y-evaluation, y);
	3407	setCharacteristic (getCharacteristic());
	3408	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
	3409	if (alpha != gamma)
	3410	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
	3411	gamma, source, dest
	3412	);
	3413	buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
	3414	}
	3415	else
	3416	{
	3417	A [ii] [i]= A [ii] [i] (y-evaluation, y);
	3418	if (alpha != gamma)
	3419	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
	3420	gamma, source, dest
	3421	);
	3422	buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
	3423	}
[9ebec2]	3424	writeInMatrix (C, buf, ii + 1, 0);
[11bf82]	3425	}
	3426	if (GF)
	3427	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
	3428	}
	3429
	3430	if (GF)
	3431	setCharacteristic(getCharacteristic());
	3432
[38ffb7]	3433	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
	3434	NTLK= (NTLC)NTLN;
[11bf82]	3435	transpose (NTLK, NTLK);
	3436	kernel (NTLK, NTLK);
	3437	transpose (NTLK, NTLK);
	3438	NTLN *= NTLK;
	3439
	3440	if (GF)
	3441	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
	3442
	3443	if (NTLN.NumCols() == 1)
	3444	{
	3445	Variable y= Variable (2);
	3446	CanonicalForm tmp= F (y - evaluation, y);
	3447	CFList source, dest;
	3448	tmp= mapDown (tmp, info, source, dest);
	3449	delete [] A;
	3450	return CFList (tmp);
	3451	}
	3452	}
	3453	}
	3454	if (NTLN.NumCols() == 1)
	3455	{
	3456	Variable y= Variable (2);
	3457	CanonicalForm tmp= F (y - evaluation, y);
	3458	CFList source, dest;
	3459	tmp= mapDown (tmp, info, source, dest);
	3460	delete [] A;
	3461	return CFList (tmp);
	3462	}
	3463
	3464	int * zeroOneVecs;
	3465	zeroOneVecs= extractZeroOneVecs (NTLN);
[38ffb7]	3466	bufF= F;
	3467	bufUniFactors= factors;
[11bf82]	3468	result= extReconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN,
	3469	info, evaluation
	3470	);
	3471	delete [] zeroOneVecs;
	3472	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
	3473	{
[c1b9927]	3474	F= bufF;
[11bf82]	3475	factors= bufUniFactors;
	3476	return result;
	3477	}
	3478
	3479	result= CFList();
	3480	oldL2= oldL;
	3481	oldL *= 2;
	3482	if (oldL > l)
	3483	{
	3484	if (!hitBound)
	3485	{
	3486	oldL= l;
	3487	hitBound= true;
	3488	}
	3489	else
	3490	break;
	3491	}
	3492	}
	3493	delete [] A;
	3494	return result;
	3495	}
	3496
	3497	CFList
	3498	increasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int oldL, int l,
	3499	int d, int* bounds, CFArray& bufQ, mat_zz_p& NTLN,
	3500	const Variable& alpha
	3501	)
	3502	{
	3503	CFList result= CFList();
	3504	CFArray * A= new CFArray [factors.length()];
	3505	int extensionDeg= degree (getMipo (alpha));
	3506	int oldL2= oldL/2;
	3507	bool hitBound= false;
	3508	bool useOldQs= false;
	3509	if (NTLN.NumRows() != factors.length()) //refined factors
	3510	ident (NTLN, factors.length());
[38ffb7]	3511	CFListIterator j;
	3512	CFMatrix C;
	3513	CFArray buf;
	3514	mat_zz_p* NTLC, NTLK;
[5335ba]	3515	CanonicalForm bufF, truncF;
[38ffb7]	3516	CFList bufUniFactors;
[5335ba]	3517	Variable y= F.mvar();
[11bf82]	3518	while (oldL <= l)
	3519	{
[38ffb7]	3520	j= factors;
[5335ba]	3521	truncF= mod (F, power (y, oldL));
[11bf82]	3522	if (useOldQs)
	3523	{
	3524	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	3525	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
[11bf82]	3526	bufQ[i]
	3527	);
	3528	}
	3529	else
	3530	{
	3531	for (int i= 0; i < factors.length(); i++, j++)
[5335ba]	3532	A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
[11bf82]	3533	}
	3534	useOldQs= true;
	3535
	3536	for (int i= 0; i < d; i++)
	3537	{
	3538	if (bounds [i] + 1 <= oldL/2)
	3539	{
	3540	int k= tmin (bounds [i] + 1, oldL/2);
[38ffb7]	3541	C= CFMatrix ((oldL - k)*extensionDeg, factors.length());
[11bf82]	3542	for (int ii= 0; ii < factors.length(); ii++)
	3543	{
	3544	if (A[ii].size() - 1 >= i)
[9ebec2]	3545	{
[11bf82]	3546	buf= getCoeffs (A[ii] [i], k, alpha);
[9ebec2]	3547	writeInMatrix (C, buf, ii + 1, 0);
	3548	}
[11bf82]	3549	}
[38ffb7]	3550	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
	3551	NTLK= (NTLC)NTLN;
[11bf82]	3552	transpose (NTLK, NTLK);
	3553	kernel (NTLK, NTLK);
	3554	transpose (NTLK, NTLK);
	3555	NTLN *= NTLK;
	3556	if (NTLN.NumCols() == 1)
	3557	{
	3558	delete [] A;
	3559	return CFList (F);
	3560	}
	3561	}
	3562	}
	3563
	3564	int * zeroOneVecs;
	3565	zeroOneVecs= extractZeroOneVecs (NTLN);
	3566
[38ffb7]	3567	bufF= F;
	3568	bufUniFactors= factors;
[11bf82]	3569	result= reconstruction (bufF, bufUniFactors, zeroOneVecs, oldL, NTLN);
	3570	delete [] zeroOneVecs;
	3571	if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
	3572	{
[c1b9927]	3573	F= bufF;
[11bf82]	3574	factors= bufUniFactors;
	3575	delete [] A;
	3576	return result;
	3577	}
	3578
	3579	result= CFList();
	3580	oldL2= oldL;
	3581	oldL *= 2;
	3582	if (oldL > l)
	3583	{
	3584	if (!hitBound)
	3585	{
	3586	oldL= l;
	3587	hitBound= true;
	3588	}
	3589	else
	3590	break;
	3591	}
	3592	}
	3593	delete [] A;
	3594	return result;
	3595	}
	3596
	3597	CFList
	3598	furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList&
	3599	factors, int l, int liftBound, int d, int*
	3600	bounds, mat_zz_p& NTLN, CFList& diophant,
	3601	CFMatrix& M, CFArray& Pi, CFArray& bufQ
	3602	)
	3603	{
	3604	CanonicalForm LCF= LC (F, 1);
	3605	CFList result;
	3606	bool irreducible= false;
	3607	CFList bufFactors= factors;
	3608	CFArray *A = new CFArray [bufFactors.length()];
	3609	bool useOldQs= false;
	3610	bool hitBound= false;
	3611	int oldL= l;
	3612	int stepSize= 8; //TODO choose better step size?
	3613	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
	3614	if (NTLN.NumRows() != factors.length()) //refined factors
	3615	ident (NTLN, factors.length());
[38ffb7]	3616	CFListIterator j;
	3617	CFMatrix C;
	3618	CFArray buf;
	3619	mat_zz_p* NTLC, NTLK;
[5335ba]	3620	CanonicalForm bufF, truncF;
	3621	Variable y= F.mvar();
[11bf82]	3622	while (l <= liftBound)
	3623	{
	3624	bufFactors.insert (LCF);
	3625	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
	3626	bufFactors.insert (LCF);
	3627	bufFactors.removeFirst();
[38ffb7]	3628	j= bufFactors;
[5335ba]	3629	truncF= mod (F, power (y, l));
[11bf82]	3630	if (useOldQs)
	3631	{
	3632	for (int i= 0; i < bufFactors.length(); i++, j++)
[5335ba]	3633	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
	3634	bufQ[i]);
[11bf82]	3635	}
	3636	else
	3637	{
	3638	for (int i= 0; i < bufFactors.length(); i++, j++)
[5335ba]	3639	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
[11bf82]	3640	}
	3641	for (int i= 0; i < d; i++)
	3642	{
	3643	if (bounds [i] + 1 <= l/2)
	3644	{
	3645	int k= tmin (bounds [i] + 1, l/2);
[38ffb7]	3646	C= CFMatrix (l - k, bufFactors.length());
[11bf82]	3647	for (int ii= 0; ii < bufFactors.length(); ii++)
	3648	{
	3649	if (A[ii].size() - 1 >= i)
[9ebec2]	3650	{
[11bf82]	3651	buf= getCoeffs (A[ii] [i], k);
[9ebec2]	3652	writeInMatrix (C, buf, ii + 1, 0);
	3653	}
[11bf82]	3654	}
[38ffb7]	3655	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
	3656	NTLK= (NTLC)NTLN;
[11bf82]	3657	transpose (NTLK, NTLK);
	3658	kernel (NTLK, NTLK);
	3659	transpose (NTLK, NTLK);
	3660	NTLN *= NTLK;
	3661	if (NTLN.NumCols() == 1)
	3662	{
	3663	irreducible= true;
	3664	break;
	3665	}
	3666	}
	3667	}
	3668
	3669	if (NTLN.NumCols() == 1)
	3670	{
	3671	irreducible= true;
	3672	break;
	3673	}
	3674
	3675	int * zeroOneVecs= extractZeroOneVecs (NTLN);
[38ffb7]	3676	bufF= F;
[11bf82]	3677	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
	3678	delete [] zeroOneVecs;
	3679	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
	3680	{
	3681	F= bufF;
	3682	factors= bufFactors;
	3683	delete [] A;
	3684	return result;
	3685	}
	3686
	3687	if (isReduced (NTLN))
	3688	{
	3689	int factorsFound= 0;
[38ffb7]	3690	bufF= F;
[11bf82]	3691	int* factorsFoundIndex= new int [NTLN.NumCols()];
	3692	for (long i= 0; i < NTLN.NumCols(); i++)
	3693	factorsFoundIndex[i]= 0;
	3694	if (l < liftBound)
	3695	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
	3696	factorsFoundIndex, NTLN, false
	3697	);
	3698	else
	3699	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
	3700	degree (LCF), factorsFound, factorsFoundIndex,
	3701	NTLN, false
	3702	);
	3703
	3704	if (NTLN.NumCols() == result.length())
	3705	{
	3706	delete [] A;
	3707	delete [] factorsFoundIndex;
	3708	return result;
	3709	}
	3710	delete [] factorsFoundIndex;
	3711	}
	3712	result= CFList();
	3713	oldL= l;
	3714	stepSize *= 2;
	3715	l += stepSize;
	3716	if (l > liftBound)
	3717	{
	3718	if (!hitBound)
	3719	{
	3720	l= liftBound;
	3721	hitBound= true;
	3722	}
	3723	else
	3724	break;
	3725	}
	3726	}
	3727	if (irreducible)
	3728	{
	3729	delete [] A;
	3730	return CFList (F);
	3731	}
	3732	delete [] A;
	3733	factors= bufFactors;
	3734	return CFList();
	3735	}
	3736
	3737	//Fq
	3738	CFList
	3739	furtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList&
	3740	factors, int l, int liftBound, int d, int*
	3741	bounds, mat_zz_pE& NTLN, CFList& diophant,
	3742	CFMatrix& M, CFArray& Pi, CFArray& bufQ
	3743	)
	3744	{
	3745	CanonicalForm LCF= LC (F, 1);
	3746	CFList result;
	3747	bool irreducible= false;
	3748	CFList bufFactors= factors;
	3749	CFArray *A = new CFArray [bufFactors.length()];
	3750	bool useOldQs= false;
	3751	bool hitBound= false;
	3752	int oldL= l;
	3753	int stepSize= 8; //TODO choose better step size?
	3754	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
	3755	if (NTLN.NumRows() != factors.length()) //refined factors
	3756	ident (NTLN, factors.length());
[38ffb7]	3757	CFListIterator j;
	3758	CFArray buf;
	3759	mat_zz_pE* NTLC, NTLK;
[5335ba]	3760	CanonicalForm bufF, truncF;
	3761	Variable y= F.mvar();
[11bf82]	3762	while (l <= liftBound)
	3763	{
	3764	bufFactors.insert (LCF);
	3765	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
[38ffb7]	3766	j= bufFactors;
[5335ba]	3767	truncF= mod (F, power (y, l));
[11bf82]	3768	if (useOldQs)
	3769	{
	3770	for (int i= 0; i < bufFactors.length(); i++, j++)
[5335ba]	3771	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
	3772	bufQ[i]);
[11bf82]	3773	}
	3774	else
	3775	{
	3776	for (int i= 0; i < bufFactors.length(); i++, j++)
[5335ba]	3777	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
[11bf82]	3778	}
	3779	for (int i= 0; i < d; i++)
	3780	{
	3781	if (bounds [i] + 1 <= l/2)
	3782	{
	3783	int k= tmin (bounds [i] + 1, l/2);
	3784	CFMatrix C= CFMatrix (l - k, bufFactors.length());
	3785	for (int ii= 0; ii < bufFactors.length(); ii++)
	3786	{
	3787	if (A[ii].size() - 1 >= i)
[9ebec2]	3788	{
[11bf82]	3789	buf= getCoeffs (A[ii] [i], k);
[9ebec2]	3790	writeInMatrix (C, buf, ii + 1, 0);
	3791	}
[11bf82]	3792	}
[38ffb7]	3793	NTLC= convertFacCFMatrix2NTLmat_zz_pE(C);
	3794	NTLK= (NTLC)NTLN;
[11bf82]	3795	transpose (NTLK, NTLK);
	3796	kernel (NTLK, NTLK);
	3797	transpose (NTLK, NTLK);
	3798	NTLN *= NTLK;
	3799	if (NTLN.NumCols() == 1)
	3800	{
	3801	irreducible= true;
	3802	break;
	3803	}
	3804	}
	3805	}
	3806	if (NTLN.NumCols() == 1)
	3807	{
	3808	irreducible= true;
	3809	break;
	3810	}
	3811
[38ffb7]	3812	int * zeroOneVecs= extractZeroOneVecs (NTLN);
	3813	bufF= F;
	3814	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
	3815	delete [] zeroOneVecs;
	3816	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
	3817	{
	3818	F= bufF;
	3819	factors= bufFactors;
	3820	delete [] A;
	3821	return result;
	3822	}
[11bf82]	3823
	3824	if (isReduced (NTLN))
	3825	{
	3826	int factorsFound= 0;
[38ffb7]	3827	bufF= F;
[11bf82]	3828	int* factorsFoundIndex= new int [NTLN.NumCols()];
	3829	for (long i= 0; i < NTLN.NumCols(); i++)
	3830	factorsFoundIndex[i]= 0;
	3831	if (l < liftBound)
	3832	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
	3833	factorsFoundIndex, NTLN, false
	3834	);
	3835	else
	3836	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
	3837	degree (LCF), factorsFound, factorsFoundIndex,
	3838	NTLN, false
	3839	);
	3840	if (NTLN.NumCols() == result.length())
	3841	{
	3842	delete [] A;
	3843	delete [] factorsFoundIndex;
	3844	return result;
	3845	}
	3846	delete [] factorsFoundIndex;
	3847	}
	3848	result= CFList();
	3849	oldL= l;
	3850	stepSize *= 2;
	3851	l += stepSize;
	3852	if (l > liftBound)
	3853	{
	3854	if (!hitBound)
	3855	{
	3856	l= liftBound;
	3857	hitBound= true;
	3858	}
	3859	else
	3860	break;
	3861	}
	3862	}
	3863	if (irreducible)
	3864	{
	3865	delete [] A;
	3866	return CFList (F);
	3867	}
	3868	delete [] A;
	3869	factors= bufFactors;
	3870	return CFList();
	3871	}
	3872
	3873	//over field extension
	3874	CFList
	3875	extFurtherLiftingAndIncreasePrecision (CanonicalForm& F, CFList& factors, int l,
	3876	int liftBound, int d, int* bounds,
	3877	mat_zz_p& NTLN, CFList& diophant,
	3878	CFMatrix& M, CFArray& Pi, CFArray& bufQ,
	3879	const CanonicalForm& evaluation, const
	3880	ExtensionInfo& info, CFList& source,
	3881	CFList& dest
	3882	)
	3883	{
	3884	CanonicalForm LCF= LC (F, 1);
	3885	CFList result;
	3886	bool irreducible= false;
	3887	CFList bufFactors= factors;
	3888	CFArray *A = new CFArray [bufFactors.length()];
	3889	bool useOldQs= false;
	3890	bool hitBound= false;
	3891	bool GF= (CFFactory::gettype()==GaloisFieldDomain);
	3892	int degMipo= degree (getMipo (info.getAlpha()));
	3893	Variable alpha= info.getAlpha();
	3894	int oldL= l; //be careful
	3895	int stepSize= 8;
	3896	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l),2);
	3897	Variable gamma= info.getBeta();
	3898	CanonicalForm primElemAlpha= info.getGamma();
	3899	CanonicalForm imPrimElemAlpha= info.getDelta();
	3900	if (NTLN.NumRows() != factors.length()) //refined factors
	3901	ident (NTLN, factors.length());
[38ffb7]	3902	Variable y= F.mvar();
[5335ba]	3903	CanonicalForm powX, imBasis, bufF, truncF;
[38ffb7]	3904	CFMatrix Mat, C;
	3905	CFIterator iter;
	3906	mat_zz_p* NTLMat,*NTLC, NTLK;
	3907	CFListIterator j;
	3908	CFArray buf;
[11bf82]	3909	while (l <= liftBound)
	3910	{
	3911	bufFactors.insert (LCF);
	3912	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
	3913
	3914	if (GF)
	3915	setCharacteristic (getCharacteristic());
	3916
[38ffb7]	3917	powX= power (y-gamma, l);
	3918	Mat= CFMatrix (ldegMipo, ldegMipo);
[11bf82]	3919	for (int i= 0; i < l*degMipo; i++)
	3920	{
	3921
[38ffb7]	3922	imBasis= mod (power (y, i), powX);
[11bf82]	3923	imBasis= imBasis (power (y, degMipo), y);
	3924	imBasis= imBasis (y, gamma);
[38ffb7]	3925	iter= imBasis;
[11bf82]	3926	for (; iter.hasTerms(); iter++)
	3927	Mat (iter.exp()+ 1, i+1)= iter.coeff();
	3928	}
	3929
[38ffb7]	3930	NTLMat= convertFacCFMatrix2NTLmat_zz_p (Mat);
[11bf82]	3931	NTLMat= inv (NTLMat);
	3932
	3933	if (GF)
	3934	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
	3935
[38ffb7]	3936	j= bufFactors;
[5335ba]	3937	truncF= mod (F, power (y, l));
[11bf82]	3938	if (useOldQs)
	3939	{
	3940	for (int i= 0; i < bufFactors.length(); i++, j++)
[5335ba]	3941	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
	3942	bufQ[i]);
[11bf82]	3943	}
	3944	else
	3945	{
	3946	for (int i= 0; i < bufFactors.length(); i++, j++)
[5335ba]	3947	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
[11bf82]	3948	}
	3949	for (int i= 0; i < d; i++)
	3950	{
	3951	if (bounds [i] + 1 <= l/2)
	3952	{
	3953	int k= tmin (bounds [i] + 1, l/2);
[38ffb7]	3954	C= CFMatrix (l*degMipo - k, bufFactors.length());
[11bf82]	3955	for (int ii= 0; ii < bufFactors.length(); ii++)
	3956	{
	3957	if (A[ii].size() - 1 >= i)
	3958	{
	3959	if (GF)
	3960	{
	3961	A [ii] [i]= A [ii] [i] (y-evaluation, y);
	3962	setCharacteristic (getCharacteristic());
	3963	A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
	3964	if (alpha != gamma)
	3965	A [ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
	3966	gamma, source, dest
	3967	);
	3968	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
	3969	}
	3970	else
	3971	{
	3972	A [ii] [i]= A [ii] [i] (y-evaluation, y);
	3973	if (alpha != gamma)
	3974	A[ii] [i]= mapDown (A[ii] [i], imPrimElemAlpha, primElemAlpha,
	3975	gamma, source, dest
	3976	);
	3977	buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
	3978	}
[9ebec2]	3979	writeInMatrix (C, buf, ii + 1, 0);
[11bf82]	3980	}
	3981	if (GF)
	3982	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
	3983	}
	3984
	3985	if (GF)
	3986	setCharacteristic(getCharacteristic());
[38ffb7]	3987	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
	3988	NTLK= (NTLC)NTLN;
[11bf82]	3989	transpose (NTLK, NTLK);
	3990	kernel (NTLK, NTLK);
	3991	transpose (NTLK, NTLK);
	3992	NTLN *= NTLK;
	3993	if (GF)
	3994	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
	3995
	3996	if (NTLN.NumCols() == 1)
	3997	{
	3998	irreducible= true;
	3999	break;
	4000	}
	4001	}
	4002	}
	4003	if (NTLN.NumCols() == 1)
	4004	{
	4005	irreducible= true;
	4006	break;
	4007	}
	4008
[38ffb7]	4009	int * zeroOneVecs= extractZeroOneVecs (NTLN);
	4010	bufF= F;
	4011	result= extReconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN, info,
	4012	evaluation
	4013	);
	4014	delete [] zeroOneVecs;
	4015	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
	4016	{
	4017	F= bufF;
	4018	factors= bufFactors;
	4019	delete [] A;
	4020	return result;
	4021	}
[11bf82]	4022
	4023	if (isReduced (NTLN))
	4024	{
	4025	int factorsFound= 0;
[38ffb7]	4026	bufF= F;
[11bf82]	4027	int* factorsFoundIndex= new int [NTLN.NumCols()];
	4028	for (long i= 0; i < NTLN.NumCols(); i++)
	4029	factorsFoundIndex[i]= 0;
	4030	if (l < degree (bufF) + 1 + degree (LCF))
	4031	extReconstructionTry (result, bufF, bufFactors, l, factorsFound,
	4032	factorsFoundIndex, NTLN, false, info, evaluation
	4033	);
	4034	else
	4035	extReconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
	4036	degree (LCF), factorsFound, factorsFoundIndex,
	4037	NTLN, false, info, evaluation
	4038	);
	4039	if (NTLN.NumCols() == result.length())
	4040	{
	4041	delete [] A;
	4042	delete [] factorsFoundIndex;
	4043	return result;
	4044	}
	4045	delete [] factorsFoundIndex;
	4046	}
	4047	result= CFList();
	4048	oldL= l;
	4049	stepSize *= 2;
	4050	l += stepSize;
	4051	if (l > liftBound)
	4052	{
	4053	if (!hitBound)
	4054	{
	4055	l= liftBound;
	4056	hitBound= true;
	4057	}
	4058	else
	4059	break;
	4060	}
	4061	}
	4062	if (irreducible)
	4063	{
	4064	delete [] A;
	4065	Variable y= Variable (2);
	4066	CanonicalForm tmp= F (y - evaluation, y);
	4067	CFList source, dest;
	4068	tmp= mapDown (tmp, info, source, dest);
	4069	return CFList (tmp);
	4070	}
	4071	delete [] A;
	4072	factors= bufFactors;
	4073	return CFList();
	4074	}
	4075
	4076	CFList
	4077	furtherLiftingAndIncreasePrecisionFq2Fp (CanonicalForm& F, CFList& factors, int
	4078	l, int liftBound, int d, int* bounds,
	4079	mat_zz_p& NTLN, CFList& diophant,
	4080	CFMatrix& M, CFArray& Pi, CFArray& bufQ,
	4081	const Variable& alpha
	4082	)
	4083	{
	4084	CanonicalForm LCF= LC (F, 1);
	4085	CFList result;
	4086	bool irreducible= false;
	4087	CFList bufFactors= factors;
	4088	CFArray *A = new CFArray [bufFactors.length()];
	4089	bool useOldQs= false;
	4090	int extensionDeg= degree (getMipo (alpha));
	4091	bool hitBound= false;
	4092	int oldL= l;
	4093	int stepSize= 8; //TODO choose better step size?
	4094	l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
	4095	if (NTLN.NumRows() != factors.length()) //refined factors
	4096	ident (NTLN, factors.length());
[38ffb7]	4097	CFListIterator j;
	4098	CFMatrix C;
	4099	mat_zz_p* NTLC, NTLK;
[5335ba]	4100	CanonicalForm bufF, truncF;
	4101	Variable y= F.mvar();
[11bf82]	4102	while (l <= liftBound)
	4103	{
	4104	bufFactors.insert (LCF);
	4105	henselLiftResume12 (F, bufFactors, oldL, l, Pi, diophant, M);
[38ffb7]	4106	j= bufFactors;
[5335ba]	4107	truncF= mod (F, power (y, l));
[11bf82]	4108	if (useOldQs)
	4109	{
	4110	for (int i= 0; i < bufFactors.length(); i++, j++)
[5335ba]	4111	A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
	4112	bufQ[i]);
[11bf82]	4113	}
	4114	else
	4115	{
	4116	for (int i= 0; i < bufFactors.length(); i++, j++)
[5335ba]	4117	A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
[11bf82]	4118	}
	4119	for (int i= 0; i < d; i++)
	4120	{
	4121	if (bounds [i] + 1 <= l/2)
	4122	{
	4123	int k= tmin (bounds [i] + 1, l/2);
[38ffb7]	4124	C= CFMatrix ((l - k)*extensionDeg, bufFactors.length());
[11bf82]	4125	for (int ii= 0; ii < bufFactors.length(); ii++)
	4126	{
	4127	CFArray buf;
	4128	if (A[ii].size() - 1 >= i)
[9ebec2]	4129	{
[11bf82]	4130	buf= getCoeffs (A[ii] [i], k, alpha);
[9ebec2]	4131	writeInMatrix (C, buf, ii + 1, 0);
	4132	}
[11bf82]	4133	}
[38ffb7]	4134	NTLC= convertFacCFMatrix2NTLmat_zz_p(C);
	4135	NTLK= (NTLC)NTLN;
[11bf82]	4136	transpose (NTLK, NTLK);
	4137	kernel (NTLK, NTLK);
	4138	transpose (NTLK, NTLK);
	4139	NTLN *= NTLK;
	4140	if (NTLN.NumCols() == 1)
	4141	{
	4142	irreducible= true;
	4143	break;
	4144	}
	4145	}
	4146	}
	4147	if (NTLN.NumCols() == 1)
	4148	{
	4149	irreducible= true;
	4150	break;
	4151	}
	4152
[38ffb7]	4153	int * zeroOneVecs= extractZeroOneVecs (NTLN);
	4154	CanonicalForm bufF= F;
	4155	result= reconstruction (bufF, bufFactors, zeroOneVecs, l, NTLN);
	4156	delete [] zeroOneVecs;
	4157	if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
	4158	{
	4159	F= bufF;
	4160	factors= bufFactors;
	4161	delete [] A;
	4162	return result;
	4163	}
[11bf82]	4164
	4165	if (isReduced (NTLN))
	4166	{
	4167	int factorsFound= 0;
[38ffb7]	4168	bufF= F;
[11bf82]	4169	int* factorsFoundIndex= new int [NTLN.NumCols()];
	4170	for (long i= 0; i < NTLN.NumCols(); i++)
	4171	factorsFoundIndex[i]= 0;
	4172	if (l < degree (bufF) + 1 + degree (LCF))
	4173	reconstructionTry (result, bufF, bufFactors, l, factorsFound,
	4174	factorsFoundIndex, NTLN, false
	4175	);
	4176	else
	4177	reconstructionTry (result, bufF, bufFactors, degree (bufF) + 1 +
	4178	degree (LCF), factorsFound, factorsFoundIndex,
	4179	NTLN, false
	4180	);
	4181	if (NTLN.NumCols() == result.length())
	4182	{
	4183	delete [] A;
	4184	delete [] factorsFoundIndex;
	4185	return result;
	4186	}
	4187	delete [] factorsFoundIndex;
	4188	}
	4189	result= CFList();
	4190	oldL= l;
	4191	stepSize *= 2;
	4192	l += stepSize;
	4193	if (l > liftBound)
	4194	{
	4195	if (!hitBound)
	4196	{
	4197	l= liftBound;
	4198	hitBound= true;
	4199	}
	4200	else
	4201	break;
	4202	}
	4203	}
	4204	if (irreducible)
	4205	{
	4206	delete [] A;
	4207	return CFList (F);
	4208	}
	4209	delete [] A;
	4210	factors= bufFactors;
	4211	return CFList();
	4212	}
	4213
	4214	void
	4215	refineAndRestartLift (const CanonicalForm& F, const mat_zz_p& NTLN, int
	4216	liftBound, int l, CFList& factors, CFMatrix& M, CFArray&
	4217	Pi, CFList& diophant
	4218	)
	4219	{
	4220	CFList bufFactors;
	4221	Variable y= Variable (2);
	4222	CanonicalForm LCF= LC (F, 1);
[38ffb7]	4223	CFListIterator iter;
	4224	CanonicalForm buf;
[11bf82]	4225	for (long i= 1; i <= NTLN.NumCols(); i++)
	4226	{
[38ffb7]	4227	iter= factors;
	4228	buf= 1;
[11bf82]	4229	for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
	4230	{
	4231	if (!IsZero (NTLN (j,i)))
	4232	buf= mulNTL (buf, mod (iter.getItem(), y));
	4233	}
	4234	bufFactors.append (buf);
	4235	}
	4236	factors= bufFactors;
	4237	M= CFMatrix (liftBound, factors.length());
	4238	Pi= CFArray();
	4239	diophant= CFList();
	4240	factors.insert (LCF);
	4241	henselLift12 (F, factors, l, Pi, diophant, M);
	4242	}
	4243
	4244	void
	4245	refineAndRestartLift (const CanonicalForm& F, const mat_zz_pE& NTLN, int
	4246	liftBound, int l, CFList& factors, CFMatrix& M, CFArray&
	4247	Pi, CFList& diophant
	4248	)
	4249	{
	4250	CFList bufFactors;
	4251	Variable y= Variable (2);
	4252	CanonicalForm LCF= LC (F, 1);
[38ffb7]	4253	CFListIterator iter;
	4254	CanonicalForm buf;
[c1b9927]	4255	for (long i= 1; i <= NTLN.NumCols(); i++)
[11bf82]	4256	{
[38ffb7]	4257	iter= factors;
	4258	buf= 1;
[11bf82]	4259	for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
	4260	{
	4261	if (!IsZero (NTLN (j,i)))
	4262	buf= mulNTL (buf, mod (iter.getItem(), y));
	4263	}
	4264	bufFactors.append (buf);
	4265	}
	4266	factors= bufFactors;
	4267	M= CFMatrix (liftBound, factors.length());
	4268	Pi= CFArray();
	4269	diophant= CFList();
	4270	factors.insert (LCF);
	4271	henselLift12 (F, factors, l, Pi, diophant, M);
	4272	}
	4273
	4274	CFList
	4275	earlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_p& N,
	4276	CanonicalForm& bufF, CFList& factors, int& l,
	4277	int& factorsFound, bool beenInThres, CFMatrix& M,
[617dbc]	4278	CFArray& Pi, CFList& diophant, bool symmetric,
	4279	const CanonicalForm& evaluation
[11bf82]	4280	)
	4281	{
[a36fcb5]	4282	int sizeOfLiftPre;
	4283	int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
	4284
	4285	Variable y= F.mvar();
[11bf82]	4286	factorsFound= 0;
	4287	CanonicalForm LCF= LC (F, 1);
	4288	CFList result;
[a36fcb5]	4289	int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
[11bf82]	4290	mat_zz_p NTLN= N;
	4291	int * factorsFoundIndex= new int [NTLN.NumCols()];
	4292	for (long i= 0; i < NTLN.NumCols(); i++)
	4293	factorsFoundIndex [i]= 0;
	4294
	4295	if (degree (F) + 1 > smallFactorDeg)
	4296	{
	4297	if (l < smallFactorDeg)
	4298	{
	4299	factors.insert (LCF);
	4300	henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
	4301	l= smallFactorDeg;
	4302	}
	4303	reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
	4304	factorsFoundIndex, NTLN, beenInThres
	4305	);
	4306	if (result.length() == NTLN.NumCols())
	4307	{
[a36fcb5]	4308	delete [] liftPre;
[11bf82]	4309	delete [] factorsFoundIndex;
	4310	return result;
	4311	}
	4312	}
	4313
[a36fcb5]	4314	int i= sizeOfLiftPre - 1;
	4315	int dummy= 1;
	4316	if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
[11bf82]	4317	{
[a36fcb5]	4318	while (i > 0)
	4319	{
	4320	if (l < liftPre[i-1] + 1)
	4321	{
	4322	factors.insert (LCF);
	4323	henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
	4324	l= liftPre[i-1] + 1;
	4325	}
	4326	else
	4327	{
	4328	i--;
	4329	if (i != 0)
	4330	continue;
	4331	}
	4332	reconstructionTry (result, bufF, factors, l, factorsFound,
	4333	factorsFoundIndex, NTLN, beenInThres
	4334	);
	4335	if (result.length() == NTLN.NumCols())
	4336	{
	4337	delete [] liftPre;
	4338	delete [] factorsFoundIndex;
	4339	return result;
	4340	}
	4341	i--;
	4342	}
[11bf82]	4343	}
[a36fcb5]	4344	else
[11bf82]	4345	{
[a36fcb5]	4346	i= 1;
	4347	while ((degree (F,y)/4)*i + 4 <= smallFactorDeg)
	4348	i++;
[617dbc]	4349	while (i < 5)
[a36fcb5]	4350	{
[617dbc]	4351	dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4);
[a36fcb5]	4352	if (l < dummy)
	4353	{
	4354	factors.insert (LCF);
	4355	henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
	4356	l= dummy;
[617dbc]	4357	if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
	4358	LC (F,1).inCoeffDomain() &&
	4359	(degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
	4360	{
	4361	Variable x= Variable (1);
	4362	CanonicalForm g, h, gg, hh, multiplier1, multiplier2, check1, check2;
	4363	int m= degree (F)/4+1;
	4364	g= factors.getFirst();
	4365	h= factors.getLast();
	4366	g= mod (g, power (y,m));
	4367	h= mod (h, power (y,m));
	4368	g= g (y-evaluation, y);
	4369	h= h (y-evaluation, y);
	4370	gg= mod (swapvar (g,x,y),power (x,m));
	4371	gg= gg (y + evaluation, y);
	4372	multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
	4373	gg= div (gg, power (y,m));
	4374	gg= gg*power (y,m);
	4375	hh= mod (swapvar (h,x,y),power (x,m));
	4376	hh= hh (y + evaluation, y);
	4377	multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
	4378	hh= div (hh, power (y,m));
	4379	hh= hh*power (y,m);
	4380	gg= multiplier1*gg+mod (factors.getLast(), power (y,m));
	4381	hh= multiplier2*hh+mod (factors.getFirst(), power (y,m));
	4382	check1= gg (y-evaluation,y);
	4383	check2= hh (y-evaluation,y);
	4384	check1= swapvar (check1, x, y);
	4385	if (check1/Lc (check1) == check2/Lc (check2))
	4386	{
	4387	result.append (gg);
	4388	result.append (hh);
	4389	delete [] liftPre;
	4390	delete [] factorsFoundIndex;
	4391	return result;
	4392	}
	4393	}
[a36fcb5]	4394	}
	4395	else
	4396	{
	4397	i++;
[617dbc]	4398	if (i < 5)
[a36fcb5]	4399	continue;
	4400	}
	4401	reconstructionTry (result, bufF, factors, l, factorsFound,
	4402	factorsFoundIndex, NTLN, beenInThres
	4403	);
	4404	if (result.length() == NTLN.NumCols())
	4405	{
	4406	delete [] liftPre;
	4407	delete [] factorsFoundIndex;
	4408	return result;
	4409	}
	4410	i++;
	4411	}
[11bf82]	4412	}
	4413
[a36fcb5]	4414	delete [] liftPre;
[11bf82]	4415	delete [] factorsFoundIndex;
	4416	return result;
	4417	}
	4418
	4419	CFList
	4420	earlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_pE& N,
	4421	CanonicalForm& bufF, CFList& factors, int& l,
	4422	int& factorsFound, bool beenInThres, CFMatrix& M,
[eca69d]	4423	CFArray& Pi, CFList& diophant, bool symmetric,
	4424	const CanonicalForm& evaluation
[11bf82]	4425	)
	4426	{
[a36fcb5]	4427	int sizeOfLiftPre;
	4428	int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
	4429	Variable y= F.mvar();
[11bf82]	4430	factorsFound= 0;
	4431	CanonicalForm LCF= LC (F, 1);
	4432	CFList result;
	4433	int smallFactorDeg= 11;
	4434	mat_zz_pE NTLN= N;
	4435	int * factorsFoundIndex= new int [NTLN.NumCols()];
	4436	for (long i= 0; i < NTLN.NumCols(); i++)
	4437	factorsFoundIndex [i]= 0;
[a36fcb5]	4438
[11bf82]	4439	if (degree (F) + 1 > smallFactorDeg)
	4440	{
	4441	if (l < smallFactorDeg)
	4442	{
	4443	factors.insert (LCF);
	4444	henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
	4445	l= smallFactorDeg;
	4446	}
	4447	reconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
	4448	factorsFoundIndex, NTLN, beenInThres
	4449	);
	4450	if (result.length() == NTLN.NumCols())
	4451	{
[a36fcb5]	4452	delete [] liftPre;
[11bf82]	4453	delete [] factorsFoundIndex;
	4454	return result;
	4455	}
	4456	}
	4457
[a36fcb5]	4458	int i= sizeOfLiftPre - 1;
	4459	int dummy= 1;
	4460	if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
[11bf82]	4461	{
[a36fcb5]	4462	while (i > 0)
	4463	{
	4464	if (l < liftPre[i-1] + 1)
	4465	{
	4466	factors.insert (LCF);
	4467	henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
	4468	l= liftPre[i-1] + 1;
	4469	}
	4470	else
	4471	{
	4472	i--;
	4473	if (i != 0)
	4474	continue;
	4475	}
	4476	reconstructionTry (result, bufF, factors, l, factorsFound,
	4477	factorsFoundIndex, NTLN, beenInThres
	4478	);
	4479	if (result.length() == NTLN.NumCols())
	4480	{
	4481	delete [] liftPre;
	4482	delete [] factorsFoundIndex;
	4483	return result;
	4484	}
	4485	i--;
	4486	}
[11bf82]	4487	}
[a36fcb5]	4488	else
[11bf82]	4489	{
[a36fcb5]	4490	i= 1;
	4491	while ((degree (F,y)/4)*i + 4 <= smallFactorDeg)
	4492	i++;
[617dbc]	4493	while (i < 5)
[a36fcb5]	4494	{
[617dbc]	4495	dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4);
[a36fcb5]	4496	if (l < dummy)
	4497	{
	4498	factors.insert (LCF);
	4499	henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
	4500	l= dummy;
[eca69d]	4501	if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
	4502	LC (F,1).inCoeffDomain() &&
	4503	(degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
	4504	{
	4505	Variable x= Variable (1);
	4506	CanonicalForm g, h, gg, hh, multiplier1, multiplier2, check1, check2;
	4507	int m= degree (F)/4+1;
	4508	g= factors.getFirst();
	4509	h= factors.getLast();
	4510	g= mod (g, power (y,m));
	4511	h= mod (h, power (y,m));
	4512	g= g (y-evaluation, y);
	4513	h= h (y-evaluation, y);
	4514	gg= mod (swapvar (g,x,y),power (x,m));
	4515	gg= gg (y + evaluation, y);
	4516	multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
	4517	gg= div (gg, power (y,m));
	4518	gg= gg*power (y,m);
	4519	hh= mod (swapvar (h,x,y),power (x,m));
	4520	hh= hh (y + evaluation, y);
	4521	multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
	4522	hh= div (hh, power (y,m));
	4523	hh= hh*power (y,m);
	4524	gg= multiplier1*gg+mod (factors.getLast(), power (y,m));
	4525	hh= multiplier2*hh+mod (factors.getFirst(), power (y,m));
	4526	check1= gg (y-evaluation,y);
	4527	check2= hh (y-evaluation,y);
	4528	check1= swapvar (check1, x, y);
	4529	if (check1/Lc (check1) == check2/Lc (check2))
	4530	{
	4531	result.append (gg);
	4532	result.append (hh);
	4533	delete [] liftPre;
	4534	delete [] factorsFoundIndex;
	4535	return result;
	4536	}
	4537	}
[a36fcb5]	4538	}
	4539	else
	4540	{
	4541	i++;
[617dbc]	4542	if (i < 5)
[a36fcb5]	4543	continue;
	4544	}
	4545	reconstructionTry (result, bufF, factors, l, factorsFound,
	4546	factorsFoundIndex, NTLN, beenInThres
	4547	);
	4548	if (result.length() == NTLN.NumCols())
	4549	{
	4550	delete [] liftPre;
	4551	delete [] factorsFoundIndex;
	4552	return result;
	4553	}
	4554	i++;
	4555	}
[11bf82]	4556	}
	4557
[a36fcb5]	4558	delete [] liftPre;
[11bf82]	4559	delete [] factorsFoundIndex;
	4560	return result;
	4561	}
	4562
	4563	//over field extension
	4564	CFList
	4565	extEarlyReconstructionAndLifting (const CanonicalForm& F, const mat_zz_p& N,
	4566	CanonicalForm& bufF, CFList& factors, int& l,
	4567	int& factorsFound, bool beenInThres, CFMatrix&
	4568	M, CFArray& Pi, CFList& diophant, const
	4569	ExtensionInfo& info, const CanonicalForm&
	4570	evaluation
	4571	)
	4572	{
[a36fcb5]	4573	int sizeOfLiftPre;
	4574	int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
	4575	Variable y= F.mvar();
[11bf82]	4576	factorsFound= 0;
	4577	CanonicalForm LCF= LC (F, 1);
	4578	CFList result;
	4579	int smallFactorDeg= 11;
	4580	mat_zz_p NTLN= N;
	4581	int * factorsFoundIndex= new int [NTLN.NumCols()];
	4582	for (long i= 0; i < NTLN.NumCols(); i++)
	4583	factorsFoundIndex [i]= 0;
	4584
	4585	if (degree (F) + 1 > smallFactorDeg)
	4586	{
	4587	if (l < smallFactorDeg)
	4588	{
	4589	factors.insert (LCF);
	4590	henselLiftResume12 (F, factors, l, smallFactorDeg, Pi, diophant, M);
	4591	l= smallFactorDeg;
	4592	}
	4593	extReconstructionTry (result, bufF, factors, smallFactorDeg, factorsFound,
	4594	factorsFoundIndex, NTLN, beenInThres, info,
	4595	evaluation
[a36fcb5]	4596	);
[11bf82]	4597	if (result.length() == NTLN.NumCols())
	4598	{
[a36fcb5]	4599	delete [] liftPre;
[11bf82]	4600	delete [] factorsFoundIndex;
	4601	return result;
	4602	}
	4603	}
	4604
[a36fcb5]	4605	int i= sizeOfLiftPre - 1;
	4606	int dummy= 1;
	4607	if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
[11bf82]	4608	{
[a36fcb5]	4609	while (i > 0)
	4610	{
	4611	if (l < liftPre[i-1] + 1)
	4612	{
	4613	factors.insert (LCF);
	4614	henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
	4615	l= liftPre[i-1] + 1;
	4616	}
	4617	else
	4618	{
	4619	i--;
	4620	if (i != 0)
	4621	continue;
	4622	}
	4623	extReconstructionTry (result, bufF, factors, l, factorsFound,
	4624	factorsFoundIndex, NTLN, beenInThres, info,
	4625	evaluation
	4626	);
	4627	if (result.length() == NTLN.NumCols())
	4628	{
	4629	delete [] liftPre;
	4630	delete [] factorsFoundIndex;
	4631	return result;
	4632	}
	4633	i--;
	4634	}
[11bf82]	4635	}
[a36fcb5]	4636	else
[11bf82]	4637	{
[a36fcb5]	4638	i= 1;
	4639	while ((degree (F,y)/4)*i + 4 <= smallFactorDeg)
	4640	i++;
[617dbc]	4641	while (i < 5)
[a36fcb5]	4642	{
[617dbc]	4643	dummy= tmin (degree (F,y)+1, (degree (F,y)/4)*i+4);
[a36fcb5]	4644	if (l < dummy)
	4645	{
	4646	factors.insert (LCF);
	4647	henselLiftResume12 (F, factors, l, dummy, Pi, diophant, M);
	4648	l= dummy;
	4649	}
	4650	else
	4651	{
	4652	i++;
[617dbc]	4653	if (i < 5)
[a36fcb5]	4654	continue;
	4655	}
	4656	extReconstructionTry (result, bufF, factors, l, factorsFound,
	4657	factorsFoundIndex, NTLN, beenInThres, info,
	4658	evaluation
	4659	);
	4660	if (result.length() == NTLN.NumCols())
	4661	{
	4662	delete [] liftPre;
	4663	delete [] factorsFoundIndex;
	4664	return result;
	4665	}
	4666	i++;
	4667	}
[11bf82]	4668	}
	4669
[a36fcb5]	4670	delete [] liftPre;
[11bf82]	4671	delete [] factorsFoundIndex;
	4672	return result;
	4673	}
	4674
	4675	CFList
[c1b9927]	4676	sieveSmallFactors (const CanonicalForm& G, CFList& uniFactors, DegreePattern&
[11bf82]	4677	degPat, CanonicalForm& H, CFList& diophant, CFArray& Pi,
	4678	CFMatrix& M, bool& success, int d
	4679	)
	4680	{
	4681	CanonicalForm F= G;
	4682	CFList bufUniFactors= uniFactors;
	4683	bufUniFactors.insert (LC (F, 1));
	4684	int smallFactorDeg= d;
	4685	DegreePattern degs= degPat;
	4686	henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant, M);
	4687	int adaptedLiftBound;
	4688	success= false;
[1a3011e]	4689	int * factorsFoundIndex= new int [uniFactors.length()];
	4690	for (int i= 0; i < uniFactors.length(); i++)
	4691	factorsFoundIndex [i]= 0;
	4692	CFList earlyFactors;
	4693	earlyFactorDetection (earlyFactors, F, bufUniFactors, adaptedLiftBound,
	4694	factorsFoundIndex, degs, success, smallFactorDeg);
	4695	delete [] factorsFoundIndex;
[11bf82]	4696	if (degs.getLength() == 1)
	4697	{
	4698	degPat= degs;
	4699	return earlyFactors;
	4700	}
	4701	if (success)
	4702	{
	4703	H= F;
	4704	return earlyFactors;
	4705	}
[69c882]	4706	int sizeOldF= size (G);
	4707	if (size (F) < sizeOldF)
[11bf82]	4708	{
[69c882]	4709	H= F;
[11bf82]	4710	success= true;
	4711	return earlyFactors;
	4712	}
	4713	else
	4714	{
	4715	uniFactors= bufUniFactors;
	4716	return CFList();
	4717	}
	4718	}
	4719
	4720	CFList
	4721	extSieveSmallFactors (const CanonicalForm& G, CFList& uniFactors, DegreePattern&
	4722	degPat, CanonicalForm& H, CFList& diophant, CFArray& Pi,
	4723	CFMatrix& M, bool& success, int d, const CanonicalForm&
	4724	evaluation, const ExtensionInfo& info
	4725	)
	4726	{
	4727	CanonicalForm F= G;
	4728	CFList bufUniFactors= uniFactors;
	4729	bufUniFactors.insert (LC (F, 1));
	4730	int smallFactorDeg= d;
	4731	DegreePattern degs= degPat;
	4732	henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant, M);
	4733	int adaptedLiftBound;
	4734	success= false;
[1a3011e]	4735	int * factorsFoundIndex= new int [uniFactors.length()];
	4736	for (int i= 0; i < uniFactors.length(); i++)
	4737	factorsFoundIndex [i]= 0;
	4738	CFList earlyFactors;
	4739	extEarlyFactorDetection (earlyFactors, F, bufUniFactors, adaptedLiftBound,
	4740	factorsFoundIndex, degs, success, info, evaluation,
	4741	smallFactorDeg);
	4742	delete [] factorsFoundIndex;
[11bf82]	4743	if (degs.getLength() == 1)
	4744	{
	4745	degPat= degs;
	4746	return earlyFactors;
	4747	}
	4748	if (success)
	4749	{
	4750	H= F;
	4751	return earlyFactors;
	4752	}
	4753	Variable y= F.mvar();
[773d28]	4754	int sizeOldF= size (G);
[69c882]	4755	if (size (F) < sizeOldF)
[11bf82]	4756	{
[773d28]	4757	H= F;
[11bf82]	4758	success= true;
[69c882]	4759	return earlyFactors;
[11bf82]	4760	}
	4761	else
	4762	{
	4763	uniFactors= bufUniFactors;
	4764	return CFList();
	4765	}
	4766	}
	4767
	4768	CFList
	4769	henselLiftAndLatticeRecombi (const CanonicalForm& G, const CFList& uniFactors,
[617dbc]	4770	const Variable& alpha, const DegreePattern& degPat,
	4771	bool symmetric, const CanonicalForm& evaluation
[11bf82]	4772	)
	4773	{
	4774	DegreePattern degs= degPat;
	4775	CanonicalForm F= G;
	4776	CanonicalForm LCF= LC (F, 1);
	4777	Variable y= F.mvar();
	4778	Variable x= Variable (1);
	4779	int d;
[542864]	4780	bool isIrreducible= false;
	4781	int* bounds= computeBounds (F, d, isIrreducible);
	4782	if (isIrreducible)
	4783	{
	4784	delete [] bounds;
	4785	return CFList (G);
	4786	}
[11bf82]	4787	int minBound= bounds[0];
	4788	for (int i= 1; i < d; i++)
	4789	{
	4790	if (bounds[i] != 0)
	4791	minBound= tmin (minBound, bounds[i]);
	4792	}
	4793
	4794	CFList bufUniFactors= uniFactors;
	4795	CFArray Pi;
	4796	CFList diophant;
	4797	int liftBound= 2*totaldegree (F) - 1;
	4798	CFMatrix M= CFMatrix (liftBound, bufUniFactors.length());
	4799
	4800	CFList smallFactors;
	4801	CanonicalForm H;
[773d28]	4802	bool success= false;
[11bf82]	4803	smallFactors= sieveSmallFactors (F, bufUniFactors, degs, H, diophant, Pi, M,
[a5450a8]	4804	success, minBound + 1
[11bf82]	4805	);
	4806
	4807	if (smallFactors.length() > 0)
	4808	{
	4809	if (smallFactors.length() == 1)
	4810	{
	4811	if (smallFactors.getFirst() == F)
	4812	{
	4813	delete [] bounds;
	4814	return CFList (G);
	4815	}
	4816	}
	4817	if (degs.getLength() <= 1)
	4818	{
	4819	delete [] bounds;
	4820	return smallFactors;
	4821	}
	4822	}
	4823
	4824	int index;
[38ffb7]	4825	CanonicalForm tmp1, tmp2;
[11bf82]	4826	for (CFListIterator i= smallFactors; i.hasItem(); i++)
	4827	{
	4828	index= 1;
	4829	tmp1= mod (i.getItem(),y);
	4830	tmp1 /= Lc (tmp1);
	4831	for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
	4832	{
	4833	tmp2= mod (j.getItem(), y);
	4834	tmp2 /= Lc (tmp2);
	4835	if (tmp1 == tmp2)
	4836	{
	4837	index++;
	4838	j.remove(index);
	4839	break;
	4840	}
	4841	}
	4842	}
	4843
	4844	if (bufUniFactors.isEmpty())
	4845	{
	4846	delete [] bounds;
	4847	return smallFactors;
	4848	}
	4849
	4850	if (success)
	4851	{
	4852	F= H;
	4853	delete [] bounds;
[542864]	4854	bounds= computeBounds (F, d, isIrreducible);
	4855	if (isIrreducible)
	4856	{
	4857	smallFactors.append (F);
	4858	delete [] bounds;
	4859	return smallFactors;
	4860	}
[11bf82]	4861	LCF= LC (F, 1);
	4862
	4863	minBound= bounds[0];
	4864	for (int i= 1; i < d; i++)
	4865	{
	4866	if (bounds[i] != 0)
	4867	minBound= tmin (minBound, bounds[i]);
	4868	}
	4869	Pi= CFArray();
	4870	diophant= CFList();
	4871	liftBound= 2*totaldegree (F) - 1;
	4872	M= CFMatrix (liftBound, bufUniFactors.length());
	4873	DegreePattern bufDegs= DegreePattern (bufUniFactors);
	4874	degs.intersect (bufDegs);
	4875	degs.refine();
	4876	if (degs.getLength() <= 1)
	4877	{
	4878	smallFactors.append (F);
	4879	delete [] bounds;
	4880	return smallFactors;
	4881	}
	4882	}
	4883
	4884	bool reduceFq2Fp= (degree (F) > getCharacteristic());
	4885	bufUniFactors.insert (LCF);
	4886	int l= 1;
	4887
	4888	zz_p::init (getCharacteristic());
	4889	mat_zz_p NTLN;
	4890	if (alpha.level() != 1)
	4891	{
	4892	zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
	4893	zz_pE::init (NTLMipo);
	4894	}
	4895	mat_zz_pE NTLNe;
	4896	if (alpha.level() == 1)
	4897	ident (NTLN, bufUniFactors.length() - 1);
	4898	else
	4899	{
	4900	if (reduceFq2Fp)
	4901	ident (NTLN, bufUniFactors.length() - 1);
	4902	else
	4903	ident (NTLNe, bufUniFactors.length() - 1);
	4904	}
	4905	bool irreducible= false;
	4906	CFArray bufQ= CFArray (bufUniFactors.length() - 1);
	4907
	4908	int oldL;
	4909	if (success)
	4910	{
	4911	int start= 0;
	4912	if (alpha.level() == 1)
	4913	oldL= liftAndComputeLattice (F, bounds, d, start, liftBound, minBound,
	4914	bufUniFactors, NTLN, diophant, M, Pi, bufQ,
	4915	irreducible
	4916	);
	4917	else
	4918	{
	4919	if (reduceFq2Fp)
	4920	oldL= liftAndComputeLatticeFq2Fp (F, bounds, d, start, liftBound,
	4921	minBound, bufUniFactors, NTLN,
	4922	diophant, M, Pi, bufQ, irreducible,
	4923	alpha
	4924	);
	4925	else
	4926	oldL= liftAndComputeLattice (F, bounds, d, start, liftBound, minBound,
	4927	bufUniFactors, NTLNe, diophant, M, Pi, bufQ,
	4928	irreducible
	4929	);
	4930	}
	4931	}
	4932	else
	4933	{
	4934	if (alpha.level() == 1)
[a5450a8]	4935	oldL= liftAndComputeLattice (F, bounds, d, minBound + 1, liftBound,
[11bf82]	4936	minBound, bufUniFactors, NTLN, diophant, M,
	4937	Pi, bufQ, irreducible
	4938	);
	4939	else
	4940	{
	4941	if (reduceFq2Fp)
[a5450a8]	4942	oldL= liftAndComputeLatticeFq2Fp (F, bounds, d, minBound + 1,
[11bf82]	4943	liftBound, minBound, bufUniFactors,
	4944	NTLN, diophant, M, Pi, bufQ,
	4945	irreducible, alpha
	4946	);
	4947	else
[a5450a8]	4948	oldL= liftAndComputeLattice (F, bounds, d, minBound + 1, liftBound,
[11bf82]	4949	minBound, bufUniFactors, NTLNe, diophant,
	4950	M, Pi, bufQ, irreducible
	4951	);
	4952	}
	4953	}
	4954
	4955	bufUniFactors.removeFirst();
	4956	if (oldL > liftBound)
	4957	{
	4958	delete [] bounds;
	4959	return Union (smallFactors,
	4960	factorRecombination (bufUniFactors, F,
	4961	power (y, degree (F) + 1 + degree (LCF)),
	4962	degs, 1, bufUniFactors.length()/2
	4963	)
	4964	);
	4965	}
	4966
	4967	l= oldL;
	4968	if (irreducible)
	4969	{
	4970	delete [] bounds;
	4971	return Union (CFList (F), smallFactors);
	4972	}
	4973
	4974	CanonicalForm yToL= power (y,l);
	4975
	4976	CFList result;
	4977	if (l >= degree (F) + 1)
	4978	{
	4979	int * factorsFoundIndex;
	4980	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
	4981	{
	4982	factorsFoundIndex= new int [NTLN.NumCols()];
	4983	for (long i= 0; i < NTLN.NumCols(); i++)
	4984	factorsFoundIndex[i]= 0;
	4985	}
	4986	else
	4987	{
	4988	factorsFoundIndex= new int [NTLNe.NumCols()];
	4989	for (long i= 0; i < NTLNe.NumCols(); i++)
	4990	factorsFoundIndex[i]= 0;
	4991	}
	4992	int factorsFound= 0;
	4993	CanonicalForm bufF= F;
	4994	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
	4995	reconstructionTry (result, bufF, bufUniFactors, degree (F) + 1,
	4996	factorsFound, factorsFoundIndex, NTLN, false
	4997	);
	4998	else
	4999	reconstructionTry (result, bufF, bufUniFactors, degree (F) + 1,
	5000	factorsFound, factorsFoundIndex, NTLNe, false
	5001	);
	5002	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
	5003	{
	5004	if (result.length() == NTLN.NumCols())
	5005	{
	5006	delete [] factorsFoundIndex;
	5007	delete [] bounds;
	5008	return Union (result, smallFactors);
	5009	}
	5010	}
	5011	else
	5012	{
	5013	if (result.length() == NTLNe.NumCols())
	5014	{
	5015	delete [] factorsFoundIndex;
	5016	delete [] bounds;
	5017	return Union (result, smallFactors);
	5018	}
	5019	}
	5020	delete [] factorsFoundIndex;
	5021	}
	5022	if (l >= liftBound)
	5023	{
	5024	int * factorsFoundIndex;
	5025	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
	5026	{
[c1b9927]	5027	factorsFoundIndex= new int [NTLN.NumCols()];
[11bf82]	5028	for (long i= 0; i < NTLN.NumCols(); i++)
	5029	factorsFoundIndex[i]= 0;
	5030	}
	5031	else
	5032	{
[c1b9927]	5033	factorsFoundIndex= new int [NTLNe.NumCols()];
[11bf82]	5034	for (long i= 0; i < NTLNe.NumCols(); i++)
	5035	factorsFoundIndex[i]= 0;
	5036	}
	5037	CanonicalForm bufF= F;
	5038	int factorsFound= 0;
	5039	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
	5040	reconstructionTry (result, bufF, bufUniFactors, degree (F) + 1 + degree
	5041	(LCF), factorsFound, factorsFoundIndex, NTLN, false
	5042	);
	5043	else
	5044	reconstructionTry (result, bufF, bufUniFactors, degree (F) + 1 + degree
	5045	(LCF), factorsFound, factorsFoundIndex, NTLNe, false
	5046	);
	5047	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
	5048	{
	5049	if (result.length() == NTLN.NumCols())
	5050	{
	5051	delete [] factorsFoundIndex;
	5052	delete [] bounds;
	5053	return Union (result, smallFactors);
	5054	}
	5055	}
	5056	else
	5057	{
	5058	if (result.length() == NTLNe.NumCols())
	5059	{
	5060	delete [] factorsFoundIndex;
	5061	delete [] bounds;
	5062	return Union (result, smallFactors);
	5063	}
	5064	}
	5065	delete [] factorsFoundIndex;
	5066	}
	5067
	5068	result= CFList();
	5069	bool beenInThres= false;
	5070	int thres= 100;
	5071	if (l <= thres)
	5072	{
	5073	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
	5074	{
	5075	if (NTLN.NumCols() < bufUniFactors.length())
	5076	{
[c1b9927]	5077	refineAndRestartLift (F, NTLN, liftBound, l, bufUniFactors, M, Pi,
[11bf82]	5078	diophant
	5079	);
	5080	beenInThres= true;
	5081	}
	5082	}
	5083	else
	5084	{
	5085	if (NTLNe.NumCols() < bufUniFactors.length())
	5086	{
	5087	refineAndRestartLift (F, NTLNe, liftBound, l, bufUniFactors, M, Pi,
	5088	diophant
	5089	);
	5090	beenInThres= true;
	5091	}
	5092	}
	5093	}
	5094
	5095	CanonicalForm bufF= F;
	5096	int factorsFound= 0;
	5097	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
	5098	{
	5099	result= earlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l,
	5100	factorsFound, beenInThres, M, Pi,
[617dbc]	5101	diophant, symmetric, evaluation
[11bf82]	5102	);
	5103
	5104	if (result.length() == NTLN.NumCols())
	5105	{
	5106	delete [] bounds;
	5107	return Union (result, smallFactors);
	5108	}
	5109	}
	5110	else
	5111	{
	5112	result= earlyReconstructionAndLifting (F, NTLNe, bufF, bufUniFactors, l,
	5113	factorsFound, beenInThres, M, Pi,
[eca69d]	5114	diophant, symmetric, evaluation
[11bf82]	5115	);
	5116
	5117	if (result.length() == NTLNe.NumCols())
	5118	{
	5119	delete [] bounds;
	5120	return Union (result, smallFactors);
	5121	}
	5122	}
	5123
	5124	if (result.length() > 0)
	5125	{
	5126	if (beenInThres)
	5127	{
[38ffb7]	5128	int index;
	5129	for (CFListIterator i= result; i.hasItem(); i++)
[11bf82]	5130	{
[38ffb7]	5131	index= 1;
	5132	tmp1= mod (i.getItem(), y);
	5133	tmp1 /= Lc (tmp1);
	5134	for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
[11bf82]	5135	{
[38ffb7]	5136	tmp2= mod (j.getItem(), y);
	5137	tmp2 /= Lc (tmp2);
	5138	if (tmp1 == tmp2)
	5139	{
	5140	index++;
	5141	j.remove(index);
	5142	break;
	5143	}
[11bf82]	5144	}
	5145	}
	5146	}
	5147	else
	5148	{
[38ffb7]	5149	int * zeroOne= extractZeroOneVecs (NTLN);
	5150	CFList bufBufUniFactors= bufUniFactors;
	5151	CFListIterator iter, iter2;
	5152	CanonicalForm buf;
[11bf82]	5153	CFList factorsConsidered;
[38ffb7]	5154	CanonicalForm tmp;
	5155	for (int i= 0; i < NTLN.NumCols(); i++)
[11bf82]	5156	{
[38ffb7]	5157	if (zeroOne [i] == 0)
	5158	continue;
	5159	iter= bufUniFactors;
	5160	buf= 1;
	5161	factorsConsidered= CFList();
	5162	for (int j= 0; j < NTLN.NumRows(); j++, iter++)
[11bf82]	5163	{
[38ffb7]	5164	if (!IsZero (NTLN (j + 1,i + 1)))
	5165	{
	5166	factorsConsidered.append (iter.getItem());
	5167	buf *= mod (iter.getItem(), y);
	5168	}
[11bf82]	5169	}
[38ffb7]	5170	buf /= Lc (buf);
	5171	for (iter2= result; iter2.hasItem(); iter2++)
[11bf82]	5172	{
[38ffb7]	5173	tmp= mod (iter2.getItem(), y);
	5174	tmp /= Lc (tmp);
	5175	if (tmp == buf)
	5176	{
	5177	bufBufUniFactors= Difference (bufBufUniFactors, factorsConsidered);
	5178	break;
	5179	}
[11bf82]	5180	}
	5181	}
[38ffb7]	5182	bufUniFactors= bufBufUniFactors;
	5183	delete [] zeroOne;
[11bf82]	5184	}
	5185
	5186	int oldNumCols;
	5187	CFList resultBufF;
	5188	irreducible= false;
	5189
	5190	if (alpha.level() == 1)
	5191	{
	5192	oldNumCols= NTLN.NumCols();
	5193	resultBufF= increasePrecision (bufF, bufUniFactors, factorsFound,
	5194	oldNumCols, oldL, l
	5195	);
	5196	}
	5197	else
	5198	{
	5199	if (reduceFq2Fp)
	5200	{
	5201	oldNumCols= NTLN.NumCols();
	5202
	5203	resultBufF= increasePrecisionFq2Fp (bufF, bufUniFactors, factorsFound,
	5204	oldNumCols, oldL, alpha, l
	5205	);
	5206	}
	5207	else
	5208	{
	5209	oldNumCols= NTLNe.NumCols();
	5210
	5211	resultBufF= increasePrecision (bufF, bufUniFactors, factorsFound,
	5212	oldNumCols, oldL, alpha, l
	5213	);
	5214	}
	5215	}
	5216
	5217	if (bufUniFactors.isEmpty() \|\| degree (bufF) <= 0)
	5218	{
	5219	delete [] bounds;
	5220	result= Union (resultBufF, result);
	5221	return Union (result, smallFactors);
	5222	}
	5223
	5224	for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
	5225	i.getItem()= mod (i.getItem(), y);
	5226
	5227	result= Union (result, resultBufF);
	5228	result= Union (result, smallFactors);
	5229	delete [] bounds;
	5230	DegreePattern bufDegs= DegreePattern (bufUniFactors);
	5231	degs.intersect (bufDegs);
	5232	degs.refine();
	5233	if (degs.getLength() == 1 \|\| bufUniFactors.length() == 1)
	5234	{
	5235	result.append (bufF);
	5236	return result;
	5237	}
	5238	return Union (result, henselLiftAndLatticeRecombi (bufF, bufUniFactors,
[617dbc]	5239	alpha, degs, symmetric,
	5240	evaluation
[11bf82]	5241	)
	5242	);
	5243	}
	5244
	5245	if (l < liftBound)
	5246	{
	5247	if (alpha.level() == 1)
	5248	{
	5249	result=increasePrecision (F, bufUniFactors, oldL, l, d, bounds, bufQ,
	5250	NTLN
	5251	);
	5252	}
	5253	else
	5254	{
	5255	if (reduceFq2Fp)
	5256	{
	5257	result=increasePrecisionFq2Fp (F, bufUniFactors, oldL, l, d, bounds,
	5258	bufQ, NTLN, alpha
	5259	);
	5260	}
	5261	else
	5262	{
	5263	result=increasePrecision (F, bufUniFactors, oldL, l, d, bounds, bufQ,
	5264	NTLNe
	5265	);
	5266	}
	5267	}
	5268	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
	5269	{
[c1b9927]	5270	if (result.length()== NTLN.NumCols())
[11bf82]	5271	{
	5272	delete [] bounds;
	5273	result= Union (result, smallFactors);
	5274	return result;
	5275	}
	5276	}
	5277	else
	5278	{
[c1b9927]	5279	if (result.length()== NTLNe.NumCols())
[11bf82]	5280	{
	5281	delete [] bounds;
	5282	result= Union (result, smallFactors);
	5283	return result;
	5284	}
	5285	}
	5286
	5287	if (result.isEmpty())
	5288	{
	5289	if (alpha.level() == 1)
	5290	result= furtherLiftingAndIncreasePrecision (F,bufUniFactors, l,
	5291	liftBound, d, bounds, NTLN,
	5292	diophant, M, Pi, bufQ
	5293	);
	5294	else
	5295	{
	5296	if (reduceFq2Fp)
	5297	result= furtherLiftingAndIncreasePrecisionFq2Fp (F,bufUniFactors, l,
	5298	liftBound, d, bounds,
	5299	NTLN, diophant, M,
	5300	Pi, bufQ, alpha
	5301	);
	5302	else
	5303	result= furtherLiftingAndIncreasePrecision (F,bufUniFactors, l,
	5304	liftBound, d, bounds,
	5305	NTLNe, diophant, M,
	5306	Pi, bufQ
	5307	);
	5308	}
	5309
	5310	if (alpha.level() == 1 \|\| (alpha.level() != 1 && reduceFq2Fp))
	5311	{
[c1b9927]	5312	if (result.length() == NTLN.NumCols())
[11bf82]	5313	{
	5314	delete [] bounds;
	5315	result= Union (result, smallFactors);
	5316	return result;
	5317	}
	5318	}
	5319	else
	5320	{
[c1b9927]	5321	if (result.length() == NTLNe.NumCols())
[11bf82]	5322	{
	5323	delete [] bounds;
	5324	result= Union (result, smallFactors);
	5325	return result;
	5326	}
	5327	}
	5328	}
	5329	}
	5330
	5331	DEBOUTLN (cerr, "lattice recombination failed");
	5332
	5333	DegreePattern bufDegs= DegreePattern (bufUniFactors);
	5334	degs.intersect (bufDegs);
	5335	degs.refine();
	5336
	5337	delete [] bounds;
[542864]	5338	bounds= computeBounds (F, d, isIrreducible);
	5339	if (isIrreducible)
	5340	{
	5341	delete [] bounds;
	5342	result= Union (result, smallFactors);
	5343	result.append (F);
	5344	return result;
	5345	}
[11bf82]	5346	minBound= bounds[0];
	5347	for (int i= 1; i < d; i++)
	5348	{
	5349	if (bounds[i] != 0)
	5350	minBound= tmin (minBound, bounds[i]);
	5351	}
	5352
	5353	if (minBound > 16 \|\| result.length() == 0)
	5354	{
	5355	result= Union (result, smallFactors);
	5356	CanonicalForm MODl= power (y, degree (F) + 1 + degree (LC (F, 1)));
	5357	delete [] bounds;
	5358	return Union (result, factorRecombination (bufUniFactors, F, MODl, degs, 1,
	5359	bufUniFactors.length()/2
	5360	)
	5361	);
	5362	}
	5363	else
	5364	{
	5365	result= Union (result, smallFactors);
	5366	for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
	5367	i.getItem()= mod (i.getItem(), y);
	5368	delete [] bounds;
	5369	return Union (result, henselLiftAndLatticeRecombi (F, bufUniFactors, alpha,
[617dbc]	5370	degs,symmetric, evaluation
[11bf82]	5371	)
	5372	);
	5373	}
	5374	}
	5375
	5376	ExtensionInfo
	5377	init4ext (const ExtensionInfo& info, const CanonicalForm& evaluation,
	5378	int& degMipo
	5379	)
	5380	{
	5381	bool GF= (CFFactory::gettype() == GaloisFieldDomain);
	5382	Variable alpha= info.getAlpha();
	5383	if (GF)
	5384	{
	5385	degMipo= getGFDegree();
	5386	CanonicalForm GFMipo= gf_mipo;
	5387	setCharacteristic (getCharacteristic());
	5388	GFMipo.mapinto();
	5389	alpha= rootOf (GFMipo);
	5390	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
	5391	}
	5392	else
	5393	{
	5394	alpha= info.getAlpha();
	5395	degMipo= degree (getMipo (alpha));
	5396	}
	5397
	5398	Variable gamma;
	5399	CanonicalForm primElemAlpha, imPrimElemAlpha;
	5400	if ((!GF && evaluation != alpha) \|\| (GF && evaluation != getGFGenerator()))
	5401	{
	5402	CanonicalForm bufEvaluation;
	5403	if (GF)
	5404	{
	5405	setCharacteristic (getCharacteristic());
	5406	bufEvaluation= GF2FalphaRep (evaluation, alpha);
	5407	}
	5408	else
	5409	bufEvaluation= evaluation;
	5410	CanonicalForm mipo= findMinPoly (bufEvaluation, alpha);
	5411	gamma= rootOf (mipo);
	5412	Variable V_buf;
[ac8e1a]	5413	bool fail= false;
[11bf82]	5414	primElemAlpha= primitiveElement (alpha, V_buf, fail);
	5415	imPrimElemAlpha= map (primElemAlpha, alpha, bufEvaluation, gamma);
	5416
	5417	if (GF)
	5418	setCharacteristic (getCharacteristic(), degMipo, info.getGFName());
	5419	}
	5420	else
	5421	gamma= alpha;
	5422	ExtensionInfo info2= ExtensionInfo (alpha, gamma, primElemAlpha,
	5423	imPrimElemAlpha, 1, info.getGFName(), true
	5424	);
	5425
	5426	return info2;
	5427	}
	5428
	5429	CFList
	5430	extHenselLiftAndLatticeRecombi(const CanonicalForm& G, const CFList& uniFactors,
	5431	const ExtensionInfo& extInfo, const
	5432	DegreePattern& degPat, const CanonicalForm& eval
	5433	)
	5434	{
	5435	CanonicalForm evaluation= eval;
	5436	ExtensionInfo info= extInfo;
	5437	Variable alpha;
	5438	DegreePattern degs= degPat;
	5439	CanonicalForm F= G;
	5440	Variable x= Variable (1);
	5441	Variable y= F.mvar();
	5442	CFList bufUniFactors= uniFactors;
	5443
	5444
	5445	int degMipo;
	5446	ExtensionInfo info2= init4ext (info, evaluation, degMipo);
	5447
	5448	CFList source, dest;
	5449	CanonicalForm LCF= LC (F, 1);
	5450
	5451	int d;
[542864]	5452	bool isIrreducible= false;
	5453	int* bounds= computeBounds (F, d, isIrreducible);
	5454	if (isIrreducible)
	5455	{
	5456	delete [] bounds;
[773d28]	5457	CFList source, dest;
	5458	CanonicalForm tmp= G (y - evaluation, y);
	5459	tmp= mapDown (tmp, info, source, dest);
	5460	return CFList (tmp);
[542864]	5461	}
[11bf82]	5462	int minBound= bounds[0];
	5463	for (int i= 1; i < d; i++)
	5464	{
	5465	if (bounds[i] != 0)
	5466	minBound= tmin (minBound, bounds[i]);
	5467	}
	5468
	5469
	5470	CFArray Pi;
	5471	CFList diophant;
	5472	int liftBound= tmax ((2*totaldegree (F) - 1)/degMipo + 1, degree (F) + 1 +
	5473	degree (LC (F, 1)));
	5474	CFMatrix M= CFMatrix (liftBound, bufUniFactors.length());
	5475
	5476	CFList smallFactors;
	5477	CanonicalForm H;
[773d28]	5478	bool success= false;
[11bf82]	5479	smallFactors= extSieveSmallFactors (F, bufUniFactors, degs, H, diophant, Pi,
	5480	M, success, minBound + 1, evaluation, info
	5481	);
	5482
	5483	if (smallFactors.length() > 0)
	5484	{
	5485	if (smallFactors.length() == 1)
	5486	{
	5487	if (smallFactors.getFirst() == F)
	5488	{
	5489	delete [] bounds;
	5490	CFList source, dest;
	5491	CanonicalForm tmp= G (y - evaluation, y);
	5492	tmp= mapDown (tmp, info, source, dest);
	5493	return CFList (tmp);
	5494	}
	5495	}
	5496	if (degs.getLength() <= 1)
	5497	{
	5498	delete [] bounds;
	5499	return smallFactors;
	5500	}
	5501	}
	5502
	5503	int index;
[38ffb7]	5504	CanonicalForm tmp1, tmp2;
[11bf82]	5505	for (CFListIterator i= smallFactors; i.hasItem(); i++)
	5506	{
	5507	index= 1;
	5508	tmp1= mod (i.getItem(), y - evaluation);
	5509	tmp1 /= Lc (tmp1);
	5510	for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
	5511	{
	5512	tmp2= mod (j.getItem(), y);
	5513	tmp2 /= Lc (tmp2);
	5514	if (tmp1 == tmp2)
	5515	{
	5516	index++;
	5517	j.remove(index);
	5518	break;
	5519	}
	5520	}
	5521	}
	5522
	5523	if (bufUniFactors.isEmpty())
	5524	{
	5525	delete [] bounds;
	5526	return smallFactors;
	5527	}
	5528
	5529	if (success)
	5530	{
	5531	F= H;
	5532	delete [] bounds;
[542864]	5533	bounds= computeBounds (F, d, isIrreducible);
	5534	if (isIrreducible)
	5535	{
	5536	delete [] bounds;
	5537	CFList source, dest;
	5538	CanonicalForm tmp= F (y - evaluation, y);
	5539	tmp= mapDown (tmp, info, source, dest);
	5540	smallFactors.append (tmp);
	5541	return smallFactors;
	5542	}
[11bf82]	5543	LCF= LC (F, 1);
	5544
	5545	minBound= bounds[0];
	5546	for (int i= 1; i < d; i++)
	5547	{
	5548	if (bounds[i] != 0)
	5549	minBound= tmin (minBound, bounds[i]);
	5550	}
	5551	Pi= CFArray();
	5552	diophant= CFList();
	5553	liftBound=tmax ((2*totaldegree (F) - 1)/degMipo + 1, degree (F) + 1 +
	5554	degree (LC (F, 1)));
	5555	M= CFMatrix (liftBound, bufUniFactors.length());
	5556	DegreePattern bufDegs= DegreePattern (bufUniFactors);
	5557	degs.intersect (bufDegs);
	5558	degs.refine();
	5559	if (degs.getLength() <= 1)
	5560	{
	5561	delete [] bounds;
	5562	CFList source, dest;
	5563	CanonicalForm tmp= F (y - evaluation, y);
	5564	tmp= mapDown (tmp, info, source, dest);
	5565	smallFactors.append (tmp);
	5566	return smallFactors;
	5567	}
	5568	}
	5569
	5570	bufUniFactors.insert (LCF);
	5571	int l= 1;
	5572
	5573	zz_p::init (getCharacteristic());
	5574	zz_pX NTLMipo;
	5575	mat_zz_p NTLN;
	5576
	5577	ident (NTLN, bufUniFactors.length() - 1);
	5578	bool irreducible= false;
	5579	CFArray bufQ= CFArray (bufUniFactors.length() - 1);
	5580
	5581	int oldL;
	5582	if (success)
	5583	{
	5584	int start= 0;
	5585	oldL= extLiftAndComputeLattice (F, bounds, d, liftBound, minBound, start,
	5586	bufUniFactors, NTLN, diophant, M, Pi, bufQ,
	5587	irreducible, evaluation, info2, source, dest
	5588	);
	5589	}
	5590	else
	5591	{
	5592	oldL= extLiftAndComputeLattice (F, bounds, d, liftBound, minBound,
	5593	minBound + 1, bufUniFactors, NTLN, diophant,
	5594	M, Pi, bufQ, irreducible, evaluation, info2,
	5595	source, dest
	5596	);
	5597	}
	5598
	5599	bufUniFactors.removeFirst();
	5600	if (oldL > liftBound)
	5601	{
	5602	delete [] bounds;
	5603	return Union (smallFactors, extFactorRecombination
	5604	(bufUniFactors, F,
	5605	power (y, degree (F) + 1 + degree (LCF)),info,
	5606	degs, evaluation, 1, bufUniFactors.length()/2
	5607	)
	5608	);
	5609	}
	5610
	5611	l= oldL;
	5612	if (irreducible)
	5613	{
	5614	delete [] bounds;
	5615	CFList source, dest;
	5616	CanonicalForm tmp= F (y - evaluation, y);
	5617	tmp= mapDown (tmp, info, source, dest);
	5618	return Union (CFList (tmp), smallFactors);
	5619	}
	5620
	5621	CanonicalForm yToL= power (y,l);
	5622
	5623	CFList result;
	5624	if (l >= degree (F) + 1)
	5625	{
	5626	int * factorsFoundIndex;
	5627
	5628	factorsFoundIndex= new int [NTLN.NumCols()];
	5629	for (long i= 0; i < NTLN.NumCols(); i++)
	5630	factorsFoundIndex[i]= 0;
	5631
	5632	int factorsFound= 0;
	5633	CanonicalForm bufF= F;
	5634
	5635	extReconstructionTry (result, bufF, bufUniFactors, degree (F) + 1,
	5636	factorsFound, factorsFoundIndex, NTLN, false, info,
	5637	evaluation
	5638	);
	5639
	5640	if (result.length() == NTLN.NumCols())
	5641	{
	5642	delete [] factorsFoundIndex;
	5643	delete [] bounds;
	5644	return Union (result, smallFactors);
	5645	}
	5646
	5647	delete [] factorsFoundIndex;
	5648	}
	5649	if (l >= liftBound)
	5650	{
	5651	int * factorsFoundIndex;
[38ffb7]	5652	factorsFoundIndex= new int [NTLN.NumCols()];
	5653	for (long i= 0; i < NTLN.NumCols(); i++)
	5654	factorsFoundIndex[i]= 0;
[11bf82]	5655	CanonicalForm bufF= F;
	5656	int factorsFound= 0;
	5657
	5658	extReconstructionTry (result, bufF, bufUniFactors, degree (F) + 1 + degree
	5659	(LCF), factorsFound, factorsFoundIndex, NTLN, false,
	5660	info, evaluation
	5661	);
	5662
	5663	if (result.length() == NTLN.NumCols())
	5664	{
	5665	delete [] factorsFoundIndex;
	5666	delete [] bounds;
	5667	return Union (result, smallFactors);
	5668	}
	5669	delete [] factorsFoundIndex;
	5670	}
	5671
	5672	result= CFList();
	5673	bool beenInThres= false;
	5674	int thres= 100;
	5675	if (l <= thres && bufUniFactors.length() > NTLN.NumCols())
	5676	{
	5677	refineAndRestartLift (F, NTLN, 2*totaldegree (F)-1, l, bufUniFactors, M, Pi,
	5678	diophant
	5679	);
	5680	beenInThres= true;
	5681	}
	5682
	5683
	5684	CanonicalForm bufF= F;
	5685	int factorsFound= 0;
	5686
	5687	result= extEarlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l,
	5688	factorsFound, beenInThres, M, Pi,
	5689	diophant, info, evaluation
	5690	);
	5691
	5692	if (result.length() == NTLN.NumCols())
	5693	{
	5694	delete [] bounds;
	5695	return Union (result, smallFactors);
	5696	}
	5697
	5698	if (result.length() > 0)
	5699	{
	5700	if (beenInThres)
	5701	{
	5702	int index;
	5703	for (CFListIterator i= result; i.hasItem(); i++)
	5704	{
	5705	index= 1;
	5706	tmp1= mod (i.getItem(), y-evaluation);
	5707	tmp1 /= Lc (tmp1);
	5708	for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
	5709	{
	5710	tmp2= mod (j.getItem(), y);
	5711	tmp2 /= Lc (tmp2);
	5712	if (tmp1 == tmp2)
	5713	{
	5714	index++;
	5715	j.remove(index);
	5716	break;
	5717	}
	5718	}
	5719	}
	5720	}
	5721	else
	5722	{
	5723	int * zeroOne= extractZeroOneVecs (NTLN);
	5724	CFList bufBufUniFactors= bufUniFactors;
[38ffb7]	5725	CFListIterator iter, iter2;
	5726	CanonicalForm buf;
	5727	CFList factorsConsidered;
[11bf82]	5728	for (int i= 0; i < NTLN.NumCols(); i++)
	5729	{
	5730	if (zeroOne [i] == 0)
	5731	continue;
[38ffb7]	5732	iter= bufUniFactors;
	5733	buf= 1;
	5734	factorsConsidered= CFList();
[11bf82]	5735	for (int j= 0; j < NTLN.NumRows(); j++, iter++)
	5736	{
	5737	if (!IsZero (NTLN (j + 1,i + 1)))
	5738	{
	5739	factorsConsidered.append (iter.getItem());
	5740	buf *= mod (iter.getItem(), y);
	5741	}
	5742	}
	5743	buf /= Lc (buf);
[38ffb7]	5744	for (iter2= result; iter2.hasItem(); iter2++)
[11bf82]	5745	{
	5746	CanonicalForm tmp= mod (iter2.getItem(), y - evaluation);
	5747	tmp /= Lc (tmp);
	5748	if (tmp == buf)
	5749	{
	5750	bufBufUniFactors= Difference (bufBufUniFactors, factorsConsidered);
	5751	break;
	5752	}
	5753	}
	5754	}
	5755	bufUniFactors= bufBufUniFactors;
	5756	delete [] zeroOne;
	5757	}
	5758
	5759	int oldNumCols;
	5760	CFList resultBufF;
	5761	irreducible= false;
	5762
	5763	oldNumCols= NTLN.NumCols();
	5764	resultBufF= extIncreasePrecision (bufF, bufUniFactors, factorsFound,
	5765	oldNumCols, oldL, evaluation, info2,
	5766	source, dest, l
	5767	);
	5768
	5769	if (bufUniFactors.isEmpty() \|\| degree (bufF) <= 0)
	5770	{
	5771	delete [] bounds;
	5772	result= Union (resultBufF, result);
	5773	return Union (result, smallFactors);
	5774	}
	5775
	5776	for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
	5777	i.getItem()= mod (i.getItem(), y);
	5778
	5779	delete [] bounds;
	5780	CFList bufResult;
	5781	DegreePattern bufDegs= DegreePattern (bufUniFactors);
	5782	degs.intersect (bufDegs);
	5783	degs.refine();
	5784	result= Union (result, smallFactors);
	5785	if (degs.getLength() == 1 \|\| bufUniFactors.length() == 1)
	5786	{
	5787	result.append (bufF);
	5788	return result;
	5789	}
	5790	return Union (result, extHenselLiftAndLatticeRecombi (bufF, bufUniFactors,
	5791	info, degs, evaluation
	5792	)
	5793	);
	5794	}
	5795
	5796	if (l/degMipo < liftBound)
	5797	{
	5798	result=extIncreasePrecision (F, bufUniFactors, oldL, l, d, bounds, bufQ,
	5799	NTLN, evaluation, info2, source, dest
	5800	);
	5801
[c1b9927]	5802	if (result.length()== NTLN.NumCols())
[11bf82]	5803	{
	5804	delete [] bounds;
	5805	result= Union (result, smallFactors);
	5806	return result;
	5807	}
	5808
	5809	if (result.isEmpty())
	5810	{
	5811	result= extFurtherLiftingAndIncreasePrecision (F,bufUniFactors, l,
	5812	liftBound, d, bounds, NTLN,
	5813	diophant, M, Pi, bufQ,
	5814	evaluation, info2, source,
	5815	dest
	5816	);
[c1b9927]	5817	if (result.length()== NTLN.NumCols())
[11bf82]	5818	{
	5819	delete [] bounds;
	5820	result= Union (result, smallFactors);
	5821	return result;
	5822	}
	5823	}
	5824	}
	5825
	5826	DEBOUTLN (cerr, "lattice recombination failed");
	5827
	5828	DegreePattern bufDegs= DegreePattern (bufUniFactors);
	5829	degs.intersect (bufDegs);
	5830	degs.refine();
	5831
	5832	delete [] bounds;
[542864]	5833	bounds= computeBounds (F, d, isIrreducible);
	5834	if (isIrreducible)
	5835	{
	5836	delete [] bounds;
	5837	CFList source, dest;
	5838	CanonicalForm tmp= F (y - evaluation, y);
	5839	tmp= mapDown (tmp, info, source, dest);
	5840	smallFactors.append (tmp);
	5841	result= Union (result, smallFactors);
	5842	return result;
	5843	}
[11bf82]	5844	minBound= bounds[0];
	5845	for (int i= 1; i < d; i++)
	5846	{
	5847	if (bounds[i] != 0)
	5848	minBound= tmin (minBound, bounds[i]);
	5849	}
	5850
	5851	if (minBound > 16 \|\| result.length() == 0)
	5852	{
	5853	result= Union (result, smallFactors);
	5854	CanonicalForm MODl= power (y, degree (F) + 1 + degree (LC (F, 1)));
	5855	delete [] bounds;
	5856	return Union (result, extFactorRecombination (bufUniFactors, F, MODl, info,
	5857	degs, evaluation, 1,
	5858	bufUniFactors.length()/2
	5859	)
	5860	);
	5861	}
	5862	else
	5863	{
	5864	result= Union (result, smallFactors);
	5865	for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
	5866	i.getItem()= mod (i.getItem(), y);
	5867	delete [] bounds;
	5868	return Union (result, extHenselLiftAndLatticeRecombi (F, bufUniFactors,
	5869	info, degs, evaluation
	5870	)
	5871	);
	5872	}
	5873	}
	5874
	5875	CFList
	5876	extBiFactorize (const CanonicalForm& F, const ExtensionInfo& info);
	5877
	5878	/// bivariate factorization over finite fields as decribed in "Factoring
	5879	/// multivariate polynomials over a finite field" by L Bernardin.
	5880	CFList
	5881	biFactorize (const CanonicalForm& F, const ExtensionInfo& info)
	5882	{
	5883	if (F.inCoeffDomain())
	5884	return CFList(F);
	5885
	5886	CanonicalForm A= F;
	5887	bool GF= (CFFactory::gettype() == GaloisFieldDomain);
	5888
	5889	Variable alpha= info.getAlpha();
	5890	Variable beta= info.getBeta();
	5891	CanonicalForm gamma= info.getGamma();
	5892	CanonicalForm delta= info.getDelta();
	5893	int k= info.getGFDegree();
	5894	bool extension= info.isInExtension();
	5895	if (A.isUnivariate())
	5896	{
	5897	if (extension == false)
	5898	return uniFactorizer (F, alpha, GF);
	5899	else
	5900	{
	5901	CFList source, dest;
	5902	A= mapDown (A, info, source, dest);
	5903	return uniFactorizer (A, beta, GF);
	5904	}
	5905	}
	5906
	5907	CFMap N;
	5908	A= compress (A, N);
	5909	Variable y= A.mvar();
	5910
	5911	if (y.level() > 2) return CFList (F);
	5912	Variable x= Variable (1);
	5913
	5914	//remove and factorize content
	5915	CanonicalForm contentAx= content (A, x);
	5916	CanonicalForm contentAy= content (A);
	5917
	5918	A= A/(contentAx*contentAy);
	5919	CFList contentAxFactors, contentAyFactors;
	5920
	5921	if (!extension)
	5922	{
	5923	contentAxFactors= uniFactorizer (contentAx, alpha, GF);
	5924	contentAyFactors= uniFactorizer (contentAy, alpha, GF);
	5925	}
	5926
	5927	//trivial case
	5928	CFList factors;
	5929	if (A.inCoeffDomain())
	5930	{
	5931	append (factors, contentAxFactors);
	5932	append (factors, contentAyFactors);
	5933	decompress (factors, N);
	5934	return factors;
	5935	}
	5936	else if (A.isUnivariate())
	5937	{
	5938	factors= uniFactorizer (A, alpha, GF);
	5939	append (factors, contentAxFactors);
	5940	append (factors, contentAyFactors);
	5941	decompress (factors, N);
	5942	return factors;
	5943	}
	5944
[3c25c9]	5945
[0777ea]	5946	//check trivial case
[3c25c9]	5947	if (degree (A) == 1 \|\| degree (A, 1) == 1 \|\|
[86aa4d5]	5948	(size (A) == 2 && igcd (degree (A), degree (A,1))==1))
[0777ea]	5949	{
	5950	factors.append (A);
	5951
	5952	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
	5953	false, false, N);
	5954
	5955	normalize (factors);
	5956	return factors;
	5957	}
	5958
[11bf82]	5959	// check derivatives
	5960	bool derivXZero= false;
	5961	CanonicalForm derivX= deriv (A, x);
	5962	CanonicalForm gcdDerivX;
	5963	if (derivX.isZero())
	5964	derivXZero= true;
	5965	else
	5966	{
	5967	gcdDerivX= gcd (A, derivX);
	5968	if (degree (gcdDerivX) > 0)
	5969	{
	5970	CanonicalForm g= A/gcdDerivX;
	5971	CFList factorsG=
	5972	Union (biFactorize (g, info), biFactorize (gcdDerivX, info));
	5973	append (factorsG, contentAxFactors);
	5974	append (factorsG, contentAyFactors);
	5975	decompress (factorsG, N);
	5976	normalize (factors);
	5977	return factorsG;
	5978	}
	5979	}
	5980	bool derivYZero= false;
	5981	CanonicalForm derivY= deriv (A, y);
	5982	CanonicalForm gcdDerivY;
	5983	if (derivY.isZero())
	5984	derivYZero= true;
	5985	else
	5986	{
	5987	gcdDerivY= gcd (A, derivY);
	5988	if (degree (gcdDerivY) > 0)
	5989	{
	5990	CanonicalForm g= A/gcdDerivY;
	5991	CFList factorsG=
	5992	Union (biFactorize (g, info), biFactorize (gcdDerivY, info));
	5993	append (factorsG, contentAxFactors);
	5994	append (factorsG, contentAyFactors);
	5995	decompress (factorsG, N);
	5996	normalize (factors);
	5997	return factorsG;
	5998	}
	5999	}
	6000	//main variable is chosen s.t. the degree in x is minimal
	6001	bool swap= false;
	6002	if ((degree (A) > degree (A, x)) \|\| derivXZero)
	6003	{
	6004	if (!derivYZero)
	6005	{
	6006	A= swapvar (A, y, x);
	6007	swap= derivXZero;
	6008	derivXZero= derivYZero;
	6009	derivYZero= swap;
	6010	swap= true;
	6011	}
	6012	}
	6013
[542864]	6014	int boundsLength;
	6015	bool isIrreducible= false;
	6016	int * bounds= computeBounds (A, boundsLength, isIrreducible);
	6017	if (isIrreducible)
	6018	{
	6019	delete [] bounds;
	6020	factors.append (A);
	6021
	6022	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
	6023	swap, false, N);
	6024
	6025	normalize (factors);
	6026	return factors;
	6027	}
	6028
[11bf82]	6029	bool fail= false;
[617dbc]	6030	CanonicalForm Aeval, evaluation, bufAeval, bufEvaluation, buf, tmp;
[11bf82]	6031	CFList uniFactors, list, bufUniFactors;
	6032	DegreePattern degs;
	6033	DegreePattern bufDegs;
	6034
	6035	bool fail2= false;
	6036	CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
	6037	CFList bufUniFactors2, list2, uniFactors2;
	6038	DegreePattern degs2;
	6039	DegreePattern bufDegs2;
	6040	bool swap2= false;
	6041
	6042	// several univariate factorizations to obtain more information about the
	6043	// degree pattern therefore usually less combinations have to be tried during
	6044	// the recombination process
	6045	int factorNums= 3;
	6046	int subCheck1= substituteCheck (A, x);
	6047	int subCheck2= substituteCheck (A, y);
[617dbc]	6048	bool symmetric= false;
[11bf82]	6049	for (int i= 0; i < factorNums; i++)
	6050	{
	6051	bufAeval= A;
	6052	bufEvaluation= evalPoint (A, bufAeval, alpha, list, GF, fail);
[3ef0a0]	6053	if (!derivXZero && !fail2 && !symmetric)
[11bf82]	6054	{
[617dbc]	6055	if (i == 0)
	6056	{
	6057	buf= swapvar (A, x, y);
	6058	symmetric= (A/Lc (A) == buf/Lc (buf));
	6059	}
[11bf82]	6060	bufAeval2= buf;
	6061	bufEvaluation2= evalPoint (buf, bufAeval2, alpha, list2, GF, fail2);
	6062	}
	6063	// first try to change main variable if there is no valid evaluation point
	6064	if (fail && (i == 0))
	6065	{
[3ef0a0]	6066	if (!derivXZero && !fail2 && !symmetric)
[11bf82]	6067	{
	6068	bufEvaluation= bufEvaluation2;
	6069	int dummy= subCheck2;
	6070	subCheck2= subCheck1;
	6071	subCheck1= dummy;
[617dbc]	6072	tmp= A;
[11bf82]	6073	A= buf;
[617dbc]	6074	buf= tmp;
[11bf82]	6075	bufAeval= bufAeval2;
	6076	swap2= true;
	6077	fail= false;
	6078	}
	6079	else
	6080	fail= true;
	6081	}
	6082
	6083	// if there is no valid evaluation point pass to a field extension
	6084	if (fail && (i == 0))
	6085	{
	6086	factors= extBiFactorize (A, info);
	6087	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
	6088	swap, swap2, N);
	6089	normalize (factors);
	6090	return factors;
	6091	}
	6092
	6093	// there is at least one valid evaluation point
	6094	// but we do not compute more univariate factorization over an extension
	6095	if (fail && (i != 0))
	6096	break;
	6097
	6098	// univariate factorization
[978ce3]	6099	TIMING_START (fac_fq_uni_factorizer);
[11bf82]	6100	bufUniFactors= uniFactorizer (bufAeval, alpha, GF);
[978ce3]	6101	TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
[7bf145]	6102	"time for univariate factorization: ");
[806c18]	6103	DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
[f3a82f4]	6104	(prod (bufUniFactors)*Lc (bufAeval) == bufAeval));
[7bf145]	6105
[3ef0a0]	6106	if (!derivXZero && !fail2 && !symmetric)
[7bf145]	6107	{
[978ce3]	6108	TIMING_START (fac_fq_uni_factorizer);
[7bf145]	6109	bufUniFactors2= uniFactorizer (bufAeval2, alpha, GF);
[978ce3]	6110	TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
[7bf145]	6111	"time for univariate factorization in y: ");
[27ab36]	6112	DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
[f3a82f4]	6113	(prod (bufUniFactors2)*Lc (bufAeval2) == bufAeval2));
[7bf145]	6114	}
	6115
[806c18]	6116	if (bufUniFactors.length() == 1 \|\|
[3ef0a0]	6117	(!fail2 && !derivXZero && !symmetric && (bufUniFactors2.length() == 1)))
[7bf145]	6118	{
	6119	if (extension)
	6120	{
	6121	CFList source, dest;
[da984c]	6122	appendMapDown (factors, A, info, source, dest);
[7bf145]	6123	}
[806c18]	6124	else
[7bf145]	6125	factors.append (A);
	6126
[806c18]	6127	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
[7bf145]	6128	swap, swap2, N);
	6129
	6130	normalize (factors);
	6131	return factors;
	6132	}
	6133
[686ce3]	6134	if (i == 0)
	6135	{
[dd8047]	6136	if (subCheck1 > 0)
[686ce3]	6137	{
[dd8047]	6138	int subCheck= substituteCheck (bufUniFactors);
	6139
	6140	if (subCheck > 1 && (subCheck1%subCheck == 0))
	6141	{
	6142	CanonicalForm bufA= A;
	6143	subst (bufA, bufA, subCheck, x);
	6144	factors= biFactorize (bufA, info);
	6145	reverseSubst (factors, subCheck, x);
	6146	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
	6147	swap, swap2, N);
	6148	normalize (factors);
	6149	return factors;
	6150	}
[686ce3]	6151	}
	6152
[3ef0a0]	6153	if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
[686ce3]	6154	{
[dd8047]	6155	int subCheck= substituteCheck (bufUniFactors2);
	6156
	6157	if (subCheck > 1 && (subCheck2%subCheck == 0))
[686ce3]	6158	{
	6159	CanonicalForm bufA= A;
	6160	subst (bufA, bufA, subCheck, y);
	6161	factors= biFactorize (bufA, info);
[2caede4]	6162	reverseSubst (factors, subCheck, y);
[686ce3]	6163	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
	6164	swap, swap2, N);
	6165	normalize (factors);
	6166	return factors;
	6167	}
	6168	}
	6169	}
	6170
[806c18]	6171	// degree analysis
	6172	bufDegs = DegreePattern (bufUniFactors);
[3ef0a0]	6173	if (!derivXZero && !fail2 && !symmetric)
[7bf145]	6174	bufDegs2= DegreePattern (bufUniFactors2);
	6175
[806c18]	6176	if (i == 0)
[7bf145]	6177	{
	6178	Aeval= bufAeval;
	6179	evaluation= bufEvaluation;
	6180	uniFactors= bufUniFactors;
	6181	degs= bufDegs;
[3ef0a0]	6182	if (!derivXZero && !fail2 && !symmetric)
[7bf145]	6183	{
	6184	Aeval2= bufAeval2;
	6185	evaluation2= bufEvaluation2;
	6186	uniFactors2= bufUniFactors2;
	6187	degs2= bufDegs2;
	6188	}
	6189	}
[806c18]	6190	else
[7bf145]	6191	{
	6192	degs.intersect (bufDegs);
[3ef0a0]	6193	if (!derivXZero && !fail2 && !symmetric)
[7bf145]	6194	{
	6195	degs2.intersect (bufDegs2);
[806c18]	6196	if (bufUniFactors2.length() < uniFactors2.length())
	6197	{
[7bf145]	6198	uniFactors2= bufUniFactors2;
	6199	Aeval2= bufAeval2;
	6200	evaluation2= bufEvaluation2;
	6201	}
[806c18]	6202	}
	6203	if (bufUniFactors.length() < uniFactors.length())
	6204	{
[3af6b6]	6205	uniFactors= bufUniFactors;
	6206	Aeval= bufAeval;
	6207	evaluation= bufEvaluation;
[7bf145]	6208	}
	6209	}
	6210	list.append (bufEvaluation);
[3ef0a0]	6211	if (!derivXZero && !fail2 && !symmetric)
[7bf145]	6212	list2.append (bufEvaluation2);
	6213	}
[806c18]	6214
[3ef0a0]	6215	if (!derivXZero && !fail2 && !symmetric)
[7bf145]	6216	{
[3af6b6]	6217	if (uniFactors.length() > uniFactors2.length() \|\|
[806c18]	6218	(uniFactors.length() == uniFactors2.length()
[3af6b6]	6219	&& degs.getLength() > degs2.getLength()))
[7bf145]	6220	{
	6221	degs= degs2;
	6222	uniFactors= uniFactors2;
	6223	evaluation= evaluation2;
	6224	Aeval= Aeval2;
	6225	A= buf;
	6226	swap2= true;
	6227	}
	6228	}
[806c18]	6229
	6230	if (degs.getLength() == 1) // A is irreducible
[7bf145]	6231	{
[806c18]	6232	if (extension)
[7bf145]	6233	{
	6234	CFList source, dest;
[11bf82]	6235	appendMapDown (factors, A, info, source, dest);
[7bf145]	6236	}
[806c18]	6237	else
[7bf145]	6238	factors.append (A);
[806c18]	6239	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
[7bf145]	6240	swap, swap2, N);
	6241	normalize (factors);
	6242	return factors;
	6243	}
	6244
[1a3011e]	6245	int liftBound= degree (A, y) + 1;
[11bf82]	6246
[542864]	6247	if (swap2)
	6248	bounds= computeBounds (A, boundsLength, isIrreducible);
	6249
[11bf82]	6250	int minBound= bounds[0];
	6251	for (int i= 1; i < boundsLength; i++)
	6252	{
	6253	if (bounds[i] != 0)
	6254	minBound= tmin (minBound, bounds[i]);
	6255	}
	6256
[3c25c9]	6257	A= A (y + evaluation, y);
	6258
[11bf82]	6259	int degMipo= 1;
	6260	if (extension && alpha.level() != 1 && k==1)
	6261	degMipo= degree (getMipo (alpha));
[7bf145]	6262
	6263	DEBOUTLN (cerr, "uniFactors= " << uniFactors);
[11bf82]	6264
[ac8e1a]	6265	if ((GF && !extension) \|\| (GF && extension && k != 1))
[11bf82]	6266	{
	6267	bool earlySuccess= false;
	6268	CFList earlyFactors;
[978ce3]	6269	TIMING_START (fac_fq_bi_hensel_lift);
[c1b9927]	6270	uniFactors= henselLiftAndEarly
[7bf145]	6271	(A, earlySuccess, earlyFactors, degs, liftBound,
[806c18]	6272	uniFactors, info, evaluation);
[978ce3]	6273	TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift, "time for hensel lifting: ");
[11bf82]	6274	DEBOUTLN (cerr, "lifted factors= " << uniFactors);
[7bf145]	6275
[11bf82]	6276	CanonicalForm MODl= power (y, liftBound);
	6277
	6278	if (extension)
	6279	factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
	6280	evaluation, 1, uniFactors.length()/2);
	6281	else
	6282	factors= factorRecombination (uniFactors, A, MODl, degs, 1,
	6283	uniFactors.length()/2);
	6284
	6285	if (earlySuccess)
	6286	factors= Union (earlyFactors, factors);
	6287	else if (!earlySuccess && degs.getLength() == 1)
	6288	factors= earlyFactors;
	6289	}
	6290	else if (degree (A) > 4 && beta.level() == 1 && (2*minBound)/degMipo < 32)
	6291	{
[978ce3]	6292	TIMING_START (fac_fq_bi_hensel_lift);
[11bf82]	6293	if (extension)
	6294	{
	6295	CFList lll= extHenselLiftAndLatticeRecombi (A, uniFactors, info, degs,
	6296	evaluation
	6297	);
	6298	factors= Union (lll, factors);
	6299	}
	6300	else if (alpha.level() == 1 && !GF)
	6301	{
[617dbc]	6302	CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
	6303	symmetric, evaluation);
[11bf82]	6304	factors= Union (lll, factors);
	6305	}
[a54114]	6306	else if (!extension && (alpha != x \|\| GF))
[11bf82]	6307	{
[617dbc]	6308	CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
	6309	symmetric, evaluation);
[11bf82]	6310	factors= Union (lll, factors);
	6311	}
[978ce3]	6312	TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift, "time for hensel lifting: ");
[11bf82]	6313	DEBOUTLN (cerr, "lifted factors= " << uniFactors);
	6314	}
[806c18]	6315	else
[11bf82]	6316	{
	6317	bool earlySuccess= false;
	6318	CFList earlyFactors;
[978ce3]	6319	TIMING_START (fac_fq_bi_hensel_lift);
[11bf82]	6320	uniFactors= henselLiftAndEarly
	6321	(A, earlySuccess, earlyFactors, degs, liftBound,
	6322	uniFactors, info, evaluation);
[978ce3]	6323	TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift, "time for hensel lifting: ");
[11bf82]	6324	DEBOUTLN (cerr, "lifted factors= " << uniFactors);
	6325
	6326	CanonicalForm MODl= power (y, liftBound);
	6327	if (!extension)
	6328	{
	6329	factors= factorRecombination (uniFactors, A, MODl, degs, 1, 3);
	6330
	6331	int oldUniFactorsLength= uniFactors.length();
	6332	if (degree (A) > 0)
	6333	{
	6334	CFList tmp;
	6335	if (alpha.level() == 1)
	6336	tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
	6337	liftBound
	6338	);
	6339	else
	6340	{
	6341	if (degree (A) > getCharacteristic())
	6342	tmp= increasePrecisionFq2Fp (A, uniFactors, 0, uniFactors.length(),
	6343	1, alpha, liftBound
	6344	);
	6345	else
	6346	tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
	6347	alpha, liftBound
	6348	);
	6349	}
	6350	factors= Union (factors, tmp);
	6351	if (tmp.length() == 0 \|\| (tmp.length() > 0 && uniFactors.length() != 0
	6352	&& uniFactors.length() != oldUniFactorsLength)
	6353	)
	6354	{
	6355	DegreePattern bufDegs= DegreePattern (uniFactors);
	6356	degs.intersect (bufDegs);
	6357	degs.refine ();
	6358	factors= Union (factors, factorRecombination (uniFactors, A, MODl,
	6359	degs, 4,
	6360	uniFactors.length()/2
	6361	)
	6362	);
	6363	}
	6364	}
	6365	}
	6366	else
	6367	{
	6368	if (beta.level() != 1 \|\| k > 1)
	6369	{
	6370	if (k > 1)
	6371	{
	6372	factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
	6373	evaluation, 1, uniFactors.length()/2
	6374	);
	6375	}
	6376	else
	6377	{
	6378	factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
	6379	evaluation, 1, 3
	6380	);
	6381	if (degree (A) > 0)
	6382	{
	6383	CFList tmp= increasePrecision2 (A, uniFactors, alpha, liftBound);
	6384	DegreePattern bufDegs= DegreePattern (tmp);
	6385	degs.intersect (bufDegs);
	6386	degs.refine ();
	6387	factors= Union (factors, extFactorRecombination (tmp, A, MODl, info,
	6388	degs, evaluation,
	6389	1, tmp.length()/2
	6390	)
	6391	);
	6392	}
	6393	}
	6394	}
	6395	else
	6396	{
	6397	factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
	6398	evaluation, 1, 3
	6399	);
	6400	int oldUniFactorsLength= uniFactors.length();
	6401	if (degree (A) > 0)
	6402	{
	6403	int degMipo;
	6404	ExtensionInfo info2= init4ext (info, evaluation, degMipo);
	6405
	6406	CFList source, dest;
	6407	CFList tmp= extIncreasePrecision (A, uniFactors, 0,
	6408	uniFactors.length(), 1, evaluation,
	6409	info2, source, dest, liftBound
	6410	);
	6411	factors= Union (factors, tmp);
	6412	if (tmp.length() == 0 \|\| (tmp.length() > 0 && uniFactors.length() != 0
	6413	&& uniFactors.length() != oldUniFactorsLength)
	6414	)
	6415	{
	6416	DegreePattern bufDegs= DegreePattern (uniFactors);
	6417	degs.intersect (bufDegs);
	6418	degs.refine ();
	6419	factors= Union (factors,extFactorRecombination (uniFactors, A, MODl,
	6420	info, degs, evaluation,
	6421	4, uniFactors.length()/2
	6422	)
	6423	);
	6424	}
	6425	}
	6426	}
	6427	}
[806c18]	6428
[11bf82]	6429	if (earlySuccess)
	6430	factors= Union (earlyFactors, factors);
	6431	else if (!earlySuccess && degs.getLength() == 1)
	6432	factors= earlyFactors;
	6433	}
	6434	delete [] bounds;
[7bf145]	6435	if (!extension)
	6436	{
	6437	for (CFListIterator i= factors; i.hasItem(); i++)
	6438	i.getItem()= i.getItem() (y - evaluation, y);
	6439	}
	6440
[806c18]	6441	appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
[7bf145]	6442	swap, swap2, N);
[806c18]	6443	normalize (factors);
[7bf145]	6444
	6445	return factors;
	6446	}
	6447
[806c18]	6448	CFList
	6449	extBiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
[7bf145]	6450	{
[806c18]	6451
[7bf145]	6452	CanonicalForm A= F;
	6453	Variable alpha= info.getAlpha();
	6454	Variable beta= info.getBeta();
	6455	int k= info.getGFDegree();
	6456	char cGFName= info.getGFName();
	6457	CanonicalForm delta= info.getDelta();
	6458
	6459	bool GF= (CFFactory::gettype() == GaloisFieldDomain);
[806c18]	6460	Variable x= Variable (1);
[7bf145]	6461	CFList factors;
	6462	if (!GF && alpha == x) // we are in F_p
	6463	{
[806c18]	6464	bool extension= true;
[7bf145]	6465	int p= getCharacteristic();
[806c18]	6466	if (p*p < (1<<16)) // pass to GF if possible
	6467	{
[7bf145]	6468	setCharacteristic (getCharacteristic(), 2, 'Z');
	6469	A= A.mapinto();
[11bf82]	6470	ExtensionInfo info2= ExtensionInfo (extension);
	6471	factors= biFactorize (A, info2);
[7bf145]	6472
[0a7d0ca]	6473	CanonicalForm mipo= gf_mipo;
[7bf145]	6474	setCharacteristic (getCharacteristic());
[0a7d0ca]	6475	Variable vBuf= rootOf (mipo.mapinto());
[806c18]	6476	for (CFListIterator j= factors; j.hasItem(); j++)
	6477	j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
[7bf145]	6478	}
[806c18]	6479	else // not able to pass to GF, pass to F_p(\alpha)
	6480	{
[a54114]	6481	CanonicalForm mipo= randomIrredpoly (2, x);
[7bf145]	6482	Variable v= rootOf (mipo);
[11bf82]	6483	ExtensionInfo info2= ExtensionInfo (v);
	6484	factors= biFactorize (A, info2);
[806c18]	6485	}
[7bf145]	6486	return factors;
	6487	}
	6488	else if (!GF && (alpha != x)) // we are in F_p(\alpha)
[806c18]	6489	{
[7bf145]	6490	if (k == 1) // need factorization over F_p
	6491	{
	6492	int extDeg= degree (getMipo (alpha));
[806c18]	6493	extDeg++;
[a54114]	6494	CanonicalForm mipo= randomIrredpoly (extDeg + 1, x);
[7bf145]	6495	Variable v= rootOf (mipo);
[11bf82]	6496	ExtensionInfo info2= ExtensionInfo (v);
	6497	factors= biFactorize (A, info2);
[7bf145]	6498	}
[806c18]	6499	else
[7bf145]	6500	{
[a54114]	6501	if (beta == x)
[7bf145]	6502	{
[11bf82]	6503	Variable v= chooseExtension (alpha, beta, k);
[7bf145]	6504	CanonicalForm primElem, imPrimElem;
	6505	bool primFail= false;
	6506	Variable vBuf;
	6507	primElem= primitiveElement (alpha, vBuf, primFail);
	6508	ASSERT (!primFail, "failure in integer factorizer");
	6509	if (primFail)
	6510	; //ERROR
	6511	else
[618da5]	6512	imPrimElem= mapPrimElem (primElem, alpha, v);
[7bf145]	6513
	6514	CFList source, dest;
[806c18]	6515	CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
[7bf145]	6516	source, dest);
[11bf82]	6517	ExtensionInfo info2= ExtensionInfo (v, alpha, imPrimElem, primElem);
	6518	factors= biFactorize (bufA, info2);
[7bf145]	6519	}
	6520	else
	6521	{
[11bf82]	6522	Variable v= chooseExtension (alpha, beta, k);
[7bf145]	6523	CanonicalForm primElem, imPrimElem;
	6524	bool primFail= false;
	6525	Variable vBuf;
	6526	ASSERT (!primFail, "failure in integer factorizer");
	6527	if (primFail)
	6528	; //ERROR
	6529	else
[618da5]	6530	imPrimElem= mapPrimElem (delta, beta, v);
[7bf145]	6531
	6532	CFList source, dest;
	6533	CanonicalForm bufA= mapDown (A, info, source, dest);
	6534	source= CFList();
	6535	dest= CFList();
	6536	bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
[11bf82]	6537	ExtensionInfo info2= ExtensionInfo (v, beta, imPrimElem, delta);
	6538	factors= biFactorize (bufA, info2);
[7bf145]	6539	}
	6540	}
	6541	return factors;
	6542	}
	6543	else // we are in GF (p^k)
[806c18]	6544	{
[7bf145]	6545	int p= getCharacteristic();
	6546	int extensionDeg= getGFDegree();
	6547	bool extension= true;
	6548	if (k == 1) // need factorization over F_p
	6549	{
	6550	extensionDeg++;
[806c18]	6551	if (ipower (p, extensionDeg) < (1<<16))
	6552	// pass to GF(p^k+1)
[7bf145]	6553	{
[0a7d0ca]	6554	CanonicalForm mipo= gf_mipo;
[7bf145]	6555	setCharacteristic (p);
[0a7d0ca]	6556	Variable vBuf= rootOf (mipo.mapinto());
[806c18]	6557	A= GF2FalphaRep (A, vBuf);
	6558	setCharacteristic (p, extensionDeg, 'Z');
[11bf82]	6559	ExtensionInfo info2= ExtensionInfo (extension);
	6560	factors= biFactorize (A.mapinto(), info2);
[7bf145]	6561	}
	6562	else // not able to pass to another GF, pass to F_p(\alpha)
[806c18]	6563	{
[0a7d0ca]	6564	CanonicalForm mipo= gf_mipo;
[806c18]	6565	setCharacteristic (p);
[0a7d0ca]	6566	Variable vBuf= rootOf (mipo.mapinto());
[806c18]	6567	A= GF2FalphaRep (A, vBuf);
[11bf82]	6568	Variable v= chooseExtension (vBuf, beta, k);
	6569	ExtensionInfo info2= ExtensionInfo (v, extension);
	6570	factors= biFactorize (A, info2);
[7bf145]	6571	}
	6572	}
	6573	else // need factorization over GF (p^k)
	6574	{
[806c18]	6575	if (ipower (p, 2*extensionDeg) < (1<<16))
[7bf145]	6576	// pass to GF (p^2k)
[806c18]	6577	{
	6578	setCharacteristic (p, 2*extensionDeg, 'Z');
[11bf82]	6579	ExtensionInfo info2= ExtensionInfo (k, cGFName, extension);
	6580	factors= biFactorize (GFMapUp (A, extensionDeg), info2);
[806c18]	6581	setCharacteristic (p, extensionDeg, cGFName);
[7bf145]	6582	}
	6583	else // not able to pass to GF (p^2k), pass to F_p (\alpha)
[806c18]	6584	{
[0a7d0ca]	6585	CanonicalForm mipo= gf_mipo;
[806c18]	6586	setCharacteristic (p);
[0a7d0ca]	6587	Variable v1= rootOf (mipo.mapinto());
[806c18]	6588	A= GF2FalphaRep (A, v1);
[11bf82]	6589	Variable v2= chooseExtension (v1, v1, k);
[7bf145]	6590	CanonicalForm primElem, imPrimElem;
	6591	bool primFail= false;
	6592	Variable vBuf;
	6593	primElem= primitiveElement (v1, vBuf, primFail);
	6594	ASSERT (!primFail, "failure in integer factorizer");
	6595	if (primFail)
	6596	; //ERROR
	6597	else
[618da5]	6598	imPrimElem= mapPrimElem (primElem, v1, v2);
[7bf145]	6599
	6600	CFList source, dest;
[806c18]	6601	CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
[7bf145]	6602	source, dest);
[11bf82]	6603	ExtensionInfo info2= ExtensionInfo (v2, v1, imPrimElem, primElem);
	6604	factors= biFactorize (bufA, info2);
[806c18]	6605	setCharacteristic (p, k, cGFName);
	6606	for (CFListIterator i= factors; i.hasItem(); i++)
	6607	i.getItem()= Falpha2GFRep (i.getItem());
[7bf145]	6608	}
	6609	}
	6610	return factors;
	6611	}
	6612	}
	6613
	6614	#endif
	6615	/* HAVE_NTL */
	6616
	6617

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

Download in other formats: