Deterministic Factorization of Polynomials over Finite Fields

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.

Creator: 

Marquis, David

Date: 

2015

Abstract: 

We give new results for the problem of deterministically and unconditionally factoring polynomials over finite fields. We give efficient algorithms for the factorization of some odd degree polynomials over finite fields. We remove the assumption of the Extended Riemann Hypothesis from a well known algorithm for factoring polynomials over finite fields in the case that the degree of the polynomial to be factored is coprime to phi(p-1) where p is the characteristic of the field and phi is the Euler totient function. We also give new results on the factorization of polynomials of bounded
degree.
Using new tools we give a concrete proof of a result from the literature that a polynomial of degree n over the finite field can be factored deterministically in a number of operations that is polynomial in n^l where l is the least prime factor of n and log(p).

Subject: 

Mathematics

Language: 

English

Publisher: 

Carleton University

Thesis Degree Name: 

Master of Science: 
M.Sc.

Thesis Degree Level: 

Master's

Thesis Degree Discipline: 

Mathematics

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).