Solving norm equations over global function fields using compact representations

Simple item page
dc.contributor.advisorScheidler, Renate
dc.contributor.advisorJacobson, Michael
dc.contributor.authorLeem, Sumin
dc.contributor.committeememberBauer, Mark
dc.contributor.committeememberGreenberg, Matthew
dc.date2024-02
dc.date.accessioned2023-12-15T19:40:25Z
dc.date.available2023-12-15T19:40:25Z
dc.date.issued2023-12-13
dc.description.abstractThis thesis provides contributions to improving the efficiency of solving norm equations over global function fields F and providing theoretical and empirical evidence of the improvement. We present two new algorithms for solving norm equations over F; one is an exhaustive search algorithm inspired by the sole existing method in [21], and the other is an algorithm using principal ideal testing via index calculus. We employed compact representations in both of the novel algorithms to represent solutions in less space and also to improve their efficiency. In order to compare the asymptotic and practical efficiency of the novel algorithms to the existing one, we performed rigorous complexity analyses and empirical analyses of the algorithms. We provided the asymptotic complexities of the algorithm as the number of bit operations required. We also analyzed for the first time the complexity of the algorithm for computing compact representations in [15] as a part of the complexity analyses of the novel algorithms. The asymptotic complexities of both of our novel algorithms were reduced by double exponential factors in the size of F, when compared to the existing algorithm in [21]. The new algorithm with principal ideal testing requires even fewer bit operations than the new exhaustive search algorithm in terms of the size of F. Empirical testing results demonstrate our novel algorithms are significantly faster than the existing one in practice as expected from the complexity analyses.
dc.identifier.citationLeem, S. (2023). Solving norm equations over global function fields using compact representations (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.
dc.identifier.urihttps://hdl.handle.net/1880/117743
dc.identifier.urihttps://doi.org/10.11575/PRISM/42586
dc.language.isoen
dc.publisher.facultyGraduate Studies
dc.publisher.institutionUniversity of Calgary
dc.rightsUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.
dc.subjectglobal function fields
dc.subjectcompact representations
dc.subjectDiophantine equations
dc.subjectnorm equations
dc.subjectprincipal ideal tests
dc.subject.classificationMathematics
dc.subject.classificationComputer Science
dc.titleSolving norm equations over global function fields using compact representations
dc.typedoctoral thesis
thesis.degree.disciplineMathematics & Statistics
thesis.degree.grantorUniversity of Calgary
thesis.degree.nameDoctor of Philosophy (PhD)
ucalgary.thesis.accesssetbystudentI do not require a thesis withhold – my thesis will have open access and can be viewed and downloaded publicly as soon as possible.
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ucalgary_2023_leem_sumin.pdf
Size:
811.09 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.62 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Open Theses and Dissertations