Research

The research I am undertaking for my PhD thesis is on the problem of polynomial factorisation within the area of algorithmic number theory.  Specifically, I am using algebro-geometric methods to seek deterministic polynomial-time algorithms which factorise specific kinds of univariate polynomials over a finite field.

In 1985, René Schoof published an algorithm which calculates the number of points on an elliptic curve over a finite field in deterministic polynomial time.  As an application, he also shows how the algorithm may be applied to find square roots modulo a prime (or equivalently, factorising a polynomial of the form x²-a over the finite field of p elements), again in deterministic polynomial time.

In 1990, my supervisor, Jonathan Pila, generalised Schoof's algorithm so that one could calculate the characteristic polynomial of the Frobenius endomorphism of a general Abelian variety, and as a consequence, the number of points on a curve of general genus over a finite field of p elements.  As an application comparable to Schoof's square-root-finding application, Pila demonstrates how to find roots of unity:  Given odd prime L with p ≡ 1 mod L, Pila's algorithm calculates the L th roots of unity modulo p in deterministic polynomial time.  This is equivalent to factorising the L th cyclotomic polynomial into linear factors over the finite field of p elements.

It is the intent of my research to generalise this algorithm further, to see what other polynomials can be factored in this manner.