dc.creator | Kelley, Alexander | |
dc.date.accessioned | 2018-07-24T15:31:47Z | |
dc.date.available | 2019-05-01T06:07:23Z | |
dc.date.created | 2017-05 | |
dc.date.issued | 2015-09-29 | |
dc.date.submitted | May 2017 | |
dc.identifier.uri | https://hdl.handle.net/1969.1/167867 | |
dc.description.abstract | For a $t$-nomial $f(x) = \sum_{i = 1}^t c_i x^{a_i} \in \mathbb{F}_q[x]$, we show that the number of distinct, nonzero roots of $f$ is bounded above by $2 (q-1)^{1-\varepsilon} C^\varepsilon$, where $\varepsilon = 1/(t-1)$ and $C$ is the size of the largest coset in $\mathbb{F}_q^*$ on which $f$ vanishes completely. Additionally, we describe a number-theoretic parameter depending only on $q$ and the exponents $a_i$ which provides a general and easily-computable upper bound for $C$. We thus obtain a strict improvement over an earlier bound of Canetti et al.\ which is related to the uniformity of the Diffie-Hellman distribution. | en |
dc.format.mimetype | application/pdf | |
dc.subject | finite field | en |
dc.subject | sparse polynomial | en |
dc.subject | sparsity-dependent bound | en |
dc.title | Roots of Sparse Polynomials over a Finite Field | en |
dc.type | Thesis | en |
thesis.degree.discipline | Computer Sci. & Engr | en |
thesis.degree.grantor | Undergraduate Research Scholars Program | en |
dc.contributor.committeeMember | Rojas, Joseph Maurice | |
dc.type.material | text | en |
dc.date.updated | 2018-07-24T15:31:47Z | |
local.embargo.terms | 2019-05-01 | |