On Solving Univariate Polynomial Equations over Finite Fields and Some Related Problems

Simple item page
dc.contributor.advisorWashington, Lawrence Cen_US
dc.contributor.authorSze, Tsz Woen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2008-04-22T16:02:43Z
dc.date.available2008-04-22T16:02:43Z
dc.date.issued2007-10-30en_US
dc.description.abstractIn 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)$.en_US
dc.format.extent440064 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/7632
dc.language.isoen_US
dc.subject.pqcontrolledMathematicsen_US
dc.subject.pqcontrolledComputer Scienceen_US
dc.subject.pquncontrolledfinite fieldsen_US
dc.subject.pquncontrolledpolynomial equationsen_US
dc.subject.pquncontrolledsquare rootsen_US
dc.subject.pquncontrolledn th rootsen_US
dc.subject.pquncontrolledprimality testingen_US
dc.titleOn Solving Univariate Polynomial Equations over Finite Fields and Some Related Problemsen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
umi-umd-4903.pdf
Size:
429.75 KB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Computer Science Theses and Dissertations