Skip to main content

Solving linear systems of equations over cyclotomic fields

Resource type
Thesis type
(Thesis) M.Sc.
Date created
Author: Chen, Liang
Let $A\in\Q^{n\times n}[z]$ be a matrix of polynomials and $b\in\Q^n[z]$ be a vector of polynomials. Let $m(z) = \Phi_k[z]$ be the $k^{th}$ cyclotomic polynomial. We want to find the solution vector $x\in\Q^n[z]$ such that the equation $Ax \equiv b \bmod{m(z)}$ holds. One may obtain $x$ using Gaussian elimination, however, it is inefficient because of the large rational numbers that appear in the coefficients of the polynomials in the matrix during the elimination. In this thesis, we present two modular algorithms namely, Chinese remaindering and linear $p$-adic lifting. We have implemented both algorithms in Maple and have determined the time complexity of both algorithms. We present timing comparison tables on two sets of data, firstly, systems with random generated coefficients and secondly real systems given to us by Vahid Dabbaghian which arise from computational group theory. The results show that both of our algorithms are much faster than Gaussian elimination.
Copyright statement
Copyright is held by the author.
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact
Scholarly level
Member of collection
Download file Size
etd3140.pdf 760.05 KB

Views & downloads - as of June 2023

Views: 0
Downloads: 0