Asir: 9.4 Operations for uni-variate polynomials over an algebraic number field

In the file ‘sp’ are provided functions for uni-variate polynomial factorization and uni-variate polynomial GCD computation over algebraic numbers, and furthermore, as an application of them, functions to compute splitting fields of univariate polynomials.

9.4.1 GCD

Greatest common divisors (GCD) over algebraic number fields are computed by cr_gcda() function. This function computes GCD by using modular computation and Chinese remainder theorem and it works for the case where the ground field is a multiple extension.

[63] A=newalg(t^9-15*t^6-87*t^3-125);
(#0)
[64] B=newalg(75*s^2+(10*A^7-175*A^4-470*A)*s+3*A^8-45*A^5-261*A^2);
(#1)
[65] P1=75*x^2+(150*B+10*A^7-175*A^4-395*A)*x
+(75*B^2+(10*A^7-175*A^4-395*A)*B+13*A^8-220*A^5-581*A^2)$
[66] P2=x^2+A*x+A^2$
[67] cr_gcda(P1,P2);
27*x+((#0^6-19*#0^3-65)*#1-#0^7+19*#0^4+38*#0)

9.4.2 Square-free factorization and Factorization

For square-free factorization (of uni-variate polynomials over algebraic number fields), we employ the most fundamental algorithm which begins first to compute GCD of a polynomial and its derivative. The function to do this factorization is asq().

[116] A=newalg(x^2+x+1);                           
(#4)
[117] T=simpalg((x+A+1)*(x^2-2*A-3)^2*(x^3-x-A)^2);
x^11+(#4+1)*x^10+(-4*#4-8)*x^9+(-10*#4-4)*x^8+(16*#4+20)*x^7
+(24*#4-6)*x^6+(-29*#4-31)*x^5+(-15*#4+28)*x^4+(38*#4+29)*x^3
+(#4-23)*x^2+(-21*#4-7)*x+(3*#4+8)
[118] asq(T);
[[x^5+(-2*#4-4)*x^3+(-#4)*x^2+(2*#4+3)*x+(#4-2),2],[x+(#4+1),1]]

Like factorization over the rational number field, the result is presented, commonly to both square-free factorization and factorization, as a list whose elements are pairs (list of two elements) in the form [factor, multiplicity] without the constant multiple part.

Here, it should be noticed that the products of all factors of the result may DIFFER from the input polynomial by a constant. The reason is that the factors are normalized so that they have integral leading coefficients for the sake of readability.

This incongruity may happen to square-free factorization and factorization commonly.

The algorithm employed for factorization over algebraic number fields is an improvement of the norm method by Trager. It is especially very effective to factorize a polynomial over a field obtained by adjoining some of its root’s to the base field.

[119] af(T,[A]);
[[x^3-x+(-#4),2],[x^2+(-2*#4-3),2],[x+(#4+1),1]]

The function takes two arguments: The second argument is a list of root’s. Factorization is performed over a field obtained by adjoining the root’s to the rational number field. It is important to keep in mind that the ordering of the root’s must obey a restriction: Last defined should come first. The automatic re-ordering is not done. It should be done by yourself.

The efficiency of factorization via norm depends on the efficiency of the norm computation and univariate factorization over the rationals. Especially the latter often causes combinatorial explosion and the computation will stick in such a case.

[120] B=newalg(x^2-2*A-3);
(#5)
[121] af(T,[B,A]);
[[x+(#5),2],[x^3-x+(-#4),2],[x+(-#5),2],[x+(#4+1),1]]

9.4.3 Splitting fields

This operation may be somewhat unusual and for specific interest. (Galois Group for example.) Procedurally, however, it is easy to obtain the splitting field of a polynomial by repeated application of algebraic factorization described in the previous section. The function is sp().

[103] sp(x^5-2);
[[x+(-#1),2*x+(#0^3*#1^3+#0^4*#1^2+2*#1+2*#0),2*x+(-#0^4*#1^2),
2*x+(-#0^3*#1^3),x+(-#0)],
[[(#1),t#1^4+t#0*t#1^3+t#0^2*t#1^2+t#0^3*t#1+t#0^4],[(#0),t#0^5-2]]]

Function sp() takes only one argument. The result is a list of two element: The first element is a list of linear factors, and the second one is a list whose elements are pairs (list of two elements) in the form [root, algptorat(defining polynomial)]. The second element, a list of pairs of form [root,algptorat(defining polynomial)], corresponds to the root’s which are adjoined to eventually obtain the splitting field. They are listed in the reverse order of adjoining. Each of the defining polynomials in the list is, of course, guaranteed to be irreducible over the field obtained by adjoining all root’s defined before it.

The first element of the result, a list of linear factors, contains all irreducible factors of the input polynomial over the field obtained by adjoining all root’s in the second element of the result. Because such field is the splitting field of the input polynomial, factors in the result are all linear as the consequence.

Similarly to function af(), the product of all resulting factors may yield a polynomial which differs by a constant.