Algebraic Integer Relation with LLL

[aidevnn]

FastGoat/FastGoat/Examples/AlgebraicIntegerRelationLLL.cs

Lines 171 to 193 in c312d8b

	public static ConcreteGroup<EPoly<Rational>> GaloisGroupLLL(KPoly<Rational> P, int O1, int O2)
	{
	Console.WriteLine(P);
	GlobalStopWatch.AddLap();
	var nRoots = FG.NRoots(P.ToBcPoly(O2));
	GlobalStopWatch.Show("Roots");
	var alpha = nRoots[0];
	return GaloisGroupNumericRoots(alpha, nRoots, P, O1);
	}
	public static void Example3()
	{
	var x = FG.QPoly();
	GlobalStopWatch.Restart();
	var galGr = GaloisGroupLLL(x.Pow(6) + 108, O1: 50, O2: 75); // S3
	DisplayGroup.HeadElements(galGr);
	var X = FG.KPoly('X', galGr.Neutral());
	Console.WriteLine("Prod[X - ri] = {0}", galGr.Aggregate(X.One, (acc, r) => acc * (X - r)));
	GlobalStopWatch.Show("END"); // Time:242 ms
	}

O1 represents the minimum number of digits required in the lattice, while O2 represents the maximum number of digits required for precise computation before populating the lattice, both of which are typically determined through trial and error. However, a more efficient approach involves using a minorant to predict O1 and O2 based on the polynomial degree and its coefficients. Although this method may be challenging, it represents a significant improvement for future applications.

[aidevnn]

The normality of the polynomial P must also be checked before continuing with LLL.