The Barreto-Naehrig method for elliptic curves with complex multiplication

Boelens, T.Y.M. (2017) The Barreto-Naehrig method for elliptic curves with complex multiplication. Bachelor's Thesis, Mathematics.

Preview	Text BSc_Math_2017_Boelens_TYM.pdf - Published Version Download (682kB) | Preview
	Text Toestemming.pdf - Other Restricted to Backend only Download (80kB)

Abstract

In this thesis, we detail the reasoning of the paper by Barreto and Naehrig titled 'Paring-Friendly Elliptic Curves of Prime Order'. In this paper they describe an algorithm that generates without effort elliptic curves that are of interest to cryptographers. In this paper we will look at two quantities associated to these curves - the embedding degree 12 and the CM-discriminant -3 - and describe how one obtains curves with these values of these quantities, and how one can obtain curves with other embedding degrees or CM-discriminants. Then we use Magma and Sage to find curves with low embedding degree and CM-discriminant -11. Before we start with Chapter 1, we give an informal introduction to elliptic curves and how one can define a group structure on them. In Chapter 1 we go into the general theory of elliptic curves. We define concepts as the endomorphism ring and the j-invariant, and we mention results for curves over the rationals (such as the Mordell-Weil theorem), and the finite fields (here we discuss the Hasse bound and the trace of the Frobenius morphism). We finish the chapter with a discussion of the connection between lattices in the complex numbers and elliptic curves, looking towards the theory of complex multiplication. In Chapter 2 we discuss the calculations Barreto and Naehrig made in their paper. We define the embedding degree of a curve, and we give an easy way to determine it, given the size of a curve and the field it is defined over. Then we see how they used this result and a theorem from Galbraith et al. to find a parametrization of the size of the curve and the size of the field. Finally we discuss their algorithm to generate elliptic curves with those properties. Chapter 3 focuses on complex multiplication. First we describe the general theory, building further on Chapter 1. Then we describe a parametrization of sizes of curves and fields of elliptic curves with specific CM-discriminants (namely those of the curve Barreto and Naehrig used, and the CM-discriminant we want). We use this to find the j-invariant of the curves with CM-discriminant -11. Chapter 4 contains all the code we used to find elliptic curves with a small embedding degree and a small CM-discriminant. We list the code, the underlying theory and the results we found with the code. The chapter is concluded with a few remarks on the search efforts. In Appendix A, at last, we give all the definitions from algebraic geometry we need in this thesis.

Item Type:	Thesis (Bachelor's Thesis)
Degree programme:	Mathematics
Thesis type:	Bachelor's Thesis
Language:	English
Date Deposited:	15 Feb 2018 08:29
Last Modified:	15 Feb 2018 08:29
URI:	https://fse.studenttheses.ub.rug.nl/id/eprint/15349

Actions (login required)

View Item