Dissertation
Algorithms for finite rings
Promotores: H.W. Lenstra, K. Belabas (University of Bordeaux)
- Author
- Iuliana Ciocanea Teodorescu
- Date
- 22 June 2016
- Links
- Thesis in Leiden Repository
An algorithm is a sequence of steps that takes as input a finite sequence of nonnegative integers and produces an output in the form of another finite sequence of nonnegative integers. Virtually any mathematical object of interest can be represented in this way.
One of the simplest algorithmic questions one can ask oneself is, if given a positive integer, whether one can find its factorisation into primes. Despite the fundamental nature of this problem, and its easy formulation, integer factorisation is notoriously difficult, which has made it the heart of many algorithms used in cryptography.
Some problems are intrinsically more difficult than others. The complexity of a problem is a notion that can be formally quantified, and algorithmic problems can be classified according to how difficult they are. Loosely speaking, an algorithmic problem is considered to be “easy” if it has a deterministic polynomial-time solution. An algorithm is deterministic if no random bit is generated during its running, and polynomial-time if the number of steps it requires to produce an output is bounded above by a polynomial expression in the size of the input.
In this thesis, we investigate algorithmic problems that arise in algebra, more specifically in the theory of finite rings and finite modules. For most of the problems we consider, we also produce deterministic polynomial-time solutions. These algorithms are mainly of theoretical interest, but can also be incorporated into the toolboxes of computer algebra systems.