University of Maryland DRUM  
University of Maryland Digital Repository at the University of Maryland

Digital Repository at the University of Maryland (DRUM) >
Theses and Dissertations from UMD >
UMD Theses and Dissertations >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1903/7632

Title: On Solving Univariate Polynomial Equations over Finite Fields and Some Related Problems
Authors: Sze, Tsz Wo
Advisors: Washington, Lawrence C
Department/Program: Computer Science
Type: Dissertation
Sponsors: Digital Repository at the University of Maryland
University of Maryland (College Park, Md.)
Subjects: Mathematics
Computer Science
Keywords: finite fields
polynomial equations
square roots
n th roots
primality testing
Issue Date: 30-Oct-2007
Abstract: In this thesis, we are mainly interested in constructing deterministic polynomial-time algorithms for solving some computational problems that arise in number theory and cryptography. The problems we are interested in include finite field arithmetic, primality testing, and elliptic curve arithmetic. We first present a novel idea to compute square roots over some families of finite fields. Our square root algorithm is deterministic polynomial-time and can be proved by elementary means. The approach of taking square roots is generalized to take $n$th roots. Then, we present a deterministic polynomial-time algorithm to solve polynomial equations over some families of finite fields. As applications, we construct a deterministic polynomial-time primality test for some forms of integers and show a deterministic polynomial-time algorithm computing elliptic curve ``$n$th roots''. For example, we prove the following statements. Denote a finite field with $q$ elements and characteristic $p$ by $\F_q$. (I) Suppose $p\equiv 1\pmod{12}$, $q=2^e3^ft+1$ for some $e,f\geq 1$ and some $t=O(\POLY(\log q))$. There is a deterministic polynomial time algorithm taking square roots over $\F_q$. (II) Let $r_1^{e_1}\cdots r_m^{e_m}$ be the prime factorization of $q-1$. Suppose $r_j=O(\POLY(\log q))$ and a primitive $r_j$th root of unity can be computed efficiently for $1\leq j\leq m$. There is a deterministic polynomial time algorithm solving any polynomial equation with degree $O(\POLY(\log q))$ over $\F_q$. (III) Let $N=r^et+1$ for some prime $r$ and some positive integers $t$ and $e$ with $r^e>t$. There is an $\O(r^2(\log^2 N)(t+r\log N))$ deterministic primality testing algorithm. If $r$ is a small constant and $t=O(\log N)$, the running time is $\O(\log^3 N)$.
URI: http://hdl.handle.net/1903/7632
Appears in Collections:UMD Theses and Dissertations
Computer Science Theses and Dissertations

Files in This Item:

File Description SizeFormatNo. of Downloads
umi-umd-4903.pdf429.75 kBAdobe PDF599View/Open

All items in DRUM are protected by copyright, with all rights reserved.

 

DRUM is brought to you by the University of Maryland Libraries
University of Maryland, College Park, MD 20742-7011 (301)314-1328.
Please send us your comments