My bachelor thesis

Factoring polynomials over finite fields

Česká verze zde
.
My bachelor thesis written in 2006 deals with factorization of polynomials over finite fields.

The annotation is:

The goal of this work is to present the problem of the decomposition 
of a polynomial over a finite field into a product of irreducible polynomials. 
By describing algorithms solving this problem, we show that the decomposition 
can always be found in polynomial time in both the degree of the polynomial 
and the number of elements of the underlying finite field.

One algorithm is studied in detail and an implementation with good asymptotic 
time complexity O(n^1.815 * log q) is described, where n is the degree 
of the polynomial over the field with q elements. A program using easier, 
but practically faster version of this algorithm is a part of this work.

The whole paper is in Czech and it can be downloaded as PDF, PS or PS.GZ.

An implementation of a factoring algorithm is a part of this work. This program is written using C++ and can be run only on IA-32 type processors. But it would not be difficult to adjust it for different architectures. The whole program and the documentation are in English. Additional documentation can be found in the archive in the directory doc.

You can download :


Back