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]]
Go to the first, previous, next, last section, table of contents.