Talk
Computing with Cubic and Quadratic Forms
Talk by Prof. Dr. Michele Elia
Speaker invited by: Prof. Dr. Joachim Rosenthal
Date: 09.05.18 Time: 15.00 - 16.00 Room:
The search for all-integer solutions of equations of the form ax^2+2bxy+cy^2=m, where a, b, c, and m are integers, is a very old problem; it can be traced back to Diophantus for special values of the coefficients. However, it is not surprising that the problem is still unsettled in its full generality, because it can be shown that solving this equation, whenever solvable, is equivalent to factoring m. Gauss’s theory of quadratic forms allows us with certainty to find the solutions when m is prime, or less easily when the quadratic form is principal, although the computations are not of polynomial complexity with respect to either m or d=b^2-ac. Unexpectedly, about forty years ago, Schoof completed Gauss’s method when m is prime, showing how to operate with polynomial complexity by exploiting a connection between quadratic forms and the point group of elliptic curves.
Soon afterwards these point groups were exploited to create efficient public-key cryptosystems. Then, very recently, systems using point groups of degenerate cubics have also been proposed, which may favorably compete with elliptic curve cryptosystems.
The aim of the lecture is to present an overview of these problems, along with some new aspects that still evade the best mathematical minds as millenary riddles, and are the crux of modern cryptographers.