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

 

 

Tags: