Context Navigation

source: git/factory/facFqBivar.cc @ 72bfc8

spielwiese

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

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

Download in other formats: