CEU Electronic Theses and Dissertations, 2017
| Author | Kutas, Péter |
|---|---|
| Title | The Explicit Isomorphism Problem |
| Summary | In this thesis we consider the following algorithmic problem. Let $K$ be a field and let $\A$ be an algebra over $K$ which is given by structure constants and is isomorphic to $M_n(K)$, the algebra of $n\times n$ matrices over $K$. The task is to find an explicit isomorphism between $\A$ and $M_n(K)$. We propose a polynomial time algorithm for the case where $K=\F_q(t)$, the field of rational functions over a finite field. Using an oracle for integer factorization, we provide an algorithm for $K=\Q(\sqrt{d})$ and $n=2$. This algorithm reduces the original problem to finding nontrivial zeros of quadratic forms in several variables over $\Q$. Since the reduction procedure works over every field of characteristic different from 2, we concern ourselves with finding nontrivial zeros of quadratic forms over $\F_q(t)$, where $q$ is odd. We propose a polynomial time algorithm for finding nontrivial zeros of quadratic forms over $\F_q(t)$. We apply the algorithm to compute the Witt decomposition of a quadratic form and decide equivalence of quadratic forms. Also, in the case two quadratic forms are equivalent, we provide a transition matrix. Finally, the algorithm is applied to compute an explicit isomorphism in the case $\A\cong M_2(L)$, where $L$ is a quadratic extension of $\F_q(t)$ (where $q$ is odd). Besides these results, we also obtained some minor results as well (such as lattice reduction over the field of formal Laurent-series) and we have implemented two of our main algorithms. |
| Supervisor | Gábor Ivanyos, Lajos Rónyai |
| Department | Mathematics PhD |
| Full text | https://www.etd.ceu.edu/2017/kutas_peter.pdf |
Visit the CEU Library.
© 2007-2021, Central European University