Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/73162
Title: | On zero-dimensional polynomial systems and their applications to the elliptic curve discrete logarithm problem | Authors: | Yun, Yang | Keywords: | DRNTU::Science::Mathematics | Issue Date: | 2018 | Source: | Yun, Y. (2018). On zero-dimensional polynomial systems and their applications to the elliptic curve discrete logarithm problem. Doctoral thesis, Nanyang Technological University, Singapore. | Abstract: | In this thesis, we first study the problem of solving zero-dimensional multivariate polynomial systems over finite fields and then study the elliptic curve discrete logarithm problem over binary fields. First, we discuss a mostly theoretical framework for solving zero-dimensional polynomial systems. Complexity bounds are obtained for solving such systems using a new parameter, called the \emph{last fall degree}, which does not depend on the choice of a monomial order. More generally, let $k$ be a finite field with $q^n$ elements and let $k'$ be the subfield with $q$ elements. Let $\mathcal{F} \subset k[X_0,\ldots,X_{m-1}]$ be a finite subset generating a zero-dimensional ideal. We give an upper bound of the last fall degree of the Weil descent system of $\mathcal{F}$ from $k$ to $k'$, which depends on $q$, $m$, the last fall degree of $\mathcal{F}$, the degree of $\mathcal{F}$ and the number of solutions of $\mathcal{F}$, but not on $n$. Second, we introduce special vector spaces and use them in the index calculus method to solve ECDLP over binary fields. We provide heuristic complexity bounds for our approach and give conditions such that an efficient index calculus method will result. Finally, we provide some concrete examples of vector spaces with the nice properties. | URI: | http://hdl.handle.net/10356/73162 | DOI: | 10.32657/10356/73162 | Schools: | School of Physical and Mathematical Sciences | Fulltext Permission: | open | Fulltext Availability: | With Fulltext |
Appears in Collections: | SPMS Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
ThesisAmendment_YANG_YUN.pdf | 985.4 kB | Adobe PDF | View/Open |
Page view(s)
372
Updated on Mar 28, 2024
Download(s) 20
196
Updated on Mar 28, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.