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

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 'ParingFriendly 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 CMdiscriminant 3  and describe how one obtains curves with these values of these quantities, and how one can obtain curves with other embedding degrees or CMdiscriminants. Then we use Magma and Sage to find curves with low embedding degree and CMdiscriminant 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 jinvariant, and we mention results for curves over the rationals (such as the MordellWeil 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 CMdiscriminants (namely those of the curve Barreto and Naehrig used, and the CMdiscriminant we want). We use this to find the jinvariant of the curves with CMdiscriminant 11. Chapter 4 contains all the code we used to find elliptic curves with a small embedding degree and a small CMdiscriminant. 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:  http://fse.studenttheses.ub.rug.nl/id/eprint/15349 
Actions (login required)
View Item 