Pintore, Federico (2015) Binary quadratic forms, elliptic curves and Schoof's algorithm. PhD thesis, University of Trento.
| 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