[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

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 | ||

9.4.2 Square-free factorization and Factorization | ||

9.4.3 Splitting fields |

[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

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)

[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

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]]

[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

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
`[`

.
The second element, a list of pairs of form
**root**, algptorat(**defining polynomial**)]`[`

,
corresponds to the **root**,algptorat(**defining polynomial**)]**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.

[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] |

This document was generated on *April 25, 2018* using *texi2html 5.0*.