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.
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)|
|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