Back to search

Rochester Institute of Technology

A Transparent Square Root Algorithm to Beat Brute Force for Sufficiently Large Primes of the Form p = 4n + 1

Abstract

dc:description.abstract

Finding square roots in the modular integers is a well known problem that is the basis for many modern cryptosystems. For primes of the form p=4n+3, given C\in\mathbb Z_p^\times , finding solutions to x^2\equiv C \pmod{p} is deterministic. For primes of the form p=4n+1, no known deterministic computation exists for determining x given C. Tonelli (later improved by Shanks,) Cipolla, and Pocklington, among others, found sophisticated algorithms to perform this task. Brute force is a transparent approach, but offers no insights into the problem. In this thesis, we produce a transparent approach to this problem, visualized using a model built on Symplectic Geometry. One of the insights from viewing the problem in this way is a conjecture on the distribution of quadratic residues, which we exploit in our algorithm. Even though the conjecture is not essential to the workings of the algorithm, it gives it an edge over brute force for large enough primes. Finally, we follow this with examples of the algorithm's execution.

Degree

thesis:*
Name thesis:degree_name
Applied and Computational Mathematics (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
School of Mathematical Sciences (COS)

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Spink, Michael R
Contributors dc:contributor
  • Manuel Lopez

Subjects

dc:subject × 3

Identifiers

dc:identifier.*
Repository record dc:identifier
https://repository.rit.edu/theses/9905

Chain of custody

source
Harvested from
Rochester Institute of Technology
Base URL
repository.rit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Spink, Michael R. A Transparent Square Root Algorithm to Beat Brute Force for Sufficiently Large Primes of the Form p = 4n + 1. Thesis thesis, https://repository.rit.edu/theses/9905