Factoring cyclotomic polynomials over finite fields.
Item
-
Title
-
Factoring cyclotomic polynomials over finite fields.
-
Identifier
-
AAI9732975
-
identifier
-
9732975
-
Creator
-
Stein, Gregory Charles.
-
Contributor
-
Adviser: Alphonse Vasquez
-
Date
-
1997
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Mathematics
-
Abstract
-
We examine the problem of deterministically factoring the {dollar}r\sp{lcub}th{rcub}{dollar} cyclotomic polynomial, {dollar}\Phi\sb{lcub}r{rcub}(x),{dollar} over {dollar}{lcub}\rm I\!F{rcub}\sb{lcub}p{rcub}{dollar}, where r and p are distinct primes, by looking at the traces of the roots of {dollar}\Phi\sb{lcub}r{rcub}(x){dollar} over {dollar}{lcub}\rm I\!F{rcub}\sb{lcub}p{rcub}{dollar}.;Chapter 1 is an introduction and a brief review of the theory of cyclotomy. In Chapter 2 we show how to derive the factors of {dollar}\Phi\sb{lcub}r{rcub}(x){dollar} using the traces of the roots of {dollar}\Phi\sb{lcub}r{rcub}(x){dollar} over {dollar}{lcub}\rm I\!F{rcub}\sb{lcub}\rm p{rcub}{dollar}. We then demonstrate a deterministic algorithm for finding these factors in time polynomial in r and {dollar}\log p{dollar} in the case where {dollar}\Phi\sb{lcub}r{rcub}(x){dollar} has precisely two irreducible factors over {dollar}{lcub}\rm I\!F{rcub}\sb{lcub}p{rcub}{dollar}. In Chapter 3 we construct an algebraic model to further explore the results of Chapter 2 and describe a technique for constructing an {dollar}{lcub}\rm I\!F{rcub}\sb{lcub}p{rcub}{dollar}-algebra isomorphic to the Berlekamp sub-algebra of {dollar}{lcub}\rm I\!F{rcub}\sb{lcub}p{rcub}/\Phi\sb{lcub}r{rcub}(x){dollar}. In Chapter 4 we use some techniques of linear algebra to derive explicit matrix descriptions of some of the maps discussed in Chapter 3. We further use these techniques to reduce our problem to that of factoring polynomials which split over {dollar}{lcub}\rm I\!F{rcub}\sb{lcub}p{rcub}{dollar}.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
