**SDSU**

presents a thesis defense for

Master of Arts degree in Mathematics

Thursday, October 25, 2012

10:00am GMCS 405

*Taking Square Roots over Finite Fields*

**Abstract **

This paper examines the proposed “novel idea to compute square roots over finite fields, without being given any quadratic nonresidue, and without assuming any unproven hypothesis” as presented recently in Tsz-Wo Sze’s paper “On Taking Square Roots Without Quadratic Nonresidues Over Finite Fields.” Sze’s algorithm claims a deterministic approach where “in some cases the algorithm runs in O((log *q*)^{2}) bit operations over finite fields with *q *elements.” A careful analysis carried out in the present work reveals that several conditions on the factors of *q-1* must be satisfied in order for the algorithm to actually run in O((log *q*)^{2}) bit operations

In addition, in this work a modification of Sze’s approach is presented as an alternative probabilistic method that runs in polynomial time and without the need for quadratic nonresidues. Moreover, the approach being proposed is slightly faster than most common known probabilistic methods of its kind. An application of Sze’s algorithm (and its probabilistic version) is a primality testing/proving algorithm that runs in polynomial time.

**Thesis Committee**

Carmelo Interlando, Thesis Chair, Department of Mathematics & Statistics

Robert Grone, Department of Mathematics & Statistics

Alan Riggins, Department of Computer Science