ETD

Archivio digitale delle tesi discusse presso l'Università di Pisa

Tesi etd-08292016-123353


Tipo di tesi
Tesi di laurea magistrale
Autore
SIRCANA, CARLO
URN
etd-08292016-123353
Titolo
Factoring polynomials over Z/(n)
Dipartimento
MATEMATICA
Corso di studi
MATEMATICA
Relatori
relatore Dott. Sbarra, Enrico
correlatore Prof.ssa Gianni, Patrizia
Parole chiave
  • normalizzazione.
  • Fattorizzazione di polinomi
Data inizio appello
16/09/2016
Consultabilità
Completa
Riassunto
The problem of factoring polynomials is one of the main issues of computational algebra and has been successfully solved for polynomials with coefficients in rings
such as the integers Z and
the finite fields F_q.
In this thesis, we deal with the problem of factoring polynomials over quotient rings of $\Z$. This topic
has its origin in the setting of coding theory, in some generalizations of cyclic codes, but it is also interesting for its own sake.
For instance, it is linked by means of Hensel's lemma to the factorization of polynomials over p-adic fields and some other main issues of algebraic number theory.
We deal with this connections in the first chapter, along with some reductions
of the problem and some introductory facts concerning the uniqueness of factorization.
The first theorems present relations between factorization over Z/(p^l) and over the p-adic integers.
In the second chapter, we study one of the main tools for p-adic factorization: Newton polygons.
We then give a brief description of the algorithm for factoring polynomials to obtain a deeper understanding of how Newton polygons are used in this context.
\newline Given this background information, we describe the state of the art for factoring polynomials over Z/(n).
In particular, we illustrate the ideas of the algorithm by Von Zur Gathen and Hartlieb and the improvements made by Cheng and Labahn
to find all the factorizations in Z/(n), assuming some conditions on n depending on the discriminant of the polynomial.
The algorithm uses the p-adic factorization of the polynomial and some properties of the resultant in order to obtain all the factorizations over Z/(n) with a lifting method,
which reduces the problem to the computation of an echelon form of a matrix over the integer.
In spite of the efficiency of this method, it does not provide a satisfactory solution, because the correctness of this algorithm depends on the valuation of the discriminant of the polynomial.
Another approach was presented by Salagean, who gives an algorithm to compute a factorization of a polynomial over Z/(p^2),
where p is a prime number, with no restrictions on the discriminant of the polynomial.
Her point of view has inspired our work. The key point of Salagean's approach is an irreducibility criterion
for polynomial over Z/(p^2). In the fourth chapter, we generalize this criterion, obtaining some interesting results:
we give two different interpretations of the irreducibility criterion for polynomials over Z/(p^2) obtaining two other independent proofs,
one using the theory about Newton's polygons, the other using Dedekind's Criterion.
Our work on the first approach consists of a generalization of the Newton's polygons.
In particular, we give a necessary condition on the shape of a Newton's polygon of an irreducible polynomial over Z/(p^l) and a criterion for
determining whether or not a polynomial is irreducible over Z/(p^l).
Furthermore, we speed up the computation of the lifting method given by Von Zur Gathen and Hartlieb by detecting the degree of some
of the factors before starting the computations.
Our second approach is related to Dedekind's criterion, which gives a necessary and sufficient condition for a ring to be normal.
This relation leads us to study the link between the index of an order and irreducibility over Z/(p^l) and we give some interesting conditions over Z/(p^3).
We identify the index as the main cause of non uniqueness of the factorization and, using the Krasner's lemma, we provide an upper bound for the minimum
l such that a polynomial is irreducible in Z/(p^l).
Finally, we apply these results to polynomials over Z/(p^3), combining the two different approaches.
File