Binary quadratic forms, elliptic curves and Schoof's algorithm

Pintore, Federico (2015) Binary quadratic forms, elliptic curves and Schoof's algorithm. PhD thesis, University of Trento.

[img]
Preview
PDF - Doctoral Thesis
Available under License Creative Commons Attribution.

1187Kb

Abstract

In this thesis, I show that the representation of prime integers by reduced binary quadratic forms of given discriminant can be obtained in polynomial complexity using Schoof's algorithm for counting the number of points of elliptic curves over finite fields. It is a remarkable fact that, although an algorithm of Gauss' solved the representation problem long time ago, a solution in polynomial complexity is very recent and almost unnoticed in the literature. Further, I present a viable alternative to Gauss' algorithm, which constitutes the main original contribution of my thesis. This alternative way of computing in polynomial time an explicit solution of the representation problem is particularly suitable whenever the number of not equivalent reduced forms is small. Lastly, I report that, in the efforts of improving Schoof's algorithm, a marginal incompleteness in its original formulation was identified. This weakness was eliminated by a slight modification of the algorithm suggested by Schoof himself.

Item Type:Doctoral Thesis (PhD)
Doctoral School:Mathematics
PhD Cycle:27
Subjects:Area 01 - Scienze matematiche e informatiche > INF/01 INFORMATICA
Area 01 - Scienze matematiche e informatiche > MAT/02 ALGEBRA
Area 01 - Scienze matematiche e informatiche > MAT/03 GEOMETRIA
Repository Staff approval on:21 Apr 2015 10:41

Repository Staff Only: item control page